Tag Info

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

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

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