Paper 2023/1609

How to Prove Statements Obliviously?

Sanjam Garg, University of California, Berkeley
Aarushi Goel, NTT Research
Mingyuan Wang, University of California, Berkeley

Cryptographic applications often require proving statements about hidden secrets satisfying certain circuit relations. Moreover, these proofs must often be generated obliviously, i.e., without knowledge of the secret. This work presents a new technique called --- FRI on hidden values --- for efficiently proving such statements. This technique enables a polynomial commitment scheme for values hidden inside linearly homomorphic primitives, such as linearly homomorphic encryption, linearly homomorphic commitment, group exponentiation, fully homomorphic encryption, etc. Building on this technique, we obtain the following results. 1. An efficient SNARK for proving the honest evaluation of FHE ciphertexts. This allows for an efficiently verifiable private delegation of computation, where the client only needs to perform logarithmic many FHE computations to verify the correctness of the computation. 2. An efficient approach for privately delegating the computation of zkSNARKs to a single untrusted server, without making any non-black-box use of cryptography. All prior works require multiple servers and the assumption that some subset of the servers are honest. 3. A weighted threshold signature scheme that does not require any setup. In particular, parties may sample their own keys independently, and no distributed key generation (DKG) protocol is needed. Furthermore, the efficiency of our scheme is completely independent of the weights. Prior to this work, there were no known black-box feasibility results for any of these applications. We also investigate the use of this approach in the context of public proof aggregation. These are only a few representative applications that we explore in this paper. We expect our techniques to be widely applicable in many other scenarios.

Available format(s)
Publication info
SNARKFRISecret statementspolynomial commitment
Contact author(s)
sanjamg @ berkeley edu
aarushi goel @ ntt-research com
mingyuan @ berkeley edu
2023-12-18: last of 2 revisions
2023-10-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sanjam Garg and Aarushi Goel and Mingyuan Wang},
      title = {How to Prove Statements Obliviously?},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1609},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.