Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs
© International Association for Cryptologic Research 2020. The Fiat-Shamir transform is a methodology for compiling a (public-coin) interactive proof system for a language L into a non-interactive argument system for L. Proving security of the Fiat-Shamir transform in the standard model, especially...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Book |
| Language: | English |
| Published: |
Springer International Publishing
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137201 |
| _version_ | 1811084520150007808 |
|---|---|
| author | Lombardi, Alex Vaikuntanathan, Vinod |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Lombardi, Alex Vaikuntanathan, Vinod |
| author_sort | Lombardi, Alex |
| collection | MIT |
| description | © International Association for Cryptologic Research 2020. The Fiat-Shamir transform is a methodology for compiling a (public-coin) interactive proof system for a language L into a non-interactive argument system for L. Proving security of the Fiat-Shamir transform in the standard model, especially in the context of succinct arguments, is largely an unsolved problem. The work of Canetti et al. (STOC 2019) proved the security of the Fiat-Shamir transform applied to the Goldwasser-Kalai-Rothblum (STOC 2008) succinct interactive proof system under a very strong “optimal learning with errors” assumption. Achieving a similar result under standard assumptions remains an important open question. In this work, we consider the problem of compiling a different succinct interactive proof system: Pietrzak’s proof system (ITCS 2019) for the iterated squaring problem. We construct a hash function family (with evaluation time roughly (Formula Presented)) that guarantees the soundness of Fiat-Shamir for this protocol assuming the sub-exponential (Formula Presented)-hardness of the n-dimensional learning with errors problem. (The latter follows from the worst-case (Formula Presented) hardness of lattice problems.) More generally, we extend the “bad-challenge function” methodology of Canetti et al. for proving the soundness of Fiat-Shamir to a class of protocols whose bad-challenge functions are not efficiently computable. As a corollary (following Choudhuri et al., ePrint 2019 and Ephraim et al., EUROCRYPT 2020), we construct hard-on-average problems in the complexity class (Formula Presented) under the (Formula Presented)-hardness of the repeated squaring problem and the (Formula Presented)-hardness of the learning with errors problem. Under the additional assumption that the repeated squaring problem is “inherently sequential”, we also obtain a Verifiable Delay Function (Boneh et al., EUROCRYPT 2018) in the standard model. Finally, we give additional PPAD-hardness and VDF instantiations demonstrating a broader tradeoff between the strength of the repeated squaring assumption and the strength of the lattice assumption. |
| first_indexed | 2024-09-23T12:52:04Z |
| format | Book |
| id | mit-1721.1/137201 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:52:04Z |
| publishDate | 2021 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1372012023-04-07T20:11:52Z Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs Lombardi, Alex Vaikuntanathan, Vinod Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © International Association for Cryptologic Research 2020. The Fiat-Shamir transform is a methodology for compiling a (public-coin) interactive proof system for a language L into a non-interactive argument system for L. Proving security of the Fiat-Shamir transform in the standard model, especially in the context of succinct arguments, is largely an unsolved problem. The work of Canetti et al. (STOC 2019) proved the security of the Fiat-Shamir transform applied to the Goldwasser-Kalai-Rothblum (STOC 2008) succinct interactive proof system under a very strong “optimal learning with errors” assumption. Achieving a similar result under standard assumptions remains an important open question. In this work, we consider the problem of compiling a different succinct interactive proof system: Pietrzak’s proof system (ITCS 2019) for the iterated squaring problem. We construct a hash function family (with evaluation time roughly (Formula Presented)) that guarantees the soundness of Fiat-Shamir for this protocol assuming the sub-exponential (Formula Presented)-hardness of the n-dimensional learning with errors problem. (The latter follows from the worst-case (Formula Presented) hardness of lattice problems.) More generally, we extend the “bad-challenge function” methodology of Canetti et al. for proving the soundness of Fiat-Shamir to a class of protocols whose bad-challenge functions are not efficiently computable. As a corollary (following Choudhuri et al., ePrint 2019 and Ephraim et al., EUROCRYPT 2020), we construct hard-on-average problems in the complexity class (Formula Presented) under the (Formula Presented)-hardness of the repeated squaring problem and the (Formula Presented)-hardness of the learning with errors problem. Under the additional assumption that the repeated squaring problem is “inherently sequential”, we also obtain a Verifiable Delay Function (Boneh et al., EUROCRYPT 2018) in the standard model. Finally, we give additional PPAD-hardness and VDF instantiations demonstrating a broader tradeoff between the strength of the repeated squaring assumption and the strength of the lattice assumption. 2021-11-03T14:38:06Z 2021-11-03T14:38:06Z 2020 2021-04-08T14:38:16Z Book http://purl.org/eprint/type/ConferencePaper 0302-9743 1611-3349 https://hdl.handle.net/1721.1/137201 Lombardi, Alex and Vaikuntanathan, Vinod. 2020. "Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12172 LNCS. en 10.1007/978-3-030-56877-1_22 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer International Publishing Other repository |
| spellingShingle | Lombardi, Alex Vaikuntanathan, Vinod Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs |
| title | Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs |
| title_full | Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs |
| title_fullStr | Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs |
| title_full_unstemmed | Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs |
| title_short | Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs |
| title_sort | fiat shamir for repeated squaring with applications to ppad hardness and vdfs |
| url | https://hdl.handle.net/1721.1/137201 |
| work_keys_str_mv | AT lombardialex fiatshamirforrepeatedsquaringwithapplicationstoppadhardnessandvdfs AT vaikuntanathanvinod fiatshamirforrepeatedsquaringwithapplicationstoppadhardnessandvdfs |