Questions tagged [security-definition]

Questions about formal definitions of "security" for various cryptographic schemes (e.g. perfect secrecy, semantic security, ciphertext indistinguishability, etc.)

Filter by
Sorted by
Tagged with
32 votes
1 answer
9k views

What do the signature security abbreviations like EUF-CMA mean?

From time to time, one stumbles across formal security definitions. This includes security definitions for signature schemes. The most common ones are the *UF-* ...
SEJPM's user avatar
  • 45.9k
41 votes
3 answers
50k views

What are preimage resistance and collision resistance, and how can the lack thereof be exploited?

What is "preimage resistance", and how can the lack thereof be exploited? How is this different from collision resistance, and are there any known preimage attacks that would be considered feasible?
John Gietzen's user avatar
  • 1,505
14 votes
2 answers
2k views

Does GCM (or GHASH) only provide 64-bit security against forgeries?

In a recent comment a doubt was voiced about my answer, which claims GCM to requires $2^{128}$ for a successful forgery. The doubt was that the square root needs to be taken meaning the security would ...
SEJPM's user avatar
  • 45.9k
7 votes
2 answers
3k views

What is the difference between information-theoretic and perfect types of security?

I'm having a hard time pinning down an exact definition of the difference between information-theoretic and perfect types of security. A rigorous definition seems elusive... A. Wikipedia puts the ...
Paul Uszak's user avatar
  • 15.3k
40 votes
8 answers
55k views

Simply put, what does “perfect secrecy” mean?

I would like to ask for a clear (but maybe not so deep) explanation of what the term "perfect secrecy" means. As far as I have researched and understood, it has to do with probabilities of assuming ...
Emyr's user avatar
  • 551
11 votes
2 answers
1k views

Definition of a CSPRNG

I am interested in what conditions are necessary and sufficient to define a cryptographically secure pseudo-random number generator (CSPRNG). Wikipedia lists two defining characteristics: It ...
Dave White's user avatar
31 votes
1 answer
2k views

Uniform vs discrete Gaussian sampling in Ring learning with errors

The Wikipedia article on RLWE mentions two methods of sampling "small" polynomials namely uniform sampling and discrete Gaussian sampling. Uniform sampling is clearly the simplest, involving simply ...
Morty's user avatar
  • 599
21 votes
2 answers
6k views

Why is AES considered to be secure?

The security of RSA is based on the integer factorization problem, which is a very well defined and understood mathematical problem. This problem must be solved in order to fundamentally break RSA. ...
Eiver's user avatar
  • 313
6 votes
1 answer
5k views

What exactly is a “security parameter”?

I often encounter the term “security parameter” when I read crypto related stuff. My basic understanding is that it just denotes some bit-length however, I'm not so sure. For example, when it says ...
SpiderRico's user avatar
6 votes
1 answer
615 views

"Power of one" as input to functions of a cryptosystem

What does $1^\lambda$ mean when you pass it as a parameter to the functions of a cryptosystem. The cryptosystem in question is this and a picture reference is this. I have been told it signifies the ...
Papa Delta's user avatar
5 votes
2 answers
666 views

What is the relationship between entropy conditioning and final output bias in a TRNG?

This question concerns the conditioning and output of true random number generators. It refers to NIST Special Publication 800-90C, Recommendation for Random Bit Generator (RBG) Constructions. It ...
Paul Uszak's user avatar
  • 15.3k
16 votes
6 answers
3k views

How exactly is "true randomness" defined in the realms of cryptography?

Especially in relation to stream ciphers, I frequently read about (sometimes theoretical, sometimes practical) attacks that are able to "distinguish a ciphertext from a truly random stream". What's ...
e-sushi's user avatar
  • 17.9k
8 votes
1 answer
3k views

Understanding Twist Security with respect to short Weierstrass curves

I'm trying to understand the "Invalid-curve attacks against ladders" section of SafeCurves Twist Security page and I have difficulties to apply it to short Weierstrass curves. That section claims ...
Ruggero's user avatar
  • 7,014
3 votes
2 answers
752 views

Comparison of security definitions for signatures

The two main security definitions for signatures are EUF-CMA and the strong version of it sEUF-CMA. What I see that their difference is that in EUF-CMA experiment, the adversary needs to produce a ...
user avatar
3 votes
3 answers
4k views

When is a cipher considered broken?

We've all read how some people claim AES is broken because there was supposedly a way to get the plain text from a cipher text faster than brute-force. But is this the definition? Is a cipher broken ...
Vincent's user avatar
  • 966
20 votes
2 answers
6k views

What stops the Multiply-With-Carry RNG from being a Cryptographically Secure PRNG?

Despite the fact that Marsaglia's MWC PRNG (multiply-with-carry random number generator) is considered to be "the mother of all RNGs", it does not seem to be considered to be a CSPRNG (...
e-sushi's user avatar
  • 17.9k
19 votes
3 answers
34k views

What is the difference between uniformly and at random in crypto definitions?

Very often in the description and analysis of a cryptographic protocol there is a need for a an element $k$ that is sampled uniformly AND at random. Is there a redundancy in the definition with ...
curious's user avatar
  • 6,150
12 votes
2 answers
8k views

Definitions of secrecy

I found terms like "forward secrecy", "future secrecy", "backwards secrecy" and "perfect forward secrecy" and I would like to know their definitions and to understand the differences among them. I ...
M-elman's user avatar
  • 1,248
11 votes
2 answers
5k views

Example of a PRP that is not a strong PRP

The exact definition of security for a pseudorandom permutation is straightforward - for some encryption scheme $E\,\colon\,\mathcal{K}\times\mathcal{D}\rightarrow\mathcal{D}$, it must be the case ...
pg1989's user avatar
  • 4,636
9 votes
1 answer
7k views

What does it mean for an adversary to run in PPT?

I've been reading this question where a detailed description of mine is given, I've understood that a polynomial-time adversary is an adversary for which the only feasible strategy are those that take ...
Daniel's user avatar
  • 3,932
7 votes
1 answer
2k views

Proofs of security methodologies

I'm looking for course material on the subject of proofs, reductions, and games, as used to prove cryptographic schemes secure. What are the methodologies? What are the preferred ones? In what cases ...
Dingo13's user avatar
  • 2,837
7 votes
2 answers
4k views

Difference left-or-right CPA security, IND-CPA security

I am trying to understand the notion of left-or-right-CPA (LOR-CPA) security for private-key encryption schemes introduced in my lecture. If I understood it correctly so far, the only difference to ...
Lemon's user avatar
  • 391
6 votes
0 answers
130 views

About the complexity of a path finding attack for a path encrypted with a block cipher (like AES). How many AES calculations count as secure?

Out of $N = s^3$ total points we pick a starting point $p$ and an end point $q$ with $$p=(p_1, p_2)$$ $$q=(q_1,q_2)$$ $$p_1,q_1 \in [0,s)$$ $$p_2,q_2 \in [0,s^2)$$ We want to find a path in between ...
J. Doe's user avatar
  • 573
5 votes
2 answers
980 views

Statistical security parameter -> information theoretically secure

If a cryptographic protocol has a computational security parameter and a statistical security parameter, does this mean it is only computationally secure instead of information-theoretically secure? I ...
HelloWorld123's user avatar
4 votes
1 answer
1k views

What's the difference between perfect security and unconditional security?

This paper refers to two distinct security models: perfect security and unconditional security. Until now, I knew of them as the same thing and equivalent to information-theoretic security. From the ...
SpiderRico's user avatar
4 votes
3 answers
920 views

Is it possible to exactly reverse engineer an unknown cipher inside a black box?

Consider the following arrangement:- There is an unknown cipher algorithm operating inside the black box. You can enter infinite key /plain text pairs, and observe all of the outputs. The box might ...
Paul Uszak's user avatar
  • 15.3k
3 votes
2 answers
817 views

Why is a non fixed-length encryption scheme worse than a fixed-length one?

I have the following definition (highlights by me): An (efficient secret-key) encryption scheme $(Gen,Enc,Dec)$, where $Gen$ and $Enc$ are PPT algorithms and $Dec$ is a Deterministic Polytime ...
Alan Bletchley's user avatar
1 vote
1 answer
8k views

What is a man-in-the-middle attack (for instance in Diffie-Hellman)?

I'm new to cryptography and I just started learning about the Diffie-Hellman key agreement. I read that this system is vulnerable to a man-in-the-middle attack when used alone. What kind of attack is ...
raha tamjid's user avatar
14 votes
1 answer
3k views

Meaning of "Security can be reduced to a problem"

I'm studying reductions in cryptography and confused about the way people use the word "reduction". My question is almost the same as a past question, but what I want to ask is slightly different. A ...
rapier's user avatar
  • 141
12 votes
3 answers
3k views

How small is negligible?

When proving theorems in crypto we often make use of the concept of negligible functions or, more simply, negligible parameters. As a rule of thumb, given today (2018) computational power, what is ...
Rexcirus's user avatar
  • 313
11 votes
1 answer
6k views

Proof that IND$-CPA implies IND-CPA?

I've read a few papers recently that used a notion of security called "indistinguishability from random bits/strings" under chosen plaintext attack, also called IND\$-CPA. See e.g. http://pdf.aminer....
J.D.'s user avatar
  • 4,415
10 votes
1 answer
3k views

Existential unforgeability vs strong unforgeability

In the article https://crypto.stanford.edu/~dabo/pubs/papers/strongsigs.pdf there are two definitions for the security of a digital signature scheme: existential unforgeability and strong ...
Evgeni Vaknin's user avatar
10 votes
2 answers
1k views

Key Size for Symmetric Homomorphic Encryption Over the Integers

In the paper Fully Homomorphic Encryption over the Integers, it mentions a symmetric key scheme on page 1 and 2. Key Generation: Pick a random odd number $p \epsilon [2^{N-1},2^N)$ Encrypt A Bit m: $...
Alan Wolfe's user avatar
8 votes
1 answer
981 views

The notion of sub-exponential security

I have been reading a paper where they construct probabilistic IO (indistinguishability obfuscation) from sub exponential IO. I want to know if the following two notions of sub-exponential security ...
user avatar
7 votes
3 answers
633 views

Is there a cryptographic approach to availability

Background Cryptography can be said to provide the tools used to fulfill the goals of information security. The three pillars of information security are confidentiality, integrity, and ...
Ella Rose's user avatar
  • 19.6k
5 votes
1 answer
191 views

Parameterizing adversaries with security parameters

In many cryptographic games, the adversary doesn't seem to be parameterized by the security parameter.‡ Are such games equivalent to variants in which the adversary is parameterized by the security ...
user2768's user avatar
  • 357
5 votes
1 answer
2k views

Signature with appendix

I see sometimes signatures schemes with appendix. This is about signatures schemes in which the message is needed in the verification algorithm, that is, the ouput of the signature algorithm is of the ...
Dingo13's user avatar
  • 2,837
5 votes
1 answer
2k views

IND-CPA security of CTR mode

Let's suppose CTR mode is instantiated such that the input to the block-cipher is $\langle \mathrm{IV}+\mathrm{ctr}\rangle$ instead of $\mathrm{IV}\mathbin\|\langle \mathrm{ctr}\rangle$, where $\...
ironhide012's user avatar
5 votes
1 answer
644 views

What does "adaptively secure" mean?

In a paper it says "In the generic group model, the PRF is adaptively secure for inputs of $\mathbb{Z}_q^n$". Maybe a stupid question, but what does "adaptively secure" mean exactly?
user4811's user avatar
  • 579
4 votes
1 answer
538 views

What are the “costs” to find a pre-image, weak collision, or strong collision?

For a secure, n-bit hash function, what are the “costs” to find a pre-image, weak collision, or strong collision?
Renato's user avatar
  • 43
4 votes
1 answer
1k views

When knowledge soundness implies soundness

In the work of Bellare–Goldreich that defines knowledge soundness BG92, the discussion of Section 4.5 specifically decouples knowledge soundness from soundness. That is, proving knowledge soundness ...
E. Postlethwaite's user avatar
4 votes
2 answers
274 views

What is the difference between security parameter and $b$-bit security?

In a previous question, I read ... for $b$-bit security meaning $O(2^b)$ work for an attacker to break the system... While in Katz's Introduction to modern Cryptography, I read: The key-generation ...
Mathsa's user avatar
  • 113
3 votes
2 answers
643 views

Differential privacy definition

Differential privacy defines "privacy" of a mechanism $A$ as the "closeness" of the two distribution $Pr[A(D) \in S]$ and $Pr[A(D') \in S]$ where $D,D'$ differ in one element. And the distance between ...
Anh's user avatar
  • 381
3 votes
2 answers
956 views

What does it mean the security parameter for a FHE scheme?

FHE schemes claim to use some security parameter $\lambda$ for deriving the other parameters of the scheme, the size of the key and the possible circuits that can be evaluated. Like in Fully ...
guglielmo london's user avatar
1 vote
0 answers
109 views

Question about sequence length/count/security of $x\mapsto x^\alpha \mod (N=Q\cdot R)$, with $Q=2q_1q_2+1$ and $R=2r_1r_2+1$ and $\alpha = 2q_2r_2$

Given a number $N$ with $$N=Q\cdot R$$ $$Q=2\cdot q_1 \cdot q_2+1$$ $$R=2\cdot r_1\cdot r_2+1$$ with different primes $P,Q,q_1,q_2,r_1,r_2$. If we now choose an exponent $\alpha$ containing prime ...
J. Doe's user avatar
  • 573
1 vote
1 answer
737 views

Deterministic symmetric indistinguishable encryption

Are there any block-cipher modes (or symmetric encryption schemes in general) that are fully-deterministic, meaning same inputs lead to the same outputs (like for all modes with constant IV) and ...
dave4422's user avatar
1 vote
2 answers
473 views

Why don't we have 256-bit security level digital signature schemes (in common use)?

Recently (2016) I've been researching on post-quantum digital signature schemes, and read about BLISS, BLZZRD, REBLISS schemes. What I've noticed about them is that they lack a parameter set for 256-...
DannyNiu's user avatar
  • 9,080
1 vote
1 answer
325 views

How does the security of Elliptic curve compare to normal discrete logarithm?

Intro: EC are often compared with RSA but how about a more safe version of the discrete logarithm? All 3 can be reduced to the problem: $$b = g^a \mod{P}$$ In RSA $P$ is a product of two primes. To ...
J. Doe's user avatar
  • 573
1 vote
2 answers
380 views

What is the Knowledge Of Secret Key Assumption (KOSK)

From what I've read it seems to be where an entity must prove that they own the secret key. Which is done by signing a message M using said secret key. Is this ...
WeCanBeFriends's user avatar
1 vote
1 answer
117 views

Question on notation of random variables in probability ensembles

Let's consider this definition of computational indistinguishability. Computational indistinguishability. A probability ensemble $X=\{X(a, n)\}_{a \in\{0,1\}^{*} ; n \in \mathbb{N}}$ is an infinite ...
tur11ng's user avatar
  • 962