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.

Filter by
Sorted by
Tagged with
0
votes
0answers
17 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 ...
2
votes
0answers
30 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
1answer
35 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
2answers
74 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
0answers
34 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
0answers
38 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)$ ...
2
votes
1answer
97 views

Random oracle based on SHA-256

I am given the following problem. Consider SHA-256 to be a random oracle in a practical application. Construct an (almost) random oracle $\{0,1\}^*→\{0,1\}^{3000}$ based on SHA-256. Does it mean ...
0
votes
0answers
39 views

Understanding a security proof

I am reading the paper "RingCT 3.0 for Blockchain Confidential Transaction: Shorter Size and Stronger Security" (https://eprint.iacr.org/2019/508.pdf), an improvement to Ring Confidential Transactions....
2
votes
0answers
50 views

Why does the random oracle receive much more criticism than the ideal cipher?

The random oracle model seems to be criticized a lot as lacking practical relevance, making wrong predictions, being programmable, etc. However, I have never heard such criticism about the ideal ...
0
votes
0answers
34 views

Linkable ring signatures from RingCT3.0 and random oracle model [duplicate]

I am trying to deal with Linkable ring signatures from RingCT3.0 (https://eprint.iacr.org/2019/508.pdf). I can not find confirmation or refutation of the following assumption: Linkable ring ...
3
votes
1answer
86 views

Bulletproof and random oracle model

I am trying to deal with Bulletproof. I can not find confirmation or refutation of the following assumption: Bulletproof cannot work without the random oracle, which is a necessary part of the ...
0
votes
1answer
86 views

Random oracle : Replay

What I understand about the random oracle game: The adversary can query the oracle polynomial many times with the same (secret but unknown) key. From the output returned by the oracle, the ...
1
vote
2answers
111 views

Why doesn't the ability to sample a single random bit imply the construction of a random oracle?

I'm trying to understand exactly how the random oracle model differs from the standard model. In many proofs & applications there are some assumptions that some randomness is sampled (i.e. a bit $...
2
votes
1answer
124 views

Why XOFs are more convenient than Hash Functions in modeling Random Oracles

In this answer, it is mentioned that Easier instantiation of random oracles. Some security proofs rely on the so-called random oracle model to prove the security of a given scheme. Normally you'd ...
2
votes
1answer
31 views

key recovery in the ideal cipher model

I'm reading up on the ideal cipher model and can't wrap my head around some basic calculation. Let $E$ is an ideal cipher with $n$-bit key and $n$-bit block. For each key $K$, $E_K$ is random ...
4
votes
1answer
123 views

A hash-based pseudorandom function

Let $H()$ be a cryptographic hash function. Question: Can we consider $c= H(r||i)$ as a pseudorandom value, where $i$ is a public value, $1\leq i\leq n$, and $r$ is a large uniformly random value/...
2
votes
1answer
70 views

Can HKDF be instantiated with HMAC-SWIFFT?

While reading through "Cryptographic Extraction and Key Derivation: The HKDF Scheme" by Hugo Krawczyk, I found the following text intriguing: In some cases, well-defined combinatorial assumptions ...
2
votes
1answer
172 views

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

If I use the standard model, then the proof must rely on mathematical assumptions. Will this security proof, generally be longer/more complex? Is there an example where the random oracle has been ...
0
votes
0answers
37 views

Does proving security in the random oracle model ensure that using a hash function is secure?

In security proofs, I have seen the random oracle model and the standard model. If I prove security in the random oracle model, does this mean that if I use SHA-3, assuming sha-3 cannot be broken, ...
10
votes
4answers
423 views

Signature security proof in the Random Oracle model

As a study case, I consider the BLS signature scheme, but the following question is relevant in the general context of security proofs in the Random Oracle model. Let us briefly recall BLS signature ...
6
votes
2answers
286 views

Understanding forking lemma and oracle replay attack

Many signature schemes use forking lemma to prove security, like scheme in here.In short, that goes through a reduction technique which called oracle-replay attack to solve the difficult algorithmic ...
4
votes
2answers
547 views

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

I am trying to implement a signature scheme involving RSA signing of a message digest generated by SHA-$256$. I want to hash the input into an RSA domain point instead of the fixed $256$ bit digest ...
3
votes
1answer
270 views

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

This is a quote from my cryptography notes: If $h$ is a random function oracle of output length $n$ then also the two KDF constructions: $K(x) = h([0] \| x) \ldots \| h([L] \| x)$ $K(x) = h(x \| [0] )...
0
votes
0answers
60 views

RSA-based encryption scheme and random oracle

I don't really get how this problem should be solved. My main issue is with the random oracle generally, a short explanation of ROs and how they are used in such proofs maybe with this example will ...
3
votes
2answers
189 views

How close is AES to random oracle model?

I'm wondering if there are any guarantees about AES's randomness in comparison to Random Oracle, but I couldn't find any papers nor publications about it. Let's say I have a blackbox B which for any ...
3
votes
0answers
54 views

Hardness or negligibility of finding small non-trivial addition coefficients for random values to sum to zero

In my cryptographic scheme, I would like to rely on the hardness or negligibility of the following problem or situation, respectively. Note the original motivation: it shall be impossible to find two ...
1
vote
2answers
288 views

Fiat-Shamir paradigm and the forking lemma

I am reading the proof by Pointcheval and Stern and by Bellare and Neven about the forking lemma. The papers discuss the security proof of digital signatures by applying the lemma. It seems also ...
0
votes
2answers
219 views

What characteristics define a function to be a block cipher

I'm trying to understand what characteristics or properties make the result of a function a block cipher. I understand that for a function to be a block cipher it has to be invertible and can't be a ...
0
votes
1answer
243 views

Does hashing a PRNG by a cryptographically secure hashing algorithm result in a CSPRNG?

Or specifically, does ChaCha20 hashing of the xoroshiro128+ random number generator result in a cryptographically secure random number generator?
9
votes
0answers
172 views

How to build a security model

What are the minimal components to build a security model proof for a protocol? This question might seem trivial, but having read many papers-- from the IEEE, ACM, etc., that talk about a KMP-- I ...
5
votes
1answer
298 views

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

I've been playing with some homomorphic encryption libraries. It's given me a greater appreciation for probabilistic encryption. These two answers were instrumental in leading to this question, but ...
4
votes
3answers
310 views

Homomorphic & Functional encryption: Mapping unencrypted outputs to encrypted outputs using existing data

Let's assume I have datapiece A which, after being put through a model or neural network, has a known output X in the unencrypted space. When I move datapiece A into an encrypted space, and put it ...
2
votes
1answer
172 views

BLS hash as a group element exponent?

In BLS short signatures paper, the authors describe a hash function $H\colon\ \{0, 1\}^∗ → G^∗$, where $G$ is a Gap-Diffie-Hellman group. They present a structure where a standard hash is used on a ...
0
votes
1answer
103 views

RSA-FDH and random oracle query count

I am now reading a paper 'The Exact Security of Digital Signatures - How to Sign with RSA and Rabin' and there is an equation e = (q_sig + q_hash) * e' on page 401. (e : success probability of RSA, e' ...
1
vote
0answers
89 views

Optimized Random-OT Security in Standard Model

I was going through the paper - " Efficient Oblivious Transfer and Extensions for Faster Secure Computation" by Asharov et al. where the authors propose an optimized OT protocol along with a Random-OT ...
2
votes
0answers
25 views

Computationally secure ORAMs with O(lg n)-bit words: shouldn't they fail with $n^{-O(1)}$ probability?

Virtually all "hierarchical" Oblivious RAMs use "cryptographically secure" hash functions to determine the position of an item at a given level; and implicitly assume (as can be evinced from the cost ...
0
votes
1answer
141 views

“Random permutation” in the random oracle model?

I'm trying to read through a paper on ring signatures - "How to Leak a Secret" by Rivest, Shamir, Tauman (link: https://link.springer.com/content/pdf/10.1007%2F3-540-45682-1_32.pdf ) In section 3.2 ...
8
votes
1answer
1k views

What is the Common Reference String (CRS) model

I came across the notion of Common Reference String (CRS) model while reading this paper on a protocol for UC Oblivious Transfer: https://eprint.iacr.org/2007/348.pdf I did some research and it seems ...
0
votes
1answer
71 views

Does a concatenation of hashes of differently prefixed variations of any chosen message contain all possible finite bitstrings?

Let $A$ denote a sequence of bits. Let $H$ denote a cryptographic hash function that has no limit on the length of its input (for example, SHA-3). Consider the following infinite sequence of ...
-3
votes
1answer
539 views

Could you list all of the security models in cryptography?

I only know some of security models: rom->crs->std How about others? Or may it be different in several fileds? Thanks.
2
votes
0answers
136 views

Is Lamport-Diffie secure EUF-CMA in standard model

Is Lamport-Diffie signature secure in the standard model?. I make this question because I am reading the Postquantum-Cryptography book and the reductions the authors use one-way functions and not hash ...
1
vote
0answers
78 views

ROM = PRP and Public Random beacon/CRS?

I am trying to understand how different assumptions might relate to each other and if they are absolute different or if they can be reduced to each other. Can the random oracle be substituted with a ...
1
vote
0answers
85 views

Why it is necessary idealized hash functions in Random Oracle Model?

I have reading about how to bring provable security for cryptographic schemes. There are two models: the standard model and the random oracle model. In random oracle model, is necessary to idealize ...
3
votes
0answers
159 views

Weak Challenge Generation - Fiat-Shamir Heuristic

The Fiat-Shamir heuristic may be applied to transform a Sigma-Protocol on R(x,w) into a ZKPoK. Let's call the prover's first message ...
1
vote
1answer
82 views

What is the probability that $(m_1,m_2,m_3)$ is a “cover”-triple for random $m_1,m_2,m_3$?

Let $H: \{0,1\}^*\to \{0,1\}^n$ be the random oracle. A "cover"-triple is a triple $(m_1,m_2,m_3)$ such that $$\bigwedge_{i=1}^n \left( \left(H(m_1)_i=H(m_2)_i\right) \vee \left(H(m_1)_i=H(m_3)_i\...
1
vote
1answer
119 views

Explain Fischlin's Fiat-Shamir like transformation

I've been trying for a while to understand why this paper is correct: ftp://ftp.inf.ethz.ch/pub/crypto/publications/Fischl05b.pdf. The idea is a NIZK-POK where you require the hash of the commit-...
5
votes
2answers
2k views

Prove the Security of Schnorr's Signature Scheme

I know that Schnorr's signature is important since it is one of the most compact signature schemes whose security has been proved in the random oracle model. Now, I want to know if such proof is ...
14
votes
3answers
3k views

Why do Feistel ciphers need round keys?

Looking at the design for Feistel ciphers, they use a list of round keys which are generated from the main key using the key schedule of the associated block cipher. Some block ciphers need this as to ...
1
vote
1answer
49 views

Equivalance Operator - Perfect Secrecy

The equivalance operator is the inverse of the XOR operator, it's symmetric. Would this mean that it would also provide theoretical perfect secrecy just like XOR? XOR ...
2
votes
1answer
146 views

Are quantum preimage attacks on hash-based random oracles serious for lattice signatures?

For most of the lattice-based signature schemes in the hash-based random oracle model (like BLISS), quantum preimage attacks (e.g., Grover's alg) against the random oracle component of the signature ...