Advances in Cryptology – CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, ... I (Lecture Notes in Computer Science, 13507)

The 4-volume sets LNCS 13507, 13508, 13509, 13510 constitutes the refereed proceedings of the 42nd Annual International Cryptology Conference, CRYPTO 2022, which was held in Santa Barbara, CA, USA, in August 2022. The total of 100 papers included in the proceedings was reviewed and selected from 455 submissions. The papers were organized in the following topical sections: Cryptanalysis; randomness; quantum cryptography; advanced encryption systems; secure messaging; lattice-based zero knowledge; lattice-based signatures; blockchain; coding theory; public key cryptography; signatures, idealized models; lower bounds; secure hash functions; post-quantum cryptography; symmetric cryptanalysis; secret sharing and secure multiparty computation; unique topics; symmetric key theory; zero knowledge; and threshold signatures. Preface Organization Contents – Part I Cryptanalysis I Rotational Differential-Linear Distinguishers of ARX Ciphers with Arbitrary Output Linear Masks 1 Introduction 2 Notations and Preliminaries 2.1 Modulo Addition with an Initial Carry Bit 2.2 Useful Partitions of F2k F2k 3 Ordinary Differential-Linear Correlation of 4 Rotational Differential-Linear Correlation of 5 Computing the (Rotational) Differential-Linear Correlation of Iterative ARX Primitives 6 Applications to ARX Primitives 6.1 Cryptanalysis of Alzette 6.2 Cryptanalysis of SipHash 6.3 Cryptanalysis of SPECK 6.4 Cryptanalysis of ChaCha 7 Conclusion, Discussion, and Open Problems References Implicit White-Box Implementations: White-Boxing ARX Ciphers 1 Introduction 1.1 Contributions 2 Preliminaries 2.1 Implicit Functions, Self-equivalences and Graph Automorphisms 2.2 Encoded Implementations 3 Implicit White-Box Implementations 3.1 Quasilinear Implicit Round Functions 4 Security Analysis 4.1 Previous Generic Attacks 4.2 Reducing Implicit Implementations to Self-equivalence Implementations 5 Self-equivalences of Modular Addition 5.1 Computing Self-equivalences from a CCZ-Equivalent Function 5.2 Self-equivalences and Graph Automorphisms of the Permuted Modular Addition 6 An Implicit Implementation of an ARX Cipher 7 Conclusion A Affine Self-equivalences of the Permuted Modular Addition with Wordsize 4 References Superposition Meet-in-the-Middle Attacks: Updates on Fundamental Security of AES-like Hashing 1 Introduction 1.1 Our Contribution 2 AES-like Hashing and MITM Preimage Attacks 3 MILP Model for the Configuration Search 3.1 Basic MILP Model for MITM 3.2 Superposition States and Separate Attribute-Propagation 3.3 Multiple Ways of AddRoundKey (MulAK) 3.4 Enhanced Model with Guess-and-Determine (GnD) 3.5 Transforming to Models for Searching for Collision Attacks 3.6 Exploit Symmetry of the Ciphers 4 Application to Preimage Attacks on Whirlpool 4.1 New Attacks Resulted from Applying the MILP Modeling 4.2 Discussions on the New Attacks 5 Application to Preimage Attacks on Grøstl 5.1 New Attacks Resulted from Applying the MILP Modeling 5.2 Discussions on the New Attacks 6 Applications to Collision and Key-Recovery Attacks References Triangulating Rebound Attack on AES-like Hashing 1 Introduction 1.1 Our Contributions 1.2 Novelty and Comparison with Previous Works 2 Preliminaries 2.1 AES-like Hashing 2.2 The Rebound Attack 2.3 The Super-Sbox Technique 2.4 Triangulation Algorithm 2.5 Collision Attacks and Its Variants 3 Triangulating Rebound Attack 3.1 Solving Non-full-active Super-Sbox by Key Bytes 3.2 Connecting Multiple Inbound Phases by Key Bytes 3.3 The Triangulating Rebound Attack 4 Improved Collision Attacks on AES-128-MMO 4.1 Semi-free-start Collision Attack on 7-Round AES-128 4.2 Semi-free-start Collision Attack on 8-Round AES-128-MMO 4.3 Quantum Collision Attack on 8-Round AES-128 5 Improved Quantum Attacks on Saturnin-Hash 5.1 Improved 8-Round Quantum Free-Start Collision 5.2 Extend the Attack to 10-round Free-Start Collision 6 Quantum Collision Attack on SKINNY-128-384-MMO 6.1 21-Round Quantum Free-Start Collision Attack 6.2 Classic Free-Start Collision Attack on 19-Round 7 Discussion and Conclusion 7.1 Possible Generalization of Triangulating Rebound 7.2 Conclusion References Randomness Public Randomness Extraction with Ephemeral Roles and Worst-Case Corruptions 1 Introduction 1.1 The Motivation Behind Our Setting 1.2 Other Related Work 1.3 Our Contributions 1.4 Technical Overview 1.5 Directions for Future Research 2 Network Models for Randomness Extraction 2.1 The Sending-Leaks Adversarial Model 2.2 The Execution-Leaks Adversarial Model 3 Zero-Error Randomness Extraction Protocols 3.1 Zero-Error Randomness Extraction in the Sending-Leaks Model 3.2 Improved Zero-Error Randomness Extraction in the Execution-Leaks Model 4 Low-Error Randomness Extraction Is Impossible with n/4 Corruptions References (Nondeterministic) Hardness vs. Non-malleability 1 Introduction 1.1 Hardness Assumptions for Nondeterministic and i-Circuits 1.2 Our Results–Included in This Work 1.3 Our Results–Included in the Full Version ch6ePrint:BalDacLos22 1.4 Technical Overview 1.5 Related Work 2 Preliminaries 2.1 Complexity Classes and Assumptions 2.2 Non-malleable Codes 2.3 Seed-Extending Pseudorandom Generators 3 A Non-malleable Code for Small Circuit Tampering References Short Leakage Resilient and Non-malleable Secret Sharing Schemes 1 Introduction 1.1 Our Results 1.2 Technical Overview 1.3 Related Work 1.4 Organization of the Paper 2 Preliminaries 2.1 Notation 2.2 Statistical Distance and Entropy - Definitions and Lemmata 2.3 Randomness Extractors 2.4 Secret Sharing Schemes 3 Leakage Resilient Secret Sharing Schemes 3.1 Local Leakage Family 3.2 Construction 3.3 Security Proof 3.4 Parameters 4 Non-malleable Secret Sharing Schemes 4.1 Building Blocks 4.2 Our Construction 4.3 Instantiation of Our Scheme References *-6ptCryptography from Pseudorandom Quantum States 1 Introduction 1.1 Our Results 1.2 Discussion: Why Explore a World Without One-Way Functions? 1.3 Technical Overview 1.4 Future Directions 2 Pseudorandom States 2.1 Pseudorandom Function-Like State (PRFS) Generators 2.2 Testing Pseudorandom States 3 Constructing PRFS from PRS 4 Quantum Pseudo One-Time Pad from PRFS 5 Quantum Bit Commitments from PRFS 5.1 Definition 5.2 Construction 5.3 Application: Secure Computation References Quantum Cryptography I .26em plus .1em minus .1emCertified Everlasting Zero-Knowledge Proof for QMA*-10pt 1 Introduction 1.1 Background 1.2 Our Results 1.3 Technical Overview 1.4 Related Works 2 Preliminaries 2.1 Notations 2.2 Quantum Computation 2.3 QMA and k-SimQMA 2.4 Cryptographic Tools 3 Commitment with Certified Everlasting Hiding and Classical-Extractor-Based Binding 3.1 Definition 3.2 Construction 4 Certified Everlasting Zero-Knowledge Proof for QMA 4.1 Definition 4.2 Construction of Three Round Protocol 4.3 Sequential Repetition for Certified Everlasting Zero-Knowledge Proof for QMA References Quantum Commitments and Signatures Without One-Way Functions 1 Introduction 1.1 Background 1.2 Our Results 1.3 Technical Overviews 1.4 Concurrent Work 2 Preliminaries 2.1 Basic Notations 2.2 Pseudorandom Quantum States Generators 3 Commitments 3.1 Definition 3.2 Construction 3.3 Computational Hiding 3.4 Statistical Binding 4 Digital Signatures 4.1 One-Way Quantum States Generators 4.2 Definition of Digital Signatures with Quantum Public Keys 4.3 Construction 4.4 Security A Making Opening Message Classical B Equivalence of Binding Properties References Semi-quantum Tokenized Signatures 1 Introduction 1.1 The Advantages of Quantum Signature Tokens 1.2 Semi-quantum Tokenized Signatures 1.3 Results 2 Technical Overview 2.1 Semi-quantum CCD Tokens and Fully-quantum Signature Tokens 2.2 Signing Coset States by Splitting 2.3 Proving CCD Security Versus Proving Tokenized Signing Security 2.4 Hardness of Concentration in Dual of Obfuscated Subspace 3 Semi-quantum Tokenized Signatures Construction 3.1 Correctness and Security Against Sabotage References Secure Multiparty Computation I Structure-Aware Private Set Intersection, with Applications to Fuzzy Matching 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries 2.1 Hamming Correlation Robustness 3 Building Blocks 3.1 2PC Ideal Functionalities 3.2 Function Secret Sharing 3.3 Oblivious Key Value Store 4 bFSS Constructions 4.1 Existing Schemes 4.2 New concat Technique for Cross Products 4.3 New Spatial Hashing Technique 4.4 xor-share Technique 5 Structure-Aware PSI from bFSS 5.1 Costs 5.2 Other Protocols as Instances of Our Framework 5.3 bFSS Performance 6 Fuzzy PSI Application and Performance 6.1 Performance Comparison 6.2 Implementation 7 Limitation and Open Problems References .28em plus .1em minus .1emTwo-Round MPC Without Round Collapsing Revisited – Towards Efficient Malicious Protocols*-12pt 1 Introduction 2 Technical Overview 2.1 Multi-party Randomized Encoding 2.2 Semi-Malicious Effective-Degree-2 MPRE 2.3 MPC for Effective-Degree-2 Functions 2.4 Lift Security with Output Substitution 2.5 Tensor OLE Correlated Randomness Generation from OT 3 Definition of Multi-Party Randomized Encoding 4 MPRE for Degree-3 Functions 4.1 Background: Semi-honest MPRE for Degree-3 Functions 4.2 CDS Encoding 4.3 Semi-Malicious MPRE for Degree-3 Functions 5 Putting Pieces Together References More Efficient Dishonest Majority Secure Computation over Z2k via Galois Rings 1 Introduction 1.1 Our Contribution 1.2 Overview of Our Techniques 1.3 Related Work 1.4 Organization of the Paper 2 Preliminaries 2.1 Basic Notation 2.2 Algebraic Preliminaries 2.3 Security Model 2.4 Communication Model 3 Online Phase 3.1 Required Functionalities 3.2 Instantiating FMPCin the [func:prep]FPrep-Hybrid Model 4 Authentication 4.1 Required Functionalities 4.2 Correlated Oblivious Product Evaluation 4.3 Authenticated Secret-Sharing 4.4 Authentication Protocol 5 Offline Phase 6 Communication Complexity Analysis References Proof Systems Parallel Repetition of (k1,...,k)-Special-Sound Multi-round Interactive Proofs 1 Introduction 1.1 Background 1.2 Contributions 1.3 Highlevel Approach 1.4 Related Work 1.5 Organization of the Paper 2 Preliminaries 2.1 Interactive Proofs 2.2 Geometric Distribution 3 Parallel Repetition of k-Special-Sound -Protocols 3.1 Knowledge Soundness of a Single Invocation 3.2 Knowledge-Soundness of the Parallel Repetition 4 Parallel Repetition of Multi-round Protocols 4.1 Knowledge Soundness of a Single Invocation 4.2 Knowledge-Soundness of the Parallel Repetition 5 Threshold Parallel Repetition References Public-Coin 3-Round Zero-Knowledge from Learning with Errors and Keyless Multi-Collision-Resistant Hash 1 Introduction 2 Overview of Our Techniques 2.1 Techniques of Bitansky et al. ch16STOC:BitKalPan18 2.2 Our Techniques 3 Preliminaries 3.1 Notations for (Keyed) Hash Functions 3.2 Keyless Multi-Collision Resistant Hash Functions 3.3 Weak Memory Delegations 3.4 Oracle Memory Delegations 3.5 Low-Degree Extensions 4 Public-Coin Tree-Hash Oracle Memory Delegation 4.1 Public-Coin Weak Tree-Hash Oracle Memory Delegation 4.2 Overview of Proof of Lemma 1 5 Public-Coin Oracle Memory Delegation 5.1 Preliminary: RAM Delegation 5.2 Proof of Lemma 6 6 Public-Coin Weak Memory Delegation 7 Public-Coin 3-Round Zero-Knowledge Argument References Faster Sounder Succinct Arguments and IOPs 1 Introduction 1.1 Our Results 1.2 Related Work 1.3 Organization 2 Technical Overview 3 Preliminaries 3.1 Notation and Conventions 3.2 Probability 3.3 Constructible Finite Fields 3.4 Error-Correcting Codes 4 Main Results 5 IOP Tools 5.1 Projectability 5.2 Encoded IOPs 6 Basic IOPs 6.1 Hadamard Check 6.2 Tensor LinCheck 7 Proof of Main Results 7.1 Efficient IOP: Proof of Theorem 4.5 7.2 From IOPs to Arguments: Proof of Theorem 4.6 References Succinct Interactive Oracle Proofs: Applications and Limitations 1 Introduction 1.1 Our Results 1.2 Related Works 1.3 Our Techniques 1.4 Organization 2 Preliminaries 2.1 Basic Complexity Notations and Definitions 2.2 Interactive Proofs and Oracle Proofs 2.3 Computational Indistinguishability 2.4 Cryptographic Primitives 2.5 Zero-Knowledge Proofs 2.6 Hoeffding's Inequality 3 Randomness Reduction 4 Limitations of Succinct IOPs 4.1 Handling Small Randomness 4.2 Handling Larger Randomness 5 Succinct Zero-Knowledge Proofs from OWF 5.1 Communication Preserving ZKP 5.2 Constructing Succinct ZKPs References Advanced Encryption Systems Candidate Witness Encryption from Lattice Techniques 1 Introduction 1.1 Our Contribution 2 Overview of Techniques 2.1 Notations 2.2 Branching Programs with Resiliency to Corrupted Inputs 2.3 The Witness Encryption Construction 2.4 Analysis Model 2.5 Security of the Construction 2.6 Phrasing the Assumption 2.7 Paper Structure 3 Lattice Tools 3.1 LWE for General Matrices and Auxiliary Information 3.2 Main Assumption 4 Candidate Witness Encryption 4.1 Encodings of Matrix Branching Programs 4.2 The Construction 4.3 Security References Securing Approximate Homomorphic Encryption Using Differential Privacy 1 Introduction 1.1 Our Results and Techniques 1.2 Paper Outline 2 Preliminaries 2.1 Probability 2.2 Bit Security 2.3 Fully Homomorphic Encryption 3 A Differentially Private Approach to IND-CPAD Security 3.1 Our Notion of Differential Privacy 3.2 Gaussian Mechanism 4 Application to CKKS 4.1 The CKKS Approximate FHE Scheme 4.2 IND-CPAD-Secure CKKS 4.3 Lower Bound for Gaussian Mechanism 4.4 Improved Parameters via a Relaxed Security Notion 4.5 Parameters for Concrete Countermeasures 4.6 The Impact of Our Countermeasure 5 Dynamic Error Estimation 5.1 A (Heuristic) Dynamic Estimation Procedure for CKKS 5.2 Dynamic Estimation 5.3 Attack Against IND-CPAD-Security of M[] for ``Natural'' 5.4 Breaking q-IND-CPAD-Security of PALISADE's Dynamic Error Estimation Countermeasure 5.5 Attack Against KRD-Security of M[] for ``Artificial'' 6 Conclusion and Open Problems References Multi-input Attribute Based Encryption and Predicate Encryption 1 Introduction 1.1 Our Results 1.2 Our Techniques 2 Multi-input Attribute Based and Predicate Encryption 2.1 Strong Security for k-ABE and k-PE 2.2 Generalization to Multi-Slot Message Scheme 3 Two-Input ABE for NC1 from Pairings and LWE 4 Compiling k-ABE to k-PE via Lockable Obfuscation 5 Two-Input PE with Stronger Security 6 Three-Input ABE from Pairings and Lattices References Formal Verification of Saber's Public-Key Encryption Scheme in EasyCrypt 1 Introduction 2 Preliminaries 3 Security 4 Correctness References Secure Multiparty Computation II SoftSpokenOT: Quieter OT Extension from Small-Field Silent VOLE in the Minicrypt Model 1 Introduction 1.1 Our Results 1.2 Technical Overview 2 Preliminaries 2.1 Notation 2.2 Universal Hashes 2.3 Ideal Functionalities 2.4 Correlation Robust Hashes 3 VOLE 3.1 For Small Fields 3.2 For Subspaces 4 Malicious Security 4.1 Flaws in Existing Consistency Checks 4.2 Our New Proof 5 OT Extension 5.1 Delta-OT 6 Base OTs 6.1 Consistency Checking 7 Implementation 7.1 Performance Comparison References Maliciously Secure Massively Parallel Computation for All-but-One Corruptions 1 Introduction 1.1 Our Results 2 Overview of Our Techniques 2.1 Our Malicious Compiler for Short Output Protocols 2.2 Our Malicious Security for Long Output Protocols 3 The MPC Model and Security Definitions 3.1 The Massively Parallel Computation Model 3.2 Malicious Security for MPC Protocols 3.3 P2P Semi-malicious Security for MPC Protocols 4 Impossibility of a (Semi-)Malicious Secure Compiler 5 Common Subprotocols 5.1 The Distribute Subprotocol 5.2 The Combine Subprotocol 6 Semi-malicious Secure MPC for Long Output 7 Malicious-Secure MPC 7.1 The Subprotocols 7.2 The Compiler 7.3 Putting It All Together References Le Mans: Dynamic and Fluid MPC for Dishonest Majority 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries and Security Model 2.1 Preliminaries 2.2 Modelling Fluid MPC in Dishonest Majority 2.3 Security Model 3 Universal Preprocessing for Dynamic Committees 3.1 Preprocessing Functionality 3.2 Preprocessing Protocol 3.3 Instantiating Multi-party VOLE 4 Dynamic SPDZ 5 Fluid SPDZ 6 Cost Analysis 6.1 Concrete Costs and Optimizations for Fluid -Online References Secure Messaging Oblivious Message Retrieval 1 Introduction 1.1 Our Contributions 2 Related Work 2.1 Message Detection 2.2 Other Works 3 Model and Definitions 3.1 Definitions 4 Preliminaries 4.1 LWE Encryption 4.2 Homomorphic Encryption 5 Generic OMR and OMD Using FHE 5.1 Oblivious Message Detection Using FHE 5.2 Payload Retrieval Using FHE 5.3 Improved Retrieval Using SRLC 6 Practical OMR 6.1 PVW Clue Ciphertext 6.2 BFV Leveled Homomorphic Encryption 6.3 A Practical OMR Scheme 6.4 A Practical Compact OMR Scheme 6.5 Additional Properties 7 Denial-of-Service Resistance 7.1 Modeling DoS Resistance 7.2 Attaining DoS-Resistant OMR 8 Key Unlinkability 9 Performance Evaluation 10 Integration and Limitations References A More Complete Analysis of the Signal Double Ratchet Algorithm 1 Introduction 1.1 Our Contributions 1.2 High-Level Summary of the Double Ratchet and Its Security Properties 1.3 High-Level Summary of Our DR Definition's Strength over Prior Notions 1.4 High-Level Summary of the DR's Minor Weakness 1.5 High-Level Summary of the Triple Ratchet 1.6 Other Related Work 1.7 Summary of the Rest of the Paper 2 Defining Security of the Double Ratchet 2.1 Honest Execution 2.2 Execution with an Unrestricted Adversary 3 Continuous Key Agreement References Author Index