Elliptic curves over large prime fields are widely deployed in non-quantum public-key cryptography. Since 2001, pairing-friendly curves allow to design new cryptosystems (identity-based encryption and short signatures are classical examples). These pairing-friendly curves are equipped with a bilinear map efficiently computable: the Tate or the Weil pairing. Variants of the Tate pairing are usually the most efficient in common cryptographic contexts.
More recently in the context of proof systems, new needs of elliptic curves arise. This mini-symposium focuses on pairing-friendly elliptic curves revisited with these new applications in mind: finding new pairing-friendly curves, finding chains or cycles of pairing-friendly elliptic curves, hashing to the group of points on a curve, improving the pairing computation in different contexts, improving the group operations (testing membership of a subgroup of the curve, or mapping a point to a specific subgroup).
Session I of III, Wednesday, July 12, 10:30 am
| Aurore Guillevic, Inria Nancy, France |
|---|
| Introduction on Elliptic Curves and Pairings in Cryptography Slides |
| Elliptic curves over large prime fields are widely deployed in non-quantum public-key cryptography. Since 2001, pairing-friendly curves allow to design new cryptosystems (identity-based encryption and short signatures are classical examples). These pairing-friendly curves are equipped with a bilinear map efficiently computable: the Tate or the Weil pairing. Variants of the Tate pairing are usually the most efficient in common cryptographic contexts. More recently in the context of proof systems, new needs of elliptic curves arise. This mini-symposium focuses on pairing-friendly elliptic curves revisited with these new applications in mind: finding new pairing-friendly curves, finding chains or cycles of pairing-friendly elliptic curves, hashing to the group of points on a curve, improving the pairing computation in different contexts, improving the group operations (testing membership of a subgroup of the curve, or mapping a point to a specific subgroup). |
| Dimitri Koshelev, ENS Lyon, France |
| Subgroup membership testing on elliptic curves via the Tate pairing Slides |
| In my talk I will explain how to guarantee the membership of a point in the prime-order subgroup of an elliptic curve (over a finite field) satisfying some moderate conditions. For this purpose, we will apply the Tate pairing on the curve, however it is not required to be pairing-friendly. Whenever the cofactor is small, the new subgroup test is much more efficient than other known ones, because it needs to compute at most two n-th power residue symbols (with small n) in the basic field. More precisely, the running time of the test is (sub-)quadratic in the bit length of the field size, which is comparable with the Decaf-style technique. The test is in particular relevant for most real-world twisted Edwards curves. |
| Jorge Chavez Saab, CINVESTAV-IPN, Technology Innovation Institute, Mexico |
| SwiftEC: Shallue–van De Woestijne Indifferentiable Function To Elliptic Curves Slides |
|
Hashing arbitrary values to points on an elliptic curve is a required step in many cryptographic constructions, and a number of techniques have been proposed to do so over the years. One of the first ones was due to Shallue and van de Woestijne (ANTS-VII), and it had the interesting property of mapping essentially any finite field to any elliptic curve over that field. It did not, however, have the desirable property of being indifferentiable from a random oracle when composed with a random oracle to the base field. Various approaches have since been considered to overcome this limitation, but despite being successful they all have the drawback of being twice as expensive to compute, requiring two field exponentiations. In this work, we revisit this long-standing open problem, and observe that the SW map actually fits in a one-parameter family of encodings, where treating the parameter as a second input results in a map to the curve that is indifferentiable. Moreover, on a very large class of curves, the one-parameter family admits a rational parametrization, which lets us compute the map at almost the same cost as the original, and finally achieve indifferentiable hashing to most curves with a single exponentiation. |
| Laurian Azebaze Guimagang |
| Faster Beta Weil Pairing on BLS Pairing Friendly Curves with Odd Embedding Degree Slides |
| Since the advent of pairing-based cryptography, various optimization methods that increase the speed of pairing computations have been exploited, as well as new types of pairings. In this work we proposed new formulas for the Beta-Weil pairing on curves with odd embedding degree by eliminating denominators and exponents during the computation of the Beta-Weil pairing. These formulas are suitable for the parallel computation for the Beta-Weil pairing on curves with odd embedding degree which involve vertical line functions useful for sparse multiplications. For computations we used Miller’s algorithm combined with storage and multifunction methods. Applying our framework to BLS-27, BLS-15 and BLS-9 curves at respectively the 256 bit, the 192 bit and the 128 bit security level, we obtain faster Beta-Weil pairings than the previous state-of-the-art constructions. |
Session II of III, Wednesday, July 12, 14:00
| Mike Scott, Technical Innovation Institute |
|---|
| Efficiently Computing a Pairing: Tricks Old and New Slides |
| In an early text on Elliptic curves, Alfred Menezes observed that the computation of the Weil pairing took around 5 minutes on contemporary hardware. Of course then pairings were only of significance as a means of cryptanalysis of certain curves that failed the so-called MOV condition. Once pairings became tools for cryptography, it became apparent that significant speed-up was going to be required if pairing based cryptography were ever to become practical. Cryptographers rose to the challenge, and now a secure pairing can be calculated in well under a millisecond. This illustrates how, with sufficient effort, the impractical can become practical (those interested in Fully Homomorphic Encryption take note!) Here we review the journey, introduce some new ideas, plug some gaps, and highlight some less well known tricks. |
| Marloes Venema, University of Wuppertal, Germany, Radboud University Nijmegen, The Netherlands |
| Accurately Benchmarking Efficiency of Pairing-Based Attribute-Based Encryption Slides |
| Measuring efficiency is difficult, and therefore schemes might not compare in the way we think. In the last decades, several works have contributed in the quest to successfully determine and compare the efficiency of pairing-based attribute-based encryption (ABE) schemes. However, many of these works are limited: they use little to no optimizations, or use underlying pairing-friendly elliptic curves that do not provide sufficient security anymore. Hence, using these works to benchmark ABE schemes does not yield accurate results. In this talk, we present a framework for accurately benchmarking efficiency of ABE: ABE Squared, published at CHES 2022. In particular, we focus on uncovering the multiple layers of optimization that are relevant to the implementation of ABE schemes. Moreover, we focus on making any comparison fairer by considering the influence of the potential design goals on any optimizations. To this end, we also introduce manual, heuristic type-conversion techniques where existing techniques fall short. Finally, to illustrate the effectiveness of ABE Squared, we implement several schemes and provide all relevant benchmarks. These show that the design goal influences the optimization approaches, which in turn influence the overall efficiency of the implementations. Importantly, these demonstrate that the schemes also compare differently than existing works previously suggested. |
| Yu Dai, Sun Yat-sen University |
| Fast Subgroup Membership Testing and Hashing on Pairing-Friendly Curves Slides |
| Recently, Scott proposed efficient methods for subgroup membership testings for G1, G2 and GT on the BLS family. In this talk, we generalize these methods and show that the new techniques are applicable to a large class of pairing-friendly curves. In addition, we also propose a general method for hashing to G2 on curves with the lack of twists. On this basis, we further optimize the general algorithm on curves with non-trivial automorphisms, which is suitable for BW13-P310 and BW19-P286. |
| Youssef El Housni, Consensys |
| Pairings in Rank-1 Constraint Systems Slides |
| Bilinear pairings have been used in different cryptographic applications and demonstrated to be a key building block for a plethora of constructions. In particular, some Succinct Non-interactive ARguments of Knowledge (SNARKs) have very short proofs and very fast verification thanks to a multi-pairing computation. This succinctness makes pairing-based SNARKs suitable for proof recursion, that is proofs verifying other proofs. In this scenario one requires to express efficiently a multi-pairing computation as a SNARK arithmetic circuit. Other compelling applications such as verifying Boneh–Lynn–Shacham (BLS) signatures or Kate–Zaverucha–Goldberg (KZG) polynomial commitment opening in a SNARK fall into the same requirement. The implementation of pairings is challenging but the literature has very detailed approaches on how to reach practical and optimized implementations in different contexts and for different target environments. In this talk we address the question of efficiently implementing a pairing as a SNARK arithmetic circuit. In this work, we consider Rank-1 Constraint Systems (R1CS), a widely used model to express SNARK statements. We implement our techniques in the gnark open-source ecosystem for BLS curves of embedding degree 12 and 24. |
Session III of III, Thursday, July 13, 10:30 am
| Emmanuel Fouotsa, University of Bamenda, Cameroon |
|---|
| X-Superoptimal Pairings on Some Elliptic Curves with Odd Prime Embedding Degrees Slides |
The choice of the elliptic curve for a given pairing based protocol is primordial. For many cryptosystems based on pairings such as group signatures and their variants (EPID, anonymous attestation, etc) or accumulators, operations in the first pairing group G of points of the elliptic curve is more predominant. At 128-bit security level two curves BW13-P310 and BW19-P286 with odd embedding degrees 13 and 19 suitable for super optimal pairing have been recommended for such pairing based protocols. But a prime embedding degree (k=13;19) eliminates some important optimisation for the pairing computation. However The Miller loop length of the superoptimal pairing is the half of that of the optimal ate pairing but involve more exponentiations that affect its efficiency. In this work, we successfully develop methods and construct algorithms to efficiently evaluate and avoid heavy exponentiations that affect the efficiency of the superoptimal pairing. This leads to the definition of new bilinear and non degenerate pairing on BW13-P310 and BW19-P286 called x-superoptimal pairing where its Miller loop is about 15.3 % and 39.8 % faster than the one of the optimal ate pairing previously computed on BW13-P310 and BW19-P286 respectively. |
| Georgios Fotiadis, Université du Luxembourg |
| A Short-List of Pairing-Friendly Curves Resistant to the Special TNFS at 192-Bit Security Level Slides |
| Selecting optimal elliptic curves for pairing-related scenarios is a complicated process. From a security point of view, one needs to consider the improved attacks of Kim-Barbulescu reducing the security level of extension fields of composite degree, hence forcing the scaling of the elliptic curve parameters so that the desired security level in the pairing-groups G1, G2, GT is preserved. From a performance perspective, depending on the application, different operations in G1, G2 and GT, such as the pairing computation, cofactor clearing, subgroup membership testing, or hashing to G1, G2, affect the efficiency of pairing-based protocols. For 128-bit security level, the BLS12 pairing-friendly elliptic curves dominate in application domains providing the best balance in terms of performance and security. For 192-bit security the situation is currently unclear. In this talk we go through new and existing TNFS-secure elliptic curves at 192-bit security, with embedding degrees from 16 to 28. We present a theoretical comparison of these curves in terms of performance and using SageMath and Magma prototype implementations for estimating cost in terms of multiplications over GF(p). Based on this theoretical comparison, we identify the most prominent pairing-friendly curves which are benchmarked in RELIC-optimized implementation considering not only the pairing computation itself, but also different group operations in the pairing groups G1, G2 and GT. |
| Marta Bellés Muños, Dusk Network, Pompeu Fabra University, Barcelona, Spain |
| Revisiting Cycles of Pairing-Friendly Elliptic Curves Slides |
| In this talk, I will present our work on 2-cycles of pairing-friendly elliptic curves of prime order. First, I will explore families of curves parameterized by polynomials, which is the only known method to produce prime-order curves, and then I will show that no 2-cycles can arise from the known families, except for those cycles already known. A consequence of this result is that it seems very unlikely that new pairing-friendly 2-cycles can be found, which has a direct impact on recursive composition of pairing-based proof systems. |
| Jean Gasnier, Université de Bordeaux, France |
| An Algebraic Point of View on the Generation of Pairing-Friendly Curves Slides |
| In 2010, Freeman Scott and Teske published a well-known taxonomy compiling the best known families of pairing-friendly elliptic curves. Since then, the research effort mostly shifted from the generation of pairing-friendly curves to the improvement of algorithms or the assessment of security parameters to resist the latest attacks on the discrete logarithm problem. Consequently, very few new families were discovered. However, the need of pairing-friendly curves of prime order in some new applications such as SNARKs has reignited the interest in the generation of pairing-friendly curves, with hope of finding families similar to the one discovered by Barreto and Naehrig. Building on the work of Kachisa, Schaefer and Scott, we show that some elements of extensions of cyclotomic field have a higher probability of generating a family of pairing friendly curves. We present a general framework which embraces the KSS families and many of the other families in the taxonomy paper, and provide an open-source SageMath implementation of our technique. We finally introduce a new family with embedding degree k=20 which we estimate to provide a faster pairing compared to KSS16 and KSS18 at the 192-bit security level. |
