Questions tagged [random-oracle-model]
A model used in cryptographic security proofs, in which concrete primitives such as hash functions are replaced with a "random oracle": a hypothetical black box that maps its inputs to truly random outputs, but in such a way that the same input always yields the same output.
158
questions
0
votes
0
answers
58
views
Why adversary have to do hash queries in RO model?
In MPC，it is common to use hash to extract the real input of malicious adversary under RO model. But I wonder why the adversary have to do hash queries rather than just select random values as the ...
- 41
4
votes
1
answer
90
views
Security impact of weakened collision resistance for 128-bit Fiat-Shamir challenges
As I understand, to achieve a security level of $\lambda$, a hash function's output should be at least $2\lambda$ in length, since the search space is halved for collision resistance.
However, I am ...
- 43
3
votes
2
answers
175
views
Spliting Random Oracle into multiple Random Oracles
I'm currently working on a proof in the random oracle model, where a single random oracle is used in multiple places.
Each use is domain-separated so I was thinking of representing it as multiple ...
- 33
1
vote
1
answer
44
views
A doubt on Proofs-of-Sequential-Work protocols
Proofs-of-Sequential-Work ($\mathsf{PoSW}$) are cryptographic protocols that engage two parties, a prover with $\mathtt{poly}(N)$-parallel processors and a deterministic verifier such that the ...
0
votes
0
answers
43
views
Showing the zero-knowledge property in a NI-ZK scheme
To my understanding, whilst the definition of zero-knowledge (zk) is the same in the non-interactive context, how one shows a non-interactive scheme is zk is very different from interactive zk ...
1
vote
0
answers
117
views
One-more co-CDH assumption in pairing group
I am asking it again because no one answered my previous question with more clarity. I have deleted that question
One more co-CDH in Type three pairing groups $G_1 \times G_2 \to G_T$: means given a ...
- 621
2
votes
1
answer
177
views
Random oracle vs implementations like hash function
In this answer, it is stated
It has actually been shown (by Canetti, Goldreich and Halevi) that
random oracles cannot exist "in all generality" in the following
sense: it is possible to ...
- 737
0
votes
1
answer
266
views
How good is blake3 compared to a random oracle?
How good is blake3 for generating pseudo-random bitstrings in comparison to a random oracle?
Let's say we generated an arbitrarily long pseudo-random bitstring by concatenating blake3 hashes together ...
- 123
4
votes
0
answers
107
views
Impossibility of uniform generation in random world
I was reading Limits on the provable consequences of one way permutations by Impagliazzo and Rudich when I got stuck on a sentence.
First of all, they define a polynomial relation that is any relation ...
- 60
0
votes
1
answer
59
views
Does quantum-sourced randomness allow a potential random oracle instantiation?
My question is essentially the same as this one.
The random oracle is a black box that does two things.
Maintain a lookup table for any query that has already been asked.
For all new queries, toss a ...
- 737
3
votes
1
answer
88
views
Where does the 8 come from? Generic Search Problem with Bounded Probabilities
I am working with lossy ID-schemes and their security in the QROM. Following the article of Kiltz et al. , I am at a loss of the number 8 appearing in most reductions throughout the article. I know it ...
- 335
2
votes
1
answer
117
views
Fiat-Shamir with interactions
Suppose we have a standard $\Sigma$-protocol for proving the knowledge of a witness $x$ for the statement $y$. It has an honest-verifier ZK and special soundness. Now we do an unusual modification to ...
- 558
3
votes
0
answers
220
views
Prove DSA signature scheme is EUF-CMA secure
I want to prove that the DSA signature scheme is EUF-CMA secure in the random oracle model, if the discrete logarithm problem is hard. I know it can be proved by the following two parts:
Discrete ...
- 31
5
votes
3
answers
517
views
Maximum entropy of a hash function?
Let $H(h,k)$ be the expected entropy of some random oracle $X:\left\{0,1\right\}^h \to \left\{0,1\right\}^k$, where $h$ does not necessarily equal $k$.
Then, is it true that $\lim\limits_{h\to\infty}...
- 343
2
votes
0
answers
41
views
Proving the minimal entropy of Dilithium-QROM?
I am working with the securit yof CRYSTAL's Dilithium signature in the QROM. I am working with Kiltz et al.'s approach through lossy ID-schemes and looking at the proof of minimal entropy for the $DFS[...
- 335