13

An interactive or non-interactive protocol is said to be sound for a language $\mathcal{L}$ if it is "hard" for a (malicious) prover $\textsf{P}$ to convince a verifier $\textsf{V}$ of a statement $I\not\in\mathcal{L}$. Depending on how "hard" it actually is for $\textsf{P}$ to cheat, we either get a (interactive or non-interactive) proof ...


4

Does it mean that the input is any length of zeros and ones and that is should hash to a value which is 3000 digits of zeros and ones? Yes, that's the meaning of $\{0,1\}^*→\{0,1\}^{3000}$. It would be better to reformulate using the usual shortcut for "digits of zeros and ones": bits. Also, $\{0,1\}^*$ is the set of all bitstrings. Could I just apply ...


2

As far as I know, the "random oracle game" doesn't exist. What your are speaking (I think) is about pseudo-random functions. And when the challenger (not the oracle) is in the "RANDOM" mode, he could keep in memory the pair input/output, according to previous queries. Then it doesn't need to output "error", he could return the same output as in the previous ...


1

@fgrieu's answer uses a stateful oracle, which I think is cheating a bit. The problem is impossible with stateless oracles (and perfect correctness). Suppose the encryption algorithm is written as $E^{\mathcal O}(pk,m;r)$ where $\mathcal O$ is any stateless oracle; $pk$ is the public key; $m$ is the plaintext; $r$ is the randomness; $E$ is a deterministic ...


1

Yes, it is possible to have perfectly secure public-key cryptography with oracles (though the oracles I'll exhibit do not seem quite reducible to those of the question). As pointed in the question, there can't be a completely public encryption procedure that works (in the sense that decryption is possible with the appropriate secret) and is perfectly secure ...


1

What you're saying is unclear... If you have uncountably many possible keys, if the scheme is computationally secure in the normal case (you're using an already-secure algorithm), your algorithm would fit your definition of being perfectly secure - the computation required to break it goes up with the key size, effectively creating an infinite search time ...


1

First of all, the random oracle is a proof model, and it can not be confused with hash functions, because these last (probably) aren't random; anyway, can be easily distinguished from such: see this Yehuda Lindell's answer. In the proof paradigm in the Random Oracle Model, a protocol $\mathcal{P}$ is first proved to be secure doing access to an oracle ...


1

Answers to your questions: 1) Random oracle - is a replacement for hash-function. Its input is any bitstring, and output - random string. In some sense - it's an ideal hash-function. But in order to evaluate it, you (attacker) need to explicitly ask the oracle. 2) "Why would the adversary query g^ab to the random oracle. Is it part of the game?" - no, ...


1

A core component of Bulletproof is a "range proof". Since Bulletproofs are designed to be used in the blockchain setting, it is important for the range proof to be non-interactive. The one used in Bulletproof is obtained by taking an interactive range proof and then compiling it into a non-interactive one using the Fiat-Shamir transform. The random oracle is ...


1

My question is: given the ability to sample a single bit at random, can't we use that to construct a random oracle? Suppose we want to simulate a random function $H:\{0,1\}^m \rightarrow \{0,1\}^n$. Just sample $n$ bits for the output, and keep a log so that all future queries are consistent. Sure. You could design a signature scheme where there is a ...


1

The main difference (from a cryptographic point of view) is whether the simulator is capable of choosing the answers to the oracle queries or not. In more detail, to prove the simulation-based security of a cryptographic construction in the random oracle model, the simulator is assumed to be able to choose answers for the queries that parties make to the ...


Only top voted, non community-wiki answers of a minimum length are eligible