Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
16 votes

What is the "Random Oracle Model" and why is it controversial?

The bear describes a process for choosing and computing a uniform random function involving gnomes in boxes, but this doesn't really explain what the random oracle model is in the context of proving ...
Squeamish Ossifrage's user avatar
13 votes
Accepted

Why do Feistel ciphers need round keys?

Iterated ciphers need variability between rounds to resist so callad Slide attacks. One common way to thwart this attack is with a key schedule generating different round keys for each round. Slide ...
user49042's user avatar
  • 146
13 votes
Accepted

What does it mean to be "sound"?

An interactive or non-interactive protocol is said to be sound for a language $\mathcal{L}$ if it is "hard" for a (malicious) prover $\textsf{P}$ to convince a verifier $\textsf{V}$ of a ...
ckamath's user avatar
  • 5,248
12 votes
Accepted

Explanation and proof of a well-know probabilistic lemma

This is based on an averaging argument (which is also used in the proof of the Goldreich-Levin hardcore bit). First, I assume that when writing $\operatorname{Pr}[A(x,y)=1] \geq \epsilon$, then the ...
Yehuda Lindell's user avatar
12 votes

Why do Feistel ciphers need round keys?

This is due to Luby and Rackoff's proof about Feistel networks. The proof assumes the PRFs are independent. See sections 4.5 and 5 of How to Construct Pseudorandom Permutations from Pseudorandom ...
otus's user avatar
  • 32.1k
12 votes
Accepted

Could you list all of the security models in cryptography?

What you are asking for is not really a list of security models, but more a list of idealized models (like the ROM), and trust assumptions (like the CRS model). Asking for a list seems a bit off-topic ...
Geoffroy Couteau's user avatar
12 votes
Accepted

What is the Common Reference String (CRS) model

The CRS has nothing to do with modeling hash functions. Rather, it is a model where there is a public string that was generated in a trusted manner, and all parties have access to the string. It has ...
Yehuda Lindell's user avatar
9 votes

Prove the Security of Schnorr's Signature Scheme

Pointcheval and Stern [PS00] proved that the Schnorr signature is existentially unforgeable under chosen-message attacks (EU-CMA) in the random oracle model assuming that the discrete-logarithm ...
ckamath's user avatar
  • 5,248
9 votes
Accepted

One-Way property of Random Oracle

This is very confusing because it seems as it should be something really easy to prove. However, it actually is not, and in fact the proof uses the Borel-Cantelli lemma. Anyway, it was formally proven ...
Yehuda Lindell's user avatar
8 votes
Accepted

What is a cyclic group of prime order $q$ such that the DLP is hard?

Cyclic group of prime order q such that the DLP is hard A simple technique to form a cyclic group $G$ of prime order $q$ such that the underlying discrete logarithm problem (DLP) is (conjecturally) ...
fgrieu's user avatar
  • 142k
8 votes
Accepted

What is meant by domain separation in the context of KDF?

With KDFs, you need domain separation when you use the same initial key material to generate keys for different purposes like using the same initial key material and nonce to generate encryption and ...
lovesh's user avatar
  • 522
8 votes
Accepted

How does the random oracle model simplify proofs versus using the standard model?

Yes, there are examples where the random oracle model has been first used, then removed, Yes, the proof becomes, in the end, much (much) more complex. But in fact, simplicity of the proof is not the ...
Geoffroy Couteau's user avatar
8 votes
Accepted

How do you instantiate a Random Oracle?

You should use a modern hash function designed to be indistinguishable from a random oracle, such as SHA-3 for fixed/short output sizes and SHAKE for variable/long output sizes. "Collision ...
CodesInChaos's user avatar
  • 24.9k
7 votes
Accepted

How to construct a hash function into a cyclic group such that its discrete log is intractable?

The obvious way to create such a hash function would be to first define a hash function $H$ (distinct from $H_1$) that generates as output an integer in the range $[2, q]$, and then define $H_2(x) = H(...
poncho's user avatar
  • 148k
7 votes
Accepted

How can I hash an input into an arbitrary domain point?

Hash functions we use, e.g. Sha-1, Sha-256, Sha-512, usually don’t have a sufficiently large range. But we can construct full domain hash via repeated application of a hash function $h$: $FDH(m) = h(m|...
Changyu Dong's user avatar
  • 4,178
6 votes

Why do Feistel ciphers need round keys?

It does not make sense to say that any fixed function $F$ "is a good PRF". A distribution on functions can, however, be pseudorandom (indistinguishable from the uniform distribution over the set of ...
p-steuer's user avatar
  • 126
6 votes

Perfect secrecy with XOR & SHIFT?

Hiding which cipher you are using means violating Kerckhoff's principle. That's actually an extremely common mistake. The problem is that such a cipher becomes very hard to analyze because you have to ...
Elias's user avatar
  • 4,913
6 votes
Accepted

How can homomorphic encryption be probabilistic while allowing for math to be conducted?

Probabilistic encryption is a necessity for ANY public-key encryption scheme. The reason is that in such schemes anybody can perform the encryption, thus if the encryption was deterministic, that ...
fgrieu's user avatar
  • 142k
6 votes
Accepted

Signature security proof in the Random Oracle model

This was discussed by Coron in 1. You are actually asking why the random oracle can't just be some uncontrollable ideal random oracle. In fact Bellare and Rogaway when introduced their Full Domain ...
Avilan's user avatar
  • 128
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,170
5 votes
Accepted

Random oracles and independence

If $H(X)$ and $H(Y)$ were not evaluated as a part of selecting $X$ and $Y$, then yes; the assumption of a random Oracle is that $H(Z)$ is an independent and uniformly distributed variable for every ...
poncho's user avatar
  • 148k
5 votes
Accepted

What if using a block cipher as compression function in Merkle–Damgård?

One issue is that it would make finding preimages significantly easier; with $O(2^{n/2})$ time rather than $O(2^n)$ time. Here's how you would do such a search: Select $2^{n/2}$ distinct initial ...
poncho's user avatar
  • 148k
4 votes

Explain Fischlin's Fiat-Shamir like transformation

I think I got it. The point, in short, is that you require multiple proofs (commit_i,challenge_i,response_i), where each proof's validity depends on all the first ...
relG's user avatar
  • 226
4 votes

Equivalance Operator - Perfect Secrecy

Actually, for any group operator $\odot$, we see that $x \odot y$ gives perfect security, assuming that $y$ is uniformly random over all possible group members. The $\equiv$ operation is a group ...
poncho's user avatar
  • 148k
4 votes

How can a hash function that implements random oracle model have collision resistance?

As Ella Rose points out in a comment, it is not that there are no collisions; rather, one can prove that the probability of encountering a collision is small in the random oracle model. The random ...
Squeamish Ossifrage's user avatar
4 votes

What is the non-programmable random oracle model?

The main difference (from a cryptographic point of view) is whether the simulator is capable of choosing the answers to the oracle queries or not. In more detail, to prove the simulation-based ...
Hamidreza's user avatar
  • 1,019
4 votes

How much entropy is lost if 1 character is fixed in HMAC SHA-512?

I'll assume the hash function is "good", i.e., equidistributed and partial-preimage-resistant. If the input length $n$ is fixed and you fix $k$ bits of the output hash, you're losing roughly $k$ bits ...
yyyyyyy's user avatar
  • 12.1k
4 votes
Accepted

Differences between OWP and OWF and their IND-CPA security

A one-way permutation is just a one-way function in which the function is a permutation (id est, a bijective function). Every OWP is a OWF, the converse is not true. IND-CPA security is a security ...
Geoffroy Couteau's user avatar
4 votes

Fiat-Shamir paradigm and the forking lemma

Let's recall important definitions. A proof system $(\mathsf{P}, \mathsf{V})$ for an NP language $\mathcal{L}$ is a pair of interactive Turing machines where the prover ($\mathsf{P}$) and the verifier ...
Alan's user avatar
  • 1,460
4 votes

How can I hash an input into an arbitrary domain point?

Why don't you use an eXtendible Output Function (XOF) for that ? For example, SHAKE-128, defined in the SHA-3 standard, allows you to hash a message and obtain as output as many bits as you want. ...
Ruggero's user avatar
  • 7,104

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