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.
153
questions
1
vote
0
answers
77
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 ...
2
votes
1
answer
157
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 ...
0
votes
1
answer
189
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 ...
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 ...
0
votes
1
answer
57
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 ...
3
votes
1
answer
87
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 ...
2
votes
1
answer
97
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 ...
3
votes
0
answers
174
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 ...
5
votes
3
answers
505
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}...
2
votes
0
answers
37
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[...
3
votes
0
answers
34
views
Data type transformation in Rust library
I am using some ark libraries, such as ark_ff and ark_bls12_381, to implement some cryptographic algorithms. In these algorithms, random oracles are needed, which gets some group elements in G1,G2,Gt ...
5
votes
1
answer
397
views
Do we need the quantum random oracle model (QROM)?
I am currently studying the proof of the Dilithium signature in the quantum random oracle model (QROM). I am curious to hear if anyone have any thoughts on the importance of having proofs in the QROM ...
4
votes
0
answers
40
views
What is the impact of leaving a salt used in HKDF open to attacker control? [duplicate]
RFC 5869 for HKDF says "an application needs to make sure that salt values are not chosen or manipulated by an attacker".1 Soatok also discusses some nuances in choosing salts for HKDF.2 ...
7
votes
1
answer
213
views
Are rejected Dilithium commitments secret?
On 6 March, Yi Lee sent over the NIST mailing list an announcement of their submitted paper that found a flaw in the original security proof for Dilithium. In their manuscript, they fix the proof on ...
1
vote
0
answers
56
views
About SNARKs general recipes (regarding required assumptions)
I'm following ZK MOOC: https://zk-learning.org/
After some previous readings about these topics, I was believing to have understood that, stated that non-interactivity isn't attainable in standard/...
4
votes
1
answer
89
views
sUF-CMA security of Lyubashevsky's ID and signature protocol
I have been working on the post-quantum safe ID/signature-schemes of Vadim Lyubashevsky (https://www.iacr.org/archive/asiacrypt2009/59120596/59120596.pdf).
I am in particular studying the security ...
5
votes
2
answers
933
views
How do you instantiate a Random Oracle?
I was recently discussing with a friend how to instantiate something that requires a RO (with a potentially long output) in a practical implementation. Specifically, for a Fiat-Shamir transform.
The ...
3
votes
1
answer
72
views
Distribution distinguishability as a decision problem
In the definition of a pseudorandom function, we consider two distributions $D_0$ and $D_1$ over functions, where $D_0$ is the distribution of a random function and $D_1$ is the distribution of a ...
2
votes
3
answers
278
views
Is exposing hash of private key provably secure?
Let's say we have an IND-CPA secure public key encryption scheme $\Pi = (\text{Gen}, \text{Enc}, \text{Dec})$. Construct a new PKE $\Pi' = (\text{Gen}', \text{Enc}', \text{Dec}')$ that behaves exactly ...
4
votes
1
answer
158
views
Random oracles and the Borel-Cantelli Lemma
I am trying to understand the implication of the Borel-Cantelli Lemma to the random oracle model.
I think understanding a special case, say, a random oracle is one-way with probability 1, would be ...
0
votes
1
answer
73
views
How to understand the argument “if the adversary outputs x then it queries (a, x) to oracle”?
When I read the work of Dodis et al. ref1, it looks as if I have encountered a simple logical bug. (I'm not concerned with the details of secure proof techniques, but with the logic of reasoning.)
In ...
4
votes
1
answer
198
views
Alternatives of how the Fiat-Shamir transform random oracle is applied to a protocol
The Fiat-Shamir transform typically works by substituting (public) coin tosses from the verifier by hashes of the prover's messages until this point, i.e.: $$H(x,\alpha_1) = \beta_1, \\ H(x,\alpha_1, \...
1
vote
1
answer
75
views
Can a cryptographic hash function that outputs a c-membered subset of the n-membered set?
Is it possible that there is a cryptographic hash function that outputs a c-membered subset of the n-membered set?
In other words, can the set of the binary representation of c-membered subsets of the ...
2
votes
1
answer
126
views
How easy is it to know how many preimages an image might have, given that there's at least one (preimage, image) pair?
I have been considering an approach to incentivize cryptocurrency miners to verify claims of quantum computational supremacy. Briefly, miners find collisions $f(x_1)=f(x_2)=y$ of some known $f:m+1\...
1
vote
0
answers
69
views
Compute a hash function given commitment to some secret element
Given a secret key x and a commitment to it comm(x) where comm(x) is both binding and hiding (it can be for example $g^x$ or some homomorphic encryption). Given public parameters $P_1,...,P_k$, comm(x)...
1
vote
1
answer
76
views
Hash functions with constant number of 1's
In the following paper: https://eprint.iacr.org/2018/056.pdf, the random oracle is defined as follows:
$ H: *\xrightarrow{} \{ \mathbf{v} | \mathbf{v} \in R_{q,[1]}, || \mathbf{v}||_{1}=\omega\}$
...
1
vote
1
answer
239
views
Models and assumptions in the post quantum world
I'm currently trying to get an overview of post-quantum cryptography. Now I'm struggling with correlations and adjustments of the PQ-world and the Modern-world of cryptography.
My Questions:
Can you ...
3
votes
2
answers
506
views
Can two different hash function create two unlinkable `ed25519` keys from the same randomness?
Assume the following scenario:
Alice has access to 32 bytes of true randomness $s$.
Alice hashes $s$ with SHA-512, and uses the resulting hash as the secret $d_{A}$ for ...
6
votes
1
answer
872
views
HKDF randomness extraction - salt or no salt?
According to the HKDF paper, the use of a salt serves two purposes: domain separation and randomness extraction.
This question is solely about the necessity of a salt for the purposes of randomness ...
1
vote
1
answer
113
views
Can an adversary distinguish QROM from ROM with a single query?
I acknowledge that QROM differs from ROM (which can be considered as a specific QROM which performs a measurement to the input). For example, one can find a preimage for an arbitrary value with $O(N)$ ...
3
votes
1
answer
268
views
How does the simulator generate a correct transcript under HVZK with the Fiat-Shamir heuristic?
Background
I understand the interactive version of Schnorr's protocol and I understand how the simulator can generate an output that is i.i.d to the output of the prover-verifier:
Question
What I don'...
1
vote
0
answers
130
views
Cryptographic Random Beacon VS Random Oracle
Let's start with what I mean by cryptographic random beacon (RB).
A RB is a protocol among some parties who generate a random value all together such that:
these parties do not trust each other
the ...
2
votes
1
answer
87
views
Security of Hash Functions
Given a Hash Function H, how are the properties such as collision resistance, target collision resistance, one wayness, and non-malleability proved? I have read about hash function and stating that it ...
2
votes
0
answers
166
views
Uniform vs Non-uniform Attackers
There is a concept of attackers gaining some information before attacking a system and those attackers being called non-uniform attackers. How do the security proofs for cryptographic primitives in ...
2
votes
0
answers
42
views
Auxiliary-Input Random Oracle Model
Referring to https://eprint.iacr.org/2007/168.pdf, is it true that the auxiliary input random oracle model strengthens the RO model captures the fact that an attacker may know (eg. have hardcoded) a ...
7
votes
1
answer
453
views
Difference between Generic Group Models
I'm trying to understand the difference between the (classical) Generic Group Model as it is described by Shoup [Shoup] and the somewhat restricted Generic Group Model as it is described by Schnorr ...
4
votes
1
answer
256
views
Is the post-quantum scheme quantum-resistant without regard to QROM
There are many "post-quantum" schemes have been proposed.
The security of most of them is only proven under random oracle model or uses forking lemma.
As described by Boneh et al. (Random ...
4
votes
1
answer
102
views
Multi Message security in Random Oracle Model
I have been learning about ROM in class and was wondering what an example of an encryption scheme that is multi-message secure in the random oracle model would look like? I have learned how to prove ...
3
votes
0
answers
435
views
Security of Full Domain Hash (or not quite full)
Full Domain Hash is the simplest signature scheme based on a trapdoor permutation (such as textbook RSA) that enjoys a strict security reduction. It was introduced by Mihir Bellare and Phillip Rogaway:...
4
votes
1
answer
382
views
Proving statistically hiding for a simple commitment scheme in the ROM
It is well known that one can construct a simple commitment scheme in the random oracle model (ROM) by setting
$\mathsf{Commit}(m;r) = H(r||m)$, where $m \in \{0,1\}^k$, $r \in \{0,1\}^{2k}$ and $H: \{...
3
votes
2
answers
220
views
Combined scheme security proof
Let CS be a combined scheme of $n$ public key subschemes.
CS is composed of two algorithms Setup and KeyGen, that all the subschemes share, plus all the other algorithms of each subscheme.
Suppose ...
3
votes
0
answers
103
views
What is the difference between non-programmable random oracle model and standard model?
I know Common ground of them is that in both model the simulator cannot choose the reply for the query, and the difference between them is that in NPROM the simulator can still see the query/answer ...
2
votes
3
answers
681
views
Is it possible to have perfectly secure public-key cryptography with oracles?
It is a basic theorem of cryptography that it is impossible to have a perfectly secure public-key encryption scheme. That’s because the adversary can search through all possible private keys.
But I’m ...
7
votes
1
answer
517
views
What does it mean to be "sound"?
I've been reading this in many places and I still don't properly understand what it means to be "sound". As an example of what I am asking for:
The Fiat-Shamir transfrom is sound in the ...
0
votes
0
answers
79
views
How to prove properties of pre-image of random oracle in zero-knowledge proof?
A signature Sig is given as input to random oracle H, such that y = H(Sig) and Sig should be hidden from the verifier. How to prove in zero-knowledge to the verifier that y is the correct output from ...
3
votes
0
answers
120
views
Is it impossible to model a homomorphic hash function as a random oracle?
Recall that, by definition, on input a query $q$, a random oracle $H$ can output a fresh random string as its response $H(q)$ (if this query has not been seen before).
My understanding. A homomorphic ...
0
votes
1
answer
119
views
Is the random oracle commitment scheme secure against PPT active adversaries?
The probability that a probabilistic polynomial adversary corrupting the sender can finds two pairs $(m,r)$ such that the output of the random oracle $c$ is the same (break the binding property) is ...
0
votes
2
answers
262
views
Random Oracle to prove an Authenticated DH protocol
I am trying to understand how they use the random oracle to solve the CDH. For example, in the security proof on page 7 of the following paper; A Lightweight Message Authentication Scheme for Smart ...
1
vote
0
answers
64
views
What is the underlying hard problem in the reduction of game-based proofs?
I am confused by how game-based proofs fit in the provable security paradigm. I understand reductions in the style of proving secrecy of RSA reducing it to integer factorization. However, when proving ...
0
votes
0
answers
136
views
How can I show, that RSA with OWP is IND-CPA secure by using H function?
How can I show, that RSA with OWP is IND-CPA secure by using H function , a random oracle model.
The Encryption goes like: $\text{Encryption_H_PK}(M)\gets(C_1,C_2)\gets(f(x),H(x)\oplus M)$
...