Skip to main content
SpringerLink
Log in

Pinocchio-Based Adaptive zk-SNARKs and Secure/Correct Adaptive Function Evaluation

  • Conference paper
  • First Online:
Progress in Cryptology - AFRICACRYPT 2017 (AFRICACRYPT 2017)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 10239))

Included in the following conference series:

Abstract

Pinocchio is a practical zk-SNARK that allows a prover to perform cryptographically verifiable computations with verification effort potentially less than performing the computation itself. A recent proposal showed how to make Pinocchio adaptive (or “hash-and-prove”), i.e., to enable proofs with respect to computation-independent commitments. This enables computations to be chosen after the commitments have been produced, and for data to be shared between different computations in a flexible way. Unfortunately, this proposal is not zero-knowledge. In particular, it cannot be combined with Trinocchio, a system in which Pinocchio is outsourced to three workers that do not learn the inputs thanks to multi-party computation (MPC). In this paper, we show how to make Pinocchio adaptive in a zero-knowledge way; apply this to make Trinocchio work on computation-independent commitments; present tooling to easily program flexible verifiable computations (with or without MPC); and use it to build a prototype in a medical research case study.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.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

Notes

  1. 1.

    In practice, computing the hash is complex itself. It can be avoided with bootstrapping [10], giving slightly worse asymptotics and again a large practical overhead.

  2. 2.

    We differ from [10] in three minor ways: (1) we generalise from commitment schemes to families because we need this in Adaptive Trinocchio; (2) we allow witnesses that are not committed to separately, giving a slight efficiency improvement; (3) the extractor has access to the trapdoor, as needed when using Pinocchio [8].

  3. 3.

    In Pinocchio, the linear terms corresponding to \(\mathbf V \), \(\mathbf W \), \(\mathbf Y \) can also contain constant values. This is achieved by assigning special meaning to a “constant” wire with value 1. We do not formalise this separately, instead leaving it up to the user to include a special variable and an equation \(x_i\cdot x_i=x_i\) that forces this variable to be one.

  4. 4.

    We use \(\langle {\alpha _v V}\rangle _2\) etc. instead of \(\langle {\alpha _v V}\rangle _1\) from [13], so that we can rely on the asymmetric q-PKE assumption from [4] (which [13] did not spell out).

  5. 5.

    Hence this construction can only handle inputs of combined size at most d.

  6. 6.

    Using non-reactive MPC requires is also possible, but then steps 3 and 4 of the protocol need to be swapped. As a consequence, data owners can abort based on the client’s choice of function, leading to a weaker form of correct function evaluation.

  7. 7.

    Equivalently, the workers can open \(c_c\) and \(\pi \) and send them to the client in the plain.

References

  1. Backes, M., Barbosa, M., Fiore, D., Reischuk, R.M.: ADSNARK: nearly practical and privacy-preserving proofs on authenticated data. In: Proceedings S&P (2015)

    Google Scholar 

  2. Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: verifying program executions succinctly and in zero knowledge. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 90–108. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40084-1_6

    Chapter  Google Scholar 

  3. Costello, C., Fournet, C., Howell, J., Kohlweiss, M., Kreuter, B., Naehrig, M., Parno, B., Zahur, S.: Geppetto: versatile verifiable computation. In: Proceedings S&P, pp. 253–270 (2015)

    Google Scholar 

  4. Danezis, G., Fournet, C., Groth, J., Kohlweiss, M.: Square span programs with applications to succinct NIZK arguments. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 532–550. Springer, Heidelberg (2014). doi:10.1007/978-3-662-45611-8_28

    Google Scholar 

  5. de Hoogh, S.: Design of large scale applications of secure multiparty computation: secure linear programming. Ph.D. thesis, Eindhoven University of Technology (2012)

    Google Scholar 

  6. de Hoogh, S., Schoenmakers, B., Veeningen, M.: Certificate validation in secure computation and its use in verifiable linear programming. In: Pointcheval, D., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT 2016. LNCS, vol. 9646, pp. 265–284. Springer, Cham (2016). doi:10.1007/978-3-319-31517-1_14

    Chapter  Google Scholar 

  7. Fiore, D., Fournet, C., Ghosh, E., Kohlweiss, M., Ohrimenko, O., Parno, B.: Hash first, argue later: adaptive verifiable computations on outsourced data. In: Proceedings CCS (2016)

    Google Scholar 

  8. 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). doi:10.1007/978-3-642-38348-9_37

    Chapter  Google Scholar 

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

    Chapter  Google Scholar 

  10. Lipmaa, H.: Prover-efficient commit-and-prove zero-knowledge SNARKs. In: Pointcheval, D., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT 2016. LNCS, vol. 9646, pp. 185–206. Springer, Cham (2016). doi:10.1007/978-3-319-31517-1_10

    Chapter  Google Scholar 

  11. Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: Proceedings S&P, pp. 238–252 (2013)

    Google Scholar 

  12. Parno, B.: A note on the unsoundness of vntinyram’s snark. Cryptology ePrint Archive, Report 2015/437 (2015). http://eprint.iacr.org/

  13. Schoenmakers, B., Veeningen, M., Vreede, N.: Trinocchio: privacy-preserving outsourcing by distributed verifiable computation. In: Manulis, M., Sadeghi, A.-R., Schneider, S. (eds.) ACNS 2016. LNCS, vol. 9696, pp. 346–366. Springer, Cham (2016). doi:10.1007/978-3-319-39555-5_19

    Google Scholar 

  14. Veeningen, M.: Pinocchio-based adaptive zk-SNARKS and secure/correct adaptive function evaluation. Cryptology ePrint Archive, Report 2017/013 (2017). http://eprint.iacr.org/2017/013

Download references

Acknowledgements

This work is part of projects that have received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No. 643964 (SUPERCLOUD) and No. 731583 (SODA).

Author information

Authors and Affiliations

  1. Philips Research, Eindhoven, The Netherlands

    Meilof Veeningen

Authors
  1. Meilof Veeningen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Meilof Veeningen .

Editor information

Editors and Affiliations

  1. NXP Semiconductors , San Jose, California, USA

    Marc Joye

  2. University of Caen , Caen, France

    Abderrahmane Nitaj

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Veeningen, M. (2017). Pinocchio-Based Adaptive zk-SNARKs and Secure/Correct Adaptive Function Evaluation. In: Joye, M., Nitaj, A. (eds) Progress in Cryptology - AFRICACRYPT 2017. AFRICACRYPT 2017. Lecture Notes in Computer Science(), vol 10239. Springer, Cham. https://doi.org/10.1007/978-3-319-57339-7_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-57339-7_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-57338-0

  • Online ISBN: 978-3-319-57339-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation