Skip to main content

04.10.2023 | Original Paper

Batch point compression in the context of advanced pairing-based protocols

verfasst von: Dmitrii Koshelev

Erschienen in: Applicable Algebra in Engineering, Communication and Computing

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper continues previous ones about compression of points on elliptic curves \(E_b\!: y^2 = x^3 + b\) (with j-invariant 0) over a finite field \(\mathbb {F}_{\!q}\) of characteristic \(p > 3\). It is shown in detail how any two (resp., three) points from \(E_b(\mathbb {F}_{\!q})\) can be quickly compressed to two (resp., three) elements of \(\mathbb {F}_{\!q}\) (apart from a few auxiliary bits) in such a way that the corresponding decompression stage requires to extract only one cubic (resp., sextic) root in \(\mathbb {F}_{\!q}\). As a result, for many fields \(\mathbb {F}_{\!q}\) occurring in practice, the new compression-decompression methods are more efficient than the classical one with the two (resp., three) x or y coordinates of the points, which extracts two (resp., three) roots in \(\mathbb {F}_{\!q}\). As a by-product, it is also explained how to sample uniformly at random two (resp., three) “independent” \(\mathbb {F}_{\!q}\)-points on \(E_b\) essentially at the cost of only one cubic (resp., sextic) root in \(\mathbb {F}_{\!q}\). Finally, the cases of four and more points from \(E_b(\mathbb {F}_{\!q})\) are commented on as well.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Zurück zum Zitat 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. Lecture Notes in Computer Science, vol. 12912, pp. 320–340. Springer, Cham (2021)CrossRef 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. Lecture Notes in Computer Science, vol. 12912, pp. 320–340. Springer, Cham (2021)CrossRef
2.
Zurück zum Zitat Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Scalable zero knowledge via cycles of elliptic curves. In: Garay, J.A., Gennaro, R. (eds.) Advances in Cryptology - CRYPTO 2014. Lecture Notes in Computer Science, vol. 8617, pp. 276–294. Springer, Berlin, Heidelberg (2014)CrossRef Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Scalable zero knowledge via cycles of elliptic curves. In: Garay, J.A., Gennaro, R. (eds.) Advances in Cryptology - CRYPTO 2014. Lecture Notes in Computer Science, vol. 8617, pp. 276–294. Springer, Berlin, Heidelberg (2014)CrossRef
3.
Zurück zum Zitat Bernstein, D.J., Yang, B.Y.: Fast constant-time GCD computation and modular inversion. IACR Trans. Cryptogr. Hardware Embedd. Syst. 2019(3), 340–398 (2019)CrossRef Bernstein, D.J., Yang, B.Y.: Fast constant-time GCD computation and modular inversion. IACR Trans. Cryptogr. Hardware Embedd. Syst. 2019(3), 340–398 (2019)CrossRef
4.
Zurück zum Zitat Bernstein, D.J., Duif, N., Lange, T., Schwabe, P., Yang, B.Y.: High-speed high-security signatures. J. Cryptogr. Eng. 2(2), 77–89 (2012)CrossRefMATH Bernstein, D.J., Duif, N., Lange, T., Schwabe, P., Yang, B.Y.: High-speed high-security signatures. J. Cryptogr. Eng. 2(2), 77–89 (2012)CrossRefMATH
5.
Zurück zum Zitat Boneh, D., Goh, E.J., Nissim, K.: Evaluating \(2\)-DNF formulas on ciphertexts. In: Kilian, J. (ed.) Theory of Cryptography. TCC 2005. Lecture Notes in Computer Science, vol. 3378, pp. 325–341. Springer, Berlin, Heidelberg (2005) Boneh, D., Goh, E.J., Nissim, K.: Evaluating \(2\)-DNF formulas on ciphertexts. In: Kilian, J. (ed.) Theory of Cryptography. TCC 2005. Lecture Notes in Computer Science, vol. 3378, pp. 325–341. Springer, Berlin, Heidelberg (2005)
6.
Zurück zum Zitat Boneh, D., Sahai, A., Waters, B.: Fully collusion resistant traitor tracing with short ciphertexts and private keys. In: Vaudenay, S. (ed.) Advances in Cryptology - EUROCRYPT 2006. Lecture Notes in Computer Science, vol. 4004, pp. 573–592. Springer, Berlin, Heidelberg (2006)CrossRef Boneh, D., Sahai, A., Waters, B.: Fully collusion resistant traitor tracing with short ciphertexts and private keys. In: Vaudenay, S. (ed.) Advances in Cryptology - EUROCRYPT 2006. Lecture Notes in Computer Science, vol. 4004, pp. 573–592. Springer, Berlin, Heidelberg (2006)CrossRef
7.
Zurück zum Zitat Botrel, G., El Housni, Y.: Faster Montgomery multiplication and multi-scalar-multiplication for SNARKs. IACR Trans. Cryptogr. Hardware Embedd. Syst. (TCHES) 2023(3), 504–521 (2023)CrossRef Botrel, G., El Housni, Y.: Faster Montgomery multiplication and multi-scalar-multiplication for SNARKs. IACR Trans. Cryptogr. Hardware Embedd. Syst. (TCHES) 2023(3), 504–521 (2023)CrossRef
8.
Zurück zum Zitat Catanese, F., Oguiso, K., Verra, A.: On the unirationality of higher dimensional Ueno-type manifolds. Rev. Roumaine Math. Pures Appl. 60(3), 337–353 (2015)MathSciNetMATH Catanese, F., Oguiso, K., Verra, A.: On the unirationality of higher dimensional Ueno-type manifolds. Rev. Roumaine Math. Pures Appl. 60(3), 337–353 (2015)MathSciNetMATH
9.
Zurück zum Zitat Chatterjee, S., Hankerson, D., Menezes, A.: On the efficiency and security of pairing-based protocols in the type \(1\) and type \(4\) settings. In: Hasan, M.A., Helleseth, T. (eds.) Arithmetic of Finite Fields. WAIFI 2010. Lecture Notes in Computer Science, vol. 6087, pp. 114–134. Springer, Berlin, Heidelberg (2010) Chatterjee, S., Hankerson, D., Menezes, A.: On the efficiency and security of pairing-based protocols in the type \(1\) and type \(4\) settings. In: Hasan, M.A., Helleseth, T. (eds.) Arithmetic of Finite Fields. WAIFI 2010. Lecture Notes in Computer Science, vol. 6087, pp. 114–134. Springer, Berlin, Heidelberg (2010)
10.
Zurück zum Zitat 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. CANS 2020. Lecture Notes in Computer Science, vol. 12579, pp. 259–279. Springer, Cham (2020) 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. CANS 2020. Lecture Notes in Computer Science, vol. 12579, pp. 259–279. Springer, Cham (2020)
11.
Zurück zum Zitat El Mrabet, N., Joye, M. (eds.): Guide to Pairing-Based Cryptography. Cryptography and Network Security Series, Chapman and Hall/CRC, New York (2017) El Mrabet, N., Joye, M. (eds.): Guide to Pairing-Based Cryptography. Cryptography and Network Security Series, Chapman and Hall/CRC, New York (2017)
13.
Zurück zum Zitat Fan, X., Otemissov, A., Sica, F., Sidorenko, A.: Multiple point compression on elliptic curves. Des. Codes Crypt. 83(3), 565–588 (2017)MathSciNetCrossRefMATH Fan, X., Otemissov, A., Sica, F., Sidorenko, A.: Multiple point compression on elliptic curves. Des. Codes Crypt. 83(3), 565–588 (2017)MathSciNetCrossRefMATH
14.
Zurück zum Zitat Freeman, D.M.: Converting pairing-based cryptosystems from composite-order groups to prime-order groups. In: Gilbert, H. (ed.) Advances in Cryptology - EUROCRYPT 2010. Lecture Notes in Computer Science, vol. 6110, pp. 44–61. Springer, Berlin, Heidelberg (2010)CrossRef Freeman, D.M.: Converting pairing-based cryptosystems from composite-order groups to prime-order groups. In: Gilbert, H. (ed.) Advances in Cryptology - EUROCRYPT 2010. Lecture Notes in Computer Science, vol. 6110, pp. 44–61. Springer, Berlin, Heidelberg (2010)CrossRef
15.
Zurück zum Zitat Galbraith, S.D.: Mathematics of Public Key Cryptography. Cambridge University Press, New York (2012)CrossRefMATH Galbraith, S.D.: Mathematics of Public Key Cryptography. Cambridge University Press, New York (2012)CrossRefMATH
16.
Zurück zum Zitat Groth, J.: On the size of pairing-based non-interactive arguments. In: Fischlin, M., Coron, J.S. (eds.) Advances in Cryptology - EUROCRYPT 2016. Lecture Notes in Computer Science, vol. 9665, pp. 305–326. Springer, Berlin, Heidelberg (2016)CrossRef Groth, J.: On the size of pairing-based non-interactive arguments. In: Fischlin, M., Coron, J.S. (eds.) Advances in Cryptology - EUROCRYPT 2016. Lecture Notes in Computer Science, vol. 9665, pp. 305–326. Springer, Berlin, Heidelberg (2016)CrossRef
17.
Zurück zum Zitat Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N. (ed.) Advances in Cryptology - EUROCRYPT 2008. Lecture Notes in Computer Science, vol. 4965, pp. 415–432. Springer, Berlin, Heidelberg (2008)CrossRef Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N. (ed.) Advances in Cryptology - EUROCRYPT 2008. Lecture Notes in Computer Science, vol. 4965, pp. 415–432. Springer, Berlin, Heidelberg (2008)CrossRef
18.
Zurück zum Zitat Guillevic, A.: Comparing the pairing efficiency over composite-order and prime-order elliptic curves. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) Applied Cryptography and Network Security. ACNS 2013. Lecture Notes in Computer Science, vol. 7954, pp. 357–372. Springer, Berlin, Heidelberg (2013) Guillevic, A.: Comparing the pairing efficiency over composite-order and prime-order elliptic curves. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) Applied Cryptography and Network Security. ACNS 2013. Lecture Notes in Computer Science, vol. 7954, pp. 357–372. Springer, Berlin, Heidelberg (2013)
19.
Zurück zum Zitat Hartshorne, R.: Algebraic Geometry, Graduate Texts in Mathematics, vol. 52. Springer, New York, 8 edition (1997) Hartshorne, R.: Algebraic Geometry, Graduate Texts in Mathematics, vol. 52. Springer, New York, 8 edition (1997)
22.
23.
Zurück zum Zitat Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: Abe, M. (ed.) Advances in Cryptology - ASIACRYPT 2010. Lecture Notes in Computer Science, vol. 6477, pp. 177–194. Springer, Berlin, Heidelberg (2010)CrossRef Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: Abe, M. (ed.) Advances in Cryptology - ASIACRYPT 2010. Lecture Notes in Computer Science, vol. 6477, pp. 177–194. Springer, Berlin, Heidelberg (2010)CrossRef
24.
Zurück zum Zitat Khabbazian, M., Gulliver, T.A., Bhargava, V.K.: Double point compression with applications to speeding up random point multiplication. IEEE Trans. Comput. 56(3), 305–313 (2007)MathSciNetCrossRefMATH Khabbazian, M., Gulliver, T.A., Bhargava, V.K.: Double point compression with applications to speeding up random point multiplication. IEEE Trans. Comput. 56(3), 305–313 (2007)MathSciNetCrossRefMATH
29.
Zurück zum Zitat Koshelev, D.: Faster point compression for elliptic curves of \(j\)-invariant \(0\). Math. Aspects Cryptogr. 12(4), 115–123 (2021)MathSciNetMATH Koshelev, D.: Faster point compression for elliptic curves of \(j\)-invariant \(0\). Math. Aspects Cryptogr. 12(4), 115–123 (2021)MathSciNetMATH
30.
Zurück zum Zitat Koshelev, D.: New point compression method for elliptic \(\mathbb{F} _{\!q^2}\)-curves of \(j\)-invariant \(0\). Finite Fields Appl. 69, 101774 (2021)MathSciNetCrossRefMATH Koshelev, D.: New point compression method for elliptic \(\mathbb{F} _{\!q^2}\)-curves of \(j\)-invariant \(0\). Finite Fields Appl. 69, 101774 (2021)MathSciNetCrossRefMATH
31.
Zurück zum Zitat Koshelev, D.: Indifferentiable hashing to ordinary elliptic \(\mathbb{F} _{\!q}\)-curves of \(j = 0\) with the cost of one exponentiation in \(\mathbb{F} _{\!q}\). Des. Codes Crypt. 90(3), 801–812 (2022)MathSciNetCrossRefMATH Koshelev, D.: Indifferentiable hashing to ordinary elliptic \(\mathbb{F} _{\!q}\)-curves of \(j = 0\) with the cost of one exponentiation in \(\mathbb{F} _{\!q}\). Des. Codes Crypt. 90(3), 801–812 (2022)MathSciNetCrossRefMATH
32.
Zurück zum Zitat Lang, S.: Algebra, Graduate Texts in Mathematics, vol. 211, 3rd edn. Springer, New York (2002) Lang, S.: Algebra, Graduate Texts in Mathematics, vol. 211, 3rd edn. Springer, New York (2002)
34.
Zurück zum Zitat Oguiso, K., Truong, T.T.: Explicit examples of rational and Calabi-Yau threefolds with primitive automorphisms of positive entropy. J. Math. Sci. Univ. Tokyo 22, 361–385 (2015)MathSciNetMATH Oguiso, K., Truong, T.T.: Explicit examples of rational and Calabi-Yau threefolds with primitive automorphisms of positive entropy. J. Math. Sci. Univ. Tokyo 22, 361–385 (2015)MathSciNetMATH
35.
Zurück zum Zitat Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) Advances in Cryptology - CRYPTO 1991. Lecture Notes in Computer Science, vol. 576, pp. 129–140. Springer, Berlin, Heidelberg (1992) Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) Advances in Cryptology - CRYPTO 1991. Lecture Notes in Computer Science, vol. 576, pp. 129–140. Springer, Berlin, Heidelberg (1992)
37.
Zurück zum Zitat Rubin, K., Silverberg, A.: Compression in finite fields and torus-based cryptography. SIAM J. Comput. 37(5), 1401–1428 (2008)MathSciNetCrossRefMATH Rubin, K., Silverberg, A.: Compression in finite fields and torus-based cryptography. SIAM J. Comput. 37(5), 1401–1428 (2008)MathSciNetCrossRefMATH
39.
40.
Zurück zum Zitat Wahby, R.S., Boneh, D.: Fast and simple constant-time hashing to the BLS12-381 elliptic curve. IACR Trans. Cryptogr. Hardware Embedd. Syst. 2019(4), 154–179 (2019)CrossRef Wahby, R.S., Boneh, D.: Fast and simple constant-time hashing to the BLS12-381 elliptic curve. IACR Trans. Cryptogr. Hardware Embedd. Syst. 2019(4), 154–179 (2019)CrossRef
Metadaten
Titel
Batch point compression in the context of advanced pairing-based protocols
verfasst von
Dmitrii Koshelev
Publikationsdatum
04.10.2023
Verlag
Springer Berlin Heidelberg
Erschienen in
Applicable Algebra in Engineering, Communication and Computing
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-023-00625-3