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
21
votes
1answer
5k 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-* ...
37
votes
3answers
40k 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?
14
votes
2answers
915 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 ...
6
votes
2answers
1k 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 ...
33
votes
8answers
43k 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 ...
11
votes
2answers
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 ...
30
votes
1answer
1k 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 ...
21
votes
2answers
4k 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. ...
5
votes
2answers
406 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 ...
6
votes
1answer
3k 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 ...
16
votes
6answers
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 ...
2
votes
3answers
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 ...
5
votes
1answer
276 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 ...
7
votes
1answer
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 ...
10
votes
2answers
3k 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 ...
10
votes
2answers
4k 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 ...
7
votes
1answer
5k 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 ...
19
votes
2answers
5k 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 (...
4
votes
3answers
654 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 ...
7
votes
2answers
3k 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 ...
2
votes
2answers
644 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
1answer
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 ...
10
votes
1answer
5k 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....
11
votes
3answers
2k 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 ...
5
votes
1answer
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 ...
7
votes
3answers
386 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 ...
7
votes
1answer
2k 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 ...
10
votes
2answers
870 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: $...
9
votes
1answer
2k 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 ...
7
votes
1answer
732 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 ...
5
votes
1answer
469 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?
1
vote
2answers
361 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-...
11
votes
1answer
2k 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 ...
3
votes
2answers
514 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 ...
5
votes
1answer
160 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 ...
5
votes
1answer
1k 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 $\...
4
votes
1answer
644 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 ...
4
votes
2answers
154 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 ...
3
votes
1answer
308 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 ...
3
votes
2answers
725 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 ...
2
votes
2answers
92 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 ...
1
vote
2answers
192 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
vote
1answer
543 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 ...
1
vote
1answer
130 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 ...
0
votes
1answer
254 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?