Post-Quantum Cryptography: 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20–22, 2021, Proceedings (Security and Cryptology)

Preface
Organization
Contents
Code-Based Cryptography
Decoding Supercodes of Gabidulin Codes and Applications to Cryptanalysis
	1 Notation and Prerequisites
	2 Two Rank Metric Proposals with Short Keys
		2.1 Liga encryption scheme
		2.2 Ramesses
	3 Decoding of Gabidulin Codes on the Right
	4 Decoding Supercodes of Gabidulin Codes
	5 Applications to Cryptanalysis
		5.1 Ramesses
		5.2 A Message Recovery Attack Against Liga Cryptosystem
	A Further Details About RAMESSES\' Specifications
		A.1 Key Generation
		A.2 Encryption
		A.3 Decryption
	B Detailed Presentation of the Right–Hand Side Version of the Decoding of Gabidulin Codes
	References
LESS-FM: Fine-Tuning Signatures from the Code Equivalence Problem
	1 Introduction
	2 Background
		2.1 Code Equivalence
	3 Code-Based Group Actions and Applications
	4 Optimizations
		4.1 Multi-bit Challenges
		4.2 Fixed-Weight Challenges
		4.3 Combining the Approaches
	5 Concrete Parameter Sets and Implementation Strategies
	A  Cryptographic Group Actions
	B  EUF-CMA Security of LESS
	C  EUF-CMA Security of LESS-M
	D  EUF-CMA Security of LESS-F
	E  The Automorphism Group of a Random Code
		E.1  Proof for the Permutations Automorphism Group
	References
Classical and Quantum Algorithms for Generic Syndrome Decoding Problems and Applications to the Lee Metric
	1 Introduction
	2 Syndrome Decoding Problems
	3 Information Set Decoding Algorithms for Any Metric
		3.1 Information Set Decoding Framework
		3.2 Information Set Decoding: Complexity Analysis (Classical and Quantum)
	4 Wagner\'s Algorithm for Solving CMSD
		4.1 Complexity Analysis of Wagner\'s Algorithm
	5 Application to Lee\'s Distance
		5.1 Computing Surface Area of a Sphere
		5.2 Results for Lee\'s Metric
	A  Quantum preliminaries
	B  Proof of Lemma 1
	C  Analysis of Wagner\'s algorithms
		C.1  The list merging procedure
		C.2  Variant 1 of Wagner\'s algorithm
		C.3  Variant 2: Unbalanced Wagner.
	D  Computing surface areas
	E  Convex optimization problem
	References
Multivariate Cryptography
Improving Thomae-Wolf Algorithm for Solving Underdetermined Multivariate Quadratic Polynomial Problem
	1 Introduction
	2 Multivariate Quadratic Polynomial Problem
		2.1 Hybrid Approach
	3 Thomae–Wolf Algorithm
		3.1 Description
		3.2 Choice of Linearization Factor
	4 Proposed Algorithm
		4.1 Description
		4.2 Choice of Linearization Factor
		4.3 Comparison
	5 Proposed Algorithm for the Binary Field
		5.1 Description
		5.2 Choice of Linearization Factor
		5.3 Comparison
	6 Conclusion
	References
New Practical Multivariate Signatures from a Nonlinear Modifier
	1 Introduction
	2 Multivariate Signature Schemes
		2.1 Unbalanced Oil-Vinegar (UOV)
		2.2 Step-Wise Triangular System (STS)
		2.3 C*
	3 Modifiers
	4 The Q Modifier
	5 New Schemes
		5.1 QC*
		5.2 QSTS
	6 Security Analysis
		6.1 Q Kernel Attacks
		6.2 Direct Attacks
		6.3 Rank Attacks
		6.4 Differential Attacks
		6.5 Chosen Message Attacks
	7 Parameters and Performance
	8 Conclusion
	A  Toy Example
	References
On the Effect of Projection on Rank Attacks in Multivariate Cryptography
	1 Introduction
	2 Big Field Cryptosystems
	3 New Rank Attack
	4 Effect of Projection on the New Rank Attack
		4.1 Projection and the HFE Central Map
		4.2 Projection and the C* Central Map
	5 Experiments
	6 Complexity
		6.1 PHFEv- Signing
		6.2 PFLASH Signing
	7 Conclusion
	A  Toy Example of Composing Minimal Polynomials
	B  GeMSS Minrank Complexity
	References
Quantum Algorithms
Quantum Key Search for Ternary LWE
	1 Introduction
	2 Preliminaries
		2.1 LWE-keys
		2.2 Quantum Walk
	3 Quantum Meet-LWE - High Level Idea
		3.1 Classical Meet-LWE
		3.2 Quantum Meet-LWE (QMeet-LWE)
	4 QRep-0: A First Implementation of QMeet-LWE
	5 QREP-1: Optimized QMeet-LWE
	6 Quantum Complexity Estimates
	7 Time-Memory Tradeoffs
	References
A Fusion Algorithm for Solving the Hidden Shift Problem in Finite Abelian Groups
	1 Introduction
	2 Consequences for the Vectorization Problem
	3 Polynomial-Time Hidden Shifts in 2tp-torsion Groups
	4 Collimation for Products of Cyclic Groups
	5 Merging both Algorithms
	6 Conclusion
	A  Expected Quality of a Collimation Step
	References
The ``Quantum Annoying\'\' Property of Password-Authenticated Key Exchange Protocols
	1 Introduction
	2 Background
		2.1 The CPace Protocol
		2.2 The Generic Group Model
	3 Generic Group Model Proof of CPace_core
		3.1 CPace_core Game Definition
		3.2 Proof Outline
		3.3 Proof of Theorem 1
	References
Implementation and Side Channel Attack
Differential Power Analysis of the Picnic Signature Scheme
	1 Introduction
	2 Preliminaries
	3 DPA on LowMC and The Extensions to Picnic
		3.1 Attack on the Secret Sharing Process
		3.2 Attack on the Substitution Layer
	4 Practical Setup and Experimental Results
		4.1 Results of the Attack on the Secret Sharing Process
		4.2 The Practical Results of Attack on the Substitution Layer
		4.3 Algebraic Key Recovery
	5 Conclusion
	A  Leakage Assessment
	B  Additional Algorithms
	C  Differential Power Analysis Results on Rounds 2–5
	References
Implementation of Lattice Trapdoors on Modules and Applications
	1 Introduction
	2 Preliminaries
	3 Gaussian Preimage Sampling on Module Lattices
		3.1 Perturbation Sampling
		3.2 Implementation
		3.3 Performances
	4 Applications
		4.1 The GPV Signature Scheme on Modules
		4.2 A Standard Model Signature Scheme on Modules
		4.3 An Identity-Based Encryption Scheme on Modules
	References
Verifying Post-Quantum Signatures in 8kB of RAM
	1 Introduction
	2 Analyzed Post-Quantum Signature Schemes
		2.1 Hash-Based Schemes
		2.2 Multivariate-Based Schemes
		2.3 Lattice-Based Schemes
	3 Implementation
		3.1 Streaming Interface
		3.2 Public Key Verification
		3.3 Implementation Details
	4 Results
	References
	A Feature Activation
	B Alternative Implementation
	C Hash-Based Signatures
Fast NEON-Based Multiplication for Lattice-Based NIST Post-quantum Cryptography Finalists
	1 Introduction
	2 Previous Work
	3 Background
		3.1 NTRU
		3.2 Saber
		3.3 Kyber
		3.4 Polynomial Multiplication
	4 Toom-Cook in NTRU and Saber Implementations
		4.1 Saber
		4.2 NTRU
	5 NTT in Kyber and Saber Implementations
		5.1 NTT
		5.2 Range Analysis
		5.3 Vectorized Modular Reduction
	6 Results
	7 Conclusions
	References
Isogeny
CSI-RAShi: Distributed Key Generation for CSIDH
	1 Introduction
	2 Background
		2.1 Very Hard Homogeneous Spaces
		2.2 Zero-Knowledge Proofs
	3 Distributed Key Generation in the VHHS-Setting
		3.1 Security Definitions
		3.2 Comparison to Security Definitions in DLOG Setting
	4 Piecewise Verifiable Proofs
	5 Distributed Key Generation
	6 Instantiation Based on Isogenies
	7 Conclusion
	A  Security Proof of NIPVP
		A.1  Completeness
		A.2  Soundness
		A.3  Zero-Knowledge
	References
SimS: A Simplification of SiGamal
	1 Introduction
	2 Preliminaries
		2.1 Public Key Encryption
		2.2 Class Group Action on Supersingular Curves Defined Over Fp
		2.3 CSIDH
	3 Another Look at SiGamal Protocol
		3.1 SiGamal Protocol and Variants
		3.2 An IND-CCA Attack on Moriya et al.\'s Variant
	4 SimS
		4.1 Overview
		4.2 The SimS Public Key Encryption Protocol
		4.3 Security Arguments
	5 Implementation Results
	6 Comparison with SiGamal and CSIDH
	7 Conclusion
	A Knowledge of Exponent Assumption
	B Generating the Distinguished Point of Order 2r
	References
Memory Optimization Techniques for Computing Discrete Logarithms in Compressed SIKE
	1 Introduction
		1.1 The Organization and Contributions:
		1.2 Notation
	2 Optimization 1: Signed Digits in the Exponent
	3 Optimization 2: Torus-Based Representation and Arithmetic in Cyclotomic Subgroups
		3.1 Linear Time Algorithms
		3.2 An Exponential Time Algorithm for l=2
		3.3 A Hybrid Algorithm for l=2
	4 Implementation Results and Comparisons
	5 Concluding Remarks
	A The Pohlig-Hellman Algorithm with width-w Windows
	B  Torus-based Representations
	C  Proofs
	D  Algorithms
	References
Lattice-Based Cryptography
Generating Cryptographically-Strong Random Lattice Bases and Recognizing Rotations of Zn
	1 Introduction
	2 Choosing Random Elements of GL(n,Z)
	3 Experiments on Recognizing Zn
		3.1 Experiments with Algorithm 2 (Magma\'s RandomSLnZ Command)
		3.2 Experiments with Algorithm 3 (Random GL(d,Z) Matrices)
		3.3 Experiments with Algorithm 4
	4 Random Basis Generation in the DRS NIST Post-Quantum Cryptography Competition Submission
	5 Conclusions
	A Experiments with Algorithm 3 (Random GL(d,Z) Matrices)
	B Experiments with Algorithm 4
	C A Reference Point for the Bit-Strength of Lattice Problems: NTRU
	References
Zero-Knowledge Proofs for Committed Symmetric Boolean Functions
	1 Introduction
	2 Background
		2.1 Zero-Knowledge Proofs of Knowledge and Stern-Like Protocols
		2.2 Commitments from Learning Parity with Noise
	3 Techniques for Evaluating Symmetric Boolean Functions in Zero-Knowledge
	4 Protocol
		4.1 Problem Statement
		4.2 Construction
	References
Short Identity-Based Signatures with Tight Security from Lattices
	1 Introduction
		1.1 Technical Details
		1.2 More on Related Work
	2 Preliminaries
	3 Generic Constructions of Adaptively Secure IBS
		3.1 Transformation in the Standard Model
		3.2 Transformation in the Random Oracle Model
	4 Non-adaptive Security from SIS
	References
On Removing Rejection Conditions in Practical Lattice-Based Signatures
	1 Introduction
		1.1 Contributions
		1.2 Technical Overview
	2 Preliminaries
	3 Adaptive Bounded Distance Decoding
	4 Proposed Scheme
	5 The Difficulty of Removing the Remaining Rejection Condition
		5.1 Impossibility of Extracting Consistent Values from Commitments with Errors
		5.2 Evidence on the Difficulty of Adapting the Reconciliation Mechanism
		5.3 Discussions of the Possible Generalizations and Limitations
	6 Parameter and Comparison
	A  Standard Definitions
		A.1  Digital Signatures
	B  Correctness and Security Analysis
	References
Secure Hybrid Encryption in the Standard Model from Hard Learning Problems
	1 Introduction
		1.1 Our Contributions
		1.2 Our Approach
	2 Preliminaries
		2.1 Definitions of Cryptographic Primitives
	3 CCA-Secure Hybrid Encryption from LWE
		3.1 Security Proof
	4 CCA-Secure Hybrid Encryption from Low-Noise LPN
	5 Conclusion
	References
Cryptanalysis
Attacks on Beyond-Birthday-Bound MACs in the Quantum Setting
	1 Introduction
	2 Preliminaries
		2.1 Quantum Algorithms
		2.2 Quantum Security of MACs
	3 Secret State Recovery Attack for BBB MACs
		3.1 Secret State Recovery Attack for SUM-ECBC-like MACs
		3.2 Secret State Recovery Attack for PMAC_Plus-like MACs
	4 Key Recovery Attack for PMAC_Plus-like MACs
		4.1 Partial Key Recovery Attack for PMAC_Plus-like MACs
		4.2 Full Key Recovery Attack for PMAC_Plus-like MACs
	5 Conclusions
	A  Proof of  for SUM-ECBC
	B  Proof of  for PMAC_Plus
	C  Proof of  for 3kf9
	D  Deviation Estimation in Key Recovery Attacks
		D.1  Deviation Estimation for PMAC_Plus
		D.2  Deviation Estimation for 3kf9
	E  Key Recovery Attack for SUM-ECBC
	References
An Algebraic Approach to the Rank Support Learning Problem
	1 Introduction
	2 Durandal and the RSL Problem
		2.1 Key Pair in Durandal
		2.2 Previous Cryptanalysis on RSL
	3 The RSL-Minors Modeling
		3.1 The Basic Modeling
		3.2 Shortening Caug as Much as Possible (= 0)
		3.3 Looking for Words of Smaller Weight in Caug (> 0)
	4 Solving the RSL Minors Equations by Linearization
		4.1 Number of Independent Equations for the System over Fqm
		4.2 Solving the RSL Minors Equations by Linearization
	5 Complexity of the Attack on New Durandal Parameters
	6 Conclusion
	A  Proofs of Lemma 1 and Theorems 1 And 2
	B  Number of Low Weight Codewords
	References
Quantum Indistinguishability for Public Key Encryption
	1 Introduction
		1.1 Our Contribution
		1.2 Related Work
	2 Preliminaries
		2.1 Quantum Notation
	3 Quantum Indistinguishability for PKE Schemes
		3.1 Type-1 Operators for PKE
		3.2 Type-2 Encryption for PKE
		3.3 Recoverable PKE Schemes
		3.4 The qIND-qCPA Security Notion
		3.5 The CCA Case
	4 Security Analysis for Real-World PKE Schemes
		4.1 Results for Code-Based PKE ROLLO-II
		4.2 Results for Hybrid Encryption
	References
A Practical Adaptive Key Recovery Attack on the LGM (GSW-like) Cryptosystem
	1 Introduction
	2 Preliminaries
		2.1 Distributions
	3 The LGM Scheme
		3.1 Parameter Derivation
	4 The Key Recovery Attack
		4.1 Generalisation of the Attack
		4.2 Implementation of the Attack
		4.3 i Drawn from a Non-uniform Distribution
		4.4 Thwarting the Attack
	5 Conclusion
	References
Author Index