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
1answer
55 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
98 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
99 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
27 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
93 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
54 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
101 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
27 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, ...
9
votes
4answers
282 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
231 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
526 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
168 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) = ...
0
votes
0answers
49 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
163 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
52 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
217 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
141 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
184 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?
8
votes
0answers
155 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
250 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
238 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 ...
1
vote
1answer
152 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
97 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
83 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
97 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 ...
7
votes
1answer
974 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
66 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
425 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
119 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
76 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
80 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
140 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
103 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
1answer
1k 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
2k 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
45 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
143 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 ...
0
votes
2answers
967 views

Perfect secrecy with XOR & SHIFT?

I have read that XOR provides perfect secrecy, when the key is perfectly random. However it's technically hard to generate truly random numbers, especially on computers, so that is why people use AES, ...
1
vote
1answer
466 views

Why are Random Oracle not achievable in practice?

I am not really sure where I read that, but I have been thought that Random Oracles cannot be used in practice. Then, I stumbled upon this paper that says: "Random Oracles are Practical: Paradigm ...
2
votes
1answer
80 views

How important is the size of the public key (for a given security level)?

I've read about different signature schemes which for the same bits of security differ largely in the size of the public key: The ones proven in the standard oracle model perform worse than the ones ...
0
votes
1answer
508 views

random oracle model vs standard model vs selective model

Can someone clearly outline the main difference between each of the three security models: random oracle model standard model selective model This post What is the "Random Oracle Model" ...
2
votes
1answer
249 views

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

We have an entropy source called “Entropy”. We encode this entropy with HMAC-SHA512 using a “Key”. The Key is public, but the Entropy is secret. We are then testing for the HMAC-SHA512 output in order ...
4
votes
1answer
367 views

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

The Merkle–Damgård construction builds a hash by iterating a compression function $F$, with $S_{j+1}=F(B_j,S_j)$ where $B_j$ is one of $n$ padded message blocks, $S_0$ is the IV, and $S_n$ is the hash....
2
votes
0answers
127 views

Hash function onto a Schnorr group

Let $q$ be a given random prime of $2b$-bit for some security parameter $b$ (say $b=128$); let $p$ be a given much larger random prime with $p=q\cdot r+1$. Let $(G,*)$ be the (Schnorr) subgroup of $\...
3
votes
1answer
501 views

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

From the Linkable Ring Signatures paper: Let $G = \langle g\rangle$ be a cyclic group of prime order $q$ such that the underlying discrete logarithm problem (DLP) is hard. Let $H_1 : {0, 1}^∗ \to \...
3
votes
1answer
969 views

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

On the original paper on Linked Ring Signatures, in order to construct its scheme, the author relies on this: Let $G = \langle g\rangle$ be a cyclic group of prime order $q$ such that the ...
0
votes
1answer
100 views

Independence of answers to queries sent to a random oracle

Assume we have an algorithm which asks random oracle $\mathcal{O}$ $Q$ queries $u_1, \ldots, u_Q$. All queries are unique, $u_i \neq u_j$ for $i \neq j$. Queries $u_i$ are random variables, too. What ...
2
votes
1answer
83 views

Random oracles and independence

I'm reading an unpublished paper in which the author makes the following conclusions several times: Assumptions: finite probability space, $H$ is a random oracle, $X$ and $Y$ are two (not necessarily ...