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

Preface
Organization
Contents – Part I
Invited Talk
Indistinguishable Predictions and Multi-group Fair Learning
	1 Introduction
	2 Outcome Indistinguishability
		2.1 Feasibility and Learnability of OI Predictors
		2.2 Broader Context and Discussion
		2.3 Further Related Work
	3 Multi-PAC Learning
		3.1 Loss Functions
		3.2 Multigroup PAC Learnability via OI
	4 Recent Developments
	References
Theoretical Foundations
Worst-Case Subexponential Attacks on PRGs of Constant Degree or Constant Locality
	1 Introduction
		1.1 Contribution
		1.2 Technical Overview
		1.3 Related Work
		1.4 Organization of this Text
	2 Preliminaries
		2.1 Notation
		2.2 Mathematical Preliminaries
		2.3 Cryptographic Preliminaries
	3 Finding Algebraic Relations
		3.1 Bounding D for Poly-stretch PRGs
	4 Attacks on Constant-Degree PRGs over Large Moduli
	5 Attacks on Binary PRGs
		5.1 Binary PRGs of Constant Degree
		5.2 Binary PRGs of Constant Locality
	6 Avoiding Subexponential Attacks
	References
Fine-Grained Non-interactive Key-Exchange: Constructions and Lower Bounds
	1 Introduction
		1.1 Our Contribution
		1.2 Technical Overview: Building NIKE in the ROM and GGM
		1.3 Technical Overview: Breaking 3-NIKE in Maurer\'s GGM
	2 Preliminaries
	3 3-NIKE in the Random Oracle Model
	4 4-NIKE in Shoup\'s Generic Group Model
		4.1 Correctness
		4.2 Security Analysis
	5 Impossibility Results
		5.1 Defining 3-NIKE in Maurer\'s Generic Group Model
		5.2 Breaking 3-NIKE in the MGGM Without Zero-Test Queries
		5.3 Breaking 3-NIKE in the MGGM with Zero-Test Queries
	References
Speak Much, Remember Little: Cryptography in the Bounded Storage Model, Revisited
	1 Introduction
		1.1 Modeling Gap: Breaking the Quadratic Barrier
		1.2 Our Results
		1.3 Our Techniques
		1.4 Related Work
	2 Preliminaries
	3 Bit-Entropy Lemma
	4 Bounded Storage Model
	5 Key Agreement
		5.1 Definition
		5.2 Construction
	6 Oblivious Transfer and Multiparty Computation
		6.1 Definition of Oblivious Transfer
		6.2 Interactive Hashing
		6.3 OT Construction
		6.4 Multiparty Computation from OT
	7 Lower Bounds on Rounds and Communication
		7.1 Model for the Lower Bound: The Unbounded Processing Model
		7.2 Lower Bound in the Unbounded Processing Model
		7.3 Model for a Lower Bound Against Streaming Adversaries
		7.4 Lower Bound Against Streaming Adversaries
	References
Non-uniformity and Quantum Advice in the Quantum Random Oracle Model
	1 Introduction
		1.1 Our Results
		1.2 Organization
	2 Preliminaries
		2.1 Quantum Random Oracle Model
		2.2 Other Useful Lemmas
	3 (S, T) Quantum Algorithms and Games in the QROM
		3.1 Quantum Bit-Fixing Model
	4 Games, POVMs and Decomposition of Advice
	5 Non-uniform Lower Bounds via Alternating Measurements
		5.1 Multi-instance via Alternating Measurements
		5.2 Advantages of Uniform Algorithms in Alternating Measurement Games
		5.3 Proof of Main Theorem
	6 Applications
		6.1 Salting Defeats Quantum Advice
	7 Advantages of Quantum Advice in the QROM
	A Proofs for the Useful Lemmas
	B Characterization of Alternating Measurements
	C Classical Version of Our Main Theorem
	D Proof for the Separation Result
	References
Black-Box Separations for Non-interactive Classical Commitments in a Quantum World
	1 Introduction
		1.1 Our Results
		1.2 Technical Overview
		1.3 Further Related Work
	2 Preliminaries
		2.1 Quantum Computation
		2.2 Polynomial Compatibility Conjecture
		2.3 The Donoho-Stark Uncertainty Principle
		2.4 Non-interactive Commitments
	3 Non-uniform Hardness of Inverting Large Sets of Oracles
		3.1 Oracle Puzzles with Advice
		3.2 Multi-instance Oracle Puzzles
		3.3 Function-Inversion Oracle Puzzles
		3.4 Proof of One-Wayness Under Quantum Advice
	4 Quantum Black-Box Separation from One-Way Functions
	References
On Non-uniform Security for Black-Box Non-interactive CCA Commitments
	1 Introduction
	2 Overview of Techniques
	3 Background
		3.1 Non-uniform Security
		3.2 CCA Commitments
	4 Setupless Equivocal Commitments Against Non-uniform Adversaries
		4.1 Distinct Strong Keyless Multi-collision Resistance
		4.2 Setupless Equivocal Commitment with Auxillary Input
		4.3 Construction
		4.4 Amplification
	5 Hinting PRGs with Injective Extension
	6 Tag Amplification
	7 Compilation of Transformations
	References
Polynomial-Time Cryptanalysis of the Subspace Flooding Assumption for Post-quantum iO*-12pt
	1 Introduction
	2 Technical Overview
		2.1 The DQVWW Assumption Implying iO
		2.2 Overview of the Attack
		2.3 The Importance of Column Spans
		2.4 Correctness of Step 1
		2.5 Correctness of Step 2
	3 Our Attack
		3.1 Distinguishing D0 from D1
		3.2 Recovery of Unique i\'s
	References
Oblivious Transfer and Data Access
Reverse Firewalls for Oblivious Transfer Extension and Applications to Zero-Knowledge*-12pt
	1 Introduction
		1.1 Our Contributions
		1.2 Future Work
		1.3 Related Work
	2 Technical Overview
		2.1 Correlated OT with Leakage Functionality
		2.2 Correlated Oblivious Transfer Extension in the RF Setting
		2.3 Base Oblivious Transfer Protocols in the RF Setting
		2.4 Malleable Interactive Protocols in the RF Setting
		2.5 Efficient Zero-Knowledge in the RF Setting
	3 Preliminaries
		3.1 Cryptographic Reverse Firewalls
	4 Correlated OT Extension in the Firewall Setting
	5 Implementing FrOT in the Firewall Setting
	6 Fully Malleable Sigma Protocols
		6.1 Malleability
		6.2 RF for OR Transform Sigma Protocol
	7 Quicksilver with Reverse Firewall
	References
Oblivious Transfer with Constant Computational Overhead
	1 Introduction
		1.1 Our Results
		1.2 Technical Overview
	2 Preliminaries
		2.1 Computational Model and Cost Measure
		2.2 Correlation Robust Local PRGs
		2.3 Pseudorandom Correlation Generators
		2.4 Learning Parity with Noise
		2.5 (Known Index) Function Secret Sharing
	3 Constant-Overhead PCG for OT from Primal LPN
	4 Constant-Overhead PCG for OT from Dual LPN
	5 Beyond Oblivious Transfer
		5.1 General Protocols with Relaxed Security
		5.2 Leveraging Perfect Security
		5.3 Reducing the Main Open Question to Simpler Questions
	References
Endemic Oblivious Transfer via Random Oracles, Revisited*-12pt
	1 Introduction
		1.1 Problem Statement
		1.2 Our Results
		1.3 Related Work
	2 Preliminaries
		2.1 Notations
		2.2 Universal Composability
		2.3 Ideal Functionalities
		2.4 Building Blocks
	3 UC-Secure Endemic OT via Random Oracles
	4 The Relations Between Endemic OT and Other Primitives
		4.1 From Endemic OT to Commitment
		4.2 From Endemic OT to Uniform OT
	5 GUC-Secure Endemic OT via Global Random Oracles
		5.1 Feasibility Results in the GroRO Model
		5.2 Impossibility and Feasibility Results in the GrpRO Model
	References
Half-Tree: Halving the Cost of Tree Expansion in COT and DPF
	1 Introduction
		1.1 Our Contribution
		1.2 Concurrent Work
	2 Preliminaries
		2.1 Notation
		2.2 Security Model and Functionalities
		2.3 Circular Correlation Robustness
		2.4 Function Secret Sharing
	3 Technical Overview
		3.1 Improved COT/sVOLE from Correlated GGM Trees
		3.2 DPF/DCF from Shared Pseudorandom Correlated GGM Trees
	4 Subfield VOLE Extension
		4.1 Single-Point COT and sVOLE from Correlated GGM
		4.2 Single-Point sVOLE from Pseudorandom Correlated GGM
	5 DPF and DCF Correlation Generation
		5.1 DPF and DCF Schemes
		5.2 DPF Correlation Generation
		5.3 DCF Correlation Generation
	References
A New Framework for Quantum Oblivious Transfer
	1 Introduction
		1.1 Open Problems and Directions for Future Research
		1.2 Related Work
	2 Technical Overview
		2.1 Non-Interactive OT in the Shared EPR Pair Model
		2.2 Two-Message OT Without Trusted Setup
		2.3 Three-Message Chosen-Input OT
		2.4 Extractable and Equivocal Commitments
	3 Seedless Extraction from Quantum Sources
		3.1 The XOR Extractor
		3.2 The Random Oracle Extractor
	4 The Fixed Basis Framework: OT from Entanglement
	References
Optimal Single-Server Private Information Retrieval*-12pt
	1 Introduction
		1.1 Our Contributions
		1.2 Additional Related Work
	2 Technical Roadmap
		2.1 Starting Point: Optimal 2-Server Scheme by Shi et al.
		2.2 Highlights of Our Construction and Proof Techniques
	3 Preliminaries
		3.1 Privately Programmable Pseudorandom Functions
		3.2 Single-Server Private Information Retrieval
		3.3 The Distribution D n
	4 Privately Programmable Pseudorandom Set
		4.1 Definition
		4.2 Construction
	5 PIR Scheme
	6 Privacy Proof
		6.1 Proof Roadmap
		6.2 Technical Lemma for Privately Programmable PRF
	References
Weighted Oblivious RAM, with Applications to Searchable Symmetric Encryption*-12pt
	1 Introduction
		1.1 Our Contributions
		1.2 Related Work
		1.3 Organization of the Paper
	2 General Preliminaries
		2.1 Majorization and Schur Convexity
	3 ORAM Preliminaries
		3.1 Weighted Oblivious RAM
		3.2 Tree ORAM
		3.3 -ORAM
	4 Generic Construction of wORAM from Tree ORAM
		4.1 Transformation Overview
		4.2 Translation Function
		4.3 Suitable Tree ORAM Schemes
		4.4 Main Result
		4.5 Experimental Results
	5 Application to Existing Tree ORAMs
		5.1 Weighted Simple ORAM ch15EPRINT:ChuPas13b
		5.2 Weighted Path ORAM ch15CCS:SvSFRY13
		5.3 Weighted Oblivious Parallel RAM ch15AC:ChaChuShi17
		5.4 Weighted Circuit ORAM ch15circuit
	6 Searchable Encryption from Weighted ORAM
		6.1 Preliminaries
		6.2 ZeroSSE
		6.3 BlockSSE
	References
NanoGRAM: Garbled RAM with O\"0365O(logN) Overhead*-12pt
	1 Introduction
	2 Technical Roadmap
		2.1 Background
		2.2 Our Approach
	3 Definitions: Garbled Data Structure
		3.1 Notational Conventions
	4 Building Blocks for Garbled Memory
		4.1 Stack (GStack)
		4.2 Switch (GSwitch)
	5 Non-Recursive Garbled Memory (NRGRAM)
		5.1 Definition
		5.2 Data Structures and Labels
		5.3 Construction
	6 Final Garbled RAM (GRAM) and Concrete Performance
	References
Lower Bound Framework for Differentially Private and Oblivious Data Structures
	1 Introduction
		1.1 Our Contributions
		1.2 Related Works
	2 Technical Overview
	3 Lower Bound Model
	4 Framework for Lower Bounds
		4.1 An Efficient Communication Protocol
		4.2 The Hard Distribution
		4.3 Bounding Query and Update Times
		4.4 Extension to Multiple Non-colluding Servers
	5 Lower Bounds
		5.1 Differentially Private RAMs
		5.2 Set Membership
		5.3 Predecessor and Successor
		5.4 Disjoint Sets (Union-Find)
		5.5 Searchable Encryption (Encrypted Multi-maps)
	6 Constructions for Oblivious Stacks and Queues
	7 Conclusions
	References
Lower Bounds for (Batch) PIR with Private Preprocessing
	1 Introduction
		1.1 Our Contributions
		1.2 Technical Overview
		1.3 Related Works
	2 Definitions
		2.1 Batch PIR with Private Preprocessing
		2.2 Lower Bound Model
	3 Lower Bound
		3.1 Characterizing Queried and Probed Entries
		3.2 Discovering Good Batch Queries
		3.3 An Impossible Encoding
	4 Upper Bound
		4.1 Blackbox Single-Query to Batch Reduction
	5 Barriers for General Lower Bounds
		5.1 Online Matrix-Vector OMV Conjecture
		5.2 Barriers for General PIR Lower Bounds
	6 Conclusions and Open Problems
	References
How to Compress Encrypted Data
	1 Introduction
		1.1 Our Contribution
		1.2 Strawman Approach
		1.3 Additional Related Works
	2 Preliminaries
		2.1 Homomorphic Encryption
		2.2 Polynomial Kung Fu
		2.3 Invertible Bloom Lookup Tables
	3 Ciphertext Compression
	4 Compression via Sparse Polynomials
	5 Compression via IBLTs
		5.1 Wunderbar Pseudorandom Vectors
		5.2 A Helpful Lemma
		5.3 Construction of Ciphertext-Compression from IBLTs
	References
Quantum Cryptography
Public Key Encryption with Secure Key Leasing
	1 Introduction
		1.1 Prior Work
		1.2 Our Results
		1.3 Technical Overview
		1.4 Other Related Work
	2 Preliminaries
	3 Public Key Encryption with Secure Key Leasing
	4 Public Key Encryption with CoIC-KLA Security
		4.1 Definition
		4.2 Construction
	5 Construction of PKE-SKL
	6 Attribute-based Encryption with Secure Key Leasing
		6.1 Definitions
		6.2 1-Bounded Distinguishing Key Construction
		6.3 Q-Bounded Distinguishing Key Construction
	7 Functional Encryption with Secure Key Leasing
		7.1 Definitions
		7.2 Constructions
	References
Another Round of Breaking and Making Quantum Money:
	1 Introduction
		1.1 Motivation
	2 Our Results
	3 Technical Overview
		3.1 How to Not Build Quantum Money from Lattices
		3.2 Quantum Money from Walkable Invariants
	4 Preliminaries
		4.1 Lattice Basics
		4.2 General LWE Definition
		4.3 Quantum Money and Quantum Lightning
	5 Our General Attack on a Class of Quantum Money
		5.1 The General Scheme
		5.2 Attacking the General Scheme
		5.3 Indistinguishability of |u\'\"526930B
		5.4 Constructing |u\'\"526930B
	6 Invariant Money
		6.1 Quantum Money from Walkable Invariants
		6.2 Approximate Verification
		6.3 Hardness Assumptions
		6.4 Security
	References
From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments*-12pt
	1 Introduction
		1.1 Our Results
	2 Technical Overview
		2.1 Part I: PKE from Group Actions
		2.2 Part II: Flavor Conversion for Commitments
	3 Preliminaries
		3.1 Canonical Quantum Bit Commitments
		3.2 Equivalence Between Swapping and Distinguishing
	4 Quantum-Ciphertext Public Key Encryption
		4.1 Swap-Trapdoor Function Pairs
		4.2 Quantum-Ciphertext Public Key Encryption
		4.3 Instantiation from Group Actions
	5 Equivalence Between Swapping and Distinguishing with Auxiliary States
	6 Our Conversion for Commitments
	References
Author Index