Paper 2024/145

Practical Batch Proofs of Exponentiation

Charlotte Hoffmann, Institute of Science and Technology Austria
Pavel Hubáček, Czech Academy of Sciences, Charles University
Svetlana Ivanova, Charles University
Abstract

A Proof of Exponentiation (PoE) allows a prover to efficiently convince a verifier that $y=x^e$ in some group of unknown order. PoEs are the basis for practical constructions of Verifiable Delay Functions (VDFs), which, in turn, are important for various higher-level protocols in distributed computing. In applications such as distributed consensus, many PoEs are generated regularly, motivating protocols for secure aggregation of batches of statements into a few statements to improve the efficiency for both parties. Rotem (TCC 2021) recently presented two such generic batch PoEs. In this work, we introduce two batch PoEs that outperform both proposals of Rotem and we evaluate their practicality. First, we show that the two batch PoEs of Rotem can be combined to improve the overall efficiency by at least a factor of two. Second, we revisit the work of Bellare, Garay, and Rabin (EUROCRYPT 1998) on batch verification of digital signatures and show that, under the low order assumption, their bucket test can be securely adapted to the setting of groups of unknown order. The resulting batch PoE quickly outperforms the state of the art in the expected number of group multiplications with the growing number of instances, and it decreases the cost of batching by an order of magnitude already for hundreds of thousands of instances. Importantly, it is the first batch PoE that significantly decreases both the proof size and complexity of verification. Our experimental evaluations show that even a non-optimized implementation achieves such improvements, which would match the demands of real-life systems requiring large-scale PoE processing. Finally, even though our proof techniques are conceptually similar to Rotem, we give an improved analysis of the application of the low order assumption towards secure batching of PoE instances, resulting in a tight reduction, which is important when setting the security parameter in practice.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Proof of ExponentiationVerifiable Delay FunctionBatching
Contact author(s)
charlotte hoffmann @ ist ac at
hubacek @ math cas cz
ivanovsv @ o365 cuni cz
History
2024-02-02: approved
2024-02-01: received
See all versions
Short URL
https://ia.cr/2024/145
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/145,
      author = {Charlotte Hoffmann and Pavel Hubáček and Svetlana Ivanova},
      title = {Practical Batch Proofs of Exponentiation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/145},
      year = {2024},
      url = {https://eprint.iacr.org/2024/145}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.