دانلود کتاب Post-Quantum Cryptography: 13th International Workshop, PQCrypto 2022, Virtual Event, September 28–30, 2022, Proceedings (Lecture Notes in Computer Science)

فهرست مطالب :

Preface
Organization
Contents
Code-Based Cryptography
Hybrid Decoding – Classical-Quantum Trade-Offs for Information Set Decoding
1 Introduction
2 Preliminaries
3 A Quantum ISD Circuit Design
3.1 Reducing the Width for Free
4 Classical-Time Quantum-Memory Trade-Offs
4.1 Shortening the Code
4.2 Puncturing the Code
4.3 Combined Hybrid
References
How to Backdoor (Classic) McEliece and How to Guard Against Backdoors
1 Introduction
2 Background
2.1 McEliece and Binary Goppa Codes
2.2 SETUP Mechanism
3 Backdooring Vanilla McEliece
3.1 Key Generation for Vanilla McEliece
3.2 Vanilla McEliece Strong SETUP
3.3 From Strong to Weak SETUP
4 How to Backdoor Classic McEliece
5 How to Use McEliece Encryption Against Classic McEliece
A Appendix: A Simpler (But Flawed) SETUP Mechanism
A.1 A Flawed SETUP
A.2 The distinguisher
References
LRPC Codes with Multiple Syndromes: Near Ideal-Size KEMs Without Ideals
1 Introduction and Previous Work
2 Background on Rank Metric Codes
2.1 General Definitions
2.2 Ideal Codes
2.3 Difficult Problems in Rank Metric
3 LRPC Codes and their Decoding
3.1 Low Rank Parity Check Codes
3.2 A Basic Decoding Algorithm
3.3 LRPC Codes Indistinguishability
4 LRPC with Multiple Syndromes
4.1 General Idea
4.2 Description of the Scheme (LRPC-MS)
4.3 Description of the Scheme with Ideal Structure (ILRPC-MS)
4.4 Decoding Failure Rate of Our Scheme
4.5 Impact on the Asymptotic Range of Parameters
5 Security
5.1 Definitions
5.2 IND-CPA Proof
5.3 Known Attacks
6 Parameters
7 Conclusion and Future Work
A Dimension of the Support of the Product of Homogeneous Matrices
A.1 Preliminary Results on Binary Matrices
A.2 Proof of Theorem 1
B Performance
References
Interleaved Prange: A New Generic Decoder for Interleaved Codes
1 Introduction
2 Preliminaries
3 Decoding Algorithms
3.1 SD-Based Algorithms
3.2 CF-Based Algorithms
3.3 Novel Approach: Interleaved Prange
3.4 Recognizing Failures
3.5 Comparison
4 Conclusion
References
A Study of Error Floor Behavior in QC-MDPC Codes
1 Introduction
2 Background
2.1 Coding Theory and QC-MDPC Codes
2.2 BIKE
2.3 Weak Keys and Near Codewords
3 Methods
4 Average DFR over Full Message Space
5 DFR on At,(S) Sets
6 Distribution of Syndrome Weight
7 Conclusion
References
Multivariate Cryptography and the MinRank Problem
Improvement of Algebraic Attacks for Solving Superdetermined MinRank Instances
1 Introduction
2 Notation and Preliminaries
3 Relations Between the Various Modelings
4 Complexity of Solving Superdetermined Systems
5 Application to DAGS
5.1 Principle of the Attack
5.2 Original Modeling
5.3 Modeling Update
A Appendix
References
A New Fault Attack on UOV Multivariate Signature Scheme
1 Introduction
2 Preliminaries
2.1 Multivariate Signature Schemes
2.2 Unbalanced Oil and Vinegar Signature Scheme
2.3 Attacks on UOV
2.4 Existing Fault Attacks on UOV or Its Variant
3 New Fault Attack on UOV
3.1 Attack Model
3.2 Description
4 Analysis of Our Proposed Attack
4.1 Application of Key Recovery Attacks
4.2 Simulations of Our Proposed Attack
4.3 Limited Faults Cases
5 Conclusion
References
MR-DSS – Smaller MinRank-Based (Ring-)Signatures
1 Introduction
1.1 Related Work
1.2 Contribution
2 Preliminaries
2.1 Sigma Protocols with Helper
2.2 Commitment Schemes
3 The Sigma Protocol of Courtois
4 Improved MinRank-Based Signature Scheme
4.1 Sigma Protocol with Helper for ZK Proof of MinRank
4.2 Removing the Helper
4.3 Further Improvements
4.4 Public Key Size
4.5 Signature Size
4.6 Parameters
5 MinRank-Based Ring Signatures
5.1 Extending to Ring Signatures
5.2 Parameters of the Scheme
5.3 Public Key and Signature Size
A Commitment Scheme
B Ring Signatures
B.1 Security Definitions
B.2 Proofs
C A Note on Santoso et al.\'s Scheme
References
IPRainbow
1 Introduction
2 UOV and Rainbow
2.1 Oil and Vinegar
2.2 Rainbow
3 Known Attacks of Rainbow
3.1 Background
3.2 Rectangular MinRank Attack
3.3 Simple Attack
4 IPRainbow
4.1 Description of IPRainbow
4.2 Security Analysis
4.3 Efficiency and Key Size
5 Conclusion
A Algorithms
References
2F - A New Method for Constructing Efficient Multivariate Encryption Schemes
1 Introduction
2 Multivariate Encryption Schemes
2.1 HFE
2.2 SQUARE
2.3 ABC Simple Matrix
2.4 PCBM
3 2F Modulus Switching
4 An Instance of 2F Multivariate Encryption
5 Security Analysis
5.1 MinRank Attacks
5.2 Differential
5.3 Direct
5.4 Lattice Attacks
6 Parameters and Performance
7 Conclusion
References
Quantum Algorithms, Attacks and Models
Quantum Attacks on Lai-Massey Structure
1 Introduction
2 Preliminaries
2.1 Notation
2.2 Pseudo-Random Permutation
2.3 Quantum Algorithms
3 Quantum Attacks on Lai-Massey Structures
3.1 Quantum Chosen-Plaintext Attack Against 3-Round Lai-Massey Structure
3.2 Quantum Chosen-Ciphertext Attack Against 4 Round Lai-Massey Structure
3.3 Quantum Key-Recovery Attack on 4-Round Lai-Massey Structure
4 Lai-Massey and Quasi-Feistel Structures
4.1 Quasi-Feistel Structure
4.2 Lai-Massey and Quasi-Feistel Structures
5 Quantum Attacks Against Quasi-Feistel Structures
5.1 Quantum Chosen-Plaintext Attack Against 3-Round Quasi-Feistel Structure
5.2 Quantum Chosen-Ciphertext Attack Against 4-Round Quasi-Feistel Structure
6 Conclusion and Discussion
A Intermediate Parameters in the Decryption Process of 4-round Lai-Massey Structure in Sect.3.2
B Proof of Theorem 4
References
Sponge-Based Authenticated Encryption: Security Against Quantum Attackers
1 Introduction
2 Preliminaries
2.1 Notation
2.2 Definitions
3 The Sponge Construction and Slae
3.1 Sponge Construction
3.2 The FGHF\' Construction and Slae
4 Post-Quantum (QS1) Security
4.1 Security of SlFunc
4.2 Security of SPrg
4.3 Security of SvHash
4.4 Security of Slae
5 Quantum (QS2) Security
5.1 QS2 Security Notions for SKE
5.2 Left-or-Right Security of SlEnc
5.3 Real-or-Random Security of SlEnc
5.4 IND-qCPA Security of Slae and FGHF\'
6 Conclusion
A Additional Preliminaries
A.1 Authenticated Encryption
A.2 Message Authentication Code
A.3 Hash Function
B QS1 Proofs
B.1 Proof of Theorem 8
B.2 Proof of Theorem 9
B.3 Proof of Theorem 10
B.4 Proof of Theorem 11
B.5 Proof of Theorem 12
C QS2 Proofs
C.1 Proof of Theorem 14
References
Post-quantum Plaintext-Awareness
1 Introduction
1.1 Motivation
1.2 Challenges and Our Contribution
1.3 Our Contribution
1.4 Organization
2 Preliminaries
2.1 Definitions
3 Post-quantum Plaintext-Awareness
3.1 Post-quantum PA0, PA1
3.2 Post-quantum PA2
4 Relationships Between Notions
4.1 Relationships Between PA Notions
4.2 Relation with IND-qCCA
5 Achievability
A Preliminaries
A.1 Commitment Scheme
A.2 Basics of Quantum Computing
B Discussion on Quantum Eavesdropping
C Proof of Theorem 8
D Achievability
D.1 OAEP transform
References
On Quantum Ciphertext Indistinguishability, Recoverability, and OAEP
1 Introduction
1.1 Our Contribution
1.2 Related Work
1.3 Outline
2 Preliminaries
2.1 Notation
2.2 Public-Key Cryptography
2.3 Quantum Computing
3 (Quantum) Ciphertext Indistinguishability
3.1 The qINDqCPA Security Notion
3.2 Interpretation of Ciphertext Indistinguishability
4 Observations on Recoverability
4.1 Recoverability
4.2 Equivalent Recoverable PKE Schemes
5 OAEP
5.1 Recoverability of OAEP
5.2 Quantum Operators for OAEP
References
Implementation and Side Channel Attacks
Efficiently Masking Polynomial Inversion at Arbitrary Order
1 Introduction
2 Preliminaries
2.1 Notation
2.2 Masking
2.3 Polynomial Inversion Applications
3 Masking Polynomial Inversion
3.1 Conversion from Additive to Multiplicative Sharing
3.2 Conversion from Multiplicative to Additive Sharing
3.3 Reducing the Number of Inversions
3.4 Reducing the Number of Multiplications
4 Implementation and Evaluation
4.1 Implementation Results
4.2 Side-Channel Evaluation
5 Conclusion
References
A Power Side-Channel Attack on the Reed-Muller Reed-Solomon Version of the HQC Cryptosystem
1 Introduction
2 Preliminaries
2.1 Notation
2.2 HQC
2.3 Choice of Error Correcting Code C
3 Novel Oracle-Based Side-Channel Attack
3.1 Support Distribution of y
3.2 General Attack Idea
3.3 Description of the Attack Strategy
3.4 Retrieval of y from Partial Information with Information Set Decoding
4 Side-Channel Targets to Build the Required Oracle
4.1 Power Side-Channel of the RS Decoder
4.2 Power Side-Channel of the Used Hash Functions G,H
4.3 Timing Side-Channel of the Used Sampler
5 Conclusion
A Counterexample to the Attack Strategy in ch16Ueno2021,ch16Xagawa21archive
B Modified Variant of Stern\'s Algorithm
C T-Test Result: Power Side-Channel of the RS Decoder
References
A New Key Recovery Side-Channel Attack on HQC with Chosen Ciphertext
1 Introduction
2 Hamming Quasi-Cyclic (HQC)
2.1 HQC Overview
2.2 Decoding Reed-Muller Codes
3 Theoretical Combined Chosen Ciphertext and Side-Channel Attacks
3.1 Support Distribution of y
3.2 Chosen Ciphertext Attack with Oracle
4 Building Decoding Oracle with a Side-Channel
4.1 Building the Oracle
4.2 Results
5 Countermeasure
6 Conclusion and Future Work
References
Isogeny
On Actively Secure Fine-Grained Access Structures from Isogeny Assumptions
1 Introduction
2 Preliminaries
2.1 Secret Sharing Schemes
2.2 Hard Homogeneous Spaces
2.3 Threshold Group Action
2.4 Piecewise Verifiable Proofs
2.5 Zero-Knowledge Proofs for the GAIP
2.6 The Adversary
2.7 Communication Channels
3 Key Exchange Mechanism
3.1 Public Parameters
3.2 Key Generation
3.3 Encapsulation
3.4 Decapsulation
3.5 Amending the PVP
3.6 Security
3.7 Efficiency
4 Actively Secure Secret Shared Signature Protocols
4.1 Instantiations
5 Generalising the Secret Sharing Schemes
5.1 Compatibility Requirements
5.2 Examples of Secret Sharing Schemes
6 Conclusion
Appendix A Algorithms
References
Attack on SHealS and HealS: The Second Wave of GPST
1 Introduction
1.1 Concurrent Works
1.2 Technical Overview
2 Preliminaries
2.1 Elliptic Curves and Isogenies
2.2 Brief Outline of HealSIDH Key Exchange
3 Parity Recovering
4 Recover the Secret
4.1 Quasi-Inverse Element
4.2 Attack on HealS and SHealS
5 Summary
A A Generalized Attack
References
Post-Quantum Signal Key Agreement from SIDH
1 Introduction
1.1 Related Work
2 The Signal X3DH Protocol
3 SIDH
3.1 New SI-CDH-Based Assumptions
4 Security Model
4.1 Key Indistinguishability Experiment
4.2 Further Security Properties
5 Using SIDH for Post-quantum X3DH
6 Efficiency
7 Conclusion
A Proofs of VCDH and HCDH Reductions
B Proof of Theorem 1
B.1 Cases E2, E3, E6 (MEX)
B.2 Cases E1, E7
B.3 Case E5 (wPFS)
B.4 Deniability Proof Sketch
C Standard Key Indistinguishability Definitions
References
Lattice-Based Cryptography
Forward-Secure Revocable Secret Handshakes from Lattices
1 Introduction
2 Preliminaries
2.1 Background on Lattices
2.2 Efficient Signature Scheme from Lattices
2.3 Zero-Knowledge Argument Systems
2.4 LWE-Based Key Exchange
3 Model of Forward-Secure Secret Handshakes
4 The Supporting Zero-Knowledge Layer
4.1 ZKAoK System for Proving a Valid User
4.2 Transformation to Anonymous Mutual Authentication
5 FSSH with Revocability from Lattices
5.1 Description of the Scheme
5.2 Analysis of the Scheme
A Deferred Proof of Theorem 3
References
Estimating the Hidden Overheads in the BDGL Lattice Sieving Algorithm
1 Introduction
1.1 Context
1.2 This Work
2 Preliminaries
2.1 List-Decoding Sieve, Idealized
2.2 List-Decoding Sieve, Instantiated
3 Analyzing the List-Decoding Sieve Instantiation
3.1 Overheads and Trade-Offs
3.2 Measuring PO, Naively
3.3 Measuring PO, a First Speed-Up
3.4 Measuring PO, a Second Speed-Up
4 Implementation and Experiments
4.1 Consistency Checks
4.2 Trends
4.3 Concrete Estimate in Dimension 384
5 Impact on Attacks
5.1 Mitigation Inside Progressive-Sieve and Progressive-BKZ
6 Open Problems
References
Cryptanalysis
Breaking Category Five SPHINCS+ with SHA-256
1 Introduction
2 The SPHINCS+ Signature Scheme
3 Building Blocks
3.1 Merkle-Damgård Hash Functions
3.2 Multi-target Preimage Attacks and SPHINCS+
3.3 Antonov\'s Attack on DM-SPR
4 Creating Forgeries for SPHINCS+ Category Five Parameters
4.1 Turning Antonov\'s Attack into a Forgery Attack
4.2 Summary of Our Attack
4.3 Overview of the Forgery Attack on SPHINCS+-SHA-256 with Category Five Parameters
5 Optimizations and Attack Cost Calculations
5.1 Collision Search and General Framework
5.2 Multi-target Preimage Search
5.3 Multi-collision Search
5.4 Batched Multi-target Multi-collision Search
6 Conclusions
References
Author Index