Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

How to Prove Statements Obliviously?

  • Conference paper
  • First Online:
Advances in Cryptology – CRYPTO 2024 (CRYPTO 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14929))

Included in the following conference series:

  • 552 Accesses

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

    An efficient approach for privately delegating the computation of zkSNARKs to a single untrusted server, without requiring the server to make 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. 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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 109.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    If these secrets are available to the prover, then various approaches can help provide efficient constructions, e.g., sigma protocols [Sch90], bulletproofs [BBB+18], etc.

  2. 2.

    For instance, \(\llbracket {m}\rrbracket \) could be a linearly homomorphic encryption of m, a linearly homomorphic commitment of m, group exponentiation (i.e., \(\llbracket {m}\rrbracket =g^m\)), or fully homomorphic encryption of m. We stress that this encapsulation could either be hiding (e.g., encryption/commitment) or not hiding (e.g., group exponentiation).

  3. 3.

    Note that the prover is able to compute this evaluation because of the linear homomorphism of the encapsulation scheme.

  4. 4.

    To be precise, the proof size and verification time is \(O(\log ^2 d\cdot \lambda )\), where \(\lambda \) is the security parameter. Throughout the paper, this \(\lambda \) factor is implicitly assumed in the proof size of all FRI-based SNARKs.

  5. 5.

    Our approach can be combined with any polynomial IOP-based SNARKs. See the full version [GGW23] for more details.

  6. 6.

    It is typically assumed that this pre-processing is done by a trusted party and the verifier only gets oracle access to it. However, one could also imagine the client himself doing this one-time reusable pre-processing.

  7. 7.

    The process of computing zkSNARKs typically starts with the computation of an extended witness. This extended witness can be seen as a computation trace generated by evaluating the relation circuit with the statement and a (short) secret witness as input.

  8. 8.

    Specifically, the server performs \(O(|\mathcal {R}|)\) FHE evaluations (that have the same multiplicative depth as \(\mathcal {R}\)) to generate the extended witness and then \(O(|\mathcal {R}|\cdot \log |\mathcal {R}|)\) additional FHE evaluations with a constant multiplicative depth.

  9. 9.

    That is, the rule that defines which subsets are authorized. For instance, for (unweighted) threshold access structure, subsets are authorized if and only if its cardinality is \(\geqslant t\).

  10. 10.

    That is, given an indicator vector \(B\in {\{0,1\}} ^n\) for a subset \(B\subseteq [n]\), \(C(B)=1\) if and only if B is authorized.

  11. 11.

    In fact, it would be linear in the threshold.

  12. 12.

    The case where both vectors are field vectors does not require pairing. However, this is not the interesting case we consider in this paper. That is, the prover knows all the witnesses in the clear.

  13. 13.

    Since there are no known linear secret sharings with weight-independent secret shares.

  14. 14.

    In more details, party i holding secret key \(\mathsf {\phantom {p}sk}_i\) needs to send \((g^{\mathsf {\phantom {p}sk}_i\cdot \tau },g^{\mathsf {\phantom {p}sk}_i\cdot \tau ^2},\ldots , g^{\mathsf {\phantom {p}sk}_i\cdot \tau ^n})\) as its hint, where \((g^{ \tau },g^{ \tau ^2},\ldots , g^{ \tau ^n})\) is the KZG-style SRS.

  15. 15.

    The committer knows the input x, but the receiver does not.

  16. 16.

    We remark that we slightly abuse notation here and use \(\llbracket {m}\rrbracket \) to denote an encapsulation of m, even when the encapsulation scheme is randomized. In particular, for simplicity of notation, we do not make the randomness explicit in this representation. Looking ahead, whenever relevant, the use of randomness will be made clear in the accompanying text.

  17. 17.

    If instead, the prover starts with domain evaluations of f on domain \(\mathbb {H}\subset \mathbb {F}\), which is a multiplicative subgroup of size \(d+1\), they can use FFT to compute evaluations on the larger domain \(D\). Since FFT is a linear operation, this translation also requires the prover to only perform linear operations on the evaluations on \(\mathbb {H}\).

  18. 18.

    The commitment is sent to the server so that the Fiat-Shamir heuristics will also take it as part of the transcript.

  19. 19.

    A multisignature scheme between n parties allows each party to sample its own key pair and sign messages independently, after which, a succinct aggregated signature can be generated to convince the verifier that all n parties have signed the message. Intuitively, a multisignature scheme is an n-out-of-n threshold signature scheme.

  20. 20.

    In order to prevent the rogue key attack [BDN18], the aggregation of the public keys typically uses a random linear combination \(\textsf{apk}= \prod _i(\mathsf {\phantom {p}pk}_i)^{\alpha _i}\) given by the random oracle \(\alpha _i = \textsf{RO}(\mathsf {\phantom {p}pk}_1,\ldots ,\mathsf {\phantom {p}pk}_n,\mathsf {\phantom {p}pk}_i)\). This can be equivalently treated as each public key \(\mathsf {\phantom {p}pk}_i\) is reset to be \( (\mathsf {\phantom {p}pk}_i)^{\alpha _i}\). For simplicity of presentation, we omit this detail.

  21. 21.

    Typically, in a multisignature scheme, we require all n parties to sign the message. In these cases, the aggregated public key \(\textsf{apk}\) can be precomputed and, hence, the verification is indeed succinct. In our setting, we do not require all parties to sign and will compute \(\textsf{apk}\) on the fly. Most known multisignature schemes [BDN18, MPSW19, NRS21] support such a modification, although the resulting verification is no longer succinct.

  22. 22.

    Note that this is a deterministic process that any party can compute given \((\mathsf {\phantom {p}pk}_1,\ldots ,\mathsf {\phantom {p}pk}_n)\) and \((w_1,\ldots ,w_n)\).

  23. 23.

    Which can be checked as \(B(x)\cdot (1-B(x))\) should be 0 on the information locations.

  24. 24.

    If the LHEncap  scheme is keyless and/or deterministic, then \(\mathcal {K}=\emptyset \) and/or \(\mathcal {R}=\emptyset \), respectively.

  25. 25.

    For instance, the Merkle hash tree-based commitment.

  26. 26.

    Here, we assume the knowledge extractor holds the secret key for LHEncap. This makes sense because in all of our applications, the verifier does hold the secret key.

  27. 27.

    This is a reasonable assumption because, in many target applications, the first layer of FRI is public and generated in the preprocessing phase. For example, in the threshold signature application, the first layer of FRI is the polynomial defined by parties’ public keys. Therefore, in the preprocessing phase, every party can check if the prover’s first message is computed correctly or not. To understand why this assumption is necessary, we refer the readers to the proof.

  28. 28.

    For appropriately chosen parameters, the knowledge soundness error \(\varepsilon \) in Corollary 1 can be made negligible in \(\lambda \).

References

  1. Aranha, D.F., Costache, A., Guimarães, A., Soria-Vazquez, E.: Heliopolis: verifiable computation over homomorphically encrypted data from interactive oracle proofs is practical. Cryptology ePrint Archive, Paper 2023/1949 (2023). https://eprint.iacr.org/2023/1949

  2. Abe, M., Fuchsbauer, G., Groth, J., Haralambiev, K., Ohkubo, M.: Structure-preserving signatures and commitments to group elements. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 209–236. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_12

    Chapter  Google Scholar 

  3. Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017: 24th Conference on Computer and Communications Security, pp. 2087–2104, Dallas, TX, USA, 31 October–2 November 2017. ACM Press (2017). https://doi.org/10.1145/3133956.3134104

  4. Applebaum, B., Ishai, Y., Kushilevitz, E.: From secrecy to soundness: efficient verification via secure computation. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 152–163. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14165-2_14

    Chapter  Google Scholar 

  5. Applebaum, B., Nir, O.: Upslices, downslices, and secret-sharing with complexity of \(1.5^n\). In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part III. LNCS, vol. 12827, pp. 627–655. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_21

    Chapter  Google Scholar 

  6. Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy, pp. 315–334, San Francisco, CA, USA, 21–23 May 2018. IEEE Computer Society Press (2018). https://doi.org/10.1109/SP.2018.00020

  7. Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast Reed-Solomon interactive oracle proofs of proximity. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) ICALP 2018: 45th International Colloquium on Automata, Languages and Programming. LIPIcs, vol. 107, pp. 14:1–14:17, Prague, Czech Republic, 9–13 July 2018. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018). https://doi.org/10.4230/LIPIcs.ICALP.2018.14

  8. Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C.: Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part II. LNCS, vol. 9666, pp. 327–357. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_12

    Chapter  Google Scholar 

  9. Bitansky, N., et al.: The hunting of the SNARK. J. Cryptol. 30(4), 989–1066 (2017). https://doi.org/10.1007/s00145-016-9241-9

  10. Bois, A., Cascudo, I., Fiore, D., Kim, D.: Flexible and efficient verifiable computation on encrypted data. In: Garay, J.A. (ed.) PKC 2021, Part II. LNCS, vol. 12711, pp. 528–558. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-75248-4_19

    Chapter  Google Scholar 

  11. Ben-Sasson, E., et a.: Zerocash: decentralized anonymous payments from bitcoin. In: 2014 IEEE Symposium on Security and Privacy, pp. 459–474, Berkeley, CA, USA, 18–21 May 2014. IEEE Computer Society Press (2014). https://doi.org/10.1109/SP.2014.36

  12. Bootle, J., Cerulli, A., Ghadafi, E., Groth, J., Hajiabadi, M., Jakobsen, S.K.: Linear-time zero-knowledge proofs for arithmetic circuit satisfiability. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part III. LNCS, vol. 10626, pp. 336–365. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70700-6_12

    Chapter  Google Scholar 

  13. Bootle, J., Cerulli, A., Groth, J., Jakobsen, S., Maller, M.: Arya: nearly linear-time zero-knowledge proofs for correct program execution. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part I. LNCS, vol. 11272, pp. 595–626. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03326-2_20

    Chapter  Google Scholar 

  14. Bootle, J., Chiesa, A., Groth, J.: Linear-time arguments with sublinear verification from tensor codes. In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part II. LNCS, vol. 12551, pp. 19–46. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64378-2_2

    Chapter  Google Scholar 

  15. Bowe, S., Chiesa, A., Green, M., Miers, I., Mishra, P., Wu, H.: ZEXE: enabling decentralized private computation. In: 2020 IEEE Symposium on Security and Privacy, pp. 947–964, San Francisco, CA, USA, 18–21 May 2020. IEEE Computer Society Press (2020). https://doi.org/10.1109/SP40000.2020.00050

  16. Ben-Sasson, E., Carmon, D., Ishai, Y., Kopparty, S., Saraf, S.: Proximity gaps for Reed-Solomon codes. In: 61st Annual Symposium on Foundations of Computer Science, pp. 900–909, Durham, NC, USA, 16–19 November 2020. IEEE Computer Society Press (2020). https://doi.org/10.1109/FOCS46700.2020.00088

  17. Ben-Sasson, E., Carmon, D., Kopparty, S., Levit, D.: Scalable and transparent proofs over all large fields, via elliptic curves - (ECFFT part II). In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC 2022, Part I. LNCS, vol. 13747, pp. 467–496. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22318-1_17

    Chapter  Google Scholar 

  18. Ben-Sasson, E., Carmon, D., Kopparty, S., Levit, D.: Elliptic curve fast Fourier transform (ECFFT) part I: low-degree extension in time O(n log n) over all finite fields. In: Bansal, N., Nagarajan, V. (eds.) Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms. SODA 2023, Florence, Italy, 22–25 January 2023, pp. 700–737. SIAM (2023). https://doi.org/10.1137/1.9781611977554.ch30

  19. Bootle, J., Chiesa, A., Liu, S.: Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part II. LNCS, vol. 13276, pp. 275–304. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-07085-3_10

    Chapter  Google Scholar 

  20. Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 31–60. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53644-5_2

    Chapter  Google Scholar 

  21. Boneh, D., Drijvers, M., Neven, G.: Compact multi-signatures for smaller blockchains. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11273, pp. 435–464. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_15

    Chapter  Google Scholar 

  22. Baird, L., et al.: Threshold signatures in the multiverse. In: 44th IEEE Symposium on Security and Privacy. SP 2023, San Francisco, CA, USA, 21–25 May 2023, pp. 1454–1470. IEEE (2023)

    Google Scholar 

  23. Block, A.R., Garreta, A., Katz, J., Thaler, J., Tiwari, P.R., Zając, M.: Fiat-Shamir security of FRI and related snarks. In: ASIACRYPT 2023 (2023). https://eprint.iacr.org/2023/1071

  24. Ben-Sasson, E., Goldberg, L., Kopparty, S., Saraf, S.: DEEP-FRI: sampling outside the box improves soundness. In: Vidick, T. (ed.) ITCS 2020: 11th Innovations in Theoretical Computer Science Conference, vol. 151, pp. 5:1–5:32, Seattle, WA, USA, 12–14 January 2020. LIPIcs (2020). https://doi.org/10.4230/LIPIcs.ITCS.2020.5

  25. Benabbas, S., Gennaro, R., Vahlis, Y.: Verifiable delegation of computation over large datasets. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 111–131. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_7

    Chapter  Google Scholar 

  26. Benhamouda, F., Halevi, S.: Stambler, L.: Weighted secret sharing from wiretap channels. In: ITC 2023 (2023). https://eprint.iacr.org/2022/1578

  27. Bhadauria, R., Hazay, C., Venkitasubramaniam, M., Wu, W., Zhang, Y.: Private polynomial commitments and applications to MPC. In: PKC 2023 (2023). https://eprint.iacr.org/2023/680

  28. Boneh, D., Lynn, B., Shacham, H.: Short signatures from the weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1_30

    Chapter  Google Scholar 

  29. Bünz, B., Maller, M., Mishra, P., Tyagi, N., Vesely, P.: Proofs for inner pairing products and applications. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13092, pp. 65–97. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92078-4_3

    Chapter  Google Scholar 

  30. Boldyreva, A.: Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 31–46. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36288-6_3

    Chapter  Google Scholar 

  31. Chen, B., Bünz, B., Boneh, D., Zhang, Z.: HyperPlonk: plonk with linear-time prover and high-degree custom gates. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part II. LNCS, vol. 14005, pp. 499–530. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30617-4_17

    Chapter  Google Scholar 

  32. Canetti, R., Chen, Y., Holmgren, J., Lombardi, A., Rothblum, G.N., Rothblum, R.D., Wichs, D.: Fiat-Shamir: from practice to theory. In: Charikar, M., Cohen, E. (eds.) 51st Annual ACM Symposium on Theory of Computing, pp. 1082–1090, Phoenix, AZ, USA, 23–26 June 2019. ACM Press (2019). https://doi.org/10.1145/3313276.3316380

  33. Chiesa, A., Hu, Y., Maller, M., Mishra, P., Vesely, N., Ward, N.: Marlin: preprocessing zkSNARKs with universal and updatable SRS. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 738–768. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_26

    Chapter  Google Scholar 

  34. Chaidos, P., Kiayias, A.: Mithril: stake-based threshold multisignatures. Cryptology ePrint Archive, Report 2021/916 (2021). https://eprint.iacr.org/2021/916

  35. Chung, K.-M., Kalai, Y., Vadhan, S.: Improved delegation of computation using fully homomorphic encryption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 483–501. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_26

    Chapter  Google Scholar 

  36. Chiesa, A., Lehmkuhl, R., Mishra, P., Zhang, Y.: Eos: efficient private delegation of zkSNARK provers. In: 32nd USENIX Security Symposium (USENIX Security 23), pp. 6453–6469, Anaheim, CA, August 2023. USENIX Association (2023). https://www.usenix.org/conference/usenixsecurity23/presentation/chiesa

  37. Chiesa, A., Ojha, D., Spooner, N.: Fractal: post-quantum and transparent recursive proofs from holography. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 769–793. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_27

    Chapter  Google Scholar 

  38. Das, S., Camacho, P., Xiang, Z., Nieto, J., Bunz, B., Ren, L.: Threshold signatures from inner product argument: succinct, weighted, and multi-threshold. In: CCS 2023 (2023). https://eprint.iacr.org/2023/598

  39. Das, S., Yurek, T., Xiang, Z., Miller, A.K., Kokoris-Kogias, L., Ren, L.: Practical asynchronous distributed key generation. In: 2022 IEEE Symposium on Security and Privacy, pp. 2518–2534, San Francisco, CA, USA, 22–26 May 2022. IEEE Computer Society Press (2022). https://doi.org/10.1109/SP46214.2022.9833584

  40. ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO’84. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1984). https://doi.org/10.1007/3-540-39568-7_2

    Chapter  Google Scholar 

  41. Fiore, D., Gennaro, R., Pastro, V.: Efficiently verifiable computation on encrypted data. In: Ahn, G.-J., Yung, M., Li, N., (eds.) ACM CCS 2014: 21st Conference on Computer and Communications Security, pp. 844–855, Scottsdale, AZ, USA, 3–7 November 2014. ACM Press (2014). https://doi.org/10.1145/2660267.2660366

  42. Fiore, D., Nitulescu, A., Pointcheval, D.: Boosting verifiable computation on encrypted data. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020. LNCS, vol. 12111, pp. 124–154. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45388-6_5

    Chapter  Google Scholar 

  43. Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12

    Chapter  Google Scholar 

  44. Gentry, C., Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st Annual ACM Symposium on Theory of Computing, pp. 169–178, Bethesda, MD, USA, 31 May–2 June 2009. ACM Press (2009). https://doi.org/10.1145/1536414.1536440

  45. Garg, S., Goel, A., Jain, A., Policharla, G.-V., Sekar, S.: zkSaaS: Zero-knowledge SNARKs as a service. In: 32nd USENIX Security Symposium (USENIX Security 23), pp. 4427–4444, Anaheim, CA, 2023 August .USENIX Association (2023). https://www.usenix.org/conference/usenixsecurity23/presentation/garg

  46. Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465–482. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_25

    Chapter  Google Scholar 

  47. Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_37

    Chapter  Google Scholar 

  48. Garg, S., Goel, A., Wang, M.: How to prove statements obliviously? IACR Cryptology ePrint Archive, p. 1609 (2023). https://eprint.iacr.org/2023/1609

  49. Green, M., Hall-Andersen, M., Hennenfent, E., Kaptchuk, G., Perez, B., Van Laer, G.: Efficient proofs of software exploitability for real-world processors. Proc. Privacy Enhanc. Technol. 2023(1), 627–640 (2023). https://doi.org/10.56553/popets-2023-0036

    Article  Google Scholar 

  50. Gentry, C., Halevi, S., Lyubashevsky, V.: Practical non-interactive publicly verifiable secret sharing with thousands of parties. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part I. LNCS, vol. 13275, pp. 458–487. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-06944-4_16

    Chapter  Google Scholar 

  51. Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure distributed key generation for discrete-log based cryptosystems. J. Cryptol. 20(1), 51–83 (2007). https://doi.org/10.1007/s00145-006-0347-3

    Article  MathSciNet  Google Scholar 

  52. Garg, S., Jain, A., Mukherjee, P., Sinha, R., Wang, M., Zhang, Y.: Cryptography with weights: MPC, encryption and signatures. In: CRYPTO 2023 (2023). https://eprint.iacr.org/2022/1632

  53. Garg, S., Jain, A., Mukherjee, P., Sinha, R., Wang, M., Zhang, Y.: hints: Threshold signatures with silent setup. In: IEEE S &P 2024 (2024). https://eprint.iacr.org/2023/567

  54. Golovnev, A., Lee, J., Setty, S., Thaler, J., Wahby, R.S.: Brakedown: linear-time and post-quantum SNARKs for R1CS. Cryptology ePrint Archive, Report 2021/1043 (2021). https://eprint.iacr.org/2021/1043

  55. Groth, J.: Short pairing-based non-interactive zero-knowledge arguments. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 321–340. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_19

  56. Groth, J.: On the size of pairing-based non-interactive arguments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part II. LNCS, vol. 9666, pp. 305–326. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_11

    Chapter  Google Scholar 

  57. Groth, J.: Non-interactive distributed key generation and key resharing. Cryptology ePrint Archive, Report 2021/339 (2021). https://eprint.iacr.org/2021/339

  58. Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_5

    Chapter  Google Scholar 

  59. Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th Annual ACM Symposium on Theory of Computing, pp. 469–477, Portland, OR, USA, 14–17 June 2015. ACM Press (2015). https://doi.org/10.1145/2746539.2746576

  60. Gabizon, A., Williamson, Z.J., Ciobotaru, O.: PLONK: permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive, Report 2019/953 (2019). https://eprint.iacr.org/2019/953

  61. Haböck, U.: A summary on the FRI low degree test. Cryptology ePrint Archive, Report 2022/1216 (2022). https://eprint.iacr.org/2022/1216

  62. Kalodner, H.A., Goldfeder, S., Chen, X., Weinberg, S.M., Felten, E.W.: Arbitrum: scalable, private smart contracts. In: Enck, W., Felt, A.P. (eds.) USENIX Security 2018: 27th USENIX Security Symposium, pp. 1353–1370, Baltimore, MD, USA, 15–17 August 2018. USENIX Association (2018)

    Google Scholar 

  63. Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: 24th Annual ACM Symposium on Theory of Computing, pp. 723–732, Victoria, BC, Canada, 4–6 May 1992. ACM Press (1992). https://doi.org/10.1145/129712.129782

  64. Kothapalli, A., Masserova, E., Parno, B.: A direct construction for asymptotically optimal zkSNARKs. Cryptology ePrint Archive, Report 2020/1318 (2020). https://eprint.iacr.org/2020/1318

  65. Kokoris-Kogias, E., Malkhi, D., Spiegelman, A.: Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures. In: Ligatti, J., Ou, X., Katz, J., Vigna, G.: (eds.) ACM CCS 2020: 27th Conference on Computer and Communications Security, pp. 1751–1767, Virtual Event, USA, 9–13 November 2020. ACM Press (2020). https://doi.org/10.1145/3372297.3423364

  66. Kattis, A.A., Panarin, K., Vlasov, A.: RedShift: transparent SNARKs from list polynomial commitments. In: Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) ACM CCS 2022: 29th Conference on Computer and Communications Security, pp. 1725–1737, Los Angeles, CA, USA, 7–11 November 2022. ACM Press (2022). https://doi.org/10.1145/3548606.3560657

  67. Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 177–194. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_11

    Chapter  Google Scholar 

  68. Lee, J.: Dory: efficient, transparent arguments for generalised inner products and polynomial commitments. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13043, pp. 1–34. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90453-1_1

    Chapter  Google Scholar 

  69. Micali, S.: CS proofs (extended abstracts). In: 35th Annual Symposium on Foundations of Computer Science, pp. 436–453, Santa Fe, NM, USA, 20–22 November 1994. IEEE Computer Society Press (1994). https://doi.org/10.1109/SFCS.1994.365746

  70. Maxwell, G., Poelstra, A., Seurin, Y., Wuille, P.: Simple Schnorr multi-signatures with applications to bitcoin. Des. Codes Cryptogr. 87(9), 2139–2164 (2019)

    Article  MathSciNet  Google Scholar 

  71. Micali, S., Reyzin, L., Vlachos, G., Wahby, R.S., Zeldovich, N.: Compact certificates of collective knowledge. In: 2021 IEEE Symposium on Security and Privacy, pp. 626–641, San Francisco, CA, USA, 24–27 May 2021. IEEE Computer Society Press (2021). https://doi.org/10.1109/SP40001.2021.00096

  72. Nick, J., Ruffing, T., Seurin, Y.: MuSig2: simple two-round Schnorr multi-signatures. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12825, pp. 189–221. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_8

    Chapter  Google Scholar 

  73. Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_16

    Chapter  Google Scholar 

  74. Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_9

    Chapter  Google Scholar 

  75. Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: 2013 IEEE Symposium on Security and Privacy, pp. 238–252, Berkeley, CA, USA, 19–22 May 2013. IEEE Computer Society Press (2013). https://doi.org/10.1109/SP.2013.47

  76. Plonky2 (2021). https://github.com/mir-protocol/plonky2

  77. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th Annual ACM Symposium on Theory of Computing, pp. 84–93, Baltimore, MA, USA, 22–24 May 2005. ACM Press (2005). https://doi.org/10.1145/1060590.1060603

  78. Rathee, D., Policharla, G.V., Xie, T., Cottone, R., Song, D.: Zebra: anonymous credentials with practical on-chain verification and applications to KYC in DEFI. Cryptology ePrint Archive, Paper 2022/1286 (2022). https://eprint.iacr.org/2022/1286

  79. Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, New York (1990). https://doi.org/10.1007/0-387-34805-0_22

    Chapter  Google Scholar 

  80. Setty, S.: Spartan: efficient and general-purpose zkSNARKs without trusted setup. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 704–737. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_25

    Chapter  Google Scholar 

  81. Shamir, A.: How to share a secret. Commun. Assoc. Comput. Mach. 22(11), 612–613 (1979)

    MathSciNet  Google Scholar 

  82. Tomescu, A., et al.: Towards scalable threshold cryptosystems. In: 2020 IEEE Symposium on Security and Privacy, pp. 877–893, San Francisco, CA, USA, 18–21 May 2020. IEEE Computer Society Press (2020). https://doi.org/10.1109/SP40000.2020.00059

  83. Wu, H., Zheng, W., Chiesa, A., Popa, R.A., Stoica, I.: DIZK: a distributed zero knowledge proof system. In: Enck, W., Felt, A.P. (eds.) USENIX Security 2018: 27th USENIX Security Symposium, pp. 675–692, Baltimore, MD, USA, 15–17 August 2018. USENIX Association (2018)

    Google Scholar 

  84. Xie, T., Zhang, Y., Song, D.: Orion: zero knowledge proof with linear prover time. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part IV. LNCS, vol. 13510, pp. 299–328. Springer, Cham. (2022). https://doi.org/10.1007/978-3-031-15985-5_11

    Chapter  Google Scholar 

  85. Xie, T., Zhang, J., Zhang, Y., Papamanthou, C., Song, D.: Libra: succinct zero-knowledge proofs with optimal prover computation. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part III. LNCS, vol. 11694, pp. 733–764. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_24

    Chapter  Google Scholar 

  86. Zhang, J., Fang, Z., Zhang, Y., Song, D.: Zero knowledge proofs for decision tree predictions and accuracy. In: Ligatti, J., Ou, X., Katz, J., Vigna, G. (eds.) ACM CCS 2020: 27th Conference on Computer and Communications Security, pp. 2039–2053, Virtual Event, USA, 9–13 November 2020. ACM Press (2020). https://doi.org/10.1145/3372297.3417278

  87. ZkRollups. An incomplete guide to rollups (2021). https://vitalik.ca/general/2021/01/05/rollup.html

  88. Zhang, J., et al.: Doubly efficient interactive proofs for general arithmetic circuits with linear prover time. In: Vigna, G., Shi, E. (eds.) ACM CCS 2021: 28th Conference on Computer and Communications Security, pp. 159–177, Virtual Event, Republic of Korea, 15–19 November 2021. ACM Press (2021). https://doi.org/10.1145/3460120.3484767

Download references

Acknowledgement

The authors would like to thank Dario Fiore, Ignacio Cascudo, Daniele Cozzo, and Paola de Perthuis for useful discussions on the security of verifying FHE delegation and also for bringing several related works to our attention. The authors would also like to thank Jiayi Kang and Frederik Vercauteren for their assistance in addressing an issue in the zkSNARK delegation protocol in a previous draft of this paper. The first and third authors are supported in part by DARPA under Agreement No. HR00112020026, AFOSR Award FA9550-19-1-0200, NSF CNS Award 1936826, and research grants by Visa Inc, BAIR Commons Meta Fund, Stellar Development Foundation, and a Bakar Fellows Spark Award.

Author information

Authors and Affiliations

  1. University of California, Berkeley, Berkeley, USA

    Sanjam Garg & Mingyuan Wang

  2. NTT Research, Sunnyvale, USA

    Aarushi Goel

Authors
  1. Sanjam Garg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Aarushi Goel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mingyuan Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Aarushi Goel .

Editor information

Editors and Affiliations

  1. Boston University, Boston, MA, USA

    Leonid Reyzin

  2. University of Waterloo, Waterloo, ON, Canada

    Douglas Stebila

Rights and permissions

Reprints and permissions

Copyright information

© 2024 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Garg, S., Goel, A., Wang, M. (2024). How to Prove Statements Obliviously?. In: Reyzin, L., Stebila, D. (eds) Advances in Cryptology – CRYPTO 2024. CRYPTO 2024. Lecture Notes in Computer Science, vol 14929. Springer, Cham. https://doi.org/10.1007/978-3-031-68403-6_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-68403-6_14

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-68402-9

  • Online ISBN: 978-3-031-68403-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation