Paper 2023/1396

Parallel Hardware for Isogeny-based VDF: Attacker's Perspective

David Jacquemin, Graz University of Technology
Anisha Mukherjee, Graz University of Technology
Ahmet Can Mert, Graz University of Technology
Sujoy Sinha Roy, Graz University of Technology
Abstract

The long running time of isogeny-based cryptographic constructions has proved to be a boon in disguise for one particular type of primitive called Verifiable Delay Functions (VDFs). VDFs are characterised by sequential function evaluation but an immediate output verification. In order to ensure secure use of VDFs in real-world applications, it is important to determine the fastest implementation. Considering the point of view of an attacker (say with unbounded resources), this paper aims to achieve the fastest possible hardware implementation of isogeny-based VDFs. It is the first work that implements the $2^T$-isogeny walk involved in the evaluation step of an isogeny VDF. To meet our goal, we use redundant representations of integers and introduce a new lookup table-based algorithm for modular reduction. We also provide a survey of elliptic curve arithmetic to arrive at the most cost-effective curve computations and propose an improvement of the point doubling algorithm for better parallelism. The evaluation step of a VDF is defined to be sequential, which means that there is limited scope for parallelism. Nevertheless, taking this constraint into account our proposed design targets the highest levels of parallelism possible on an architectural level of an isogeny VDF implementation. We provide detailed analysis of all our arithmetic modules as well as estimates for their critical path delays and area consumption. Our 28nm ASIC design computes a $4^{100} = 2^{200}$-isogeny in 7.1$\mu s$. It is the first high-performance ASIC implementation for evaluation of isogeny VDFs.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
Verifiable delay functionsIsogenyRedundant representationASIC
Contact author(s)
david jacquemin @ iaik tugraz at
anisha mukherjee @ iaik tugraz at
ahmet mert @ iaik tugraz at
sujoy sinharoy @ iaik tugraz at
History
2023-09-21: approved
2023-09-18: received
See all versions
Short URL
https://ia.cr/2023/1396
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1396,
      author = {David Jacquemin and Anisha Mukherjee and Ahmet Can Mert and Sujoy Sinha Roy},
      title = {Parallel Hardware for Isogeny-based {VDF}: Attacker's Perspective},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1396},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1396}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.