research-article

High-Performance Implementation of the Identity-Based Signature Scheme in IEEE P1363 on GPU

Authors:

Xinyi HuangAuthors Info & Claims

ACM Transactions on Embedded Computing Systems, Volume 22, Issue 2

Article No.: 25, Pages 1 - 35

https://doi.org/10.1145/3564784

Published: 24 January 2023 Publication History

Abstract

Identity-based cryptography is proposed to solve the complicated certificate management of traditional public-key cryptography. The pairing computation and high-level tower extension field arithmetic turn out to be the performance bottleneck of pairing-based signature schemes. Graphics processing units have been increasingly popular for general-purpose computing in recent years. They have shown a lot of promise in speeding up cryptographic schemes such as AES, RSA, and ECDSA. However, to our knowledge, the research on parallel implementation of pairings and identity-based cryptographic schemes on graphics processing units is somewhat outdated. Therefore, in this article, we implement the identity-based signature scheme in the IEEE P1363 Standard on a modern NVIDIA RTX 3060 card. We convert the pairing computation in signature verification into a product of pairings with fixed arguments and therefore avoid the scalar multiplication in 𝔾₂. Then we employ the precomputation technique to improve the elliptic curve scalar multiplication, exponentiation in \(\mathbb {F}_{p^{12}}\) and the pairing computation. We also apply PTX ISA to multiple-precision arithmetic. Experiments demonstrate that our implementation can perform 43,856/46,753/39,798 pairings/sec for the Optimal Ate pairing, the pairing with a fixed argument, and two pairings with fixed arguments, respectively. Peak throughputs of signature generation and verification can achieve 322.6 and 40.6 kops/sec over the BN254 curve.

References

[1]

Diego F. Aranha, Paulo S. L. M. Barreto, Patrick Longa, and Jefferson E. Ricardini. 2013. The realm of the pairings. In Selected Areas in Cryptography (SAC’13). Springer, Berlin, Germany, 3–25.

Digital Library

[2]

Diego F. Aranha, Koray Karabina, Patrick Longa, Catherine H. Gebotys, and Julio López. 2011. Faster explicit formulas for computing pairings over ordinary curves. In Advances in Cryptology (EUROCRYPT’11). Springer, Berlin, Germany, 48–68.

[3]

Tair Askar, Bekdaulet Shukirgaliyev, Martin Lukac, and Ernazar Abdikamalov. 2021. Evaluation of pseudo-random number generation on GPU cards. Computation 9, 12 (2021), 142.

[4]

Reza Azarderakhsh, Dieter Fishbein, Gurleen Grewal, Shi Hu, David Jao, Patrick Longa, and Rajeev Verma. 2015. Fast software implementations of bilinear pairings. IEEE Transactions on Dependable and Secure Computing 14, 6 (2015), 605–619.

[5]

Milad Bahadori and Kimmo Järvinen. 2020. Compact and programmable yet high-performance SoC architecture for cryptographic pairings. In Proceedings of the 2020 30th International Conference on Field-Programmable Logic and Applications (FPL’20). IEEE, Los Alamitos, CA, 176–184.

[6]

Dirk Balfanz, Glenn Durfee, Narendar Shankar, Diana Smetters, Jessica Staddon, and Hao-Chi Wong. 2003. Secret handshakes from pairing-based key agreements. In Proceedings of the 2003 Symposium on Security and Privacy.IEEE, Los Alamitos, CA, 180–196.

[7]

Paulo S. L. M. Barreto, Benoît Libert, Noel McCullagh, and Jean-Jacques Quisquater. 2005. Efficient and provably-secure identity-based signatures and signcryption from bilinear maps. In Advances in Cryptology (ASIACRYPT’05). Springer, Berlin, Germany, 515–532.

Digital Library

[8]

Paulo S. L. M. Barreto and Michael Naehrig. 2005. Pairing-friendly elliptic curves of prime order. In Selected Areas in Cryptography (SAC’05). Springer, Berlin, Germany, 319–331.

Digital Library

[9]

Daniel J. Bernstein, Tien-Ren Chen, Chen-Mou Cheng, Tanja Lange, and Bo-Yin Yang. 2009. ECM on graphics cards. In Advances in Cryptology (EUROCRYPT’09). Springer, Berlin, Germany, 483–501.

Digital Library

[10]

Jean-Luc Beuchat, Jorge E. González-Díaz, Shigeo Mitsunari, Eiji Okamoto, Francisco Rodríguez-Henríquez, and Tadanori Teruya. 2011. High-speed software implementation of the Optimal Ate pairing over Barreto–Naehrig curves. In Pairing-Based Cryptography (Pairing’10). Springer, Berlin, Germany, 21–39.

[11]

Dan Boneh and Xavier Boyen. 2004. Efficient selective-ID secure identity-based encryption without random oracles. In Advances in Cryptology (EUROCRYPT’04). Springer, Berlin, Germany, 223–238.

[12]

Dan Boneh and Xavier Boyen. 2004. Short signatures without random oracles. In Advances in Cryptology (EUROCRYPT’04). Springer, Berlin, Germany, 56–73.

[13]

Dan Boneh and Xavier Boyen. 2008. Short signatures without random oracles and the SDH assumption in bilinear groups. Journal of Cryptology 21, 2 (April2008), 149–177.

Digital Library

[14]

Dan Boneh and Matt Franklin. 2001. Identity-based encryption from the Weil pairing. In Advances in Cryptology (CRYPTO’01). Springer, Berlin, Germany, 213–229.

[15]

Dan Boneh, Ben Lynn, and Hovav Shacham. 2001. Short signatures from the Weil pairing. In Advances in Cryptology (ASIACRYPT’01). Springer, Berlin, Germany, 514–532.

[16]

Utsab Bose, Anup Kumar Bhattacharya, and Abhijit Das. 2013. GPU-based implementation of 128-bit secure eta pairing over a binary field. In Progress in Cryptology (AFRICACRYPT’13). Springer, Berlin, Germany, 26–42.

[17]

Jae Cha Choon and Jung Hee Cheon. 2003. An identity-based signature from gap Diffie-Hellman groups. In Public Key Cryptography (PKC’03). Springer, Berlin, Germany, 18–30.

[18]

Jaewook Chung and M. Anwar Hasan. 2007. Asymmetric squaring formulae. In Proceedings of the 18th IEEE Symposium on Computer Arithmetic (ARITH’07). IEEE, Los Alamitos, CA, 113–122.

Digital Library

[19]

Shujie Cui, Johann Großschädl, Zhe Liu, and Qiuliang Xu. 2014. High-speed elliptic curve cryptography on the NVIDIA GT200 graphics processing unit. In Information Security Practice and Experience (ISPEC’14). Springer, Berlin, Germany, 202–216.

Digital Library

[20]

Augusto Jun Devegili, Michael Scott, and Ricardo Dahab. 2007. Implementing cryptographic pairings over Barreto-Naehrig curves. In Pairing-Based Cryptography (Pairing’07). Springer, Berlin, Germany, 197–207.

[21]

Jiankuo Dong, Guang Fan, Fangyu Zheng, Jingqiang Lin, and Fu Xiao. 2021. TX-RSA: A high performance RSA implementation scheme on NVIDIA Tegra X2. In Wireless Algorithms, Systems, and Applications (WASA’21). Springer, Berlin, Germany, 210–222.

Digital Library

[22]

Jiankuo Dong, Fangyu Zheng, Jingqiang Lin, Zhe Liu, Fu Xiao, and Guang Fan. 2022. EC-ECC: Accelerating elliptic curve cryptography for edge computing on embedded GPU TX2. ACM Transactions on Embedded Computing Systems 21, 2 (March2022), 1–25.

Digital Library

[23]

Gerhard Frey and Hans-Georg Rück. 1994. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Mathematics of Computation 62, 206 (1994), 865–874.

[24]

Lili Gao, Fangyu Zheng, Rong Wei, Jiankuo Dong, Niall Emmart, Yuan Ma, Jingqiang Lin, and Charles Weems. 2021. DPF-ECC: A framework for efficient ECC with double precision floating-point computing power. IEEE Transactions on Information Forensics and Security 16 (July2021), 3988–4002.

[25]

Craig Gentry and Zulfikar Ramzan. 2006. Identity-based aggregate signatures. In Public Key Cryptography (PKC’06). Springer, Berlin, Germany, 257–273.

Digital Library

[26]

Robert Granger, Florian Hess, Roger Oyono, Nicolas Thériault, and Frederik Vercauteren. 2007. Ate pairing on hyperelliptic curves. In Advances in Cryptology (EUROCRYPT’07). Springer, Berlin, Germany, 430–447.

Digital Library

[27]

Robert Granger and Michael Scott. 2010. Faster squaring in the cyclotomic subgroup of sixth degree extensions. In Public Key Cryptography (PKC’10). Springer, Berlin, Germany, 209–223.

Digital Library

[28]

Jens Groth. 2016. On the size of pairing-based non-interactive arguments. In Advances in Cryptology (EUROCRYPT’16). Springer, Berlin, Germany, 305–326.

[29]

Darrel Hankerson, Alfred J. Menezes, and Scott Vanstone. 2006. Guide to Elliptic Curve Cryptography. Springer Science & Business Media, New York, NY.

Digital Library

[30]

Florian Hess. 2002. Efficient identity based signature schemes based on pairings. In Selected Areas in Cryptography (SAC 2002). Springer, Berlin, Germany, 310–324.

[31]

Anatolii Alekseevich Karatsuba and Yu P. Ofman. 1962. Multiplication of many-digital numbers by automatic computers. In Doklady Akademii Nauk (Proceedings of the USSR Academy of Sciences). Russian Academy of Sciences, Moscow, Russia, 293–294.

[32]

C. Kaya Koc, Tolga Acar, and Burton S. Kaliski. 1996. Analyzing and comparing Montgomery multiplication algorithms. IEEE Micro 16, 3 (1996), 26–33.

Digital Library

[33]

Arthur Lavice, Nadia El Mrabet, Alexandre Berzati, Jean-Baptiste Rigaud, and Julien Proy. 2021. Hardware implementations of pairings at updated security levels. In Smart Card Research and Advanced Applications (CARDIS’21). Springer, Berlin, Germany, 189–209.

Digital Library

[34]

Eunjeong Lee, Hyang-Sook Lee, and Cheol-Min Park. 2009. Efficient and generalized pairing computation on abelian varieties. IEEE Transactions on Information Theory 55, 4 (2009), 1793–1803.

Digital Library

[35]

Jun-Jie Liu, Ken K. T. Tsang, and Yu-Hui Deng. 2021. Improved parallel RSA cryptosystem with GPU for network information security. In Advances in Natural Computation, Fuzzy Systems, and Knowledge Discovery (ICNC-FSKD’20). Springer, Berlin, Germany, 1061–1068.

[36]

Alfred J. Menezes, Jonathan Katz, Paul C. van Oorschot, and Scott A. Vanstone. 1996. Handbook of Applied Cryptography. CRC Press, Boca Raton, FL.

Digital Library

[37]

Peter L. Montgomery. 1985. Modular multiplication without trial division. Mathematics of Computation 44, 170 (1985), 519–521.

[38]

Michael Naehrig, Ruben Niederhagen, and Peter Schwabe. 2010. New software speed records for cryptographic pairings. In Progress in Cryptology (LATINCRYPT’10). Springer, Berlin, Germany, 109–123.

[39]

NVIDIA. 2022. cuRAND Library. Retrieved February 22, 2022 from https://docs.nvidia.com/cuda/curand/index.html.

[40]

NVIDIA. 2022. Parallel Thread Execution ISA Version 7.6. Retrieved February 22, 2022 from https://docs.nvidia.com/cuda/parallel-thread-execution/index.html.

[41]

Antoine Joux. 2000. A one round protocol for tripartite Diffie-Hellman. In Algorithmic Number Theory (ANTS’00). Springer, Berlin, Germany, 385–393.

[42]

Holger Orup. 1995. Simplifying quotient determination in high-radix modular multiplication. In Proceedings of the 12th Symposium on Computer Arithmetic.IEEE, Los Alamitos, CA, 193–199.

[43]

Wuqiong Pan, Fangyu Zheng, Yuan Zhao, Wen-Tao Zhu, and Jiwu Jing. 2016. An efficient elliptic curve cryptography signature server with GPU acceleration. IEEE Transactions on Information Forensics and Security 12, 1 (2016), 111–122.

Digital Library

[44]

Kenneth G. Paterson. 2002. ID-based signatures from pairings on elliptic curves. Electronics Letters 38, 18 (2002), 1025–1026.

[45]

Kenneth G. Paterson and Jacob C. N. Schuldt. 2006. Efficient identity-based signatures secure in the standard model. In Proceedings of the Australasian Conference on Information Security and Privacy (ACISP’06). 207–222.

Digital Library

[46]

Shi Pu and Jyh-Charn Liu. 2013. EAGL: An elliptic curve arithmetic GPU-based library for bilinear pairing. In Pairing-Based Cryptography (Pairing’13). Springer, Berlin, Germany, 1–19.

Digital Library

[47]

Shuming Qiu, Ding Wang, Guoai Xu, and Saru Kumari. 2020. Practical and provably secure three-factor authentication protocol based on extended chaotic-maps for mobile lightweight devices. IEEE Transactions on Dependable and Secure Computing 19, 2 (2020), 1338–1351.

[48]

Michael Scott. 2019. Pairing Implementation Revisited. Retrieved October 5, 2022 from https://eprint.iacr.org/2019/077.pdf.

[49]

Michael Scott, Naomi Benger, Manuel Charlemagne, Luis J. Dominguez Perez, and Ezekiel J. Kachisa. 2009. On the final exponentiation for calculating pairings on ordinary elliptic curves. In Pairing-Based Cryptography (Pairing’09). Springer, Berlin, Germany, 78–88.

Digital Library

[50]

Adi Shamir. 1984. Identity-based cryptosystems and signature schemes. In Advances in Cryptology (CRYPTO’84). Springer, Berlin, Germany, 47–53.

[51]

Brian Smith. 2017. The Most Efficient Known Addition Chains for Field Element & Scalar Inversion for the Most Popular & Most Unpopular Elliptic Curves. Retrieved February 22, 2022 from https://briansmith.org/ecc-inversion-addition-chains-01.

[52]

Robert Szerwinski and Tim Güneysu. 2008. Exploiting the power of GPUs for asymmetric cryptography. In Cryptographic Hardware and Embedded Systems (CHES’08). Springer, Berlin, Germany, 79–99.

Digital Library

[53]

Jitendra V. Tembhurne and S. R. Sathe. 2016. RSA public key acceleration on CUDA GPU. In Artificial Intelligence and Evolutionary Computations in Engineering Systems (ICAIECES’15). Springer, Berlin, Germany, 365–375.

[54]

Frederik Vercauteren. 2009. Optimal pairings. IEEE Transactions on Information Theory 56, 1 (2009), 455–461.

Digital Library

[55]

A. Tengfei Wang, B. Wei Guo, and C. Jizeng Wei. 2019. Highly-parallel hardware implementation of Optimal Ate pairing over Barreto-Naehrig curves. Integration 64 (2019), 13–21.

[56]

Ding Wang and Ping Wang. 2016. Two birds with one stone: Two-factor authentication with security beyond conventional bound. IEEE Transactions on Dependable and Secure Computing 15, 4 (2016), 708–722.

Digital Library

[57]

André Weil. 1940. Sur les fonctions algébriquesa corps de constantes fini. Comptes Rendus de l’Académie des Sciences (Paris) 210, 592-594 (1940), 149.

[58]

William Whyte, Don Johnson, and Kendall Ananyi. 2013. IEEE standard for identity-based cryptographic techniques using pairings. IEEE Std 1363.3-2013 (2013), 1–151.

[59]

Yue Xing, Bo-Yuan Huang, Aarti Gupta, and Sharad Malik. 2018. A formal instruction-level GPU model for scalable verification. In Proceedings of the International Conference on Computer-Aided Design (ICCAD’18). ACM, New York, NY, 1–8.

Digital Library

[60]

Yang Yang, Zhi Guan, Huiping Sun, and Zhong Chen. 2015. Accelerating RSA with fine-grained parallelism using GPU. In Information Security Practice and Experience (ISPEC’15). Springer, Berlin, Germany, 454–468.

[61]

Eric Zavattoni, Luis J. Dominguez Perez, Shigeo Mitsunari, Ana H. Sánchez-Ramırez, Tadanori Teruya, and Francisco Rodríguez-Henríquez. 2014. Software implementation of an attribute-based encryption scheme. IEEE Transactions on Computers 64, 5 (2014), 1429–1441.

Digital Library

[62]

Fangyu Zheng, Wuqiong Pan, Jingqiang Lin, Jiwu Jing, and Yuan Zhao. 2014. Exploiting the potential of GPUs for modular multiplication in ECC. In Information Security Applications (WISA’14). Springer, Berlin, Germany, 295–306.

Cited By

Xu WMa HZhang R(2024)GAPS: GPU-accelerated processing service for SM9Cybersecurity10.1186/s42400-024-00217-97:1Online publication date: 2-Oct-2024
https://doi.org/10.1186/s42400-024-00217-9
Sakamoto JFujimoto DAnzai RYoshida NMatsumoto T(2024)High-Throughput Bilinear Pairing Processor for Server-Side FPGA ApplicationsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2024.340216432:8(1498-1511)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVLSI.2024.3402164

Index Terms

High-Performance Implementation of the Identity-Based Signature Scheme in IEEE P1363 on GPU
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
      1. Digital signatures

Recommendations

Forgery attacks on Kang et al.'s identity-based strong designated verifier signature scheme and its improvement with security proof

Recently, Kang et al. proposed a new identity-based strong designated verifier signature scheme (ID-SDVS) and identity-based designated verifier proxy signature scheme (ID-DVPS). They claimed that their schemes are unforgeable. However, we found out ...
Tightly Secure Identity-Based Signature from Cryptographic Group Actions
Provable and Practical Security
Abstract
Identity-based Signatures (IBS) are a form of digital signature scheme that enables the generation and verification of signatures based on a user’s identity, such as an email address, social security number, or any other unique identifier. Recent ...
A novel identity-based strong designated verifier signature scheme

Unlike ordinary digital signatures, a designated verifier signature scheme makes it possible for a signer to convince a designated verifier that she has signed a message in such a way that the designated verifier cannot transfer the signature to a third ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 22, Issue 2

March 2023

560 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/3572826

Editor:
Tulika Mitra
National University of Singapore, Singapore

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 24 January 2023

Online AM: 27 September 2022

Accepted: 19 September 2022

Revised: 20 August 2022

Received: 31 May 2022

Published in TECS Volume 22, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

Major Scientific and Technological Innovation Project of Shandong Province
National Natural Science Foundation of China
Special Project on Science and Technology Program of Hubei Provience
Natural Science Foundation of Hubei Province
Wuhan Municipal Science and Technology Project

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
549
Total Downloads

Downloads (Last 12 months)164
Downloads (Last 6 weeks)12

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xu WMa HZhang R(2024)GAPS: GPU-accelerated processing service for SM9Cybersecurity10.1186/s42400-024-00217-97:1Online publication date: 2-Oct-2024
https://doi.org/10.1186/s42400-024-00217-9
Sakamoto JFujimoto DAnzai RYoshida NMatsumoto T(2024)High-Throughput Bilinear Pairing Processor for Server-Side FPGA ApplicationsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2024.340216432:8(1498-1511)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TVLSI.2024.3402164

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Figures

Tables

Media

View full text|Download PDF

View Issue’s Table of Contents