NIST POST-QUANTUM CRYPTOGRAPHY
UPDATE

Dustin Moody

Computer Security Division
NIST

THE QUANTUM THREAT
•

NIST public-key crypto standards
• SP 800-56A: Diffie-Hellman, ECDH
• SP 800-56B: RSA encryption
• FIPS 186: RSA, DSA, and ECDSA signatures

all vulnerable to attacks from
a (large-scale) quantum computer



Symmetric-key crypto (AES, SHA) would also be
affected (by Grover’s algorithm), but less dramatically

THE NIST PQC “COMPETITION”
•

IN 2016, NIST CALLED FOR QUANTUM-RESISTANT
CRYPTOGRAPHIC ALGORITHMS FOR NEW PUBLIC-KEY
CRYPTO STANDARDS
• DIGITAL SIGNATURES
• ENCRYPTION/KEY-ESTABLISHMENT

•

OUR ROLE: MANAGING A PROCESS OF ACHIEVING
COMMUNITY CONSENSUS IN A TRANSPARENT AND TIMELY
MANNER

•

DIFFERENT AND MORE COMPLICATED THAN PAST AES/SHA-3
COMPETITIONS

•

THERE WOULD NOT BE A SINGLE “WINNER”
• IDEALLY, SEVERAL ALGORITHMS WILL EMERGE AS ‘GOOD CHOICES’

THE FIRST THREE ROUNDS
2016: NIST ANNOUNCES PROCESS FOR PQC STANDARDIZATION
2017: INITIAL SUBMISSIONS (64 ACCEPTED: 19 SIGS + 45 KEMS)
2019: 2ND ROUND START (26 SCHEMES: 9 SIGS + 17 KEMS)
2020: 3RD ROUND START (7 FINALISTS, 8 ALTERNATES):

Finalists

KEM
Signature

Kyber, NTRU, Saber,
Classic McEliece
Dilithium, Falcon,
Rainbow

Alternates

Bike, FrodoKEM, HQC,
NTRUPrime, SIKE
GeMSS, Picnic, SPHINCS+

ROUND 3 RESULTS
ROUND 3 RESULTS

KEMs

Signatures

CRYSTALS-Kyber

CRYSTALS-Dilithium, Falcon, SPHINCS+

See NISTIR 8413, Status Report on the 3rd Round of the NIST PQC Standardization Process, for the rationale on the selections

4th round candidates (all KEMs)
evaluated for 18-24 months
o ClassicMcEliece
o BIKE
o HQC
On-ramp signatures
o SIKE

 NIST issued a new call for additional
signatures – preferably for signatures
based on non-lattice problems

THE SELECTED ALGORITHMS
•

•

•

CRYSTALS-KYBER
•

KEM BASED ON STRUCTURED LATTICES

•

GOOD ALL-AROUND PERFORMANCE AND SECURITY

CRYSTALS-DILITHIUM
•

DIGITAL SIGNATURE BASED ON STRUCTURED LATTICES

•

GOOD ALL-AROUND PERFORMANCE AND SECURITY, RELATIVELY SIMPLE IMPLEMENTATION

•

NIST RECOMMENDS IT BE THE PRIMARY SIGNATURE ALGORITHM USED

FALCON
•

DIGITAL SIGNATURE BASED ON STRUCTURED LATTICES

•

SMALLER BANDWIDTH, BUT MUCH MORE COMPLICATED IMPLEMENTATION

•

THE FALCON STANDARD WILL COME OUT AFTER THE OTHERS

• SPHINCS+
•

DIGITAL SIGNATURE BASED ON STATELESS HASH-BASED CRYPTOGRAPHY

•

SOLID SECURITY, BUT PERFORMANCE NOT AS GOOD IN COMPARISON TO DILITHIUM/FALCON

TIMELINE

• The 5th NIST PQC Standardization Conference
• April 10-12, 2024 in Rockville, Maryland

• Draft standards for public comment released Aug 2023
• Deadline for comments: November 22, 2023

• The first PQC standards should be published in 2024

STANDARDIZATION
• THE 1ST PQC STANDARDS
• FIPS 203: ML-KEM (KYBER)
• FIPS 204: ML-DSA (DILITHIUM)
• FIPS 205: SLH-DSA (SPHINCS+)
• FN-DSA (FALCON) – UNDER DEVELOPMENT
• WILL HAVE OTHER DOCS WITH MORE GUIDANCE/DETAILS

• SOME CHOICES MADE
• WHICH PARAMETER SETS, WHICH HASH FUNCTIONS, OTHER
SYMMETRIC PRIMITIVES, ETC

• PLEASE PROVIDE FEEDBACK
• PQC-FORUM, EMAIL ETC

THE KEMS IN THE 4TH ROUND
• Classic McEliece

• NIST is confident in the security
• Smallest ciphertexts, but largest public keys
• We’d like feedback on specific use cases for Classic McEliece

• BIKE

• Most competitive performance of 4th round candidates
• We encourage vetting of IND-CCA security

• HQC

• Offers strong security assurances and mature decryption failure rate analysis
• Larger public keys and ciphertext sizes than BIKE

• SIKE

• The SIKE team acknowledges that SIKE (and SIDH) are insecure and should not be used

AN ON-RAMP FOR SIGNATURES
• Scope:

• NIST is primarily interested in additional general-purpose
signature schemes that are not based on structured lattices.

• (No on-ramp for KEMs currently planned)
• July 2023: 40 submissions accepted
• From 5 continents and 28 countries

• For complete specs (including code):
see www.nist.gov/pqcrypto

Type

Number

Lattice

7

Code-based

6

Multivariate

11

MPC in the head

6

Symmetric

4

Isogeny

1

Other

5

Total

40

STATEFUL HASH BASED SIGNATURES FOR EARLY
ADOPTION

Stateful hash-based signatures from SP 800-208 are allowed for signing
software/firmware updates in CNSA 2.0

OTHER STANDARDS ORGANIZATIONS
•

WE ARE AWARE THAT MANY STANDARDS ORGANIZATIONS AND EXPERT GROUPS ARE
WORKING ON PQC
• ASC X9 HAS DONE STUDIES AND WRITTEN WHITE PAPERS
• IEEE P1363.3 HAS STANDARDIZED SOME LATTICE-BASED SCHEMES
• IETF HAS STANDARDIZED STATEFUL HASH-BASED SIGNATURES LMS/XMSS AND IS CURRENTLY
DOING NEW WORK GEARED TO THE PQC MIGRATION
• ETSI HAS RELEASED QUANTUM-SAFE CRYPTOGRAPHY REPORTS
• EU EXPERT GROUPS PQCRYPTO AND SAFECRYPTO MADE RECOMMENDATIONS AND RELEASED
REPORTS
• ISO/IEC JTC 1 SC27 WG2 IS DEVELOPING A STANDARD TO SPECIFY PQC ALGORITHMS AS AN
AMENDMENT TO ISO/IEC 18033-2

•

NIST IS INTERACTING AND COLLABORATING WITH THESE ORGANIZATIONS AND
GROUPS

•

SOME COUNTRIES HAVE BEGUN STANDARDIZATION ACTIVITIES

RECENT GUIDANCE

”The United States must prioritize the
transition of cryptographic systems to
quantum-resistant cryptography, with the
goal of mitigating as much of the quantum
risk as is feasible by 2035.”

TRANSITION AND MIGRATION
•

THERE HAS BEEN MUCH DISCUSSION ON
HYBRID/COMPOSITE MODES
•

•

B

ECDH

NIST SP800-56C REV. 2 ALLOWS FOR A CERTAIN HYBRID MODE

PQC
ECDH

NIST WILL PROVIDE TRANSITION GUIDELINES TO
PQC STANDARDS
•

NIST HAS PROVIDED SUCH GUIDANCE BEFORE
•

•

A

EXAMPLES: TRIPLE DES, SHA-1, KEYS < 112 BITS

NEW CISA/NSA/NIST FACTSHEET: QUANTUM READINESS
– MIGRATION TO POST-QUANTUM CRYPTOGRAPHY
•
•
•

CRYPTOGRAPHIC INVENTORY
DISCUSS POST-QUANTUM ROADMAP W/ TECHNOLOGY
VENDORS
SUPPLY CHAIN QUANTUM-READINESS

PQC
ECDH

Z

KDF(𝑍𝑍||𝑇𝑇)

THE NCCOE MIGRATION TO PQC PROJECT
• COMPLEMENT STANDARDIZATION AND TACKLE CHALLENGES
WITH ADOPTION, IMPLEMENTATION AND DEPLOYMENT TO
PQC
•

COORDINATE WITH SDO’S AND INDUSTRY COLLABORATORS

• PRODUCT DELIVERABLES
•

PRACTICE GUIDES, PLAYBOOKS, REFERENCE ARCHITECTURES,
AUTOMATED TOOLS, PROOF OF CONCEPT CODE, ETC

•

DRAFT SP 1800-38 VOLUME A

• OUTREACH AND ENGAGEMENT
•

COMMUNITY OF INTEREST, WEBINARS, PUBLIC EVENTS

•

IN PERSON MEETING – AUG 15 AT NCCOE

•

APPLIED-CRYPTO-PQC@NIST.GOV

• THE BEGINNING OF THE END IS HERE!
• OR IS IT THE END OF THE BEGINNING?
• NIST IS GRATEFUL FOR EVERYBODY’S EFFORTS
• CHECK OUT WWW.NIST.GOV/PQCRYPTO
• SIGN UP FOR THE PQC-FORUM FOR ANNOUNCEMENTS &
DISCUSSION
• SEND E-MAIL TO PQC-COMMENTS@NIST.GOV
