Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

4
votes
2answers
502 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 ...
2
votes
1answer
52 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
26 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
136 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
42 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
1answer
78 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
122 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
106 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?
6
votes
0answers
105 views

How to build a security model

Probably this question could appear trivial, but when you are building a security protocol (i.e. you can read a lot of papers on IEEE, ACM and so on, that talk about a KMP), most of authors build the ...
5
votes
1answer
195 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
161 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
107 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
54 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
81 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
23 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
57 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 ...
5
votes
1answer
447 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
57 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 ...
-4
votes
1answer
260 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
98 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
48 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
62 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 ...
2
votes
0answers
106 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
80 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
81 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
811 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
44 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 ...
3
votes
1answer
133 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
676 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
356 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 ...
3
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
413 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" ...
3
votes
1answer
228 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
295 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
101 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
355 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
706 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
88 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
77 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 ...
1
vote
0answers
103 views

Why security proof uses random oracles in identity-based encryption?

In identity-based encryption, users decrypt the ciphertext by using private keys. Without private key, no one will be able to decrypt.In security proofs like here, random oracles are used with the ...
3
votes
1answer
223 views

How is a hash function that implements random oracle model collision resistance?

ROM is considered as collision resistance. Does ROM assume there is an infinite set of output, or assume the output set is always larger than the input set? Because by the pigeonhole principle, ROM is ...
-1
votes
1answer
241 views

What is the non-programmable random oracle model?

I would like to know the difference between the random oracle model and the non-programmable random oracle model. ​ What is the difference?
4
votes
1answer
138 views

Padding schemes for asymmetric encryption with provable security in the standard model

Most padding schemes for asymmetric encryption (OAEP, OAEP+) are only proven secure in the random oracle model. Although no attacks are known, it would be nice to find a padding scheme with provable ...
1
vote
1answer
395 views

Differences between OWP and OWF and their IND-CPA security

I am learning about one way permutations and one way functions and am not sure of the differences if there are any. Also in the random oracle model are they both IND-CPA secure?
13
votes
1answer
229 views

Explanation and proof of a well-know probabilistic lemma

Pointcheval and Stern in their paper on "Security proofs for Signature Schemes" state the following "well-known" probabilistic lemma: Let $A \subset X \times Y$, such that $\mathrm{Pr}[A(x, y)] \...
3
votes
0answers
154 views

Unlinkability of Merkle-Damgård hash function results

Question: Are multiple outputs of a Merkle-Damgård hash function (or specifically SHA-256, if this can only be said for a specific algorithm) on unknown data unlinkable? If yes: Can this be formally ...
1
vote
1answer
52 views

Is there any benefit to using a randomly chosen replacement strategy on a string before or after encrypting it?

This is more of a mental exercise for me than anything else. I've thought about doing something like this before, mostly to make a broken cipher a little more difficult to decrypt to plain text. I've ...
6
votes
1answer
646 views

One-Way property of Random Oracle

I'm currently working on a proof in the Random Oracle model, and could not find the formal argument on why the random oracle is one-way (i.e. for an Oracle $O$, it is easy to calculate $x=O(n)$, but ...
1
vote
1answer
83 views

Explanation of protocol secure under random oracle but insecure with any hash fuction

It is known that there is a protocol that is secure in the random oracle model, but where any real hash function makes the protocol insecure. The proof is constructive, but I could not understand the ...