Paper 2020/351

Optimized and secure pairing-friendly elliptic curves suitable for one layer proof composition

Youssef El Housni and Aurore Guillevic

Abstract

A zero-knowledge proof is a method by which one can prove knowledge of general non-deterministic polynomial (NP) statements. SNARKs are in addition non-interactive, short and cheap to verify. This property makes them suitable for recursive proof composition, that is proofs attesting to the validity of other proofs. To achieve this, one moves the arithmetic operations to the exponents. Recursive proof composition has been empirically demonstrated for pairing-based SNARKs via tailored constructions of expensive pairing-friendly elliptic curves namely a pair of 753-bit MNT curves, so that one curve’s order is the other curve’s base field order and vice-versa. The ZEXE construction restricts to one layer proof composition and uses a pair of curves, BLS12-377 and CP6-782, which improve significantly the arithmetic on the first curve. In this work we construct a new pairing-friendly elliptic curve to be used with BLS12- 377, which is STNFS-secure and fully optimized for one layer composition. We propose to name the new curve BW6-761. This work shows that it is at least five times faster to verify a composed SNARK proof on this curve compared to the previous state-of-the-art, and proposes an optimized Rust implementation that is almost thirty times faster than the one available in ZEXE library.

Note: This is the extended version of the paper submitted to CANS 2020 (https://cans2020.at). It includes appendices related to pairing computation and security analysis. Rust implementation can is available at (https://github.com/scipr-lab/zexe) and SageMath/Magma scripts at (https://gitlab.inria.fr/zk-curves/bw6-761/).

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. MINOR revision.CANS 2020 https://cans2020.at
Keywords
elliptic curvebilinear pairingzkSNARKproof composition
Contact author(s)
youssef el housni @ fr ey com
aurore guillevic @ inria fr
History
2020-10-09: last of 3 revisions
2020-03-26: received
See all versions
Short URL
https://ia.cr/2020/351
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/351,
      author = {Youssef El Housni and Aurore Guillevic},
      title = {Optimized and secure pairing-friendly elliptic curves suitable for one layer proof composition},
      howpublished = {Cryptology ePrint Archive, Paper 2020/351},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/351}},
      url = {https://eprint.iacr.org/2020/351}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.