Advances in Cryptology – EUROCRYPT 2023 : 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part I

This five-volume set, LNCS 14004 - 14008 constitutes the refereed proceedings of the 42 nd Annual International Conference on Theory and Applications of Cryptographic Techniques, Eurocrypt 2023, which was held in Lyon, France, in April 2023. The total of 109 full papers presented were carefully selected from 415 submissions. They are organized in topical sections as follows: Theoretical Foundations; Public Key Primitives with Advanced Functionalities; Classic Public Key Cryptography; Secure and Efficient Implementation, Cryptographic Engineering, and Real-World Cryptography; Symmetric Cryptology; and finally Multi-Party Computation and Zero-Knowledge. Preface Organization Contents – Part V Cryptographic Protocols Unique-Path Identity Based Encryption with Applications to Strongly Secure Messaging 1 Introduction 1.1 Technical Overview 2 UPIBE Definition 3 Bounded-Depth UPIBE from Bounded-Collusion IBE 4 Unbounded-Depth UPIBE from Bounded-Depth HIBE 4.1 Relaxing Assumptions: Adaptive UPIBE from Selective HIBE 5 CCA Secure UPIBE 5.1 Bounded-Depth UPIBE 5.2 Unbounded-Depth UPIBE 6 Key-Updatable KEM from UPIBE 7 Evaluation References End-to-End Secure Messaging with Traceability Only for Illegal Content 1 Introduction 1.1 Summary of Our Contributions 1.2 Our Approach 1.3 Discussion 1.4 Related Work 2 Preliminaries 2.1 Basic Cryptographic Primitives and Assumptions 2.2 Non-interactive Arguments of Knowledge 2.3 Groth-Sahai Proofs 2.4 Cuckoo Hashing 3 Set Pre-constrained Encryption 3.1 Overview 3.2 Definitions 3.3 Construction 4 SPC Group Signatures 4.1 Definitions 4.2 Generic Construction 4.3 An Efficient Instantiation References Asymmetric Group Message Franking: Definitions and Constructions 1 Introduction 2 Preliminaries 3 Asymmetric Group Message Franking 3.1 AGMF Algorithms 3.2 Security Notions for AGMF 4 HPS-Based KEM Supporting Sigma Protocols 4.1 Definition 4.2 Construction 5 Generic Construction of AGMF from HPS-KEM References Password-Authenticated TLS via OPAQUE and Post-Handshake Authentication*-9pt 1 Introduction 2 TLS-OPAQUE Specification 3 Preliminaries 4 Secure Channels with Binders 4.1 TLS 1.3 as UC Secure Channel with Binder 5 Post-Handshake Authentication 5.1 Post-Handshake Authentication Model 5.2 The Exported Authenticators Protocol 6 Security of TLS-OPAQUE 6.1 Password-Based Post-Handshake Authentication 6.2 A UC Version of TLS-OPAQUE References Randomized Half-Ideal Cipher on Groups with Applications to UC (a)PAKE 1 Introduction 2 Preliminaries 2.1 Single-Round Key Exchange (KE) Scheme 2.2 Key Encapsulation Mechanism (KEM) 3 Universally Composable Half-Ideal Cipher 4 Half-Ideal Cipher Construction: Modified 2-Feistel 5 Encrypted Key Exchange with Half-Ideal Cipher 5.1 EKE with Half-Ideal Cipher: The KEM Version 6 Applications of Half-Ideal Cipher to aPAKE References End-to-End Encrypted Zoom Meetings: Proving Security and Strengthening Liveness 1 Introduction 1.1 Contributions 1.2 Related Work 2 Continuous Multi-Recipient KEM 2.1 Syntax 2.2 PKI 2.3 Security Definition 2.4 Zoom's Scheme 3 Leader-Based GCKA with Liveness 3.1 Syntax 3.2 Security Definition 3.3 Zoom's Scheme 4 Improved Liveness 4.1 Limitations of Zoom's Protocol 4.2 Additional Interaction 4.3 Leveraging Clock Synchronicity 5 Meeting Stream Security 6 Conclusions References Caveat Implementor! Key Recovery Attacks on MEGA 1 Introduction 1.1 Contributions 1.2 Related Work 1.3 Validation 1.4 Disclosure 2 Oracles 2.1 Notation 2.2 ECB Encryption Oracle 2.3 Oracles from Decoding and Decryption Error Reports 3 Attack Based on Modular Inverse Computation 3.1 Block-Aligned, Small-Length Version 3.2 Full-Length Version 4 Attack Based on Small Subgroups 4.1 Simplified Version 4.2 Full Version 5 Recovering the RSA Private Key 6 Attacking Unpatched Clients 7 Discussion and Future Work References Public-Key Cryptanalysis Finding Many Collisions via Reusable Quantum Walks 1 Introduction 2 Preliminaries 2.1 Collision Search 2.2 Quantum Algorithms 2.3 Grover's Algorithm 3 Quantum Walks for Collision Finding 3.1 Definition and Example 3.2 Details of the MNRS Framework 3.3 Vertex-Coin Encoding 4 A Chained Quantum Walk to Find Many Collisions 4.1 New Algorithm 4.2 Complexity Analysis 5 Quantum Radix Trees and Extractions 5.1 Logical Level 5.2 Memory Representation 5.3 Basic Operations 5.4 Quantum Memory Allocators 5.5 Higher-Level Operations for Collision Walks 6 Searching for Many Collisions, in General 7 Applications 7.1 Improvements in Quantum Sieving for Solving the Shortest Vector Problem 7.2 Solving the Limited Birthday Problem 7.3 On Multicollision-Finding References Just How Hard Are Rotations of Zn? Algorithms and Cryptography with the Simplest Lattice 1 Introduction 1.1 Our Results 1.2 Related Work 2 Preliminaries 2.1 The Continuous and Discrete Gaussian Distributions and the Smoothing Parameter 2.2 Lattice Problems 2.3 Primitive Vectors and Vector Counting 2.4 Probability 3 How to Sample a Provably Secure Basis 3.1 A Rotation-Invariant Generating Set to Basis Conversion Algorithm 4 We Have an Encryption Scheme to Sell You 4.1 Basic Security 4.2 A Worst-Case to Average-Case Reduction (of a Sort) 4.3 Putting Everything Together 5 Reductions and Provable Algorithms 5.1 The Main Reduction and Algorithms 6 Experiments 6.1 Experiments on Different Procedures for Generating Bases 6.2 A Threshold Phenomenon 6.3 Sieving Experiments References M-SIDH and MD-SIDH: Countering SIDH Attacks by Masking Information 1 Introduction 1.1 Outline 2 The SIDH Protocol and Attacks 2.1 The SIDH Protocol 2.2 Cryptanalysis Attempts and Successes 3 Masked SIDH Variants 3.1 Masked Torsion Points Variant 3.2 Masked-Degree Variant 3.3 On the Effectiveness of the Countermeasures 4 Security Analysis of the Masked Torsion Points Variant 4.1 Guessing Enough Exact Torsion Point Information 4.2 Polynomial Time Attack When E0 Has j-invariant =1728 4.3 Generalization to Other Starting Curves 4.4 Generalization Attempt to Unknown Endomorphism Rings 5 Security Analysis of the Masked Degree Variant 5.1 Recovering the Degree up to Squares 5.2 On the Value of t 5.3 Reduction to the M-SIDH Variant 5.4 Reduction Impact: Porting M-SIDH Attacks to MD-SIDH 6 Adaptive Attacks 6.1 Fouotsa-Petit Adaptive Attack 6.2 GPST Adaptive Attack 7 Parameter Selection and Efficiency 7.1 Choosing the Starting Curve E0 7.2 Parameter Selection for M-SIDH 7.3 Parameter Selection for MD-SIDH 7.4 Preliminary Efficiency Analysis 8 Conclusion and Perspectives A On the claims of ePrint 2022/1667 B Using B-SIDH primes in M-SIDH References Disorientation Faults in CSIDH 1 Introduction 2 Background 2.1 CSIDH 2.2 Algorithmic Aspects 3 Attack Scenario and Fault Model 4 Exploiting Orientation Flips 4.1 Implications of Flipping the Orientation of a Point 4.2 Faulty Curves and Full-Order Points 4.3 Missing Torsion: Faulty Curves and Points of Non-full Order 4.4 Torsion Noise 4.5 Connecting Curves from the Same Round 4.6 Connecting the Components Gr,s 4.7 Revealing the Private Key 4.8 Complexity of Recovering the Secret a 5 Case Studies: CSIDH and CTIDH 5.1 Breaking CSIDH-512 5.2 Breaking CTIDH-512 5.3 Other Variants of CSIDH 6 The pubcrawl Tool 7 Hashed Version 8 Exploiting the Twist to Allow Precomputation 9 Countermeasures 9.1 Protecting Square Checks Against Fault Attacks 9.2 Implementation Costs References On the Hardness of the Finite Field Isomorphism Problem 1 Introduction 1.1 Our Contribution 2 Preliminaries 2.1 Notations 2.2 Reminders from Finite Field Theory 2.3 Lattice Reduction 2.4 Semantic Attack of an Encryption Scheme 3 Finite Field Isomorphism Problem 3.1 Previous Attacks 4 Proposed Attack on the Decisional FFI Problem 5 Proposed Semantic Attack on the Fully Homomorphic Encryption Scheme 6 Proposed Attack on the Computational FFI Problem 6.1 Lattice Reduction on Trace Lattice 7 Conclusion References New Time-Memory Trade-Offs for Subset Sum – Improving ISD in Theory and Practice 1 Introduction 1.1 Related Work 1.2 Our Contribution 2 Preliminaries 3 The Generalized BCJ Algorithm 4 New Subset Sum Trade-Off 5 Application to Decoding Binary Linear Codes 5.1 Improved ISD Trade-Offs 5.2 Asymptotic Behavior of New Trade-Offs' 5.3 Practical Results and Security Estimates A Generalization to Arbitrary Depth d References A New Algebraic Approach to the Regular Syndrome Decoding Problem and Implications for PCG Constructions 1 Introduction 2 Preliminaries 2.1 Algebraic Background 2.2 Solving Polynomial Systems 3 Algebraic Modeling of the RSD Problem 3.1 Deriving Hilbert Series 3.2 Estimating the Witness Degree 4 Hybrid Approach 4.1 Guessing Error-Free Positions in All Blocks 4.2 Restricting to f h Blocks 4.3 Witness Degree for the Hybrid Approach 4.4 Complexity with XL Wiedemann 4.5 Rationale and Experimental Verification 5 Application to Some Parameters 5.1 Comments on the Results 6 Asymptotic Analysis 6.1 Solving at Low Degree 6.2 Asymptotic Analysis of dreg A Proof of Theorems 1 and 2 A.1 Proof of Theorem 1 A.2 Proof of Theorem 2 B Missing Details in Section4 B.1 Regularity Assumption for Specialized Modeling 1 B.2 XL Wiedemann Complexity for Modeling 2 C Experiments C.1 Hilbert Series C.2 Witness Degree for Plain Systems D Proof of Proposition 6 References An Efficient Key Recovery Attack on SIDH 1 Introduction 2 Impact and Non-impact on Isogeny-Based Cryptosystems 3 Concrete Set-Up 4 Decision via Kani's Reducibility Criterion 4.1 (2a, 2a)-Subgroups Built from Torsion Point Information 4.2 Kani's Theorem 4.3 Decision Strategy 5 Constructing and Evaluating the Auxiliary Isogeny 5.1 Construction 5.2 Evaluation: Case b 5.3 Evaluation: General Case 5.4 Away from the Endomorphism 2i 6 Key Recovery Algorithm: Basic Version 6.1 Iteration 6.2 Step Sizes 6.3 Rephrasing in Terms of Bob's Secret Key 6.4 Walking Backwards 7 Speed-Ups 7.1 Take i as Large as Possible 7.2 Use a Precomputed Table 7.3 Extend Bob's Secret Isogeny Where Useful 8 Computing Chains of (2, 2)-isogenies 8.1 Gluing Elliptic Curves into a Jacobian 8.2 Richelot Isogenies 8.3 Split or Not? 9 Magma Code 10 Achieving (heuristic) Polynomial Runtime 11 Generalizations 11.1 Arbitrary Torsion 11.2 Other Starting Curves with a Known Endomorphism Ring 11.3 Base Curves Whose Endomorphism Ring is Unknown References A Direct Key Recovery Attack on SIDH 1 Introduction 2 The Core of the Attack 2.1 Isogenies Between Abelian Surfaces 2.2 The Algorithm 2.3 Proof of Theorem 1 3 The Case of Unknown Endomorphism Ring 3.1 Heuristic Complexity of Algorithm 2 3.2 Computing the Cofactor Isogeny 3.3 Computing (,)-isogenies 4 The Case of Known Endomorphism Ring 5 Future Work References Breaking SIDH in Polynomial Time 1 Introduction 1.1 Result 1.2 Outline 1.3 Context 1.4 Torsion Points Attacks 1.5 Complexities of the Different Attacks 1.6 Thanks 2 Dimension 8 Attack 3 Description of the Dimension 2g Attack 3.1 N-isogenies 3.2 Isogeny Diamonds 3.3 Description of the Attack 4 Dimension 4 Attack 4.1 Parameter Selection 5 Dimension 2 Attack 6 Parameter Tweaks 6.1 Constructing a Basis of the e-torsion of E 6.2 Building a Smooth Isogeny on a Supersingular Elliptic Curve E/Fp2 6.3 Recovering a NAe-isogeny from Its Action on the NA-torsion 6.4 Recovering a NA2-isogeny from Its Action on the NA-torsion 7 Open Problem References Signature Schemes A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies 1 Introduction 1.1 Our Results 1.2 Discussion 1.3 Technical Overview 2 Preliminaries 2.1 Group Actions 2.2 ID Protocols Using a Group Action Oracle 3 The Lower Bound 3.1 The Main Theorem 3.2 Normal Form Protocols 3.3 The Transcript Graph 3.4 Respecting Verifiers 3.5 Guessing Provers 3.6 Finishing the Proof of Theorem 3.1 4 Extensions 4.1 Direct Sampling 4.2 Black Box Graph Actions 4.3 A Fully Idealized Graph Action References Short Signatures from Regular Syndrome Decoding in the Head 1 Introduction 1.1 Our Contribution 2 Preliminaries 2.1 Syndrome Decoding Problems 2.2 Honest-Verifier Zero-Knowledge Arguments of Knowledge 2.3 The MPC-in-the-Head Paradigm 3 Technical Overview 3.1 Our Template Zero-Knowledge Proof 3.2 Concrete Instantiation for Regular Syndrome Decoding 3.3 Combinatorial Analysis 3.4 Cryptanalysis of RSD 4 Zero-Knowledge Proof for Regular Syndrome Decoding 4.1 Optimizations 4.2 Security Analysis 4.3 Communication 5 A Signature Scheme from Regular Syndrome Decoding 5.1 Description of the Signature Scheme 5.2 Parameters Selection Process References The Return of the SDitH 1 Introduction 1.1 Contributions 2 Preliminaries 2.1 Basic Cryptographic Definitions and Lemmas 2.2 Zero-Knowledge Proofs 2.3 Commitments 2.4 Additive Secret Sharing and Computing on Shares 2.5 MPC-in-the-Head Paradigm 2.6 Syndrome Decoding 2.7 Syndrome Decoding in the Head 3 Batch MPCitH on a Hypercube for ZK Proofs 3.1 High-Level Description 3.2 Leaf Witness Share Generation 3.3 Leaf Witness Shares on a Hypercube 3.4 Main Party Witness Shares 3.5 Proofs of Security 4 A Signature Scheme Based on Syndrome Decoding with Hypercube-MPCitH 5 Performance and Analysis 5.1 Comparing Code-Based Zero-Knowledge Protocols 5.2 Parameter Selection 5.3 Implementation References Chopsticks: Fork-Free Two-Round Multi-signatures from Non-interactive Assumptions 1 Introduction 1.1 Our Contribution 1.2 Concurrent Work 1.3 Technical Overview 2 Preliminaries 3 Constructions 3.1 Preparation: Special Commitments 3.2 Our Construction with Key Aggregation 3.3 Our Tight Construction 4 Instantiation 4.1 Linear Function Family 4.2 Commitment Scheme 4.3 Efficiency References Threshold and Multi-signature Schemes from Linear Hash Functions 1 Introduction 1.1 DL-Based Instantiations 1.2 RSA-Based Instantiation 2 Preliminaries 2.1 Notations 2.2 Basic Algebra 3 Algebraic One-More Preimage Resistance 3.1 Linear Hash Functions 3.2 Algebraic One-More Preimage Resistance 4 Schemes Based on Linear Hash Functions 4.1 Multi-signatures 4.2 Threshold Signatures 5 Instantiations 5.1 Instantiations from the Discrete Logarithm Problem 5.2 Instantiations from the RSA Problem 5.3 Multi-signatures from RSA 5.4 Threshold Signatures from RSA References New Algorithms for the Deuring Correspondence 1 Introduction 1.1 Technical Overview 2 Preliminaries 2.1 Mathematical Background on the Deuring Correspondence 2.2 The SQISign Protocol 2.3 Algorithms from Previous Works 3 Solving Norm Equations Inside Maximal Orders 3.1 Special Extremal Order Case: Exploiting the Full Order 3.2 Norm Equations in Generic Maximal Orders: The Algorithm 4 A New Algorithm for Ideal to Isogeny Translation 4.1 Ideal to Isogeny Translation 4.2 A Detailed Description of the Ideal Translation Algorithm. 4.3 Handling Special Failure Cases 5 Parameters and Implementation for SQISign 5.1 Cost Estimate 5.2 New Prime Search 5.3 C Implementation 6 Cryptanalysis 6.1 An Attack on SQISign's Zero-Knowledge Assumption 6.2 Further Analysis on the First Steps of 7 Open Problems References Revisiting BBS Signatures 1 Introduction 1.1 Technical Overview 2 Preliminaries 3 New Proof for (Short) BBS Signatures 3.1 Description and Implementation Details 3.2 Security Analysis 3.3 Proof of Theorem 1 3.4 Proof of Lemma 1 3.5 Proof of Lemma 4 4 Tighter Proofs for BBS in the AGM 4.1 Proof of Theorem 2 5 Efficient Proofs of Knowledge for BBS Signatures 5.1 Proofs of Knowledge for Signatures 5.2 Protocols 6 Signatures for Group Elements and Blind Issuance References Non-interactive Blind Signatures for Random Messages 1 Introduction 2 Preliminaries 2.1 Notation, Bilinear Groups and Assumptions 2.2 Signature Schemes 2.3 Dual-Mode Witness Indistinguishable Proofs 2.4 Verifiable Random Function ch25FOCS:MicRabVad99 2.5 Structure-Preserving Signatures of Equivalence Classes 2.6 Tag-Based Equivalence Class Signatures 3 Non-interactive Blind Signatures (NIBS) 4 Tagged NIBS 5 SPS-EQ Construction of NIBS 5.1 Tagged NIBS from TBEQ 5.2 Discussion 6 Generic Construction 7 Conclusions References Rai-Choo! Evolving Blind Signatures to the Next Level 1 Introduction 1.1 Background and Limitations of Existing Constructions 1.2 Our Contribution 1.3 Technical Overview 1.4 More on Related Work 2 Preliminaries 3 Our Blind Signature Scheme 3.1 Construction 3.2 Security Analysis 4 Extension: Partial Blindness and Batching 4.1 Overview 4.2 Model for Batched (Partially) Blind Signatures 4.3 Construction 4.4 Security Analysis 5 Concrete Parameters and Efficiency References Author Index