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 III

Preface
Organization
Contents – Part III
Differential Privacy
A Theory of Composition for Differential Obliviousness*-12pt
	1 Introduction
		1.1 Main Contribution: A Theory of Composition for Differential Obliviousness
		1.2 Additional Result: Optimal Privacy Amplification in the DO-Shuffle Model
	2 Model and Preliminaries
		2.1 Model of Computation
		2.2 Preliminaries
	3 A Composition Framework for DO
		3.1 Strongly Neighbor-Preserving
		3.2 (, )-Neighbor-Preserving Differential Obliviousness (NPDO)
		3.3 Main Composition Theorem
		3.4 Helpful Tools for Proving NPDO
		3.5 Our Composition Theorem in Action
	4 Proof of Main Composition Theorem
	5 Application: DO Compaction w.r.t. Edit Distance
		5.1 Additional Preliminaries
		5.2 Roadmap and Intuition
		5.3 RandBin Algorithm
		5.4 CompactBin Algorithm
	6 Application: Optimal Privacy Amplification in the Differentially Oblivious Shuffle Model
		6.1 Definitions
		6.2 Privacy Amplification in the DO-Shuffle Model
	References
On Differential Privacy and Adaptive Data Analysis with Bounded Space
	1 Introduction
		1.1 Differential Privacy
		1.2 Adaptive Data Analysis
		1.3 Our Techniques
		1.4 Applications to Communication Complexity
		1.5 Related Works
		1.6 Paper Structure
	2 Multi-instance Leakage-Resilient Scheme
	3 Space Hardness for Differential Privacy
		3.1 Preliminaries on Computational Differential Privacy and Fingerprinting Codes
		3.2 A Negative Result for the DA Problem
	4 Space Hardness for Adaptive Data Analysis (ADA)
		4.1 Informal Proof Sketch
	5 Construction of an MILR Scheme from a Semantically Secure Encryption Scheme
	6 Multi-security Against a Bounded Preprocessing Adversary
		6.1 Preliminaries
		6.2 Key Leakage Lemma
		6.3 The Proof of Theorem 5.2
		6.4 Proof of Lemma 6.2
	References
Compromise-Resilient Cryptographic Primitives
Deniable Authentication When Signing Keys Leak
	1 Introduction
	2 Technical Overview
		2.1  MDVS Construction
		2.2 PKEBC Construction
	3 Preliminaries
	4 Multi-designated Verifier Signature Schemes with Enhanced Off-The-Record Security
		4.1 Security Notions
		4.2 DVS Construction
		4.3 A Conceptually Simple  MDVS Construction
		4.4 Achieving Tight Security Under Adaptive Corruptions
	5 PKEBC Scheme with Linear Ciphertext Size and Decryption Time
		5.1 Security Notions for Adaptive Corruptions
		5.2 Achieving Linear Ciphertext Size
		5.3 Achieving Linear Time Decryption
		5.4 Achieving Tight Security Under Adaptive Corruptions
	6 Multi-designated Receiver Signed Public Key Encryption Schemes
		6.1 Security Notions
		6.2 Construction of  MDRS-PKE with Short Ciphertexts
	References
Let Attackers Program Ideal Models: Modularity and Composability for Adaptive Compromise
	1 Introduction
		1.1 Adaptive Compromise and SIM-AC Security
		1.2 Our Results
	2 Preliminaries
	3 SIM-AC Definitions and Their Shortcomings
		3.1 SIM-AC Definitions
		3.2 Shortcomings of SIM-AC
	4 SIM*-AC Security
		4.1 SIM*-AC Definitions
		4.2 Single-user Security Implies Multi-user Security
		4.3 Cascade Construction
	5 Asymmetric Encryption
		5.1 Definitions
		5.2 Comparison to SIM-FULL Definition
		5.3 KEM/DEM Hybrid Encryption
		5.4 Hashed KEM
		5.5 Fujisaki-Okamoto Transform
	6 Recovering Prior Results
		6.1 High-Level Proofs
		6.2 Intermediate-Level Proofs
		6.3 Low-Level Proofs
	References
Almost Tight Multi-user Security Under Adaptive Corruptions & Leakages in the Standard Model*-12pt
	1 Introduction
		1.1 Our Contributions
	2 Technical Overview
		2.1 Our SIG: Technical Overview
		2.2 Our PKE: Technical Overview
		2.3 Our SC, MAC and AE: Technical Overview
		2.4 Instantiations from MDDH Assumptions and Leakage Resilience
		2.5 Comparison with Existing Techniques for Tight MUc Security
	3 Preliminaries
		3.1 Language Distribution
		3.2 Quasi-Adaptive Hash Proof System
		3.3 Tag-Based Quasi-Adaptive Non-Interactive Zero-Knowledge
	4 Publicly-Verifiable QA-HPS and New Properties
	5 SIG with Tight Strong MUc&l-CMA Security
		5.1 Definition of Strong MUc&l-CMA Security
		5.2 Generic Construction of SIG from PV-QA-HPS and QA-NIZK
	6 PKE with Tight MUMCc&l-CCA Security
		6.1 Definition of MUMCc&l-CCA Security
		6.2 Generic Construction of PKE from QA-HPS and QA-NIZK
	7 More Primitives and Instantiations from MDDH
	References
Privately Puncturing PRFs from Lattices: Adaptive Security and Collusion Resistant Pseudorandomness*-4pt
	1 Introduction
		1.1 Our Results
		1.2 Technical Overview
		1.3 Related Work
	2 Preliminaries
	3 Explainable Hash Functions
		3.1 The Definition
		3.2 The Construction
	4 Private Puncturable PRFs
		4.1 The Definition
		4.2 The Construction
	References
Constrained Pseudorandom Functions from Homomorphic Secret Sharing
	1 Introduction
		1.1 Our Contributions
	2 Technical Overview
		2.1 General Strategy
		2.2 CPRF from HSS with Simulatable Memory Shares
		2.3 Handling More Constraints via Staged HSS
		2.4 Applications of Staged HSS to Secure Computation
	3 Preliminaries
	4 Homomorphic Secret Sharing and Extensions
		4.1 Homomorphic Secret Sharing
		4.2 HSS Following the RMS Template
		4.3 Extended Evaluation and Simulatable Memory Values
		4.4 Staged Homomorphic Secret Sharing
	5 Constrained Pseudorandom Functions
		5.1 CPRF for Inner-Product from HSS
		5.2 CPRF for NC1 from HSS
	6 Applications to Secure Multiparty Computation
		6.1 Sublinear Computation with One-Sided Statistical Security
	References
Advanced Public Key Primitives
Efficient FHEW Bootstrapping with Small Evaluation Keys, and Applications to Threshold Homomorphic Encryption
	1 Introduction
		1.1 Our Results
		1.2 Techniques
		1.3 Applications to Threshold and Multi-key FHE
		1.4 Other Important Related Works
		1.5 Organization
	2 Preliminaries
		2.1 Basic Lattice-Based Encryption
		2.2 FHEW-Like Bootstrapping
	3 New Blind Rotation Techniques
		3.1 The Core Blind Rotation Algorithm
		3.2 Dealing with Even i
		3.3 Improved FHEW Scheme and Removal of brknsum
	4 Analysis
		4.1 Analysis of the Number of Automorphisms
		4.2 Complexity, Key Size, and Error Analysis
	5 Implementation
		5.1 Parameter Sets
		5.2 Runtime Results
	6 Applications to Threshold Homomorphic Encryption
		6.1 Distributed Generation of Evaluation Keys
		6.2 Performance Analysis
	7 Conclusion
	References
On Polynomial Functions Modulo pe and Faster Bootstrapping for Homomorphic Encryption*-12pt
	1 Introduction
		1.1 Related Work
		1.2 Our Contributions
	2 Preliminaries
		2.1 Notations
		2.2 Newton Interpolation over R
		2.3 Polyfunctions Modulo pe
		2.4 Lattices
		2.5 Homomorphic Encryption
	3 Systematic Study of Polyfunctions
		3.1 Null Polynomials
		3.2 Cosets of Equivalent Polynomials
		3.3 Existence of Polynomial Representation
		3.4 Bit and Digit Extraction Function
		3.5 Further Properties of Polyfunctions
	4 Faster Bootstrapping for BGV and BFV
		4.1 Cost Model
		4.2 Digit Removal Algorithm
		4.3 Faster Digit Removal
	5 Implementation and Performance
		5.1 Function Composition
	6 Conclusion
	References
Functional Commitments for All Functions, with Transparent Setup and from SIS*-12pt
	1 Introduction
		1.1 Our Contributions
		1.2 Concurrent Related Work
		1.3 Technical Overview
		1.4 Future Work
	2 Preliminaries
		2.1 Short Integer Solution
		2.2 Functional Commitments
	3 Functional Commitments from SIS
		3.1 Homomorphic Computation
		3.2 Functional Commitment Construction
	4 Concrete Instantiations
		4.1 Bounded-Support Commitments
		4.2 Polynomial Commitments
		4.3 Functional Commitments for Bounded Boolean Functions
	References
Batch Bootstrapping I:
	1 Introduction
		1.1 Our Contributions
		1.2 Technical Overview
	2 Preliminary
		2.1 Lattices and Sub-Gaussian Random Variables
		2.2 Algebraic Number Theory Background
		2.3 Learning with Errors Assumption
	3 RGSW in General Cyclotomic Rings
		3.1 RLWE Scheme
		3.2 RGSW Scheme
	4 New Batch Homomorphic Methods via Tensor Rings
		4.1 Framework of Batch Plaintext Computation
		4.2 Homomorphic Encoding and Computation
		4.3 Homomorphic Evaluation of the Trace Function
	5 Instantiations
	6 Batch Bootstrapping via Our New Framework
		6.1 Bootstrapping Background
		6.2 Batch Bootstrapping
		6.3 Efficiency
	References
Batch Bootstrapping II:
	1 Introduction
		1.1 Our Contributions
		1.2 Technical Overview
	2 Preliminaries
		2.1 Lattices and Sub-Gaussian Random Variables
		2.2 Algebraic Number Theory Background
		2.3 Learning with Errors Assumption
		2.4 RLWE/RGSW in General Cyclotomic Rings
	3 Foundation Developed in Batch Bootstrapping I
		3.1 The Framework of Batch Homomorphic Computation
	4 New Batch Homomorphic Algorithms
		4.1 Batch ``Vector\'\'-``Encrypted Matrix\'\' Multiplication
		4.2 Multiplications Over Small(er) Rings
	5 Homomorphic DFT/Inverse-DFT
		5.1 First Attempt
		5.2 New Building Blocks
		5.3 Our Improved Method
	6 Homomorphic DFT-1, Recursively
		6.1 Nussbaumer Transform
		6.2 Homomorphic Evaluation
	7 Putting Things Together – Faster Bootstrapping
		7.1 MSB Extract and LWE Packing
		7.2 Our Batch Bootstrapping Method
		7.3 Efficiency
	References
Succinct Vector, Polynomial, and Functional Commitments from Lattices*-12pt
	1 Introduction
		1.1 Our Results
		1.2 Technical Overview
		1.3 Related Work and Concurrent Work
	2 Preliminaries
	3 Vector Commitments with Private Opening from SIS
		3.1 The Basis-Augmented SIS (BASIS) Assumption
		3.2 Vector Commitments with Private Opening from SIS
	4 Succinct Functional Commitments for Circuits
		4.1 Opening to Linear Functions and Applications to Polynomial Commitments
		4.2 Supporting Private Openings
	5 Aggregatable Vector Commitments
	6 New SIS Assumptions: Relations and Discussion
		6.1 Another View of the BASISstruct Assumption
	References
Efficient Laconic Cryptography from Learning with Errors
	1 Introduction
		1.1 Our Results
		1.2 Related Work
	2 Technical Overview
		2.1 Laconic Encryption
		2.2 Applications
	3 Preliminaries
		3.1 Lattices
	4 Laconic Encryption
		4.1 Definition
		4.2 Our Construction
	References
Fully Adaptive Decentralized Multi-Authority ABE
	1 Introduction
		1.1 Our Results
	2 Technical Overview
		2.1 Background on MA-ABE
		2.2 Fully Adaptive Security
		2.3 Limitations of Previous Works
		2.4 Overview of Our Approach and Our (Composite Order) Scheme
		2.5 Porting to Prime Order Groups
	3 Preliminaries
		3.1 Access Structures and Linear Secret Sharing Schemes
		3.2 Strong Randomness Extractors
		3.3 Fully-Adaptive Decentralized MA-ABE for LSSS
	4 Our Composite Order Group MA-ABE Scheme
		4.1 Composite Order Bilinear Groups
		4.2 The Construction
		4.3 Correctness
	5 Our Prime Order Group MA-ABE Scheme
		5.1 Prime Order Bilinear Groups and Associated Notations
		5.2 Composite to Prime Order Translation Framework
		5.3 The Construction
	References
On the Optimal Succinctness and Efficiency of Functional Encryption and Attribute-Based Encryption
	1 Introduction
		1.1 Our Results
		1.2 Technical Overview
		1.3 Related Works
	2 Preliminaries
		2.1 Laconic Garbled RAM
		2.2 Partially Hiding Functional Encryption and FE for Circuits
		2.3 Universal RAM and PHFE for RAM
	3 Efficiency Trade-Offs of PHFE for RAM
		3.1 Contention Between Storage Overhead and Decryption Time
	References
Registered Attribute-Based Encryption
	1 Introduction
		1.1 Related Work
	2 Technical Overview
		2.1 Constructing Slotted Registered ABE from Pairings
	3 Preliminaries
	4 Registered Attribute-Based Encryption
		4.1 Slotted Registered Attribute-Based Encryption
	5 Slotted Registered ABE from Pairings
		5.1 Preliminaries: Composite-Order Pairing Groups
		5.2 Slotted Registered ABE from Composite-Order Pairing Groups
	6 From Slotted Registered ABE to Registered ABE
	7 Registered ABE from Indistinguishability Obfuscation
	References
Unbounded Quadratic Functional Encryption and More from Pairings
	1 Introduction
		1.1 Our Results
		1.2 Technical Overview
	2 Preliminaries
		2.1 Notations
		2.2 Basic Tools and Assumptions
		2.3 Functional Encryption
	3 Predicate Slotted Inner Product Functional Encryption
		3.1 Definitions
		3.2 Predicate Slotted IPFE from Slotted IPFE
	4 Unbounded Slotted Inner Product Functional Encryption
		4.1 Definitions
		4.2 Unbounded Slotted IPFE from Predicate Slotted IPFE
		4.3 Security Analysis
	5 Unbounded Quadratic Functional Encryption
		5.1 Construction
		5.2 Security
		5.3 Bounded Variable-Length Scheme Without Random Oracles
	6 Functional Encryption for ABPUQF
		6.1 Partial Garbling Scheme for FABPn,n\'
		6.2 Construction
		6.3 Security
	References
Multi-key and Multi-input Predicate Encryption from Learning with Errors
	1 Introduction
		1.1 Our Contributions
		1.2 Technical Overview
		1.3 Applications
		1.4 Relation with Witness Encryption (WE)
	2 Related Work
	3 Preliminaries
	4 Multi-key and Multi-input Predicate Encryption
	5 Constructions
		5.1 Multi-key PE from PE and Lockable Obfuscation
		5.2 Multi-input PE from PE, Lockable Obfuscation and PKE
	References
Broadcast, Trace and Revoke with Optimal Parameters from Polynomial Hardness
	1 Introduction
		1.1 Prior Work: Embedded Identity Trace and Revoke
		1.2 Our Results
		1.3 Technical Overview
	2 Revocable Predicate Encryption
	3 Public-key RPE from FE and LWE
		3.1 Alternate Construction Using LOT
	4 Revocable Mixed Functional Encryption
		4.1 Definition
		4.2 Construction
	References
Traitor Tracing with N1/3-Size Ciphertexts and O(1)-Size Keys from k-Lin
	1 Introduction
		1.1 Our Results
		1.2 Technical Overview
		1.3 Discussion
	2 Preliminaries
		2.1 Prime-Order Bilinear Groups
		2.2 Traitor Tracing
		2.3 Attribute-Based Functional Encryption
	3 Building Traitor Tracing
		3.1 TB-PLBE
		3.2 Traitor Tracing from TB-PLBE
	4 Building Attribute-Based Functional Encryption
		4.1 Building Block: Functional Encryption for Quadratic Functions
		4.2 Building Block: Attribute-Based Key Encapsulation Mechanism
		4.3 AB-FE for Quadratic Functions
		4.4 AB-KEM for Local (Read-Once) Monotone Span Programs
		4.5 Threshold Broadcast, Private Linear Broadcast Encryption
	References
Author Index