30 votes
Accepted

What is the difference between uniformly and at random in crypto definitions?

If you sample a random element, then you sample it according to some distribution. Uniformly then means that you sample from the uniform distribution, i.e., you sample it from a set where drawing ...
user avatar
  • 12.1k
29 votes
Accepted

What do the signature security abbreviations like EUF-CMA mean?

Notation. Sets are represented using the calligraphic font and algorithms using the straight font. Throughout, $\Sigma:=(\mathsf{K},\mathsf{S},\mathsf{V})$ denotes a signature scheme on a key-space $\...
user avatar
  • 4,463
25 votes

Simply put, what does “perfect secrecy” mean?

Perfect Secrecy (or information-theoretic secure) means that the ciphertext conveys no information about the content of the plaintext. In effect this means that, no matter how much ciphertext you have,...
user avatar
22 votes

Is the one-time-pad a secure system according to modern definitions?

Modern security has moved beyond looking just at passive attacks (in which the attacker is just a passive eavesdropper seeking to learn what was said); attackers are generally considered to be able ...
user avatar
  • 3,547
18 votes
Accepted

Example of a PRP that is not a strong PRP

A three-round Feistel network is a good example of a realistic construction that is a secure "weak" PRP, but not a "strong" PRP. A Feistel network uses the permutation $P_f(L, R) = R, (L\oplus f(R))$,...
user avatar
  • 2,706
16 votes

Uniform vs discrete Gaussian sampling in Ring learning with errors

The TL;DR: From a theoretic point of view, Gaussians are the better choice, both for the easiness of the security proof and its optimality in terms of tightness; In practice, most of the time you can ...
user avatar
  • 1,082
15 votes
Accepted

Existential unforgeability vs strong unforgeability

It is easy to construct a signature scheme that is existentially unforgeable but not strong. All you have to do is add a bit to the end of a strong scheme, and ignore it upon verification. This ...
user avatar
14 votes

Meaning of "Security can be reduced to a problem"

You are (mostly) right. Reductions are an algorithmic notion — $P$ reduces to $Q$ if the ability to solve $Q$ allows you to solve $P$. There are many ways to formalize this, but the one that you ...
user avatar
  • 8,424
13 votes
Accepted

How small is negligible?

Negligible is a human term, not a precise definition. It refers to things which are sufficiently small that one is willing to ignore it in the interests of expediency. The threshold varies from ...
user avatar
  • 3,161
12 votes
Accepted

What is a q-type assumption?

The classic standard assumptions (such as DDH, CDH) are not parametrized and always have constant size (are static). Consequently, the assumption when used in a reductionist proof is independent of ...
user avatar
  • 12.1k
12 votes

What are the exceptions to Kerckhoffs's principle?

Kerckhoffs's principle: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge. The principle does not state that it is unconditionally unacceptable ...
user avatar
  • 19.2k
10 votes
Accepted

"Power of one" as input to functions of a cryptosystem

The notation $1^\lambda$ means a string with $\lambda$ characters all of them equal to 1. For instance, if $\lambda = 3$, then $1^\lambda$ is $111$. And yes, it typically stands to the security ...
user avatar
10 votes

Does GCM (or GHASH) only provide 64-bit security against forgeries?

According to the references, AES-GCM offers roughly 64-bit authenticity security (i.e., against forgery attacks) for 128-bit block size and long-enough (>=64-bit) tag size. When the number of queries ...
user avatar
  • 2,625
9 votes
Accepted

What does it mean for an adversary to run in PPT?

An algorithm being probabilistic means that it is allowed to "throw coins", and use the results of the coin throws in its computations. This is reasonable because a realistic adversary has access to ...
user avatar
  • 7,904
9 votes
Accepted

What exactly is a “security parameter”?

Quoting the obvious (Wikipedia article about the term “security parameter”.) In cryptography, the security parameter is a variable that measures the input size of the computational problem. Both the ...
user avatar
  • 17.3k
8 votes
Accepted

Understanding Twist Security with respect to short Weierstrass curves

The twist attack is best explained in Fouque et al's paper. While the (quadratic) twist of the curve $E : y^2 = x^3 + ax + b \in \mathbb{F}_p$ is indeed of the form $E^t : y^2 = x^3 + d^2ax + d^3b \in ...
user avatar
  • 11.6k
8 votes
Accepted

An unpredictable PRG is secure (Theorem Yao'82)

This lecture (PDF) has the solution in section 3. Here's my informal explanation of the proof: We have an unpredictable PRG $G$. We want to show that $G$ is secure, or in other words ...
user avatar
8 votes

Key Size for Symmetric Homomorphic Encryption Over the Integers

The paper says that the parameters are $r ≈ 2^{\sqrt \eta}$ and $q ≈ 2^{\eta^3}$. Note that these values are expressed as functions of $\eta$, not $N$. With regard to the parameters, it is common ...
user avatar
  • 4,822
8 votes
Accepted

Does information theoretical security definition imply DDH, RSA, QR does not hold?

Does this mean that the standard definitions for DDH, RSA or QR do no hold in that setting, because the definitions assume some bounds on the computational power of the adversary? That is correct; a ...
user avatar
  • 131k
8 votes
Accepted

Does GCM (or GHASH) only provide 64-bit security against forgeries?

The phrase ‘128-bit security’ is a bit glib to cover the online/offline distinction—the purpose of the explicit formulas is to quantify the forgery probability in terms of limits on the online and ...
user avatar
8 votes
Accepted

What is the difference between information-theoretic and perfect types of security?

Information-theoretic security means that any algorithm (even unbounded) has a negligible probability of breaking the security property (in the security parameter). This is the same as unconditional ...
user avatar
8 votes

What is the security concept in printer cartridge?

A company can make more money if the printers it sells only work with the cartridges they sell, which does not work if there is competition. It's cheaper to force a vendor lock-in than it is to ...
user avatar
  • 12.9k
7 votes

Simply put, what does “perfect secrecy” mean?

Perfect Secrecy essentially means these notions: $P(M=m|C=c) = P(M=m)$ i.e. seeing a ciphertext doesn't give you any extra information about the plaintext. The probability of seeing a message $m$ ...
user avatar
7 votes
Accepted

Is the practice of "security through obscurity" violating Kerckhoffs's second principle?

"It should not require secrecy, and it should not be a problem if it falls into enemy hands" Where "it" is the algorithm design itself, and not an input to it... But isn't the practice of ...
user avatar
  • 19.2k
7 votes
Accepted

Indistinguishability of symmetric encryption under CCA

CCA security always seems extreme to people who are just learning about it. The premise seems ridiculous, why would we give the attacker so much power? Why would we just let the attacker decrypt ...
user avatar
  • 10.6k
6 votes

Simply put, what does “perfect secrecy” mean?

Perfect secrecy is the notion that, given an encrypted message (or ciphertext) from a perfectly secure encryption system (or cipher), absolutely nothing will be revealed about the unencrypted message (...
user avatar
  • 1,928
6 votes
Accepted

Effective security of block cipher – equal the key size, or half the key size?

I just read that chapter of the book, and the authors don't really justify their claim. They also talk about "using random data to prevent collision and precomputation attacks" (which would then give ...
user avatar
6 votes
Accepted

Key Size for Symmetric Homomorphic Encryption Over the Integers

-- Introduction First of all, I know that you are trying to have a better understanding about the symmetric scheme, but, since the authors focused on the public key scheme, you will have to ...
user avatar
6 votes

Example of a PRP that is not a strong PRP

For convenience, let's assume that $\mathcal{K} = \mathcal{D}$ so that the key $k \in \mathcal{D}$. Define $E$ to be some strong PRP, and let $D$ be its inverse. Now, define a PRP $E' : \mathcal{D} \...
user avatar
  • 2,706
6 votes
Accepted

Confusion about definition of homomorphic encryption

The operation does not have to be the same. For example, with Paillier, we multiply ciphertexts to get the addition of the plaintexts. That said, I think what the 2nd quotation is saying is that the ...
user avatar
  • 37.7k

Only top scored, non community-wiki answers of a minimum length are eligible