I am trying to deal with Bulletproof. I can not find confirmation or refutation of the following assumption:

Bulletproof cannot work without the random oracle, which is a necessary part of the protocol.

Thanks in advance for your answers.

  • $\begingroup$ It's unclear what you're asking. Bulletproof are designed and proven in the ROM. What more do you need to know? $\endgroup$
    – Maeher
    Dec 21 '19 at 12:19
  • $\begingroup$ I guess he is asking about the validity of Bulletproof in the standard model. $\endgroup$
    – Binou
    Dec 21 '19 at 13:39
  • $\begingroup$ Where did you encounter this quote/assumption? How is this question different from your other one? $\endgroup$
    – Ella Rose
    Dec 21 '19 at 16:27
  • $\begingroup$ For @Maeher: I would like to know for what purpose the random oracle model in Bulletproof is used, at what stage this is happening and whether the use of the random oracle model is a necessary condition for the operation of Bulletproof. $\endgroup$
    – lfrickel
    Dec 22 '19 at 11:35
  • $\begingroup$ For @Binou: and this too $\endgroup$
    – lfrickel
    Dec 22 '19 at 11:38

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 used to establish the soundness of this transformed protocol. In practice one would instantiate this random oracle with a concrete hash function (say SHA-$3$).

Now, to answer your question whether a random oracle is necessary, it is not clear and is an active line of research. It has been shown that in some cases it is possible to instantiate the Fiat-Shamir transform with concrete hash functions (e.g., the recent construction of NIZK from LWE relies on such an instantiation of the Fiat-Shamir transform [PS19]).

[PS19]: Peikert and Sheihan Non-Interactive Zero Knowledge for NP from (Plain) LWE.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.