# 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.

114 questions
Filter by
Sorted by
Tagged with
1answer
87 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 ...
0answers
33 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 ...
0answers
23 views

### Extractability of random oracle in simulation-based proof

I am working on the simulation-based proof, where Random Oracle (RO) is used to extract malicious parties' input. In particular, the RO considered in the proof has a small range (whose size is ...
3answers
273 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 ...
1answer
440 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 ...
0answers
27 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 ...
0answers
38 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 ...
1answer
40 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 ...
2answers
105 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 ...
0answers
43 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 ...
0answers
58 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)$ ...
1answer
121 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 ...
0answers
51 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 ...
1answer
90 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 ...
1answer
108 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 ...
1answer
129 views

0answers
85 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 ...
2answers
219 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 ...
0answers
55 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 ...
2answers
394 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 ...
2answers
440 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 ...
1answer
297 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?
0answers
186 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 ...
1answer
371 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 ...
3answers
339 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 ...
1answer
187 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 ...
1answer
110 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' ...
0answers
101 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 ...
0answers
27 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 ...
1answer
161 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 ...
1answer
2k 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 ...
1answer
78 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 ...
1answer
639 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.
1answer
162 views

### Is Lamport-Diffie EUF-CMA secure in the standard model?

Is the Lamport-Diffie signature secure in the standard model? I ask this question because I am reading the Postquantum-Cryptography book and the reductions the authors use one-way functions and not ...
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 ...
0answers
89 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 ...
0answers
179 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 ...
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\...
1answer
133 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-...
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 ...