دانلود کتاب Post-Quantum Cryptography: 14th International Workshop, PQCrypto 2023, College Park, MD, USA, August 16–18, 2023, Proceedings (Lecture Notes in Computer Science)

فهرست مطالب :

Preface
Organization
Contents
Code-Based Cryptography
An Extension of Overbeck\'s Attack with an Application to Cryptanalysis of Twisted Gabidulin-Based Schemes
1 Prerequisites
1.1 Notation
1.2 Rank Metric Codes
1.3 Gabidulin Codes
1.4 Twisted Gabidulin Codes
1.5 GPT System and Variants
2 On the Decoding of Gabidulin Codes and Their Twists
2.1 An Important Remark on the Decoder of Gabidulin Codes
2.2 Decoding Twisted Gabidulin Codes
2.3 Discussion About the Claim
2.4 A Remark on the Code that is Actually Decoded
3 Revisiting Overbeck\'s Attack
3.1 A Distinguisher
3.2 The Structure of i(Gpub)
3.3 Overbeck\'s Attack
3.4 Analyzing the Dimension of i (Cpub) for Small i\'s
3.5 Puchinger, Renner and Wachter–Zeh Variant of GPT
4 An Extension of Overbeck\'s Attack
4.1 Sketch of the Attack
4.2 Some Algebraic Preliminaries
4.3 Description of Our Extension of Overbeck\'s Attack
4.4 Summary of the Attack
4.5 Discussions and Simplifications
4.6 Complexity
4.7 Discussion About the Claims on Conductors and Stabilizers
5 Don\'t Twist Again
5.1 A Distinguisher
5.2 The Structure of i(GTpub)
5.3 Attacking the System for Small i\'s
References
Cryptanalysis of Rank-Metric Schemes Based on Distorted Gabidulin Codes
1 Introduction
2 Preliminaries on the Rank Metric
3 Loidreau Cryptosystem
3.1 Description of the Scheme
3.2 Security
4 A Constrained Linear System for Decryption
5 Combinatorial Approach
6 A Bilinear System
7 Tools to Analyze System 1
7.1 Algebraic Background
7.2 Understanding the Projection Over Fq
8 Degree Fall Polynomials from Jacobians
8.1 Jacobian with Respect to the R Variables
8.2 Jacobian with Respect to the Cj Variables
8.3 Approach Based on Degree Fall Polynomials
9 Conclusion
References
A High-Performance Hardware Implementation of the LESS Digital Signature Scheme
1 Introduction
2 Previous Work
3 Background
3.1 Generator, Permutation, and Monomial Matrices
3.2 LESS
4 Hardware Architecture
4.1 Top Level Architecture
4.2 Submodule Design
4.3 Operation Scheduling
5 Results
5.1 Software Comparison
5.2 Comparison with Other Digital Signature Schemes
6 Conclusions
References
Wave Parameter Selection
1 Introduction
2 Preliminaries
2.1 Error Correcting Code
2.2 Decoding Problem
2.3 Generalized Ternary (U|U+V) Code
2.4 The Wave Signature Scheme
2.5 Weight Distribution and (U|U+V)-Specific Codewords
3 q-ary Information Set Decoding (ISD)
3.1 An ISD Framework
3.2 ISD-MMT
3.3 ISD-GBA
4 Best Known Attacks on Wave
4.1 Forgery Attack
4.2 Key Attack
4.3 Wave Parameter Selection
4.4 Sizes
4.5 Scaling Security
4.6 Quantum Security
5 Conclusion
References
Group-Action-Based Cryptography
SPDH-Sign: Towards Efficient, Post-quantum Group-Based Signatures
1 Preliminaries
1.1 The Semidirect Product
1.2 Proofs of Knowledge and Identification Schemes
1.3 Signature Schemes
2 A Novel Connection to a Group Action
2.1 Semidirect Discrete Logarithm Problem
3 SPDH-Sign
3.1 An Identification Scheme
3.2 A Digital Signature Scheme
4 On the Difficulty of SDLP
4.1 Dihedral Hidden Subgroup Problem
4.2 Semidirect Computational Diffie-Hellman
5 A Candidate Group
6 Conclusion
References
Isogeny-Based Cryptography
A Tightly Secure Identity-Based Signature Scheme from Isogenies
1 Introduction
2 Preliminaries
2.1 Elliptic Curve and Ideal Class Group
2.2 Lossy Identification Schemes
2.3 Identity-Based Signatures
2.4 Hardness Assumptions
3 The Lossy CFI-FiSh Scheme
3.1 The Lossy CFI-FiSh
4 Tightly Secure IBS from Lossy CSI-FiSh
4.1 Construction
4.2 Security Analysis
5 Conclusion
References
Lattice-Based Cryptography
New NTRU Records with Improved Lattice Bases
1 Introduction
1.1 Our Results
1.2 Future Work
1.3 Organization of Our Paper
2 Preliminaries
2.1 Notations
2.2 Lattices
2.3 Lattice Reduction
3 NTRU
3.1 NIST Submission
3.2 NTRU Challenges
4 Lattice Reduction with a Hint
5 Choosing Lattices for NTRU-HPS and NTRU-HRSS
5.1 The Coppersmith-Shamir Lattice
5.2 The Cyclotomic Lattice and the Projected Cyclotomic Lattice
5.3 Further Improvement by Exploiting Design Choices
6 Experimental Results for HRSS and HPS
6.1 NTRU-HRSS
6.2 NTRU-HPS
6.3 Comparison Between HRSS and HPS, and Implications
7 New NTRU Record: n = 181
7.1 Choosing a Lattice for the NTRU Challenges
7.2 Record Computation Details
References
On the Hardness of Scheme-Switching Between SIMD FHE Schemes
1 Introduction
1.1 Our Results
1.2 Technical Overview
1.3 Related Works
1.4 Organization
2 Preliminaries
2.1 RLWE SIMD Schemes
2.2 Useful Lemmas
2.3 Bootstrapping Circuits for BGV and CKKS
3 Homomorphic Scheme-Switching
3.1 Weak Scheme-Switching Oracles
3.2 Strong Scheme-Switching Oracles
4 Bootstrapping via a Weak Scheme-Switching Oracle
4.1 Bootstrapping in CKKSfrom a BGV-to-CKKS Oracle
4.2 Bootstrapping in BGVfrom a CKKS-to-BGV Oracle
4.3 Switching Between Schemes Using Bootstrapping
5 Bootstrapping via a Comparison Oracle
5.1 Comparison Oracles
5.2 Bootstrapping in CKKS from Comparisons
5.3 Bootstrapping in BGV from Comparisons
6 Conclusion
References
Classical and Quantum 3 and 4-Sieves to Solve SVP with Low Memory
1 Introduction
2 Preliminaries
2.1 Quantum Computing
2.2 Lattice Sieving
2.3 Configurations
3 Code Structure and Filtering
3.1 Locality Sensitive Filtering
3.2 Residual Vectors in Filter
4 Framework
5 Classical Sieving
5.1 Classical 2-Sieve
5.2 Classical 3-Sieve
5.3 Classical 4-Sieve
6 Quantum Sieving
6.1 Quantum 3-Sieve
6.2 Quantum 4-Sieve
References
NTRU in Quaternion Algebras of Bounded Discriminant
1 Introduction
2 Preliminaries
3 NTRU
4 Cyclic Division Algebras
5 NTRU in CDAs
6 Results on q-Ary Lattices
7 An NTRU Key Generation Algorithm
8 A Provably Secure NTRU-Based Scheme
9 Conclusion
A Proofs
B Choosing Parameters and Number Fields
C Sketched Cryptographic Functionality
References
Do Not Bound to a Single Position: Near-Optimal Multi-positional Mismatch Attacks Against Kyber and Saber
1 Introduction
1.1 Related Work
1.2 Contributions
1.3 Organization
2 Background
2.1 CPA-Secure Version of Kyber
2.2 CPA-Secure Version of Saber
2.3 The Threat Model – Mismatch Attack Model
2.4 Huffman Coding
3 One-Positional Mismatch Attacks
3.1 Kyber
3.2 Saber
3.3 The Lower Bounds from ch11AC21:QCZPHD
3.4 The Practical Mismatch Attacks from ch11AC21:QCZPHD
3.5 On the Performance of the Mismatch Attacks from ch11AC21:QCZPHD
4 Multi-positional Mismatch Attacks
4.1 Two-Positional Mismatch Attacks on Kyber
4.2 Two-Positional Mismatch Attacks on Saber
4.3 Hyperrectangular Cuts
4.4 The Optimization Problem
4.5 Comparisons
5 Discussions
5.1 Room for Further Improvements
5.2 Post-processing with Lattice Reduction
5.3 Relation to Side-Channel and Fault-Injection Attacks
6 Conclusions and Future Work
References
NTWE: A Natural Combination of NTRU and LWE
1 Introduction
1.1 Our Contribution
1.2 Paper Outline
2 Background
2.1 Notation
2.2 Lattices
2.3 Algebraic Number Theory
2.4 LWE and NTRU
2.5 Lattice Reduction
3 The NTWE Problem
3.1 Relation to Other Problems
4 The NTWE Lattice Problems
4.1 NTRU Problem
4.2 Module-LWE Problem
4.3 NTWE Problem
5 Our Cryptosystem
5.1 Security
5.2 Correctness of Decryption
5.3 Comparison to Other Cryptosystems
6 Example Parametrizations
6.1 Skewed Parameters
6.2 Parameters Similar to Kyber
6.3 Parameters Combining NTRU and LWE
7 Final Remarks
References
Multivariate Cryptography
Fast Enumeration Algorithm for Multivariate Polynomials over General Finite Fields
1 Introduction
2 Classical Approach
3 Enumeration Algorithm of Bouillaguet et al.
3.1 Notations
3.2 Enumeration Algorithm
4 Our Proposed Algorithms
4.1 Notations
4.2 Enumeration Order
4.3 Data Structure
4.4 Successive Classification of Inputs
4.5 Our Enumeration Algorithm
4.6 Complexity
5 Conclusion
A Application to Solving Polynomial Equations
B Toy Example of Our Enumeration
C Magma Code
References
DME: A Full Encryption, Signature and KEM Multivariate Public Key Cryptosystem
1 Introduction
2 Mathematical Description of DME
3 Computing the Public Key F
3.1 Computing the Monomials of F
3.2 Computing the Coefficients of the Public Key F
4 DME as a Trapdoor One Way Permutation
5 Set up of the DME
5.1 The Configuration Matrices
5.2 Reduction of the Number of Monomials
6 Security of the DME
6.1 Gröbner Basis
6.2 Weil Descent
6.3 Estimation of the Number of Monomials of the Inverse
6.4 Structural Cryptanalysis
7 Implementation and Timings
References
Quantum Algorithms, Cryptanalysis and Models
On the Quantum Security of HAWK
1 Introduction
2 Preliminary
2.1 Setting up the Stage
2.2 Geometric Units
2.3 Adaptive Reprogramming Lemma
3 Brief Recap on HAWK and the One-More SVP
4 Quantum Security of HAWK
4.1 Warming Up: NMA Security
4.2 Full CMA Quantum Security
4.3 Classical Security
A More Proofs
References
Non-Observable Quantum Random Oracle Model
1 Introduction
1.1 Our Contributions
1.2 Related Work
2 Preliminaries
2.1 Quantum Random Oracle Model (QROM)
2.2 Commitments
2.3 Other Basic Cryptographic Primitives
3 The Non-Observable Quantum Random Oracle Model
4 Extractable Non-Malleable Commitments in the NO QROM
5 Signature Schemes in the NO QROM
5.1 Signatures with History-Free Reductions
5.2 FDH Based Signature Schemes
6 Hinting PRGs in the NO QROM
References
Characterizing the qIND-qCPA (In)security of the CBC, CFB, OFB and CTR Modes of Operation
1 Introduction
1.1 Context and Results
1.2 Our Contributions
1.3 Previous Work
2 Prerequisites
2.1 Notations and Definitions
2.2 Lemmas
2.3 IND-qCPA Security of CBC, CFB, CTR and OFB
3 Our Results
3.1 qIND-qCPA-P13 Insecurity of CTR and OFB
3.2 qIND-qCPA-P13 Insecurity of CFB
3.3 qIND-qCPA-P13 Insecurity of CBC
3.4 General Results and Discussion
4 Conclusion
A Adapting Anand et al.\'s Work to the More General IND-qCPA Notions
A.1 Definitions
A.2 Lemmas
A.3 IND-qCPA Security of CTR and OFB
A.4 Potential IND-qCPA Insecurity of CFB Used with a PRP
A.5 Potential IND-qCPA Insecurity of CBC Used with a PRP
A.6 IND-qCPA Security of CBC and CFB Used with a qPRP
References
Breaking the Quadratic Barrier: Quantum Cryptanalysis of Milenage, Telecommunications\' Cryptographic Backbone
1 Introduction
1.1 Contributions
2 Background
2.1 Notation
2.2 The AKA Protocol and Milenage Algorithms
2.3 Classical Cryptanalysis of Milenage algorithms
2.4 Quantum Computation
2.5 Attacker Model
3 The Quantum Cryptanalysis Toolbox
3.1 Grover\'s Algorithm: Fast Unstructured Search
3.2 Simon\'s Algorithm: Quantum Period Finding
3.3 Offline Simon\'s Algorithm: Attacks Without Superposition Queries
4 Quantum Cryptanalysis of the Milenage Algorithms
4.1 The Grover Key Recovery for f1, …, f5
4.2 Quantum Slide Attacks Against f2
4.3 Existential Forgery of f1
4.4 Quantum Related Key Attacks Against f1, …, f5
5 Discussion
6 Conclusion
A List of Abbreviations
B The AKA Protocol
C Proof of the Hidden Period Required for the Quantum Slide Attack
D Proof of the Hidden Period Required for the Existential Forgery Attack
References
Time and Query Complexity Tradeoffs for the Dihedral Coset Problem
1 Introduction
2 Preliminaries
2.1 Phase Vectors and Kuperberg\'s First Algorithm
2.2 Regev\'s Algorithm
2.3 Kuperberg\'s Second Algorithm
2.4 The Subset-Sum Problem
3 Reducing DCP To a Subset-Sum Problem
3.1 Using a Classical Subset-Sum Solver
3.2 Using a Quantum Subset-Sum Solver
4 Interpolation Algorithm
5 Quantum Subset-Sum Algorithms
5.1 Algorithms Based on Representations
5.2 From Asymptotic to Exact Optimizations
5.3 Solving Subset-Sum in Superposition
References
Post-Quantum Protocols
Post-Quantum Signatures in DNSSEC via Request-Based Fragmentation*-4pt
1 Introduction
1.1 Our Contributions
2 The Domain Name System
3 Request-Based Fragmentation
3.1 Resource Record Fragments
3.2 Using RRFRAGs
3.3 Example Execution of ARRF
3.4 Caching and DNSSEC Considerations
4 Evaluation
4.1 Experiment Setup
4.2 Algorithm Performance
4.3 Post-quantum with Standard DNSSEC
4.4 Post-quantum with ARRF
4.5 Data Transmission
4.6 Results
5 Discussion
5.1 Performance
5.2 Backwards Compatibility
5.3 Security Considerations
5.4 Comparing ARRF against Previous DNS Fragmentation Proposals
6 Future Work
7 Conclusion
A Appendix – Performance Graphs
References
Hash-Based Direct Anonymous Attestation
1 Introduction
2 Preliminaries
2.1 Hash-Based Signatures
2.2 MPC-in-the-Head and Picnic-Style Signatures
2.3 DAA Concept
3 Construction
3.1 F-SPHINCS+ and M-FORS
3.2 The DAA Scheme
3.3 The Proof D
4 Security Analysis of F-SPHINCS+
5 Soundness Analysis of D
6 UC Security Model for DAA
7 UC Security Proof of the DAA Scheme
7.1 High-Level Description of Our Proof
7.2 The DAA Scheme Proof
8 Conclusion
References
Muckle+: End-to-End Hybrid Authenticated Key Exchanges
1 Introduction
1.1 Contribution
1.2 Related Work
2 Preliminaries
2.1 Cryptographic Primitives and Schemes
2.2 Hybrid Authenticated Key Exchange
3 Extending Muckle with Signature-Based Authentication
3.1 Muckle
3.2 Extending Muckle with Signature-Based Authentication
3.3 Security of Muckle+
3.4 Instantiating Muckle+
4 Implementation and Evaluation
5 Conclusion and Outlook
References
Side-Channel Cryptanalysis and Countermeasures
WrapQ: Side-Channel Secure Key Management for Post-quantum Cryptography
1 Introduction
1.1 Side-Channel Countermeasures for Lattice Cryptography
1.2 Sensitivity Analysis: Private Keys and Secret Variables
1.3 Outline of this Work and Our Contributions
2 Masked Key Wrapping
2.1 High Level Interface
3 WrapQ 1.0 Design Outline
3.1 Design Choices
3.2 Masked XOF and Domain Separation
3.3 Integrity Protection: Masked MAC Computation
3.4 Confidentiality Protection: Encrypting Masked Plaintext
4 Kyber and Dilithium Private Keys
4.1 CRYSTALS-Kyber
4.2 CRYSTALS-Dilithium
5 Parameter Selection and Algorithm Analysis
5.1 Wrapping Process
5.2 Unwrapping Process
5.3 Size Metrics
6 Implementation and Leakage Assessment
6.1 FPGA Platform Overview
6.2 Implementation Overview
6.3 Leakage Assessment: Fixed-vs-Random Experiments
6.4 Trace Acquisition and Results
7 Conclusions and Future Work
References
Faulting Winternitz One-Time Signatures to Forge LMS, XMSS, or SPHINCS+ Signatures
1 Introduction
2 Hash-Based Signatures
2.1 Winternitz One-Time Signatures
2.2 LMS, XMSS, and SPHINCS+
3 Attack Sketch
3.1 Brute-Force Forgery of WOTS
3.2 Fault Attack on WOTS Checksum Chains
3.3 Faulting WOTS to Break LMS, XMSS, and SPHINCS+
3.4 Attack Variants
3.5 Adversarial Model
4 Probabilistic Analysis
4.1 Probabilities
4.2 Probabilities wrt. Adversary Capabilities
5 Countermeasures
6 Attack in Practice
6.1 Brute-force Forgery of WOTS
6.2 Fault Attack on HBSs
7 Conclusion
References
Breaking and Protecting the Crystal: Side-Channel Analysis of Dilithium in Hardware
1 Introduction
2 Preliminaries
2.1 Notation
2.2 CRYSTALS-Dilithium
2.3 Side-Channel Analysis
3 Conceptual Considerations
3.1 Bit-Packing and Decoding of Secret Polynomials s1,s2
3.2 Number-Theoretic Transform
3.3 Polynomial Multiplication
3.4 Measurement Setup
4 Simple Power Analysis
4.1 Targeting Single Coefficients
4.2 Extension to Multiple Coefficients
4.3 Attack on =4
5 Correlation Power Analysis on the Polynomial Multiplication
5.1 Power Model
5.2 Noise
5.3 Attacks
6 Countermeasures
6.1 Integration of Decoding into the First NTT Stage
6.2 Masking
6.3 Evaluation
7 Discussion and Future Work
References
Author Index