IP Library › Granted Patent US 12,452,084
Granted Patent B2
US 12,452,084 · App. 17/739,036 · Granted Oct 21, 2025

Lightweight post-quantum authentication

Inventors: Rouzbeh Behnia (Tampa, FL); Attila Altay Yavuz (Tampa, FL)
Assignee: UNIVERSITY OF SOUTH FLORIDA
H04L9/3268H04L9/0869H04L9/321H04L9/3236
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,452,084
App. No.
17/739,036
Granted
Oct 21, 2025
Kind
B2
Abstract

A method, system, or apparatus for generating and/or verifying a signature on a message is provided. The method, system, or apparatus at a signer may include receiving a message, generating a security parameter, generating at least two seeds corresponding to at least two servers based on the security parameter, transmitting the at least two seeds to each server of the at least two servers, determine a private key based on the security parameter or the at least two seeds, and generating, on the message, a signature based on the private key. The method, system, or apparatus at a verifier may include receiving, from a signer, a signature on a message, obtaining at least two partial public keys, determining a full public key based on the at least two partial public keys, and authenticating the signature on the message based on the full public key. Other aspects, embodiments, and features are also claimed and described.

Claims (67)

1. A method for lightweight post-quantum authentication comprising:

receiving a message at a signer device;

generating a security parameter;

generating a number of seeds associated with the signer device, the number of seeds being at least two seeds and corresponding in number to a set of at least two servers, based on the security parameter;

transmitting the at least two seeds to each server of the at least two servers;

determining via the signer device a private key based on the security parameter or the at least two seeds, the private key corresponding to a public key generated in a distributed manner by the at least two servers based on the at least two seeds; and

generating, via the signer device, on the message, a signature based on the private key.

2. The method of claim 1 , wherein the generating at least two seeds is further based on a pseudorandom function.

3. The method of claim 1 , wherein the determining of the private key is based on the at least two seeds without regenerating the at least two seeds.

4. The method of claim 1 , wherein the determining of the private key is based on the at least two seeds,

wherein the method further comprises:

exploiting a hash function for each of the at least two seeds; and

updating the private key based on the hash function, and

wherein the generating of the signature is based on the updated private key.

5. The method of claim 4 , wherein the hash function comprises a hash chain.

6. The method of claim 1 , wherein the generating of the signature comprises:

generating a first signature parameter based on a first sampling function and the at least two seeds;

generating a second signature parameter based on a second sampling function and the at least two seeds;

applying the first signature parameter to a hash function; and

generating the signature based on the applied first signature parameter and the second signature parameter.

7. A method for lightweight post-quantum authentication comprising:

receiving, from a signer device, a signature on a message;

accessing at least two servers;

obtaining, from the at least two servers, at least two partial public keys, the at least two partial public keys comprising a first partial public key parameter and a second partial public key parameter, wherein the at least two partial public keys are generated by the at least two servers distinct from the signer device;

determining a full public key based on the at least two partial public keys; and

authenticating the signature on the message based on the full public key.

8. The method of claim 7 , wherein the at least two partial public keys correspond in number to the at least two servers.

9. The method of claim 8 , the at least two partial public keys are based on at least two seeds of each of the at least two servers.

10. The method of claim 8 , wherein each of the at least two partial public keys comprises a first partial public key parameter and a second partial public key parameter.

11. The method of claim 10 , wherein the full public key comprises:

a first full public key parameter based on the respective first partial public key parameter of each of the at least two partial public keys; and

a second full public key parameter based on the respective second partial public key parameter of each of the at least two partial public keys.

12. The method of claim 11 , wherein the authenticating of the signature comprises:

applying the first full public key parameter to a hash function;

generating a public key signature by adding the applied first full public key parameter and the second full public key parameter;

comparing the public key signature with the signature on the message; and

determining authentication of the signature on the message.

13. A method comprising:

receiving, on a first server, a number of seeds from a signer, the number of seeds being at least two;

determining, on the first server, a first partial public key;

transmitting, from the first server, the partial public key to at least two second servers, the at least two second servers with the first server corresponding in number to the number of seeds;

receiving, on the first server, at least two second partial public keys from the at least two second servers;

determining, on the first server, a full public key based on the first partial public key and the at least two second partial public keys;

receiving, on a verifier, a signature on a message;

receiving, on the verifier, the full public key and a certificate; and

authenticating, on the verifier, the signature on the message based on the full public key.

14. The method of claim 13 , further comprising:

transmitting, from the first server, the full public key to a certificate authority;

receiving, on the first server, the certificate from the certificate authority; and

transmitting, from the first server, the certificate and the full public key to the verifier.

15. The method of claim 13 , further comprising:

determining a root of at least two public keys corresponding to the first server and the at least two second servers;

transmitting, from the first server, the root to a certificate authority;

receiving, on the first server, the certificate from the certificate authority; and

transmitting, from the first server, the certificate and the full public key to the verifier.

16. The method of claim 13 , wherein the full public key comprises a first full public key parameter and a second full public key parameter,

wherein the authenticating of the signature comprises:

applying the first full public key parameter to a hash function;

generating a public key signature by adding the applied first full public key parameter and the second full public key parameter;

comparing the public key signature with the signature on the message; and

determining authentication of the signature on the message.

17. The method of claim 13 , further comprising:

generating, on the first server, a second signature on the partial public key,

wherein the transmitting of the partial public key comprises: transmitting, from the first server, the partial public key and the second signature to the at least two second servers, and

wherein the receiving the at least two partial public keys comprises: receiving, on the first server, the at least two partial public keys and at least two second signatures from corresponding at least two second servers.

18. The method of claim 17 , further comprising:

verifying the at least two second signatures corresponding to the at least two partial public keys.

Assignments (2)
CONFIRMATORY LICENSE Recorded Mar 13, 2025
From: UNIVERSITY OF SOUTH FLORIDA
To: NATIONAL SCIENCE FOUNDATION
Reel/Frame 070499/0113 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Sep 14, 2022
From: BEHNIA, ROUZBEH; YAVUZ, ATTILA ALTAY
To: UNIVERSITY OF SOUTH FLORIDA
Reel/Frame 061088/0636 →
Continuity (2)
Provisional Application 63185205 · May 6, 2021
Related Publication 20220385484A1 · Dec 1, 2022
References Cited (74)
US 9673975B1 · Machani · 2017 [cited by examiner]
US 9954680B1 · Machani · 2018 [cited by examiner]
US 10511441B2 · Maximov et al. · 2019 [cited by applicant]
US 10511447B1 · Lakk · 2019 [cited by applicant]
US 11588645B1 · Yavuz · 2023 [cited by examiner]
US 11736283B2 · Nix · 2023 [cited by examiner]
US 11777719B2 · Nix · 2023 [cited by examiner]
US 20040218763A1 · Rose · 2004 [cited by examiner]
US 20050010758A1 · Landrock · 2005 [cited by examiner]
US 20050149730A1 · Aissi · 2005 [cited by examiner]
US 20070104322A1 · Ding · 2007 [cited by examiner]
US 20090106560A1 · Chopart · 2009 [cited by examiner]
US 20130046973A1 · Resch · 2013 [cited by examiner]
US 20130191632A1 · Spector · 2013 [cited by examiner]
US 20140250303A1 · Miller · 2014 [cited by examiner]
US 20150121066A1 · Nix · 2015 [cited by examiner]
US 20150363775A1 · Li · 2015 [cited by examiner]
US 20190007205A1 · Corduan · 2019 [cited by examiner]
US 20190114401A1 · De · 2019 [cited by examiner]
US 20190319801A1 · Sastry et al. · 2019 [cited by applicant]
US 20190342080A1 · Vakili · 2019 [cited by examiner]
US 20190354972A1 · Di Nicola · 2019 [cited by examiner]
US 20200119908A1 · Christensen · 2020 [cited by examiner]
US 20200380503A1 · Prokop · 2020 [cited by examiner]
US 20210051003A1 · Jarjoui · 2021 [cited by examiner]
US 20210075600A1 · Trevethan · 2021 [cited by examiner]
US 20230111741A1 · Ho · 2023 [cited by examiner]
US 20230163948A1 · Trevethan · 2023 [cited by examiner]
US 20230299981A1 · Zacher · 2023 [cited by examiner]
US 20230318851A1 · Kojima · 2023 [cited by examiner]
Abdalla et al., “A New Forward-Secure Digital Signature Scheme,” in Advances in Cryptology—Asiacrypt 2000, T. Okamoto, Ed. Berlin, Heidelberg:Springer Berlin Heidelberg, 2000, pp. 116-129. [cited by applicant]
Atkins, “Requirements for post-quantum cryptography on embedded devices in the iot.” NIST, Computer Security Resource Center 2021, 4 pages. [cited by applicant]
Aumasson et al., “Sha-3 proposal blake,” Submission to NIST (Round 3), 2010. [Online]. Available: http://131002.net/blake/blake.pdf, 8 pages. Downloaded Sep. 13, 2022. [cited by applicant]
Behnia et al., “Towards Practical Post-quantum Signatures for Resource-Limited Internet of Things.” Annual Computer Security Applications Conference. 2021. (pp. 119-130). [cited by applicant]
Bellare et al., “The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs,” in Advances in Cryptology—Eurocrypt2006, S. Vaudenay, Ed. Springer Berlin Heidelberg, 2006, pp. 409-426. [cited by applicant]
Bernstein et al., “SPHINCS: Practical Stateless Hash-Based Signatures,” in Advances in Cryptology—Eurocrypt 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer… [cited by applicant]
Bernstein et al., “The SPHINCS+ Signature Framework,” in Proceedings of the 2019 ACMSIGSAC Conference on Computer and Communications Security, ser. CCS '19. NewYork, NY, USA: Association for Computing Machinery, 2019, p… [cited by applicant]
Bernstein, “New stream cipher designs,” M. Robshaw and O. Billet, Eds.Berlin, Heidelberg: Springer-Verlag, 2008, ch. The Salsa20 Family of StreamCiphers, pp. 84-97. [cited by applicant]
Bos et al., “Rapidly verifiable xmss signatures,” IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 137-168, 2021. [cited by applicant]
Boyko et al., “Speeding up discrete log and factoring based schemes via precomputations,” in Advances in Cryptology—Eurocrypt' 98: International Conference on the Theory and Application of Cryptographic Techniques Espoo… [cited by applicant]
Bruinderink, “Flush, Gauss, and Reload—A Cache Attack on the BLISS Lattice-Based Signature Scheme,” in Cryptographic Hardware and Embedded Systems—CHES 2016: 18th International Conference, Santa Barbara, CA, USA, Aug. 1… [cited by applicant]
Buchmann et al., “XMSS—A Practical Forward Secure Signature Scheme based onMinimal Security Assumptions,” in Proceedings of the4th International Conference on Post-Quantum Cryptography, ser. PQCrypto'11. Berlin, Heidelb… [cited by applicant]
Camara et al., “Security and privacy issues in implantable medical devices: A comprehensive survey” J Biomed Inform . Jun. 2015;55:272-89. [cited by applicant]
Chen et al. “Light-weight and privacy-preserving authentication protocol for mobile payments in the context of IoT.” IEEE Access 7 (2019): 15210-15221. [cited by applicant]
Cheng et al., “Lattice-based signature from key consensus.” Cryptology ePrint Archive (2018). 19 pages. [cited by applicant]
Costello et al., “Schnorrq: Schnorr signatures on fourq,” MSR TechReport, 2016. Available at: https://www.microsoft. com/en-us/research/wpcontent/uploads/2016/07/SchnorrQ. pdf, Tech. Rep., 2016. 5 pages. [cited by applicant]
Ding et al., “Rainbow, a new multivariable polynomial signaturescheme,” in International Conference on Applied Cryptography and Network Security. Springer, 2005, pp. 164-175. [cited by applicant]
Ducas et al., “Crystals—dilithium: Digital signatures from module lattices.” Cryptology ePrint Archive, Report 2017/633, 2017, http://eprint.iacr.org/2017/633.). 18 pages. [cited by applicant]
Ducas et al., “Lattice Signatures and Bimodal Gaussians,” in Advances in Cryptology—CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, Aug. 18-22, 2013. Proceedings, Part I, R. Canetti and J. A. Gar… [cited by applicant]
Espitau et al., “Side-Channel Attacks on BLISS Lattice-Based Signatures,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017,2017, pp. 1857-1874. [cited by applicant]
Fouque et al., “Falcon: Fast-fourier latticebasedcompact signatures over ntru,” Submission to the NIST?s post-quantum cryptography standardization process, 2018. 75 Pages. [cited by applicant]
Garcia et al., “Make Sure DSA Signing Exponentiations Really areConstant-Time” in Proceedings of the 2016 ACM SIGSACConference on Computer and Communications Security, ser. CCS '16. New York, NY, USA: ACM, 2016, pp. 163… [cited by applicant]
Güneysu et al., “Practical lattice-based cryptography:A signature scheme for embedded systems,” in Cryptographic Hardwareand Embedded Systems—CHES 2012, E. Prouff and P. Schaumont, Eds. Berlin, Heidelberg: Springer Berl… [cited by applicant]
Hülsing et al., in Security Engineering and Intelligence Informatics, A. Cuzzocrea, C. Kittl, D. E. Simos, E.Weippl, and L. Xu, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg,2013, pp. 194-208. [cited by applicant]
Hülsing, “Armed sphincs,” in Public-Key Cryptography—PKC 2016. Springer, 2016, pp. 446-470. [cited by applicant]
Hutter et al., “Nacl on 8-bit avr microcontrollers,” in Progress in Cryptology—Africacrypt 2013, A. Youssef, A. Nitaj, and A. E. Hassanien, Eds. 18 pages. [cited by applicant]
Ishai et al., “Improved upper bounds on information-theoretic private information retrieval (extended abstract),” in Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, ser. STOC '99. New York, … [cited by applicant]
K. MacKay, “micro-ecc: Ecdh and ecdsa for 8-bit, 32-bit, and 64-bit processors,” Github Repository, 2013. [Online]. Available: https://github.com/kmackay/microecc. 3 pages. [cited by applicant]
Kannwischer et al., “pqm4: Testing and benchmarking nist pqc on arm cortex-m4,” 2019. Radboud Repository, Downloaded Jul. 29, 2022, 23 pages. [cited by applicant]
Khalid et al., “Lattice-based Cryptography for IoT in A Quantum World: Are We Ready?” in 2019 IEEE 8th International Workshop on Advances in Sensors and Interfaces (IWASI), 2019, pp. 194-199. [cited by applicant]
Kiltz et al., “A Concrete Treatment of Fiat-ShamirSignatures in the Quantum Random-Oracle Model,” in Advances in Cryptology—Eurocrypt 2018, J. B. Nielsen and V. Rijmen, Eds. Cham: Springer InternationalPublishing, 2018,… [cited by applicant]
Liu et al., “FourQ on embeddeddevices with strong countermeasures against side-channel attacks,” in CryptographicHardware and Embedded Systems—CHES 2017,W. Fischer and N. Homma,Eds. Cham: Springer International Publishi… [cited by applicant]
Lyubashevsky et al., “Asymptotically efficient lattice-based digital signatures,” J. Cryptology, vol. 31, No. 3, pp. 774-797, 2018. [cited by applicant]
Lyubashevsky, “Fiat-shamir with aborts: Applications to lattice and factoringbasedsignatures,” in Advances in Cryptology—Asiacrypt 2009: 15th InternationalConference on the Theory and Application of Cryptology and Infor… [cited by applicant]
Merkle, “A certified digital signature,” in Proceedings on Advances in cryptology,ser. CRYPTO '89. New York, NY, USA: Springer-Verlag, 1989, pp. 218-238. [cited by applicant]
Migliore et al., “Masking dilithium—efficientimplementation and side-channel evaluation,” in Applied Cryptography and NetworkSecurity—17th International Conference, ACNS 2019, Bogota, Colombia, Jun. 5-7, 2019, Proceedin… [cited by applicant]
Noura et al., “DistLog: A distributed logging scheme for IoT forensics,” Ad Hoc Networks, vol. 98, p. 102061, 16 pages. 2020. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1570870519306997. [cited by applicant]
Ozmen et al., “Energy-aware digital signatures forembedded medical devices,” in 2019 IEEE Conference on Communications andNetwork Security (CNS), 2019, pp. 55-63. [cited by applicant]
“Pulse sensor by world famous electronics llc.” https://pulsesensor.com. Downloaded Sep. 13, 2022, 2 pages. [cited by applicant]
Reyzin et al., “Better than BiBa: Short one-time signatures withfast signing and verifying,” in Proceedings of the 7th Australian Conference onInformation Security and Privacy (ACIPS '02). Springer-Verlag, 2002, pp. 144… [cited by applicant]
Rushanan et al. “Sok: Security and privacy in implantable medical devices and body area networks. In 2014 IEEE symposium on security and privacy” (pp. 524-539). [cited by applicant]
Shor “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.” SIAM review 41.2 (1999): 303-332. [cited by applicant]
Yavuz, “ETA: Efficient and Tiny and Authentication for Heterogeneous Wireless Systems” in Proceedings of the sixth ACM conference on Security and privacy in wireless and mobile networks, ser. WiSec '13. New York, NY, US… [cited by applicant]
ANSI X9.62-1998: Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), American Bankers Association, 1999. 128 pages. [cited by applicant]