Questions tagged [security-definition]
Questions about formal definitions of "security" for various cryptographic schemes (e.g. perfect secrecy, semantic security, ciphertext indistinguishability, etc.)
288
questions
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
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
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
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
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
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
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 ...
- 45.7k
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
13
votes
1
answer
5k
views
Proofs by reduction and times of adversaries
I have some difficulties to understand, when we construct a reduction, how we determine the time for the constructed adversary to break a target security property.
In general these details are not ...
- 2,837
12
votes
4
answers
3k
views
Is the one-time-pad a secure system according to modern definitions?
Occasionally I hear people say that one-time pads are "useless" or even "broken".
"modern cryptography knows more security definitions, under some of
which the one-time pad is completely broken."
...
- 5,594
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
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
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
11
votes
3
answers
2k
views
How to prove the security of block ciphers
I see very often proofs of security for asymmetric crypto algorithms, for instance, using reductions to known hard problems, or game based proofs...
In the field of protocols (like authentication) it ...
11
votes
1
answer
464
views
What does 'a reduction is tight' mean rigorously?
As far as I know, when someone says 'a reduction is tight', it means that given that there is an adversary $A$ with advantage $\epsilon$ and running time $t$ and another adversary $B$ utilizing $A$ ...
- 363
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
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
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
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
8
votes
2
answers
2k
views
What is a q-type assumption?
I've seen the term "$q$-type assumption" used in a few papers without a definition. A Google search doesn't seem to come up with anything useful either (except the same papers without a definition). ...
- 375
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
8
votes
1
answer
3k
views
An unpredictable PRG is secure (Theorem Yao'82)
in the Mr Boneh's online course is stated the following theorem:
Let $G:K \to \{0,1\}^n$ be a PRG.
“Thm”: if $\forall i \in \{0, … ,n-1\}$ the PRG $G$ is unpredictable at pos. $i$,
then $G$ ...
- 3,922
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
8
votes
1
answer
166
views
Definition of secure computation with more that two parties
In Definition of secure computation in m-party case with respect to semi-honest adversary (Definition 7.5.1 in Foundations of Cryptography: Volume 2, Basic Applications by Oded Goldriech) we say ...
- 398
8
votes
1
answer
6k
views
Difference between semi-honest and malicious adversary using Ideal Real Model Paradigm
Would you please explain to me why in the security definition of ideal/real model paradigm which is described in the efficient secure two-party protocol book(Hazay, Lindell), the simulator tries to ...
7
votes
2
answers
215
views
Confusion about definition of homomorphic encryption
I am trying to better understand homomorphic encryption, but I feel like I keep getting inconsistent information in the papers that I am reading.
One of the papers I am reading says the following:
...
- 173
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
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
3
answers
607
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
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
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
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
870
views
Exact mathematical definition of simulation based security?
I've been trying to understand cryptographic protocols and how to define their security. The problem is that while I can understand what the intuitive definition says, I have trouble understanding how ...
- 61
6
votes
1
answer
681
views
What is the difference between RCCA and CCA2?
Well, I know it's easy to tell CCA1 from CCA2, but I failed to find the difference between RCCA and CCA2.
What is the difference?
- 61
6
votes
1
answer
2k
views
Public-Key Deterministic Encryption : Why does not provide perfect security?
I've got a question about an assignment . The question is "Why a Public-Key Deterministic Encryption Algorithm does not provide perfect security ?" . I suppose it means according to Shannon .
Any ...
- 163
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
5
answers
2k
views
Effective security of block cipher – equal the key size, or half the key size?
The Wikipedia “Key Size” article states:
The security of an algorithm cannot exceed its key length (since any algorithm can be cracked by brute force), but it can be smaller. … … … Most symmetric-...
- 17.8k
5
votes
2
answers
871
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 ...
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
2
answers
3k
views
Block Ciphers and (Non-)Generic Attacks
I am currently reading through Cryptography Engineering and came across this definition of block cipher security:
Definition 2 An attack on a block cipher is a non-generic method of
...
- 193
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
645
views
Strong One-Way Function
In the book "Foundations of cryptography-Oded Goldreich-Page 33", if we use the deterministic polynomial-time algorithm instead of the probabilistic polynomial-time algorithm for case 2 (Hard to ...
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
5
votes
1
answer
467
views
What is a non-OWF?
We know that A function $f:\Bbb Z_2^n \longrightarrow\Bbb Z_2^m$ is a (strong) one-way function (OWF), if:
$f$ can be computed by a PT algorithm. Equivalently, there exists a PPT algorithm that on ...
- 206
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
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
1k
views
Why is the definition of Special-honest verifier zero-knowledge probabilistic?
Let $P$ be a prover willing to prove to a verifier $V$ that he knows a witness $w$ satisfying $(x,w) \in R$ for some relation $R$ and some common input $x$.
As found in the literature, $P$ can use a $...
- 1,346