[Resource Topic] 2023/1609: How to Prove Statements Obliviously?

Resource Foundations
#1

Welcome to the resource topic for 2023/1609

Title:
How to Prove Statements Obliviously?

Authors: Sanjam Garg, Aarushi Goel, Mingyuan Wang

Abstract:

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.

ePrint: https://eprint.iacr.org/2023/1609

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .