Skip to main content
35 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 $\...
ckamath's user avatar
  • 5,338
17 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 ...
Yehuda Lindell's user avatar
16 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 ...
Mark Schultz-Wu's user avatar
  • 13.5k
15 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 ...
Thomas Prest's user avatar
  • 1,080
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 ...
Cort Ammon's user avatar
  • 3,261
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 ...
Ella Rose's user avatar
  • 19.7k
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 ...
Hilder Vitor Lima Pereira's 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 ...
Shan Chen's user avatar
  • 2,725
10 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 ...
Geoffroy Couteau's user avatar
9 votes
Accepted

Definitions of secrecy

In cryptography, forward secrecy = perfect forward secrecy, backward secrecy = future secrecy. First, recall some background. The above terms are often discussed in the setting of secure channel ...
Shan Chen's user avatar
  • 2,725
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 ...
e-sushi's user avatar
  • 18k
9 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 ...
Squeamish Ossifrage's user avatar
9 votes

Statistical security parameter -> information theoretically secure

In interactive protocols (like MPC) you will often see a combination of computational and statistical security parameters used together. Computational security parameter: tunes the hardness of some ...
Mikero's user avatar
  • 13.6k
8 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$ ...
Rajat Subhra Roy's user avatar
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 ...
poncho's user avatar
  • 148k
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 ...
forest's user avatar
  • 15.3k
8 votes
Accepted

Statistical security parameter -> information theoretically secure

A protocol (and in general, a cryptographic construction) satisfies information-theoretic security if no adversary can break the system, no matter how powerful the adversary is. The term "...
Daniel's user avatar
  • 3,972
8 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 ...
Mikero's user avatar
  • 13.6k
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 ...
Ella Rose's user avatar
  • 19.7k
7 votes
Accepted

When knowledge soundness implies soundness

The difference is that in Section 4.5, knowledge soundness (i.e., extraction) is required to hold only for every $x\in L_R$, and so there is no requirement at all for the case that $x$ is not in the ...
Yehuda Lindell's user avatar
7 votes
Accepted

Security definition for IND-CPA of public key encryption

In public-key cryptography, the adversary is indeed able to create encryptions of their chosen messages $m_1$ and $m_2$ on their own. This is why any IND-CPA-secure public-key cryptosystem cannot be ...
Morrolan's user avatar
  • 1,157
6 votes

Confusion about definition of homomorphic encryption

In short, the operations may be different, but they do not must be. For instance, in the scheme presented on the pages 6 and 7 of this paper the homomorphic addition is simply a addition, but the ...
Hilder Vitor Lima Pereira's user avatar
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 ...
mikeazo's user avatar
  • 38.7k
6 votes
Accepted

An example of of an information theoretically secure protocol that is not cryptographically secure

In order for information-theoretic security to imply computational security, you need to require that the simulator run in time that is polynomial in the running time of the real adversary. This is ...
Yehuda Lindell's user avatar
6 votes

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

Yes, it does. Any cryptosystem relying on factoring being hard (RSA, Paillier, Rabin, etc.) is immediately broken by an unbounded adversary, because he can just try out all smaller prime factors to ...
tylo's user avatar
  • 12.7k
6 votes
Accepted

difference between the uniform and non-uniform probabilistic polynomial algorithms (ppt)

The non-uniformity needed for the proofs of security is in the distinguisher (in order to get advice as to which inputs the protocol breaks on in the reduction). However, if you are already assuming ...
Yehuda Lindell's user avatar
6 votes

How long would it take all of the supercomputers or cloud computing on Earth to bruteforce a significantly long password?

A salt is supposed to be publicly available, for instance it needs to be stored in a DB next to the password hash. In that case the time it takes to recover the password is just a brute force or ...
Maarten Bodewes's user avatar
  • 93.3k
5 votes

random oracle model vs standard model vs selective model

In the random oracle model, you assume the existence of random behaving function, which is at the control of the protocol designer-challenger- during the game played between the adversary and the ...
curious's user avatar
  • 6,200
5 votes
Accepted

Can you help me understand indistinguishably as described in the CPA security definition?

Yes, your intuition is completely right (assuming a polynomial-time adversary and a super-polynomial message space, which is the usual setting). If the scheme were deterministic, then the adversary ...
cygnusv's user avatar
  • 5,002
5 votes
Accepted

What does it mean the security parameter for a FHE scheme?

What does this parameter signify ? It's a tweakable parameter that varies (typically) the sizes of various objects in the cipher, and while any non-silly value will work (e.g. encrypt and decrypt ...
poncho's user avatar
  • 148k

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