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

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