Practical batch proofs of exponentiation

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F25%3A00639767" target="_blank" >RIV/67985840:_____/25:00639767 - isvavai.cz</a>

Alternative codes found

RIV/00216208:11320/25:10512205

Result on the web

<a href="https://doi.org/10.62056/abvur-iuc" target="_blank" >https://doi.org/10.62056/abvur-iuc</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.62056/abvur-iuc" target="_blank" >10.62056/abvur-iuc</a>

Result language

angličtina

Original language name

Practical batch proofs of exponentiation

Original language description

A Proof of Exponentiation (PoE) allows a prover to efficiently convince a verifier that 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.nIn 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.nOur 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. Our proof techniques are conceptually similar to Rotem. However, 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.nFinally, we discuss a new application of batch PoEs towards efficient remote attestation of parallel computational power. We show that, under a natural generalization of the hardness of iterated squaring in groups of unknown order, any batch PoE can be used to construct a secure protocol for testing the parallelism of the prover with optimal communication complexity independent of the claimed number of available processors.

Czech name

—

Czech description

—

Type

J_ost - Miscellaneous article in a specialist periodical

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2025

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

IACR Communications in Cryptology

ISSN

3006-5496

e-ISSN

—

Volume of the periodical

2

Issue of the periodical within the volume

3

Country of publishing house

US - UNITED STATES

Number of pages

28

Pages from-to

9

UT code for WoS article

—

EID of the result in the Scopus database

—