# Questions tagged [security-definition]

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

303 questions
Filter by
Sorted by
Tagged with
51k 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
56k 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 ...
• 551
10k 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-* ...
• 46.2k
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 ...
• 599
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. ...
• 323
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 (...
• 18k
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 ...
• 6,200
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 ...
• 18k
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 ...
• 46.2k
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 ...
• 141
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,867
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,684
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,656
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 ...
6k views

• 4,465
579 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
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,096
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: $... • 540 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 ... • 4,002 9 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 ... • 7,104 9 votes 1 answer 1k 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 ... 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 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.6k 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$... • 4,002 8 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 ... • 411 8 votes 1 answer 169 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 225 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 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,867 7 votes 3 answers 667 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.7k 6 votes 2 answers 1k 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 ... 6 votes 1 answer 707 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 ... • 273 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 ... • 451 6 votes 1 answer 880 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 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 1 answer 703 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? 6 votes 0 answers 137 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 ... • 453 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-... • 18k 5 votes 1 answer 672 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? • 589 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 816 views ### Indistinguishability of symmetric encryption under CCA I am learning about symmetric encryption and its security properties. One of the security notion is security against chosen cipher-text attacks (CCA), particularly IND-CCA notion. Under this notion, ... • 73 5 votes 1 answer 803 views ### Is the practice of "security through obscurity" violating Kerckhoffs's second principle? Security through obscurity is the reliance on the secrecy of the design or implementation as the main method of providing security for a system or component of a system. Kerckhoffs's second principle:... • 6,462 5 votes 1 answer 3k 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,867 5 votes 1 answer 669 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 748 views ### Can you help me understand indistinguishably as described in the CPA security definition? When I read the definition of the CPA indistinguishably encryption scheme, I see that the adversary can use an oracle as many times (to get as many encryptions of any messages it choose). An the end ... • 383 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$\...
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 ...