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