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 II

The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors, and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Preface Organization Contents – Part II Multi-party Computation New Ways to Garble Arithmetic Circuits 1 Introduction 1.1 Our Results 1.2 Related Works 1.3 Technical Overview 2 Definitions 2.1 Definition of Garbling Schemes 2.2 Definition of Garbling Gadgets 3 Linearly Homomorphic Encryption 3.1 Definition of Basic LHE 3.2 A Construction of Special-Purpose LHE 4 Key Extension for Bounded Integer Computation 4.1 The Setup Algorithm 4.2 Length-Doubling Key Extension 5 Potential for Concrete Efficiency Improvement References .26em plus .1em minus .1emActively Secure Half-Gates with Minimum Overhead Under Duplex Networks 1 Introduction 1.1 Our Contribution 2 Preliminaries 2.1 Notation 2.2 Information-Theoretic Message Authentication Codes 2.3 Correlated Oblivious Transfer 2.4 Designated-Verifier Zero-Knowledge Proofs 3 Technical Overview 3.1 Overview of the State-of-the-Art Solution 3.2 Our Solution for Generating Authenticated AND Triples 3.3 Our Solution for Dual Execution Without Leakage 4 Preprocessing with Compressed Wire Masks 4.1 Dual-Key Authentication 4.2 Global-Key Sampling 4.3 Consistency Check Between Values and MAC Tags 4.4 Circuit Dependent Compressed Preprocessing 5 Authenticated Garbling from COT 5.1 Distributed Garbling 5.2 A Dual Execution Protocol Without Leakage 5.3 Security Analysis References Black-Box Reusable NISC with Random Oracles 1 Introduction 1.1 Our Contribution 2 Technical Overview 2.1 Constructing a Reusable Outer Protocol 2.2 A New Protocol Compiler 2.3 Extension to the Two-Sided Setting 3 Definitions 3.1 Reusable NISC Protocol 3.2 Reusable Two-Sided NISC 4 Reusable Verifiable Client-Server Protocol 4.1 Definition 5 Black-Box Reusable NISC 5.1 Construction 6 Non-interactive Reusable Commit-and-Prove 6.1 Definition 7 Black-Box Reusable Two-Sided NISC References Maliciously-Secure MrNISC in the Plain Model 1 Introduction 1.1 Our Results 1.2 On the Necessity of iO 1.3 Related Work 2 Technical Overview 2.1 The MrNISC Protocol 3 Preliminaries 4 MrNISC Syntax and Security 5 Main Building Blocks 5.1 Reusable Statistical ZK Arguments with Sometimes-Statistical Soundness 5.2 One-Round Simultaneous-Message CCA-Non-malleable Commitments 6 Malicious-Secure MrNISC References Minimizing Setup in Broadcast-Optimal Two Round MPC 1 Introduction 1.1 Terminology 1.2 Prior Work 1.3 Our Contributions 1.4 Technical Overview 1.5 Broadcast Complexity 2 Secure Multiparty Computation (MPC) Definitions 2.1 Security Model 2.2 Notation 3 Upper Bounds 3.1 One-or-Nothing Secret Sharing with Intermediaries 3.2 IA Feasibility Result: P2P-BC, IA, 3t< n 3.3 Feasibility Results for SIA 4 Lower Bounds References Sublinear-Communication Secure Multiparty Computation Does Not Require FHE 1 Introduction 1.1 Our Results 1.2 Technical Overview 2 Preliminaries 2.1 Assumptions 2.2 Function Secret Sharing and Homomorphic Secret Sharing 3 General Template for (N+1)-Party Sublinear Secure Computation from N-Party FSS 3.1 Requirements of the FSS Scheme 3.2 The Secure Computation Protocol 4 Oblivious Evaluation of LogLog-Depth FSS from PIR 4.1 LogLog-Depth FSS 4.2 Oblivious Evaluation of LogLog-Depth FSS from PIR 5 LogLog-Depth FSS from Compact and Additive HSS 5.1 An Overview of the Construction 5.2 Defining the LogLog-Depth FSS Scheme 5.3 Securely Realising FSDFSS in Low Communication 6 Instantiations 6.1 Sublinear-Communication Secure Multiparty Computation from PIR and Additive HSS 6.2 Four-Party Additive HSS from DCR 6.3 Sublinear-Communication Secure Multiparty Computation from New Assumptions References Actively Secure Arithmetic Computation and VOLE with Constant Computational Overhead 1 Introduction 1.1 ADINZ: Constant Overhead with Passive Security 1.2 Actively Secure Arithmetic MPC with Constant Overhead? 2 Our Contribution 2.1 The VOLE Protocols 2.2 The Batch-OLE Protocol 2.3 Technical Overview of the VOLE Protocols 2.4 Technical Overview of the Batch-OLE Protocol 3 Preliminaries 3.1 Linear Algebraic Notations 4 The ADINZ Protocol 5 RVOLE Protocol Against Actively-Corrupted Receiver 6 Actively-Secure VOLE Under Correlated Noisy-Codewords 6.1 The Correlated Noisy-Codeword Hardness Assumption 6.2 The VOLE2 Protocol 7 Actively-Secure VOLE Under Fast Pseudorandom Matrix 7.1 Useful Observations 7.2 The VOLE3 Protocol 8 Batch-OLE References SuperPack: Dishonest Majority MPC with Constant Online Communication 1 Introduction 1.1 Our Contribution 2 Overview of the Techniques 2.1 Starting Point: TurboPack 2.2 Achieving Active Security 2.3 Instantiating the Circuit-Dependent Preprocessing 2.4 Instantiating the Circuit-Independent Preprocessing 3 Preliminaries 4 Online Protocol 4.1 Circuit-Dependent Preprocessing Functionality 4.2 Input Gates 4.3 Computing Addition and Multiplication Gates 4.4 Output Gates and Verification 4.5 Full Online Protocol 5 Circuit-Dependent Preprocessing Phase 6 Circuit-Independent Preprocessing Phase 7 Implementation and Experimental Results References Detect, Pack and Batch: Perfectly-Secure MPC with Linear Communication and Constant Expected Time 1 Introduction 1.1 Related Work 2 Technical Overview 2.1 Detectable and Verifiable Secret Sharing 2.2 Our MPC Protocol 2.3 Multiplication Triplets with a Dealer 3 Preliminaries 4 Packed Secret Sharing 4.1 Sharing Attempt 4.2 Reconstruction of g-polynomials in CONFLICTS 4.3 Reconstruction of f-polynomials in CONFLICTS 4.4 Putting Everything Together: Packed Secret Sharing 5 Batched and Packed Secret Sharing 5.1 Sharing 5.2 Reconstruction 6 Packed and Batched Verifiable Triple Sharing 7 The MPC Protocol References An Incremental PoSW for General Weight Distributions 1 Introduction 1.1 Graph-Labeling PoSW Schemes 1.2 Incremental PoSW 1.3 Incremental PoSWs for Incremental SNACKs 1.4 Our Contributions 1.5 A High-Level Technical Overview 2 Preliminaries 2.1 Notations 2.2 Graph Labeling 3 The Skiplist PoSW Scheme 3.1 Construction 3.2 Prover Efficiency and Space-Time Tradeoffs 4 Incremental Proofs of Sequential Work 5 A Skiplist-Based Incremental PoSW Scheme 5.1 Parameters 5.2 A High-Level Overview 5.3 Scheme Description 5.4 Efficiency Analysis 5.5 The Security Proof 6 Incremental PoSW for General Distributions 6.1 Incrementally Sampleable Distributions 6.2 Scheme Description 6.3 Theorem Statement and Proof Outline References (Zero-Knowledge) Proofs Witness-Succinct Universally-Composable SNARKs 1 Introduction 1.1 Technical Overview 1.2 Related Work 2 Preliminaries 2.1 UC Framework 2.2 Succinct Non Interactive Zero-Knowledge Proof 2.3 Succinct Polynomial Commitment Scheme 3 Succinctness-Preserving UC NIZK Compiler 4 Instantiating Our Compiler 4.1 A Candidate PCS and PSE Scheme 4.2 Candidate NIZK Schemes References Speed-Stacking: Fast Sublinear Zero-Knowledge Proofs for Disjunctions*-12pt 1 Introduction 1.1 Our Contributions 2 Technical Overview 2.1 Disjunctive Templates for Zero-Knowledge 2.2 Stacking Sigmas for Sublinear-Sized Proofs 2.3 Speed-Stacking Interactive Oracle Proofs 2.4 Speed-Stacking Folding Arguments 2.5 Notation 3 Stacking Zero-Knowledge Interactive-Proofs 3.1 Defining Stackable ZK-IP 3.2 Compiler for Stacking ZK-IPs 4 Speed-Stacking Interactive Oracle Proofs 4.1 Holographic IOPs 4.2 Reed–Solomon Encoded Holographic IOPs 4.3 Defining a Stackable IOP and Stackable RS-IOP 4.4 Compiling RS-IOP to Stackable IP via Stackable IOP 4.5 Stackable RS-IOPs 4.6 Stactal 5 Speed-Stacking Compressed -Protocols 5.1 Compressed -Protocols are Stackable References Proof-Carrying Data from Arithmetized Random Oracles 1 Introduction 1.1 Our Results 1.2 Related Work 2 Techniques 2.1 Starting Point: The Low-Degree Random Oracle Model 2.2 The Arithmetized Random Oracle Model 2.3 Building PCD Secure in the AROM 2.4 Emulation of the ARO 3 Preliminaries 3.1 Notations 3.2 Non-interactive Arguments in Oracle Models 3.3 Proof-Carrying Data 3.4 Accumulation Schemes 3.5 Commitment Schemes 3.6 Constraint Detection for Low-Degree Polynomials 3.7 Forking Lemmas 3.8 Identical-Until-Bad 4 Arithmetized Random Oracle Model References Supersingular Curves You Can Trust 1 Introduction 1.1 Generating a Secuer 1.2 Proof of Isogeny Knowledge 2 Preliminaries 2.1 General Notations 2.2 Elliptic Curves, Isogenies and ``SIDH Squares'' 2.3 Proofs of Knowledge 2.4 Non-Interactive Zero-Knowledge Proofs 3 Isogeny Graphs and Expansion 3.1 Generalities on the Graph and Its Adjacency Matrix 3.2 Proof of Theorem 3 3.3 Mixing Time of Non-backtracking Walks 4 Proof of Knowledge 4.1 Protocol Description and Analysis 4.2 Executing the Protocol 5 Distributed Secuer Setup and Its Security 5.1 The NIZK Protocol 5.2 Our Distributed Secuer setup protocol 5.3 Proof of Security for Secuer 6 Implementation and Results 7 Conclusion References On Valiant's Conjecture 1 Introduction 1.1 Relation to Other Results 1.2 Can We Drop the ZK Assumption? 2 Definitions 2.1 Rerandomizable Commitments 2.2 Collision Intractable Hashes 2.3 Basic Notation 3 Theorem Statements 4 Impossibility from Zero-Knowledge 5 On Proving Impossibility Without Zero-Knowledge References SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption 1 Introduction 1.1 Technical Overview 1.2 Related Work 2 Preliminaries 2.1 Cryptographic Groups 2.2 Lossy Trapdoor Functions 2.3 Correlation-Intractable Hash Families 2.4 Lossy CI Hash Functions 2.5 SNARGs for Bounded Depth Computations 3 Root-Finding in TC0 3.1 Basic Finite Field Operations 3.2 Finding Roots of K-quadratics in L 3.3 Finding Roots of Cubics in K 4 PPAD-Hardness from Subexponential DDH 5 Delegation for Bounded Depth Computations from Subexponential DDH 5.1 Variable-Extended Formulations for Boolean Functions 5.2 A GKR Protocol with Degree 3 Sumcheck Polynomials References HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates 1 Introduction 1.1 Technical Overview 2 Preliminaries 2.1 Proofs and Arguments of Knowledge 2.2 Multilinear Polynomial Commitments 2.3 PIOP Compilation 3 A Toolbox for Multivariate Polynomials 3.1 SumCheck PIOP for High Degree Polynomials 3.2 ZeroCheck PIOP 3.3 ProductCheck PIOP 3.4 Multiset Check PIOP 3.5 Permutation PIOP 3.6 Lookup PIOP 3.7 Batch Openings 4 HyperPlonk: Plonk on the Boolean Hypercube 4.1 Constraint Systems 4.2 The PolyIOP Protocol 5 Orion+: A Linear-Time Multilinear PCS with Constant Proof Size References Spartan and Bulletproofs are Simulation-Extractable (for Free!)*-12pt 1 Introduction 1.1 Our Results 1.2 Technical Overview 1.3 Related Work 2 Preliminaries 2.1 Assumptions 2.2 Interactive Arguments 2.3 Non-Interactive Arguments in the ROM 2.4 The Fiat-Shamir Transformation 3 Simulation Extractability 4 Tree of Transcripts and Special Soundness 5 Simulation Extractability of Spartan 5.1 Spartan Protocols 5.2 SIM-EXT Analysis of Spartan-NIZK 5.3 SIM-EXT of Spartan-SNARK 6 Simulation Extractability of Bulletproofs 6.1 Aggregate Range Proof 6.2 Arithmetic Circuit Satisfiability Proof 7 Quantitative Discussion of Our SIM-EXT Bounds References Complete Characterization of Broadcast and Pseudo-signatures from Correlations*-4pt 1 Introduction 1.1 Problem Formulation 1.2 Related Work 1.3 Main Contributions and Results 1.4 Technical Overview 2 Preliminaries 3 Constructions 3.1 A Pseudo-signature Protocol from Correlations 3.2 Altering the Transfer Path of a Pseudo-signature Protocol 4 Impossibility 5 Characterizations 6 Characterizations for Pseudo-signatures with Limited Connectivity References Privacy-Preserving Blueprints 1 Introduction 2 Preliminaries 2.1 Non-interactive Zero Knowledge 2.2 NIZK Proof of Knowledge 2.3 -Protocol for Proof of Equality of Discrete Logarithm Representations 2.4 From -Protocols to BB Simulation Extractable NIZK PoK via Fiat-Shamir 2.5 gx-BB-PSL Simulation Extractable NIZK from eqrep 3 Definition of Security of f-Blueprint Scheme 4 Homomorphic Enough Encryption 5 A Generic f-Blueprint Scheme from HEC 6 HEC from the ElGamal Cryptosystem 6.1 The ElGamalHEC Construction and Its Security 6.2 From ElGamalHEC to an Efficient Secure Blueprint Scheme 7 HEC for Any f from Fully Homomorphic Encryption References Author Index 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.