Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 10/2023

29-05-2023

Fast subgroup membership testings for \(\mathbb {G}_1\), \(\mathbb {G}_2\) and \(\mathbb {G}_T\) on pairing-friendly curves

Authors: Yu Dai, Kaizhan Lin, Chang-An Zhao, Zijian Zhou

Published in: Designs, Codes and Cryptography | Issue 10/2023

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Pairing-based cryptographic protocols are typically vulnerable to small-subgroup attacks in the absence of protective measures. Subgroup membership testing is one of the feasible methods to address this security weakness. However, it generally causes an expensive computational cost on many pairing-friendly curves. Recently, Scott proposed efficient methods of subgroup membership testings for \(\mathbb {G}_1 \), \(\mathbb {G}_2 \) and \(\mathbb {G}_T \) on the BLS family. In this paper, we generalize these methods and show that the new techniques are applicable to a large class of pairing-friendly curves. In particular, we also confirm that our new methods lead to a significant speedup for subgroup membership testings on many popular pairing-friendly curves at high security level.
previous article New sets of non-orthogonal spreading sequences with low correlation and low PAPR using extended Boolean functions
next article On the exceptionality of rational APN functions
Literature
1.
2.
Aranha D.F., Pagnin E., Rodríguez-Henríquez F.: LOVE a pairing. In: Longa P., Ràfols C. (eds.) Progress in Cryptology—LATINCRYPT 2021, pp. 320–340. Springer, Cham (2021).CrossRef
3.
4.
Balasubramanian R., Koblitz N.: The improbability that an elliptic curve has subexponential discrete log problem under the Menezes–Okamoto–Vanstone algorithm. J. Cryptol. 11(2), 141–145 (1998).MathSciNetCrossRefMATH
5.
6.
Barreto P.S.L.M., Naehrig M.: Pairing-friendly elliptic curves of prime order. In: Preneel B., Tavares S. (eds.) Selected Areas in Cryptography—SAC 2005, pp. 319–331. Springer, Berlin (2006).
7.
Barreto P.S.L.M., Lynn B., Scott M.: On the selection of pairing-friendly groups. In: Matsui M., Zuccherato R.J. (eds.) Selected Areas in Cryptography—SAC 2003, pp. 17–25. Springer, Berlin (2004).
8.
Barreto P.S.L.M., Costello C., Misoczki R., Naehrig M., Pereira G.C.C.F., Zanon G.: Subgroup security in pairing-based cryptography. In: Lauter K., Rodríguez-Henríquez F. (eds.) Progress in Cryptology—LATINCRYPT 2015, pp. 245–265. Springer, Cham (2015).
9.
Boneh D., Franklin M.: Identity-based encryption from the Weil pairing. In: Kilian J. (ed.) Advances in Cryptology—CRYPTO 2001, pp. 213–229. Springer, Berlin (2001).
10.
Bosma W., Cannon J., Playoust C.: The Magma Algebra System. I. The user language. J. Symb. Comput. 24(3–4), 235–265 (1997). Computational algebra and number theory (London, 1993).
11.
Bowe S., Chiesa A., Green M., Miers I., Mishra P., Wu H.: Zexe: enabling decentralized private computation. In: 2020 IEEE Symposium on Security and Privacy (SP), pp. 947–964 (2020).
12.
Brickell E., Li J.: Enhanced Privacy ID: a direct anonymous attestation scheme with enhanced revocation capabilities. IEEE Trans. Depend. Secure Comput. 9(3), 345–360 (2012).CrossRef
13.
Brickell E., Camenisch J., Chen L.: Direct anonymous attestation. In: Proceedings of the 11th ACM Conference on Computer and Communications Security—CCS2004, pp. 132–145. Association for Computing Machinery, New York (2004).
14.
Budroni A., Pintore F.: Efficient Hash maps to \({\mathbb{G} }_2\) on BLS curves. Appl. Algebra Eng. Commun. Comput. 33(3), 261–281 (2022).CrossRefMATH
15.
Chen L., Cheng Z., Smart N.P.: Identity-based key agreement protocols from pairings. Int. J. Inf. Security 6(4), 213–241 (2007).CrossRef
16.
Clarisse R., Duquesne S., Sanders O.: Curves with Fast Computations in the First Pairing Group. In: Krenn S., Shulman H., Vaudenay S. (eds.) Cryptology and Network Security - CANS 2020, pp. 280–298. Springer, Cham (2020).
17.
Costello C., Fournet C., Howell J., Kohlweiss M., Kreuter B., Naehrig M., Parno B., Zahur S.: Geppetto: versatile verifiable computation. In: 2015 IEEE Symposium on Security and Privacy, pp. 253–270 (2015).
18.
19.
Diem C., Thomé E.: Index calculus in class groups of non-hyperelliptic curves of genus three. J. Cryptol. 21(4), 593–611 (2008).MathSciNetCrossRefMATH
20.
El Housni Y., Guillevic A.: Optimized and secure pairing-friendly elliptic curves suitable for one layer proof composition. In: Krenn S., Shulman H., Vaudenay S. (eds.) Cryptology and Network Security. Springer, Heidelberg (2020).MATH
21.
El Housni Y., Guillevic A., Piellard T.: Co-factor clearing and subgroup membership testing on pairing-friendly curves. In: Batina L., Daemen J. (eds.) Progress in Cryptology—AFRICACRYPT 2022, pp. 518–536. Springer, Cham (2022).CrossRef
22.
Enge A., Milan J.: Implementing cryptographic pairings at standard security levels. In: Chakraborty R.S., Matyas V., Schaumont P. (eds.) Security, Privacy, and Applied Cryptography Engineering—SPACE 2014, pp. 28–46. Springer, Cham (2014).
23.
24.
Fuentes-Castañeda L., Knapp E., Rodríguez-Henríquez F.: Faster Hashing to \({\mathbb{G} }_2\). In: Miri A., Vaudenay S. (eds.) Selected Areas in Cryptography—SAC 2011, pp. 412–430. Springer, Berlin (2012).
25.
Galbraith S.D.: Mathematics of Public Key Cryptography, version 2. Cambridge University Press, Cambridge (2018).
26.
27.
Galbraith S.D., Scott M.: Exponentiation in pairing-friendly groups using homomorphisms. In: Galbraith S.D., Paterson K.G. (eds.) Pairing-Based Cryptography—Pairing 2008, pp. 211–224. Springer, Berlin (2008).CrossRefMATH
28.
Galbraith S.D., Lin X., Scott M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. In: Joux A. (ed.) Advances in Cryptology—EUROCRYPT 2009, pp. 518–535. Springer, Berlin (2009).CrossRef
29.
Gallant R.P., Lambert R.J., Vanstone S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Kilian J. (ed.) Advances in Cryptology—CRYPTO 2001, pp. 190–200. Springer, Berlin (2001).CrossRef
30.
Gaudry P., Hess F., Smart N.P.: Constructive and destructive facets of Weil descent on elliptic curves. J. Cryptol. 15(1), 19–46 (2002).MathSciNetCrossRefMATH
31.
Granger R., Scott M.: Faster squaring in the cyclotomic subgroup of sixth degree extensions. In: Nguyen P.Q., Pointcheval D. (eds.) Public Key Cryptography—PKC 2010, pp. 209–223. Springer, Berlin (2010).CrossRef
32.
Guillevic A.: A short-list of pairing-friendly curves resistant to special TNFS at the 128-bit security level. In: Kiayias A., Kohlweiss M., Wallden P., Zikas V. (eds.) Public-Key Cryptography—PKC 2020, pp. 535–564. Springer, Cham (2020).CrossRef
33.
Hamburg M.: Decaf: eliminating cofactors through point compression. In: Gennaro R., Robshaw M. (eds.) Advances in Cryptology—CRYPTO 2015, pp. 705–723. Springer, Berlin (2015).
34.
35.
Hu Z., Longa P., Xu M.: Implementing the 4-dimensional GLV method on GLS elliptic curves with j-invariant 0. Des. Codes Cryptogr. 63(3), 331–343 (2012).MathSciNetCrossRefMATH
36.
Joux A.: A one round protocol for tripartite Diffie–Hellman. In: Bosma W. (ed.) Algorithmic Number Theory Symposium—ANTS 2000, pp. 385–393. Springer, Berlin (2000).
37.
Joye M., Neven G.: Identity-based Cryptography. Cryptology and Information Security. IOS Press, Amsterdam (2009).MATH
38.
Kachisa E.J., Schaefer E.F., Scott M.: Constructing Brezing–Weng pairing-friendly elliptic curves using elements in the cyclotomic field. In: Galbraith S.D., Paterson K.G. (eds.) Pairing-Based Cryptography—Pairing 2008, pp. 126–135. Springer, Berlin (2008).CrossRefMATH
39.
40.
Kim T., Kim S., Cheon J.H.: On the final exponentiation in Tate pairing computations. IEEE Trans. Inf. Theory 59(6), 4033–4041 (2013).MathSciNetCrossRefMATH
41.
Lim C.H., Lee P.J.: A key recovery attack on discrete log-based schemes using a prime order subgroup. In: Kaliski B.S. (ed.) Advances in Cryptology—CRYPTO 1997, pp. 249–263. Springer, Berlin (1997).
42.
Pohlig S., Hellman M.: An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Trans. Inf. Theory 24(1), 106–110 (1978).MathSciNetCrossRefMATH
43.
44.
45.
Scott M., Benger N., Charlemagne M., Dominguez Perez L.J., Kachisa E.J.: Fast Hashing to \({\mathbb{G} }_2\) on pairing-friendly curves. In: Shacham H., Waters B. (eds.) Pairing-Based Cryptography—Pairing 2009, pp. 102–113. Springer, Berlin (2009).CrossRefMATH
46.
Tian S., Li B., Wang K., Yu W.: Cover attacks for elliptic curves with cofactor two. Des. Codes Cryptogr. 86(11), 2451–2468 (2018).MathSciNetCrossRefMATH
47.
48.
Metadata
Title
Fast subgroup membership testings for , and on pairing-friendly curves
Authors
Yu Dai
Kaizhan Lin
Chang-An Zhao
Zijian Zhou
Publication date
29-05-2023
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 10/2023
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-023-01223-7

Other articles of this Issue 10/2023

Designs, Codes and Cryptography 10/2023 Go to the issue

OriginalPaper

Extremely primitive groups and linear spaces

OriginalPaper

The average density of K-normal elements over finite fields

OriginalPaper

On the exceptionality of rational APN functions

OriginalPaper

Projective tilings and full-rank perfect codes

OriginalPaper

Lattices in real quadratic fields and associated theta series arising from codes over and

OriginalPaper

Two properties of prefix codes and uniquely decodable codes

Premium Partner

    Image Credits