Public-Key Cryptography – PKC 2022: 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Virtual Event, March 8–11, 2022, Proceedings, Part I (Security and Cryptology)

The two-volume proceedings set LNCS 13177 and 13178 constitutes the refereed proceedings of the 25th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2022, which took place virtually during March 7-11, 2022. The conference was originally planned to take place in Yokohama, Japan, but had to change to an online format due to the COVID-19 pandemic. The 40 papers included in these proceedings were carefully reviewed and selected from 137 submissions. They focus on all aspects of public-key cryptography, covering cryptanalysis; MPC and secret sharing; cryptographic protocols; tools; SNARKs and NIZKs; key exchange; theory; encryption; and signatures. Preface Organization Contents – Part I Contents – Part II Cryptanalysis Multitarget Decryption Failure Attacks and Their Application to Saber and Kyber 1 Introduction 2 Preliminaries 2.1 Notation 2.2 Cryptographic Definitions 2.3 Lattice-Based Encryption 2.4 Chosen-Ciphertext Security 2.5 Decryption Failures 3 Failure Boosting Attacks 3.1 Directional Failure Boosting 3.2 Estimation of Efficiency 4 Multitarget Attacks 4.1 Naive Multitarget 4.2 Levelled Multitarget 5 Better Failure Boosting Estimation 5.1 Weak Keys 5.2 Calculating SE 5.3 Inclusion of S and G 6 Dealing with Uneven Distributions 6.1 Uneven Distributions 6.2 Meet-in-the-middle Speedup 6.3 Removing the Bias 6.4 Discussion 7 Attack Constraints 8 Results 8.1 Impact on Saber and Kyber 8.2 Increasing the Attack Cost 8.3 Possible Future Advances References Post-quantum Security of Plain OAEP Transform 1 Introduction 2 Preliminaries 2.1 Quantum Computing 2.2 Definitions 2.3 Compressed Standard Oracle 3 Security of OAEP References On the Security of OSIDH 1 Introduction 1.1 Overview 2 Oriented Supersingular Elliptic Curves 2.1 Oriented Elliptic Curves and Isogenies 2.2 Class Group Action 2.3 Oriented Supersingular Isogeny Graphs 2.4 Effective Computation of the Ideal Class Group Action 3 Oriented Supersingular Isogeny Diffie–Hellman 3.1 The OSIDH Setup 3.2 A Straw Man Key Exchange Scheme 3.3 Inverting the Class Group Action on Descending Chains 3.4 The OSIDH Key Exchange 4 Our Attack on OSIDH 4.1 Onuki's Idea 4.2 Finding Endomorphisms via Relations 4.3 Extending the Attack by Exhaustive Search 4.4 Implementation of Our Attack 5 Countermeasures 5.1 Increase t, and Everything Else 5.2 Increase #Cl(On), Keep the Same Key Space 5.3 OSIDH and Cryptographic Group Actions 6 Conclusion A Time Complexity of the Chain Attack of Sect.3.3 B Complexity Analysis of Onuki's Attack Presented in Sect.4.1 References Time-Memory Tradeoffs for Large-Weight Syndrome Decoding in Ternary Codes 1 Introduction 2 Preliminaries 2.1 Notation and Definitions 2.2 The Large-Weight Ternary Syndrome Decoding Problem 3 A Framework for Solving the Ternary Syndrome Decoding Problem 3.1 The PGE+SS Framework 3.2 Required Number of Solution for the Subset-Sum Problem 3.3 Parameterization of the Subset-Sum Problem 4 Fundamental Algorithms for the Generalised Birthday Problem 4.1 Subset Sum as a Generalised Birthday Problem 4.2 Application of the k-Tree Algorithm to Syndrome Decoding 4.3 Solving Generalised Birthday Problems with Dissection 4.4 Application of the Dissection Framework to Syndrome Decoding 4.5 Comparison of the k-Tree and Dissection Frameworks 5 Dissection in Tree for Syndrome Decoding 5.1 The Main Algorithm of Dissection in Tree 5.2 Improvements for Syndrome Decoding 5.3 Experimental Results 6 Application to Wave References Syndrome Decoding Estimator 1 Introduction 2 Preliminaries 3 ISD Algorithms from a Nearest Neighbor Perspective 4 An ISD Framework Based on Nearest Neighbor Search 4.1 Concrete Practical Instantiations of the Framework 4.2 Joint Weight Distributions 5 Estimator 5.1 Quantum Security References On the Isogeny Problem with Torsion Point Information 1 Introduction 2 Preliminaries 2.1 Elliptic Curves and Isogenies 2.2 SIDH and B-SIDH 2.3 KLPT and LLL Lattice Reduction 2.4 GPST 3 Computing Isogenies Using Torsion Information 3.1 Evaluating Non-smooth Degree Isogenies 3.2 Main Algorithm 3.3 Example 4 Relevance to Isogeny-Based Cryptography 5 Conclusion References MPC and Secret Sharing Reusable Two-Round MPC from LPN 1 Introduction 1.1 Our Results 2 Technical Overview 2.1 Multi-party Silent NISC 2.2 Reusable Two-Round MPC from LPN 3 Preliminaries 3.1 Learning Parity with Noise 3.2 PCG 4 Multiparty NISC with Silent Preprocessing 4.1 Multiparty Silent NISC: Definition 4.2 A Strawman from GS18 Compiler 4.3 A PCG Protocol for GS18 Correlation 4.4 Multiparty Silent NISC: The Construction 4.5 Extensions 5 Reusable Two-Round MPC from LPN 5.1 Multiparty Silent NISC with Reusable Large CRS Bounded FMS-MPC 5.2 Bounded FMS-MPC FMS-MPC 5.3 FMS-MPC Reusable Two-Round MPC References On the Bottleneck Complexity of MPC with Correlated Randomness 1 Introduction 1.1 Our Contribution 1.2 Related Work 2 Preliminaries 2.1 Notation 2.2 Security Model 2.3 Definitions 2.4 Primitives 3 BC-Efficient MPC for Abelian Programs 3.1 Protocol for AND 3.2 Protocol for XOR 3.3 Protocol for Abelian Programs 4 BC-Efficient Protocol for Selection Functions References Low-Communication Multiparty Triple Generation for SPDZ from Ring-LPN 1 Introduction 1.1 Our Contributions 2 Notation and Preliminaries 2.1 Module-LPN 2.2 Pseudorandom Correlation Generators 2.3 Distributed Point Functions 3 Generalisation of the 3-Party DPF to Prime Fields 4 Multiparty PCG for Triple Generation 4.1 Construction 5 Distributed Setup for the 3-Party DPF 5.1 Resources 5.2 The Protocol 6 Offline Phase 6.1 Concrete Efficiency References Storing and Retrieving Secrets on a Blockchain 1 Introduction 1.1 Our Results 1.2 Related Work 2 Preliminaries 2.1 DPSS Security Definition 2.2 DPSS Definition Discussion 3 Technical Overview – FaB-DPSS 3.1 FaB-DPSS: Semi-honest Case 3.2 Moving to a Fully-Malicious Setting 3.3 FaB-DPSS Setup Phase 3.4 FaB-DPSS Reconstruction Phase 3.5 Security of Our Construction 4 DPSS Applications – eWEB Primitive 5 Our eWEB Protocol Design 5.1 Assumptions 5.2 Our eWEB Construction 5.3 Security Proof Intuition 6 Application Examples 6.1 Voting Protocol 7 Implementation 8 Experimental Evaluation 8.1 DPSS Comparison 8.2 eWEB Performance 8.3 Applications 9 Conclusion References CNF-FSS and Its Applications 1 Introduction 1.1 Improved Multiparty DPF with t > 1 from CNF-DPF 1.2 1-out-of-3 CNF-DPF 1.3 Related Work 1.4 Organization 2 Model and Definitions 3 t-out-of-p DPF from CNF-DPF 3.1 Example: 2-out-of-5 DPF 3.2 Extending to General t-out-of-p DPF 4 1-out-of-3 CNF-DPF 4.1 Overview of Construction 4.2 Variants of DPF 4.3 Detailed Construction of 1-out-of-3 CNF-DPF A Proof of Theorem 9 References Cryptographic Protocols Efficient Verifiable Partially-Decryptable Commitments from Lattices and Applications 1 Introduction 1.1 Our Contributions 1.2 Our Results and Techniques 2 Preliminaries 2.1 Security Assumptions 2.2 Zero-Knowledge Proofs 2.3 Commitment Schemes 3 VPDC: Verifiable Partially-Decryptable Commitments 4 Generalized Decryption Feasibility for Relaxed Proofs 5 HMC-Based VPDC from Lattices 5.1 Instantiation of (Ordinary) HMC 5.2 Instantiation of NIZK 5.3 VPDC Trapdoor for HMC 5.4 Gadget-Based Regev-Style Decryption for HMC 5.5 Generalized Decryption 5.6 Succinctness of Our HMC-Based VPDC 6 Extending MatRiCTto Auditable Setting References Making Private Function Evaluation Safer, Faster, and Simpler 1 Introduction 1.1 Our Results 2 Preliminaries 2.1 Circuit Representation and Extended Permutation 2.2 Building Blocks 3 PFE Protocol for Active Security 3.1 Full Description of the Protocol 3.2 Realization of Functionality FzkEncEP 4 PFE Protocol for PVC Security 4.1 Full Description of the Protocol 5 Analysis 5.1 Performance of zkEncEP 5.2 Performance of Our PFE Protocols References Two-Round Oblivious Linear Evaluation from Learning with Errors 1 Introduction 1.1 Our Results 1.2 Related Work and Comparison 1.3 Open Problems 2 Technical Outline 2.1 The PVW Protocol 2.2 An Oblivious Linear Evaluation Protocol Based on PVW 2.3 Applications to PVW OT 2.4 Extending to Malicious Adversaries 3 Preliminaries 3.1 Universal Composability 3.2 Lattices and Hardness Assumptions 4 Finding Short Vectors in a Lattice with a Trapdoor 5 Oblivious Linear Evaluation Secure Against a Corrupted Receiver 5.1 Protocol 5.2 Analysis 5.3 Batch OLE 6 OLE from LWE Secure Against Malicious Adversaries 6.1 Protocol 6.2 Analysis 6.3 Instantiating the Functionalities References Improved Constructions of Anonymous Credentials from Structure-Preserving Signatures on Equivalence Classes 1 Introduction 1.1 Limitations of State-of-the-art ABCs 1.2 Summary of Contributions 1.3 Roadmap 2 Background and Related Work 2.1 Structure-Preserving Signatures on Equivalence Classes 2.2 Accumulators and Set-Commitments 2.3 Attribute-Based Credentials 2.4 Signer-Hiding 3 Preliminaries 3.1 Non-interactive Zero-Knowledge Arguments and Malleable Proof Systems 4 A Set-Commitment Scheme Supporting Disjoint Sets 4.1 Construction 5 Our SPS-EQ Construction 5.1 Our Malleable NIZK Argument 5.2 Signature Construction 6 Extending the ABC Model from ch15AnonCredJournal 6.1 Security Properties 7 Our ABC Construction 7.1 Revocation Strategies 7.2 Signer-Hiding 8 Comparison of State-of-the-art ABC 9 Conclusions and Future Work References Traceable PRFs: Full Collusion Resistance and Active Security 1 Introduction 1.1 Construction Overview 1.2 Additional Related Work 2 Preliminaries 2.1 Fingerprinting Codes 2.2 Traceable PRFs 3 Traceable PRF Constructions 3.1 Tracing Security with Active Adversaries 3.2 Collusion Resistant Traceable PRFs 4 An Application: Traitor Tracing with Active Security 4.1 Traceable PRFs to Traitor Tracing References Tools Radical Isogenies on Montgomery Curves 1 Introduction 2 Preliminaries 2.1 Elliptic Curves and Isogenies 2.2 Congruence Subgroups and Enhanced Elliptic Curves 2.3 Montgomery Curves 2.4 Vélu's Formulas 2.5 Radical Isogenies 3 Radical-Isogeny Formulas on Montgomery Curves 3.1 Degree 3 3.2 Degree 4 3.3 Degree 5 4 Consideration to Formulas on S0(N) 5 Application to Cryptography 5.1 Degree-3 Isogenies 5.2 Degree-4 Isogenies 5.3 Computational Efficiency 6 Conclusion References Towards a Simpler Lattice Gadget Toolkit 1 Introduction 2 Preliminaries 2.1 Notation 2.2 Linear Algebra 2.3 Lattices 2.4 Gaussian 2.5 Subgaussian Random Variables 3 Recall the Gadget Sampling 3.1 Gadget Gaussian Sampling 3.2 Gadget Subgaussian Sampling 4 Gadget Gaussian Sampling Without Floats 4.1 The Algorithm 4.2 Comparison 5 Improved Gadget Subgaussian Sampling 5.1 The Algorithm 5.2 Comparison 6 Conclusion 6.1 Future Work References SNARKs and NIZKs Polynomial IOPs for Linear Algebra Relations 1 Introduction 2 Preliminaries 2.1 Indexed Relations 2.2 Constraint Systems 2.3 Interactive Proof Systems 2.4 Polynomial IOP 3 Dense Linear Algebra Relations 3.1 Inner Product 3.2 Batched Inner Product 3.3 Modular Reduction 3.4 Matrix-Vector Product 3.5 Hadamard Product 4 Sparse Linear Algebra Relations 4.1 High-Level Overview 5 A Polynomial IOP for Arithmetic Circuits 5.1 The Protocol 5.2 The Role of Preprocessing 5.3 Optimizations 6 Zero-Knowledge 7 Comparison 7.1 Abstract Comparison 7.2 Concrete Comparison 8 Conclusion References A Unified Framework for Non-universal SNARKs 1 Introduction 1.1 Technical Overview 1.2 Further Work 2 Preliminaries 3 Knowledge-Sound SNARK for QAP 3.1 Security Theorem 4 Any-Simulation Extractability of Sqap 5 Subversion-Zero Knowledge References ECLIPSE: Enhanced Compiling Method for Pedersen-Committed zkSNARK Engines 1 Introduction 1.1 Applications 1.2 Our Contributions 1.3 Technical Overview 1.4 Related Work 2 Preliminaries 2.1 Algebraic Holographic Proofs 2.2 Polynomial Commitment 3 AHP-to-CP-SNARK Compiler 3.1 Additional Preliminaries for Compiler 3.2 Additional Properties for AHP 3.3 Our Compiler 4 Compressed -Protocol for Equality 4.1 AmComEq: Amortization of Commitment Equality Proofs 4.2 CompAmComEq: Recursive Compression 5 Instantiation with PLONK 5.1 PLONK AHP 5.2 CP-PLONK 6 Instantiation with Marlin 6.1 Marlin AHP 6.2 CP-Marlin References Rational Modular Encoding in the DCR Setting: Non-interactive Range Proofs and Paillier-Based Naor-Yung in the Standard Model 1 Introduction 1.1 Our Contribution 1.2 Technical Overview 1.3 Related Work 2 Background 2.1 Hardness Assumptions 2.2 Correlation Intractable Hash Functions 2.3 Trapdoor -Protocols 2.4 Trapdoor -Protocol Showing Composite Residuosity 2.5 Encoding and Decoding Bounded Rationals in ZN 2.6 Paillier Decryption of (Rounded) Rationals 3 Constant-Rate Unbounded Non-interactive Range Proofs in the Standard Model 4 Instantiating Naor-Yung Under the DCR Assumption 4.1 A Trapdoor -Protocol Showing Plaintext Equalities Between Paillier Ciphertexts for Distinct Moduli 4.2 New Construction of One-Time Simulation-Sound NIZK Arguments from Trapdoor -Protocols 4.3 A DCR-Based CCA2-Secure Threshold Cryptosystem from the Naor-Yung Paradigm References Author Index