Theory of Cryptography: 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 – December 2, 2023, Proceedings, Part II (Lecture Notes in Computer Science)

Preface
Organization
Contents – Part II
Multi-party Computation II
Broadcast-Optimal Four-Round MPC in the Plain Model
	1 Introduction
		1.1 Our Contributions
		1.2 Technical Overview
		1.3 Related Work
	2 Preliminaries and Notations
	3 Positive Results
	4 Negative Results
		4.1 SIA Impossibility Results
	References
Taming Adaptivity in YOSO Protocols: The Modular Way
	1 Introduction
		1.1 Our Contributions
	2 Preliminaries
		2.1 Key and Message Non-commiting Encryption
		2.2 Cryptographic Sortition
		2.3 The You-Only-Speak-Once Model
		2.4 Compiling Abstract YOSO Protocols
	3 Role Assignment
	4 Compiling Abstract to Natural YOSO
	5 Security of the Compiler
	6 Compiling Abstract Protocols Requiring Verification
		6.1 Verifiable State Propagation
		6.2 Extending to Verifiable State Propagation
		6.3 Security of the Extended Compiler
	7 Realising Role Assignment
	8 The Versatility of Our Compiler
	References
Network Agnostic MPC with Statistical Security
	1 Introduction
		1.1 Our Motivation and Results
		1.2 Detailed Technical Overview
		1.3 Other Related Works
		1.4 Open Problems
		1.5 Paper Organization
	2 Preliminaries and Definitions
	3 Network Agnostic Byzantine Agreement
	4 Network Agnostic Information Checking Protocol
	5 Network Agnostic Verifiable Secret Sharing (VSS)
		5.1 Reconstruction and Secure Multicast Protocol
	6 Network Agnostic Protocol for Generating Linearly Secret-Shared Random Values with IC-Signatures
		6.1 Network Agnostic VSS for Multiple Dealers
		6.2 Protocol for Generating Secret-Shared Random Values
	7 Network Agnostic Protocol for Triple Generation
		7.1 Generating Linear Secret Sharing of a Value with IC-Signatures
		7.2 Non-robust Multiplication Protocol
		7.3 Random Triple Generation with Cheater Identification
		7.4 The Multiplication-Triple Generation Protocol
	References
On Secure Computation of Solitary Output Functionalities with and Without Broadcast
	1 Introduction
		1.1 Our Contributions
		1.2 Our Techniques
		1.3 Related Work
		1.4 Organization
	2 Preliminaries
		2.1 Notations
	3 Our Main Results in the Point-to-Point Model
		3.1 Useful Definitions
		3.2 Our Main Results
	References
On the Round Complexity of Fully Secure Solitary MPC with Honest Majority
	1 Introduction
		1.1 Our Results
		1.2 Roadmap
	2 Technical Overview
		2.1 Overview of Upper Bounds
		2.2 Overview of Lower Bounds
	3 Preliminaries
		3.1 Notation and Setting
		3.2 Cryptographic Primitives
	4 With Broadcast and No PKI
		4.1 Necessity of Three Rounds
		4.2 Necessity of Broadcast in Round 1
		4.3 Necessity of Broadcast in Round 2
	5 With PKI and No Broadcast
		5.1 Necessity of Four Rounds
		5.2 General Five-Round Protocol
		5.3 (t + 2) Round Protocol
	References
Three Party Secure Computation with Friends and Foes
	1 Introduction
		1.1 Our Results
		1.2 Our Techniques
		1.3 Related Work
		1.4 Organization
	2 Preliminaries
		2.1 Notations
		2.2 The Model of Computation
		2.3 FaF Security-With-Identifiable-Abort
		2.4 The Two-Party Model
	3 The Dealer Model
	4 Feasibility Results for Three-Party FaF Security
		4.1 A Compiler from 2-Party Standard Security to 3-Party FaF-Security
		4.2 FaF Secure Protocols for Boolean Functionalities
	5 Lower Bound on the Round Complexity of FaF Secure Protocols
	6 Impossibility for a Two-Input Three-Party Functionality
	References
Encryption
CASE: A New Frontier in Public-Key Authenticated Encryption
	1 Introduction
		1.1 Related Work
	2 Technical Overview
		2.1 Defining COA-Secure CASE
		2.2 Constructing a COA-Secure CASE
		2.3 A Real-Ideal Definition
		2.4 Proving COA Security  -s-IND-PRE Secure CASE
	3 COA Security for CASE
		3.1 Encasing Resistance
		3.2 Augmented Security
	4 Constructing a COA-Secure CASE scheme
		4.1 Building Block: COA-Secure QD-PKE
		4.2 Building Block: Existentially Consistent Anonymous Signature
		4.3 Main Construction: COA-Secure CASE
		4.4 Improving the Efficiency of COA-Secure CASE
	5 Active Agents Framework
		5.1 The Model
	6 CASE in the Active Agents Framework
	References
Revisiting Updatable Encryption: Controlled Forward Security, Constructions and a Puncturable Perspective
	1 Introduction
		1.1 Our Contribution
		1.2 Preliminaries and Outline
	2 Updatable Encryption with Expiry Epochs
		2.1 Relation to Other UE Security Notions
	3 UE from a Puncturable-Encryption Perspective
		3.1 Tag-Inverse Puncturable Encryption
		3.2 Generic UE Construction from TIPE
		3.3 TIPE from Standard Assumptions
	References
Combinatorially Homomorphic Encryption
	1 Introduction
		1.1 Combinatorially Homomorphic Encryption
		1.2 Related Work
	2 Preliminaries
		2.1 Communication Complexity
		2.2 Encryption
		2.3 Collision Resistant Hash Function
	3 Combinatorially Homomorphic Encryption
		3.1 CC-Homomorphic Encryption
	4 Applications
		4.1 Lossy Encryption
		4.2 Collision Resistant Hash Function
	5 Instantiations
		5.1 Low Noise LPN
	References
Security with Functional Re-encryption from CPA
	1 Introduction
		1.1 Our Main Result
	2 Definitions
		2.1 An Alternative Definition of FuncCPA
	3 From CPA to FuncCPA
		3.1 Technical Overview
		3.2 Building Blocks
		3.3 The CDMW Transformation
		3.4 Proof of Security
		3.5 Extension to General FuncCPA-Security
	4 Conclusions and Open Problems
	A Direct Implications and Separations
	References
Lower Bounds on Assumptions Behind Registration-Based Encryption
	1 Introduction
		1.1 Our Results
	2 Technical Overview
	3 Preliminaries
		3.1 Public Key Compression
	4 Impossibility of PKCom from TDPs
		4.1 Oracle-Based Target-Restricted Signatures
		4.2 Impossibility of CRS-Free PKCom from TDP
	5 Impossibility in Shoup\'s Generic Group Model
		5.1 Impossibility of CRS-Free PKCom in Shoup\'s GGM
	A Omitted Proofs
	B Attacks on RBE with CRS
		B.1 TDP-Impossibility of PKCom with CRS
		B.2 Impossibility of PKCom with CRS in Shoup\'s GGM
	References
Secret Sharing, PIR and Memory Checking
Proactive Secret Sharing with Constant Communication
	1 Introduction
	2 Related Work
	3 Model
	4 Expander Graphs
	5 O(n)-Private PSS with Constant Communication
	6 O(n)-Robust only PSS with Constant Communication
	7 O(na)-Private, O(n1-a)-Robust PSS with O() Communication
	8 Securing Channels Using Signing Oracles
	9 O(n)-secure Proactive Pseudorandomness with O() Communication
	A  Previous Work
		A.1  PSS Protocols
		A.2  Refreshing Secure Channels
	B  Ramanujan Expanders
	C  Epoch Length
	D  Proof of Lemma 10
	References
Improved Polynomial Secret-Sharing Schemes
	1 Introduction
		1.1 Our Techniques
		1.2 Previous Works
	2 Preliminaries
		2.1 Notations
		2.2 Access Structures and Secret-Sharing Schemes
		2.3 Conditional Disclosure of Secrets
		2.4 Degree-d Secret Sharing and Degree-d CDS Protocols
		2.5 Matching Vectors
	3 A Polynomial 2-Server CDS Protocol
		3.1 The CDS Protocol over m = p1p2
		3.2 Sparse Matching Vectors
	4 Constructions of d-Sparse Matching Vector Families
		4.1 Efremenko\'s Construction
		4.2 Our Construction
		4.3 Kutin\'s Construction
		4.4 Comparison of the Three Constructions
	5 A Polynomial k-Server CDS Protocol
		5.1 The Selection Protocol
		5.2 Protocols for the Simulation of Bob\'s Messages
		5.3 The k-Server CDS Protocol
	6 Construction of Decomposable Matching Vector Families
		6.1 Decomposability of Efremenko\'s and Our MVs
		6.2 Decomposability of Kutin\'s MVs
	7 A Polynomial Secret Sharing Scheme for General Access Structures
	References
Near-Optimal Private Information Retrieval with Preprocessing
	1 Introduction
	2 Background: PIR, Puncturable Functions and Puncturable Sets
	3 Preliminary 2PIR+ Protocol
	4 Adaptable Pseudorandom Sets
	5 More Efficient 2PIR+ and Near-Optimal 1PIR
	A  Definitions
		A.1  Additional Definitions for Adaptable PRSs
	B  Correctness Lemmata
	C  PRS Constructions and Proofs
	References
Memory Checking for Parallel RAMs
	1 Introduction
		1.1 Our Contributions
		1.2 Related Work
		1.3 Organization
	2 Technical Overview
		2.1 Overview of Our Constructions
		2.2 Main Challenges with Concurrency
		2.3 Our Techniques for Concurrency
	3 Preliminaries
		3.1 Parallel RAM Machines
		3.2 Authentication
	4 Memory Checking Model
		4.1 Memory Checking for RAMs
		4.2 Memory Checking for Parallel RAMs
	5 Efficient Parallel Online Checker
	6 Statistically Secure EREW Parallel Offline Checker
	7 CRCW Parallel Offline Checker from One-Way Functions
	8 Maliciously Secure Oblivious Parallel RAM
	References
Author Index