Paper 2020/772
FiatShamir for Repeated Squaring with Applications to PPADHardness and VDFs
Alex Lombardi and Vinod Vaikuntanathan
Abstract
The FiatShamir transform is a methodology for compiling a (publiccoin) interactive proof system for a language $L$ into a noninteractive argument system for $L$. Proving security of the FiatShamir 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 FiatShamir transform applied to the GoldwasserKalaiRothblum (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 $2^{\lambda^{\epsilon}}$) that guarantees the soundness of FiatShamir for this protocol assuming the subexponential ($2^{n^{1\epsilon}}$)hardness of the $n$dimensional learning with errors problem. (The latter follows from the worstcase $2^{n^{1\epsilon}}$ hardness of lattice problems.) More generally, we extend the ``badchallenge function'' methodology of Canetti et al. for proving the soundness of FiatShamir to a class of protocols whose badchallenge functions are not efficiently computable. As a corollary (following Choudhuri et al., ePrint 2019 and Ephraim et al., EUROCRYPT 2020), we construct hardonaverage problems in the complexity class $\mathbf{CLS}\subset \mathbf{PPAD}$ under the $2^{\lambda^\epsilon}$hardness of the repeated squaring problem and the $2^{n^{1\epsilon}}$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 PPADhardness and VDF instantiations demonstrating a broader tradeoff between the strength of the repeated squaring assumption and the strength of the lattice assumption.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in CRYPTO 2020
 Contact author(s)
 alexjl @ mit edu
 History
 20200625: revised
 20200624: received
 See all versions
 Short URL
 https://ia.cr/2020/772
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/772, author = {Alex Lombardi and Vinod Vaikuntanathan}, title = {FiatShamir for Repeated Squaring with Applications to {PPAD}Hardness and {VDFs}}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/772}, year = {2020}, url = {https://eprint.iacr.org/2020/772} }