# 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
Filter by
Sorted by
Tagged with
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 ...
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
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
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
1k views

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
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
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
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 \$...