Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 13044))
Included in the following conference series:
851Accesses
Abstract
We study the problem ofbatch verification for verifiable delay functions (VDFs), focusing on proofs of correct exponentiation (PoCE), which underlie recent VDF constructions. We show how to compile any PoCE into a batch PoCE, offering significant savings in both communication and verification time. Concretely, given any PoCE with communication complexityc, verification timet and soundness error\(\delta \), and any pseudorandom function with key length\(\mathsf{k}_\mathsf{prf}\) and evaluation time\( t_\mathsf{prf}\), we construct:
A batch PoCE for verifyingn instances with communication complexity\(m\cdot c +\mathsf{k}_\mathsf{prf}\), verification time\(m\cdot t + n\cdot m\cdot O(t_\mathsf{op} + t_\mathsf{prf})\) and soundness error\(\delta + 2^{-m}\), where\(\lambda \) is the security parameter,m is an adjustable parameter that can take any integer value, and\(t_\mathsf{op}\) is the time required to evaluate the group operation in the underlying group. This should be contrasted with the naïve approach, in which the communication complexity and verification time are\(n \cdot c\) and\(n \cdot t\), respectively. The soundness of this compiler relies only on the soundness of the underlying PoCE and the existence of one-way functions.
An improved batch PoCE based on the low order assumption. For verifyingn instances, the batch PoCE requires communication complexity\(c +\mathsf{k}_\mathsf{prf}\) and verification time\(t + n\cdot (t_\mathsf{prf} + \log (s)\cdot O(t_\mathsf{op}))\), and has soundness error\(\delta + 1/s\). The parameters can take any integer value, as long as it is hard to find group elements of order less thans in the underlying group. We discuss instantiations in whichs can be exponentially large in the security parameter\(\lambda \).
If the underlying PoCE is constant round and public coin (as is the case for existing protocols), then so are all of our batch PoCEs, implying that they can be made non-interactive using the Fiat-Shamir transform.
Additionally, for RSA groups with moduli which are the products of two safe primes, we show how to efficiently verify that certain elements are not of order 2. This protocol, together with the second compiler above and any (single-instance) PoCE in these groups, yields an efficient batch PoCE in safe RSA groups. To complete the picture, we also show how to extend Pietrzak’s protocol (which is statistically sound in the group\(QR_N^+\) whenN is the product of two safe primes) to obtain a statistically-sound PoCE in safe RSA groups.
L. Rotem—supported by the Adams Fellowship Program of the Israel Academy of Sciences and Humanities and by the European Union’s Horizon 2020 Framework Program (H2020) via an ERC Grant (Grant No. 714253).
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 11439
- Price includes VAT (Japan)
- Softcover Book
- JPY 14299
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Often, these protocols offer only computational soundness guarantee. Nevertheless, we use the nameproofs (rather thanarguments) throughout, for more concise presentation and for consistency with previous works (e.g., [BBF19]).
- 2.
In the updated longer version of his work [Wes20].
- 3.
For example, in cyclic groups of prime (and publicly known) order, the low order assumption holds information-theoretically, whereas the adaptive root assumption does not hold. Moreover, even in groups which are believed to be of unknown order, the adaptive root assumption seems to be a stronger one: For instance, for a modulusN which is the product of two safe primes, the low order assumption holds information-theoretically in the group of quadratic residues moduloN. This is in contrast to the adaptive root assumption which is at least as strong as assuming the hardness of factoringN. See Sect. 2 for details.
- 4.
Note that our definition of batch proofs of correct exponentiation deals with scenarios in which all instances should be verified with respect to the same exponent. We discuss this point further in Sect. 3, and leave it as an interesting open question to construct batch proofs for different exponents.
- 5.
- 6.
For example, when it comes to proofs of replication, if a file is retrievable given an encodingy which is the output of a VDF, then it is also retrievable given\(-y\). As an additional example, in the context of verifiable randomness beacons, this weakened soundness guarantee gives a malicious prover the ability to convince the verifier that the shared randomness is\(-y\), when in fact it should bey, but no more than that.
- 7.
This is in contrast to the quotient group\(\mathbb {Z}_N^*\setminus \{ \pm 1 \}\) or the subgroups\(QR_N\) and\(QR_N^+\) of\(\mathbb {Z}_N^*\).
- 8.
See also [CHP07] and the many references therein.
- 9.
Recall that Boneh et al. [BBF18] proved computational soundness by extending this analysis to the case where there are elements of order less than\(2^{\lambda }\), but these are hard to find. We focus here on statistical soundness, as this is what we will obtain in safe RSA groups.
- 10.
This is the case since, as observed by Fischlin and Schnorr [FS00],\({QR}_N^+ = \mathbb {J}_N^+\), where\(\mathbb {J}_N\) is the group of elements with Jacobi symbol\(+1\) and\(\mathbb {J}_N^+ {\mathop {=}\limits ^\mathsf{def}} \mathbb {J}_N/\pm 1\). Hence, deciding whether an integerx is in\({QR}_N^+\) amounts to checking that\(x \ge 0\) and that its Jacobi symbol is\(+1\).
- 11.
This is indeed the case for RSA groups, which are embedded in the ring\(\mathbb {Z}_N\).
- 12.
We implicitly assume here thatm andn are both polynomially-bounded functions of the security parameter.
- 13.
Recall that in the compiler from Sect. 5, in order to obtain an additive soundness loss of\(2^{-m}\), the communication had to grow linearly withm.
- 14.
Given any efficient algorithm\(\mathsf{Samp}\) for sampling from the uniform distribution over [s] using\(r = r(s)\) random coins,\(\mathsf {PRF}\) can be implemented by invoking a PRF mapping\(\{0,1\}^{\lceil \log (n) \rceil }\) into\(\{0,1\}^r\) and then applying\(\mathsf{Samp}\) using the output of the PRF as random coins.
- 15.
Their proof can also be used, essentially unchanged, to show that (the strong variant of) the low order assumption in\(\mathbb {Z}_N^*\ \{ \pm 1 \}\) is equivalent to factoringN.
- 16.
Observe that in\(\mathsf{Batch}_3^s(\pi )\), the exponents\(\alpha _1,\ldots , \alpha _n\) are not chosen uniformly at random from [s], but using the pseudorandom function\(\mathsf {PRF}\). This is handled in exactly the same manner in which it was handled in the previous section. The reader is referred to the full version for further details.
References
Armknecht, F., Barman, L., Bohli, J.-M., Karame, G.O.: Mirror: enabling proofs of data replication and retrievability in the cloud. In: Proceedings of the 25th USENIX Conference on Security Symposium, SEC 2016, pp. 1051–1068 (2016)
Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Struct. Algorithms3(3), 289–304 (1992)
Boneh, D., Bonneau, J., Bünz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 757–788. Springer, Cham (2018).https://doi.org/10.1007/978-3-319-96884-1_25
Boneh, D., Bünz, B., Fisch, B.: A survey of two verifiable delay functions. Cryptology ePrint Archive, Report 2018/712 (2018)
Boneh, D., Bünz, B., Fisch, B.: Batching techniques for accumulators with applications to IOPs and stateless blockchains. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 561–586. Springer, Cham (2019).https://doi.org/10.1007/978-3-030-26948-7_20
Bonneau, J., Clark, J., Goldfeder, S.: On bitcoin as a public randomness source. Cryptology ePrint Archive, Report 2015/1015 (2015)
Benet, J., Dalrymple, D., Greco, N.: Proof of replication (2017).https://filecoin.io/proof-of-replication.pdf. Accessed 16 Sep 2021
Bellare, M., Garay, J.A., Rabin, T.: Fast batch verification for modular exponentiation and digital signatures. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 236–250. Springer, Heidelberg (1998).https://doi.org/10.1007/BFb0054130
Bentov, I., Gabizon, A., Zuckerman, D.: Bitcoin beacon.arXiv:605.04559 (2016)
Block, A.R., Holmgren, J., Rosen, A., Rothblum, R.D., Soni, P.: Time- and space-efficient arguments from groups of unknown order. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 123–152. Springer, Cham (2021).https://doi.org/10.1007/978-3-030-84259-8_5
Belabas, K., Kleinjung, T., Sanso, A., Wesolowski, B.: A note on the low order assumption in class group of an imaginary quadratic number fields. Cryptology ePrint Archive, Report 2020/1310 (2020)
Boneh, D.: Twenty years of attacks on the RSA cryptosystem. Not. AMS46(2), 203–213 (1999)
Boyd, C., Pavlovski, C.: Attacking and repairing batch verification schemes. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 58–71. Springer, Heidelberg (2000).https://doi.org/10.1007/3-540-44448-3_5
Clark, J., Essex, A.: CommitCoin: carbon dating commitments with Bitcoin. In: Financial Cryptography and Data Security, FC 2012, pp. 390–398 (2012)
Camenisch, J., Hohenberger, S., Pedersen, M.Ø.: Batch verification of short signatures. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 246–263. Springer, Heidelberg (2007).https://doi.org/10.1007/978-3-540-72540-4_14
Crescenzo, G.D., Khodjaeva, M., Kahrobaei, D., Shpilrain, V.: Computing multiple exponentiations in discrete log and RSA groups: from batch verification to batch delegation. In: IEEE Conference on Communications and Network Security (CNS), pp. 531–539 (2017)
Cheon, J.H., Lee, D.H.: Use of sparse and/or complex exponents in batch verification of exponentiations. IEEE Trans. Comput.55(12), 1536–1542 (2006)
Cheon, J.H., Lee, M.-K.: Improved batch verification of signatures using generalized sparse exponents. Comput. Stand. Interfaces40, 42–52 (2015)
Cohen, B., Pietrzak, K.: The Chia network blockchain (2019).https://www.chia.net/assets/ChiaGreenPaper.pdf. Accessed 16 Sep 2021
Cheon, J.H., Yi, J.H.: Fast batch verification of multiple signatures. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 442–457. Springer, Heidelberg (2007).https://doi.org/10.1007/978-3-540-71677-8_29
Döttling, N., Garg, S., Malavolta, G., Vasudevan, P.N.: Tight verifiable delay functions. In: Galdi, C., Kolesnikov, V. (eds.) SCN 2020. LNCS, vol. 12238, pp. 65–84. Springer, Cham (2020).https://doi.org/10.1007/978-3-030-57990-6_4
Ephraim, N., Freitag, C., Komargodski, I., Pass, R.: Continuous verifiable delay functions. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 125–154. Springer, Cham (2020).https://doi.org/10.1007/978-3-030-45727-3_5
Fiat, A.: Batch RSA. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 175–185. Springer, New York (1990).https://doi.org/10.1007/0-387-34805-0_17
Fisch, B.: Tight proofs of space and replication. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 324–348. Springer, Cham (2019).https://doi.org/10.1007/978-3-030-17656-3_12
De Feo, L., Masson, S., Petit, C., Sanso, A.: Verifiable delay functions from supersingular isogenies and pairings. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 248–277. Springer, Cham (2019).https://doi.org/10.1007/978-3-030-34578-5_10
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
Fischlin, R., Schnorr, C.: Stronger security proofs for RSA and Rabin bits. J. Cryptol.13(2), 221–244 (2000)
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM33(4), 792–807 (1986)
Galindo, D., Liu, J., Ordean, M., Wong, J.-M.: Fully distributed verifiable random functions and their application to decentralised random beacons. In: IEEE European Symposium on Security and Privacy (2021, to appear)
Goldschlag, D.M., Stubblebine, S.G.: Publicly verifiable lotteries: applications of delaying functions. In: Financial Cryptography, FC 1998, pp. 214–226 (1998)
Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput.28(4), 1364–1396 (1999)
Hofheinz, D., Kiltz, E.: The group of signed quadratic residues and applications. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 637–653. Springer, Heidelberg (2009).https://doi.org/10.1007/978-3-642-03356-8_37
Han, R., Yu, R., Lin, H.: RANDCHAIN: decentralised randomness beacon from sequential proof-of-work. In: IEEE International Conference on Blockchain, pp. 442–449 (2020)
Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 220–229 (1997)
Lerner, S.D.: Proof of unique blockchain storage (2014).https://bitslog.com/2014/11/03/proof-of-local-blockchain-storage/. Accessed 16 Sep 2021
Landerreche, E., Stevens, M., Schaffnerevan, C.: Non-interactive cryptographic timestamping based on verifiable delay functions. In: Financial Cryptography and Data Security, FC 2020, pp. 541–558 (2020)
Lombardi, A., Vaikuntanathan, V.: Fiat-Shamir for repeated squaring with applications to PPAD-hardness and VDFs. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 632–651. Springer, Cham (2020).https://doi.org/10.1007/978-3-030-56877-1_22
Lenstra, A.K., Wesolowski, B.: A random zoo: sloth, unicorn, and trx. Cryptology ePrint Archive, Report 2015/366 (2015)
Naor, M.: Bit commitment using pseudorandomness. J. Cryptol.4(2), 151–158 (1991)
Naccache, D., et al.: Can D.S.A. be improved?—Complexity trade-offs with the digital signature standard. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 77–85. Springer, Heidelberg (1995).https://doi.org/10.1007/BFb0053426
Naor, M., Naor, J.: Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput.22(4), 838–856 (1993)
Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. Syst. Sci.49(2), 149–167 (1994)
Pietrzak, K.: Simple verifiable delay functions. In: Proceedings of the 10th Conference on Innovations in Theoretical Computer Science, pp. 60:1–60:15 (2019)
Protocol Labs: Filecoin: a decentralized storage network (2017).https://filecoin.io/filecoin.pdf. Accessed 16 Sep 2021
Pierrot, C., Wesolowski, B.: Malleability of the blockchain’s entropy. Cryptogr. Commun.10(1), 211–233 (2018)
Rotem, L., Segev, G., Shahaf, I.: Generic-group delay functions require hidden-order groups. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 155–180. Springer, Cham (2020).https://doi.org/10.1007/978-3-030-45727-3_6
Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto (1996)
Seres, I.A., Burcsi, P.: A note on low order assumptions in RSA groups. Cryptology ePrint Archive, Report 2020/402 (2020)
Shani, B.: A note on isogeny-based hybrid verifiable delay functions. Cryptology ePrint Archive, Report 2019/205 (2019)
StarkWare: Presenting: VeeDo (2020).https://medium.com/starkware/presenting-veedo-e4bbff77c7ae. Accessed 16 Sep 2021
Ta-Shma, A.: Explicit, almost optimal, epsilon-balanced codes. In: Proceedings of the 49rd Annual ACM Symposium on Theory of Computing, pp. 238–251 (2017)
Wesolowski, B.: Efficient verifiable delay functions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 379–407. Springer, Cham (2019).https://doi.org/10.1007/978-3-030-17659-4_13
Wesolowski, B.: Efficient verifiable delay functions. J. Cryptol.33, 2113–2147 (2020)
Yen, S.-M., Laih, C.-S.: Improved digital signature suitable for batch verification. IEEE Trans. Comput.44(7), 957–959 (1995)
Author information
Authors and Affiliations
School of Computer Science and Engineering, Hebrew University of Jerusalem, 91904, Jerusalem, Israel
Lior Rotem
- Lior Rotem
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toLior Rotem.
Editor information
Editors and Affiliations
Georgetown University, Washington, WA, USA
Kobbi Nissim
The University of Texas at Austin, Austin, TX, USA
Brent Waters
Rights and permissions
Copyright information
© 2021 International Association for Cryptologic Research
About this paper
Cite this paper
Rotem, L. (2021). Simple and Efficient Batch Verification Techniques for Verifiable Delay Functions. In: Nissim, K., Waters, B. (eds) Theory of Cryptography. TCC 2021. Lecture Notes in Computer Science(), vol 13044. Springer, Cham. https://doi.org/10.1007/978-3-030-90456-2_13
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-030-90455-5
Online ISBN:978-3-030-90456-2
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
