Questions tagged [security-definition]
Questions about formal definitions of "security" for various cryptographic schemes (e.g. perfect secrecy, semantic security, ciphertext indistinguishability, etc.)
51
questions
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-* ...
- 45.7k
41
votes
3
answers
49k
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?
- 1,505
14
votes
2
answers
1k
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 ...
- 45.7k
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 ...
- 15.2k
39
votes
8
answers
54k
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 ...
- 541
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 ...
- 213
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 ...
- 589
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.
...
- 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
...
- 441
6
votes
1
answer
557
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 ...
- 263
5
votes
2
answers
633
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 ...
- 15.2k
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 ...
- 17.8k
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 ...
- 6,904
3
votes
3
answers
3k
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 ...
- 966
3
votes
2
answers
692
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 ...
user4936
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 (...
- 17.8k
19
votes
3
answers
33k
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 ...
- 6,140
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 ...
- 1,248
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 ...
- 313
10
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 ...
- 4,626
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 ...
- 3,922
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 ...
- 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 ...
- 391
6
votes
0
answers
125
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 ...
- 573
5
votes
2
answers
869
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 ...
4
votes
3
answers
896
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 ...
- 15.2k
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 ...
- 441
3
votes
2
answers
800
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 ...
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 ...
- 13
13
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 ...
- 131
10
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....
- 4,405
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 ...
- 1,066
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: $...
- 530
8
votes
1
answer
947
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 ...
user38956
7
votes
3
answers
606
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 ...
- 19.5k
5
votes
1
answer
632
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?
- 579
5
votes
1
answer
190
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 ...
- 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 ...
- 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 $\...
- 53
4
votes
1
answer
493
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?
- 43
4
votes
2
answers
265
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 ...
- 113
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 ...
- 155
3
votes
2
answers
612
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 ...
- 371
3
votes
2
answers
939
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 ...
- 681
1
vote
1
answer
309
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 ...
- 573
1
vote
0
answers
108
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 ...
- 573
1
vote
2
answers
467
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-...
- 9,001
1
vote
2
answers
367
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 ...
- 1,303
1
vote
1
answer
728
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 ...
- 13
0
votes
1
answer
444
views
Security of this PRF [closed]
Given $F$ a secure PRF with input size $\lambda$. Define $F'$ as
$F'(k,x||x') = F(k, 0||x)\oplus F(k, 1||x')$
with $x$ and $x'$ of $\lambda-1$ bits.
Is $F'$ a secure PRF?
- 111