Stack Exchange Network

Stack Exchange network consists of 174 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.

3
votes
2answers
129 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
31 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 ...
0
votes
0answers
28 views

Intuition for CL signatures security

I'm trying to understand why the CL signature scheme (PDF) works only under the strong RSA assumption. Other well known signature schemes like ECDSA, Schnorr and even RSA can be proven secure only in ...
1
vote
1answer
60 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
114 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
0answers
67 views

Oracle version of the IND-PRG game with q queries

Consider the following oracle-based game: $O_0$: Init: $1^n$; Query: output $y \stackrel{u}{\in} \{0,1\}^{l(n)}$ $O_1$: Init: $1^n$; Query: output $G(x)$ with $x \stackrel{u}{\in} \{0,1\}^{n}...
0
votes
1answer
89 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
96 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
174 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
152 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
96 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
0answers
21 views

In PKEET, OW-CCA definition, I can not understand their OW-CCA security model?

Specifically in "Probabilistic Public Key Encryption with Equality Test" article? In the article, OW-CCA definition author shown two decryption queries in random oracle model. On first Queries, ...
0
votes
1answer
45 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
79 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
21 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
54 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 ...
4
votes
1answer
338 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
55 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
184 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.
0
votes
0answers
42 views

Why is the expected number of calls to a random oracle to generate a collision is of the order of 2^(n/2)?

I'm reading this paper on sponge functions where on page 1 the authors state this: https://keccak.team/files/SpongeFunctions.pdf Why is this true?
2
votes
0answers
88 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
43 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
60 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
96 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
79 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
67 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
752 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 ...
13
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
132 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
581 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
311 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
78 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
366 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
221 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
249 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
94 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 $\...
2
votes
1answer
332 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 \...
2
votes
1answer
597 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
85 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
102 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
209 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
232 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
130 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
369 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
221 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
152 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
635 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 ...