How to Make Rational Arguments Practical and Extractable

Matteo Campanelli; Chaya Ganesh; Rosario Gennaro

doi:10.62056/a63zl86bm

How to Make Rational Arguments Practical and Extractable

Authors

Matteo Campanelli, Chaya Ganesh, Rosario Gennaro

Matteo Campanelli

Protocol Labs, United States
matteo dot campanelli at gmail dot com

Chaya Ganesh

Indian Institute of Science, India
chaya at iisc dot ac dot in

Rosario Gennaro

The City University of New York, United States
rosario at ccny dot cuny dot edu

Abstract

We investigate proof systems where security holds against rational parties instead of malicious ones. Our starting point is the notion of rational arguments, a variant of rational proofs (Azar and Micali, STOC 2012) where security holds against rational adversaries that are also computationally bounded.

Rational arguments are an interesting primitive because they generally allow for very efficient protocols, and in particular sublinear verification (i.e. where the Verifier does not have to read the entire input). In this paper we aim at narrowing the gap between literature on rational schemes and real world applications. Our contribution is two-fold.

We provide the first construction of rational arguments for the class of polynomial computations that is practical (i.e., it can be applied to real-world computations on reasonably common hardware) and with logarithmic communication. Techniques-wise, we obtain this result through a compiler from information-theoretic protocols and rational proofs for polynomial evaluation. The latter could be of independent interest.

As a second contribution, we propose a new notion of extractability for rational arguments. Through this notion we can obtain arguments where knowledge of a witness is incentivized (rather than incentivizing mere soundness). We show how our aforementioned compiler can also be applied to obtain efficient extractable rational arguments for $\mathsf{NP}$.

References

[ABC⁺22]

Diego F. Aranha, Emil Madsen Bennedsen, Matteo Campanelli, Chaya Ganesh, Claudio Orlandi, and Akira Takahashi. ECLIPSE: enhanced compiling method for pedersen-committed zkSNARK engines. In Goichiro Hanaoka, Junji Shikata, and Yohei Watanabe, editors, PKC 2022, Part I, volume 13177 of LNCS, 584–614. March 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-97121-2_21.

Google Scholar ePrint

[AM12]

Pablo Daniel Azar and Silvio Micali. Rational proofs. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, 1017–1028. ACM, 2012. https://doi.org/10.1145/2213977.2214069.

Google Scholar ePrint

[AM13]

Pablo Daniel Azar and Silvio Micali. Super-efficient rational proofs. In Michael J. Kearns, R. Preston McAfee, and Éva Tardos, editors, Proceedings of the fourteenth ACM Conference on Electronic Commerce, EC 2013, Philadelphia, PA, USA, June 16-20, 2013, 29–30. ACM, 2013. https://doi.org/10.1145/2492002.2482561.

Google Scholar ePrint

[BCG⁺13]

Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. SNARKs for C: verifying program executions succinctly and in zero knowledge. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, 90–108. August 2013. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-40084-1_6.

Google Scholar ePrint

[BEJ⁺09]

Adam L. Beberg, Daniel L. Ensign, Guha Jayachandran, Siraj Khaliq, and Vijay S. Pande. Folding@home: lessons from eight years of volunteer distributed computing. In 23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2009, Rome, Italy, May 23-29, 2009, 1–8. IEEE, 2009. https://doi.org/10.1109/IPDPS.2009.5160922.

Google Scholar ePrint

[BFS20]

Benedikt Bünz, Ben Fisch, and Alan Szepieniec. Transparent SNARKs from DARK compilers. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, 677–706. May 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-45721-1_24.

Google Scholar ePrint

[CFF⁺21]

Matteo Campanelli, Antonio Faonio, Dario Fiore, Anaïs Querol, and Hadrián Rodríguez. Lunar: A toolbox for more efficient universal and updatable zkSNARKs and commit-and-prove extensions. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part III, volume 13092 of LNCS, 3–33. December 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-92078-4_1.

Google Scholar ePrint

[CFK22]

Matteo Campanelli, Dario Fiore, and Hamidreza Khoshakhlagh. Witness encryption for succinct functional commitments and applications. 2022.

Google Scholar ePrint

[CFQ19]

Matteo Campanelli, Dario Fiore, and Anaïs Querol. LegoSNARK: modular design and composition of succinct zero-knowledge proofs. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, 2075–2092. November 2019. ACM Press. https://doi.org/10.1145/3319535.3339820.

Google Scholar ePrint

[CG15]

Matteo Campanelli and Rosario Gennaro. Sequentially composable rational proofs. In M. H. R. Khouzani, Emmanouil A. Panaousis, and George Theodorakopoulos, editors, Decision and Game Theory for Security - 6th International Conference, GameSec 2015, London, UK, November 4-5, 2015, Proceedings, volume 9406 of Lecture Notes in Computer Science, 270–288. Springer, 2015. https://doi.org/10.1007/978-3-319-25594-1_15.

Google Scholar ePrint

[CG17]

Matteo Campanelli and Rosario Gennaro. Efficient rational proofs for space bounded computations. In Stefan Rass, Bo An, Christopher Kiekintveld, Fei Fang, and Stefan Schauer, editors, Decision and Game Theory for Security - 8th International Conference, GameSec 2017, Vienna, Austria, October 23-25, 2017, Proceedings, volume 10575 of Lecture Notes in Computer Science, 53–73. Springer, 2017. https://doi.org/10.1007/978-3-319-68711-7_4.

Google Scholar ePrint

[CG18]

Matteo Campanelli and Rosario Gennaro. Fine-grained secure computation. In Amos Beimel and Stefan Dziembowski, editors, TCC 2018, Part II, volume 11240 of LNCS, 66–97. November 2018. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-03810-6_3.

Google Scholar ePrint

[CGG⁺23a]

Matteo Campanelli, Nicolas Gailly, Rosario Gennaro, Philipp Jovanovic, Mara Mihali, and Justin Thaler. Sftestudo: linear time prover snarks with constant size proofs and square root size universal setup. In Abdelrahaman Aly and Mehdi Tibouchi, editors, Progress in Cryptology - LATINCRYPT 2023 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Quito, Ecuador, October 3-6, 2023, Proceedings, volume 14168 of Lecture Notes in Computer Science, 331–351. Springer, 2023. https://doi.org/10.1007/978-3-031-44469-2_17.

Google Scholar ePrint

[CGG23b]

Matteo Campanelli, Chaya Ganesh, and Rosario Gennaro. How to make rational arguments practical and extractable. 2023.

Google Scholar ePrint

[CHM⁺20]

Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, and Nicholas P. Ward. Marlin: preprocessing zkSNARKs with universal and updatable SRS. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, 738–768. May 2020. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-45721-1_26.

Google Scholar ePrint

[ECK⁺23]

Jens Ernstberger, Stefanos Chaliasos, George Kadianakis, Sebastian Steinhorst, Philipp Jovanovic, Arthur Gervais, Benjamin Livshits, and Michele Orrù. Zk-bench: a toolset for comparative evaluation and performance benchmarking of snarks. 2023.

Google Scholar ePrint

[FFG⁺16]

Dario Fiore, Cédric Fournet, Esha Ghosh, Markulf Kohlweiss, Olga Ohrimenko, and Bryan Parno. Hash first, argue later: adaptive verifiable computations on outsourced data. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, 1304–1316. October 2016. ACM Press. https://doi.org/10.1145/2976749.2978368.

Google Scholar ePrint

[FKL18]

Georg Fuchsbauer, Eike Kiltz, and Julian Loss. The algebraic group model and its applications. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part II, volume 10992 of LNCS, 33–62. August 2018. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-96881-0_2.

Google Scholar ePrint

[GGPR13]

Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, 626–645. May 2013. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-38348-9_37.

Google Scholar ePrint

[GGSW13]

Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters. Witness encryption and its applications. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, 467–476. June 2013. ACM Press. https://doi.org/10.1145/2488608.2488667.

Google Scholar ePrint

[GHRV14]

Siyao Guo, Pavel Hubácek, Alon Rosen, and Margarita Vald. Rational arguments: single round delegation with sublinear verification. In Moni Naor, editor, ITCS 2014, 523–540. January 2014. ACM. https://doi.org/10.1145/2554797.2554845.

Google Scholar ePrint

[GHRV16]

Siyao Guo, Pavel Hubácek, Alon Rosen, and Margarita Vald. Rational sumchecks. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A, Part II, volume 9563 of LNCS, 319–351. January 2016. Springer, Heidelberg. https://doi.org/10.1007/978-3-662-49099-0_12.

Google Scholar ePrint

[Gro16]

Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, 305–326. May 2016. Springer, Heidelberg. https://doi.org/10.1007/978-3-662-49896-5_11.

Google Scholar ePrint

[GWC19]

Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. 2019.

Google Scholar ePrint

[KPV22]

Assimakis A. Kattis, Konstantin Panarin, and Alexander Vlasov. RedShift: transparent SNARKs from list polynomial commitments. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, ACM CCS 2022, 1725–1737. November 2022. ACM Press. https://doi.org/10.1145/3548606.3560657.

Google Scholar ePrint

[KRR14]

Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. How to delegate computations: the power of no-signaling proofs. In David B. Shmoys, editor, 46th ACM STOC, 485–494. May / June 2014. ACM Press. https://doi.org/10.1145/2591796.2591809.

Google Scholar ePrint

[KWA⁺01]

Eric Korpela, Dan Werthimer, David P. Anderson, Jeff Cobb, and Matt Lebofsky. Seti@home-massively distributed computing for SETI. Comput. Sci. Eng., 3(1):78–83, 2001. https://doi.org/10.1109/5992.895191.

Google Scholar ePrint

[KZG10]

Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. In Masayuki Abe, editor, ASIACRYPT 2010, volume 6477 of LNCS, 177–194. December 2010. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-17373-8_11.

Google Scholar ePrint

[Lee21]

Jonathan Lee. Dory: efficient, transparent arguments for generalised inner products and polynomial commitments. In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part II, volume 13043 of LNCS, 1–34. November 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-90453-1_1.

Google Scholar ePrint

[LSTW21]

Jonathan Lee, Srinath Setty, Justin Thaler, and Riad Wahby. Linear-time and post-quantum zero-knowledge SNARKs for R1CS. 2021.

Google Scholar ePrint

[MBKM19]

Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: zero-knowledge SNARKs from linear-size universal and updatable structured reference strings. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, 2111–2128. November 2019. ACM Press. https://doi.org/10.1145/3319535.3339817.

Google Scholar ePrint

[RVW13]

Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson. Interactive proofs of proximity: delegating computation in sublinear time. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, 793–802. June 2013. ACM Press. https://doi.org/10.1145/2488608.2488709.

Google Scholar ePrint

[RZ21]

Carla Ràfols and Arantxa Zapico. An algebraic framework for universal and updatable SNARKs. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, 774–804. Virtual Event, August 2021. Springer, Heidelberg. https://doi.org/10.1007/978-3-030-84242-0_27.

Google Scholar ePrint

[WTs⁺18]

Riad S. Wahby, Ioanna Tzialla, abhi shelat, Justin Thaler, and Michael Walfish. Doubly-efficient zkSNARKs without trusted setup. In 2018 IEEE Symposium on Security and Privacy, 926–943. May 2018. IEEE Computer Society Press. https://doi.org/10.1109/SP.2018.00060.

Google Scholar ePrint

[WYX⁺21]

Chenkai Weng, Kang Yang, Xiang Xie, Jonathan Katz, and Xiao Wang. Mystique: efficient conversions for zero-knowledge proofs with applications to machine learning. In Michael D. Bailey and Rachel Greenstadt, editors, 30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021, 501–518. USENIX Association, 2021.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a63zl86bm

History

Submitted: 2024-01-08
Accepted: 2024-03-05
Published: 2024-04-09

How to cite

Matteo Campanelli, Chaya Ganesh, and Rosario Gennaro, "How to Make Rational Arguments Practical and Extractable," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a63zl86bm.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-1-19,
    author = "Campanelli, Matteo and Ganesh, Chaya and Gennaro, Rosario",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "How to Make Rational Arguments Practical and Extractable",
    volume = "1",
    number = "1",
    date = "2024-04-09",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/a63zl86bm"
}

TY - JOUR
AU - Campanelli, Matteo
AU - Ganesh, Chaya
AU - Gennaro, Rosario
PY - 2024
TI - How to Make Rational Arguments Practical and Extractable
JF - IACR Communications in Cryptology
JA - CIC
VL - 1
IS - 1
DO - 10.62056/a63zl86bm
UR - https://doi.org/10.62056/a63zl86bm
AB - We investigate proof systems where security holds against rational parties instead of malicious ones. Our starting point is the notion of rational arguments, a variant of rational proofs (Azar and Micali, STOC 2012) where security holds against rational adversaries that are also computationally bounded.Rational arguments are an interesting primitive because they generally allow for very efficient protocols, and in particular sublinear verification (i.e. where the Verifier does not have to read the entire input). In this paper we aim at narrowing the gap between literature on rational schemes and real world applications. Our contribution is two-fold.We provide the first construction of rational arguments for the class of polynomial computations that is practical (i.e., it can be applied to real-world computations on reasonably common hardware) and with logarithmic communication. Techniques-wise, we obtain this result through a compiler from information-theoretic protocols and rational proofs for polynomial evaluation. The latter could be of independent interest.As a second contribution, we propose a new notion of extractability for rational arguments. Through this notion we can obtain arguments where knowledge of a witness is incentivized (rather than incentivizing mere soundness). We show how our aforementioned compiler can also be applied to obtain efficient extractable rational arguments for $\mathsf{NP}$. 
ER -

Matteo Campanelli, Chaya Ganesh, and Rosario Gennaro, "How to Make Rational Arguments Practical and Extractable," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a63zl86bm.