Cryptology ePrint Archive: Report 2019/403

Fast and simple constant-time hashing to the BLS12-381 elliptic curve

Riad S. Wahby and Dan Boneh

Abstract: Pairing-friendly elliptic curves in the Barreto-Lynn-Scott family have experienced a resurgence in popularity due to their use in a number of real-world projects. One particular Barreto-Lynn-Scott curve, called BLS12-381, is the locus of significant development and deployment effort, especially in blockchain applications. This effort has sparked interest in using BLS12-381 for BLS signatures, and in particular for aggregatable signatures, which requires hashing to one of the groups of the bilinear pairing defined by the BLS12-381 elliptic curve.

While there is a substantial body of literature on the problem of hashing to elliptic curves, much of this work does not apply to Barreto-Lynn-Scott curves. Moreover, the work that does apply has the unfortunate property that fast implementations are complex, while simple implementations are slow.

In this work, we address these issues. First, we show a straightforward way of adapting the "simplified SWU" map of Brier et al. to BLS12-381. Second, we describe optimizations to the SWU map that both simplify its implementation and improve its performance; these optimizations may be of interest in other contexts. Third, we implement and evaluate. We find that our work yields constant-time hash functions that are simple to implement, yet perform within 9% of the fastest, non--constant-time alternatives, which require much more complex implementations.

Category / Keywords: public-key cryptography / hash functions, elliptic curve cryptosystem, implementation

Date: received 16 Apr 2019, last revised 26 Apr 2019

Contact author: rsw at cs stanford edu

Available format(s): PDF | BibTeX Citation

Note: Add an optimization due to Michael Scott (Section 5); update and expand evaluation (Section 6)

Version: 20190426:065120 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]