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

Preface
Organization
Contents – Part I
Proofs and Outsourcing
Beyond MPC-in-the-Head: Black-Box Constructions of Short Zero-Knowledge Proofs
	1 Introduction
		1.1 Our Contribution
		1.2 Technical Overview
		1.3 Related Works
		1.4 Paper Organization
	2 Preliminaries
		2.1 Commitment Schemes
		2.2 Zero-Knowledge Proofs (ZKPs)
		2.3 Interactive Oracle Proofs (IOP)
		2.4 Homomorphic Secret Sharing (HSS)
	3 ZKPs from Game-Based Primitives
	4 Zero-Knowledge Proof Constructions
		4.1 Zero-Knowledge Proofs from Homomorphic Secret Sharing (HSS)
		4.2 Constant-Round ZKPs Approaching Witness Length
	References
Your Reputation\'s Safe with Me: Framing-Free Distributed Zero-Knowledge Proofs
	1 Introduction
		1.1 Our Contribution
		1.2 Highlights of Our Techniques
		1.3 Open Problems and Future Directions
		1.4 Paper Organization
		1.5 Related Works
	2 Preliminaries
		2.1 Distributed Zero-Knowledge (dZK) Proofs
		2.2 Secure Multi-Party Computation (MPC) Protocols
	3 Checking Membership in a Robust Code
	4 dZK Proofs from Secure MPC Protocols
	References
Locally Verifiable Distributed SNARGs
	1 Introduction
		1.1 Background on Distributed Certification
		1.2 Background on Delegation of Computation
		1.3 Our Results
	2 Model and Definitions
		2.1 Locally Verifiable Distributed SNARGs
	3  LVDSNARGs with a Global Prover
	4 LVDSNARGs with a Distributed Prover
	5 Distributed Merkle Trees
	References
Distributed-Prover Interactive Proofs
	1 Introduction
		1.1 Techniques: Distributed IOPs and Distributed Streaming Polynomial Commitments
		1.2 Related Work
		1.3 Organization
	2 Preliminaries
		2.1 Multilinear Polynomials
	3 Model Definition
		3.1 Succinct Arguments in the MPC Model
	4 Defining Multilinear Polynomial Commitments in the MPC Model
	5 Constructing Succinct Arguments in the MPC Model
		5.1 Tools from Prior Work
		5.2 Notation
		5.3 The Construction
		5.4 From Round Verification to a Full Argument
	6 Constructing Polynomial Commitments in the MPC Model
		6.1 Distributed Streaming Model
		6.2 Our New Construction
		6.3 Proof of Theroem 2
	References
Rogue-Instance Security for Batch Knowledge Proofs
	1 Introduction
		1.1 Our Contributions
	2 Our Techniques
		2.1 High-Moment Hardness
		2.2 Rogue-Instance Security for Batch Protocols
		2.3 Batching Algebraic Sigma Protocols
		2.4 Non-interactive Batch Arguments
		2.5 General Batch Sigma Protocols
		2.6 Expected Time Hardness Framework
	3 Preliminaries
		3.1 High-Moment Hardness
		3.2 Sigma Protocols
		3.3 Batch Sigma Protocols
	4 Rogue-Instance Security
		4.1 Batch Sigma Protocols
	5 Batching Algebraic Sigma Protocols
		5.1 Algebraic Sigma Protocols
		5.2 The Collision Game
		5.3 Rogue Soundness Error Bound from the Collision Game
		5.4 Algebraic Batch Identification Schemes
	6 Proving Expected-Time Hardness in Generic Models
		6.1 Our Framework
	References
On Black-Box Verifiable Outsourcing
	1 Introduction
		1.1 Our Results
		1.2 Our Techniques
		1.3 Related Work
	2 Preliminaries
		2.1 Mathematical Preliminaries and Definitions
		2.2 Bit Fixing Random Oracle Model
		2.3 Homomorphic Encryption
		2.4 Random Self Reducibility
		2.5 No-Signaling Prover
	3 Defining Oracle-Aided Batch Verifiable Computation
	4 Protocol for Functions Admitting 1-RSR
	5 Protocol for Functions Admitting K-RSR
		5.1 OBVC with Multiple Provers
		5.2 OBVC with a Single Prover
	6 Impossibility of Oracle-Aided Batch Verifiable Computation
	References
Theoretical Foundations
Counting Unpredictable Bits: A Simple PRG from One-Way Functions
	1 Introduction
	2 Proof Overview
	3 Preliminaries
		3.1 Notations
		3.2 One-Way Functions and Pseudorandom Generators
		3.3 Min-Entropy and Extraction
	4 Unpredictable Bits
	5 OWFs  Unpredictable Bits
		5.1 Proving Lemma5.3.
		5.2 Proving Theorem 5.1
	6 Bits Unpredictability  Random Bits Unpredictability
		6.1 Proving Theorem 6.1
	7 Extracting Pseudorandomness and the Main Theorem
		7.1 Exponentially-Hard OWFs
		7.2 Proving Theorem 7.1
		7.3 Proving Claim 7.6
		7.4 Proving Claim 7.7
	8 Saving Seed Length
	References
On One-Way Functions and Sparse Languages
	1 Introduction
		1.1 Our Results
		1.2 Proof Overview
	2 OWFs from Avg-Case Hardness of Sparse Languages
	3 Avg-Case Hardness of Sparse Languages from OWFs
	4 Corollaries
		4.1 Kolmogorov Complexity
		4.2 k-SAT
		4.3 t-Clique
	5 OWF from Hardness of Approximating K-Complexity
	References
Security Proofs for Key-Alternating Ciphers with Non-Independent Round Permutations
	1 Introduction
	2 Preliminaries
		2.1 Notation
		2.2 Random Permutation Model, Transcripts and Graph View
		2.3 Two Useful Lemmas
	3 Technical Overview
		3.1 Proof Method of ch9DBLP:journalsspsjocspsChenLLSS18
		3.2 A General Transformation
		3.3 New Proof Strategies
	4 Improved Security Bound of P1P1P1-Construction
		4.1 Comparison of the Results
		4.2 Proof of Theorem 2
	5 Tight Security Bound of t-Round KACSP
		5.1 Case 1: q = (N1/2)
		5.2 Case 2: q = O(N1/2)
	6 Remarks on Other Variants of KACS
	References
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method
	1 Introduction
		1.1 Goldreich\'s Pseudorandom Generator
		1.2 A New Public-Key Encryption Scheme
		1.3 Correctness
		1.4 Security
		1.5 The Low-Degree Method
		1.6 Relation to the ABW Schemes
		1.7 Open Questions
	2 Public Key Encryption
	3 The Low-Degree Method
	4 Planting Hyperloops
		4.1 Expansion of 3-Regular Graphs
	5 Low-Degree Security of Goldreich\'s Function
	6 The Encryption Scheme
	References
Cryptography from Planted Graphs: Security with Logarithmic-Size Messages
	1 Introduction
		1.1 Our Results
	2 Overview of Techniques
		2.1 Planted Subgraph Assumptions
		2.2 PSM Protocols with Logarithmic Message-Size
		2.3 Forbidden Graph Secret-Sharing Schemes with Logarithmic Share-Size
		2.4 On Breaking the log n Barrier for 2-out-of-n Secret-Sharing Schemes
	3 Preliminaries
	4 The Planted Subgraph Problem
		4.1 The Planted Clique Assumption
		4.2 The Planted Subgraph Assumption
		4.3 The Planted Subgraph Assumption with Hints
	References
Multi-party Computation I
Randomized Functions with High Round Complexity
	1 Introduction
		1.1 Discussion: Interaction in a World Without Security
		1.2 Round Complexity of Deterministic Functions
		1.3 Round Complexity of Randomized Functions with Small Output Set
		1.4 Round Complexity of Randomized Functions (General Case)
		1.5 Overview of the Paper
	2 Our Contributions
	3 Technical Overview of Our Results
		3.1 High-Level Summary of the BKMN Geometric Framework
		3.2 The ``Tartan Square\'\' Meets Secure Computation
		3.3 Overview: Proof of Theorem 1
		3.4 Overview: Proof of Theorem 2
	4 Lamination Hull
	5 BKMN Geometric Framework: A Formal Introduction
		5.1 An Example
	6 Preliminaries
		6.1 Notations
		6.2 Convex Geometry
	7 Functions with High Round Complexity
		7.1 Proofs of Theorem 3 and Theorem 4
		7.2 Proofs of Claims Needed for Theorem 3
		7.3 Proof of Claims Needed for Lemma2, Lemma3, and Lemma4
		7.4 Properties of the Four Sequences
	8 On the Optimality of Our Constructions
		8.1 Proof of Theorem 5
	References
Towards Topology-Hiding Computation from Oblivious Transfer
	1 Introduction
		1.1 Our Result
	2 Technical Overview
		2.1 A High-Level Overview
		2.2 Technical Overview of the Core Protocol: Locally Simulatable MPC on a Path
	3 Preliminaries
		3.1 Topology-Hiding Computation (THC)
		3.2 Constant-Overhead Two-Party Computation for Semi-Honest Adversaries
		3.3 Efficiently Invertible from Local Information Functionalities
	4 Locally Simulatable MPC
		4.1 Locally Simulatable Protocols Are Execution-Oblivious
	5 Locally Simulatable Protocol for Directed Paths
		5.1 The Path Protocol
	6 Extension to All Graphs
	References
On the Impossibility of Surviving (Iterated) Deletion of Weakly Dominated Strategies in Rational MPC
	1 Introduction
		1.1 Our Contribution
		1.2 Consequences
		1.3 The Way Forward for Rational MPC
		1.4 Organization
	2 Discussion of Related Work
		2.1 History of (Iterated) Deletion of Weakly Dominated Strategies
		2.2 In Defense of Weak Domination
		2.3 Alternative Notions
	3 Preliminaries
		3.1 Model of Computation and Communication
		3.2 Secret Sharing
		3.3 Game-Theoretic Notions
		3.4 Rational Secret Reconstruction
	4 Weak Domination in Existing Secret Reconstruction Protocols
	5 Impossibility Results for Surviving Iterated Deletion of Weakly Dominated Strategies
		5.1 Impossibility with Respect to Non-uniform Strategies
		5.2 Impossibility with Respect to Other Settings
	6 Impossibility of Rational Mechanisms for Majority Coalitions
		6.1 Weak Domination for Coalitions
		6.2 An Assumption on the Secret-Sharing Scheme
		6.3 Proving Impossibility
	References
Synchronizable Fair Exchange
	1 Introduction
	2 Preliminaries
		2.1 Secure Computation
		2.2 The Hybrid Model
		2.3 Fairness Versus Guaranteed Output Delivery
	3 Synchronizable Exchange
	4 Fair Secure Computation in the –Hybrid Model
		4.1 Intuition
		4.2 Protocol
		4.3 Proof Sketch of Security
		4.4 Getting to the –Hybrid Model
	5 Preprocessing
		5.1 Intuition
	References
DORAM Revisited: Maliciously Secure RAM-MPC with Logarithmic Overhead
	1 Introduction
		1.1 MPC in the RAM Model
		1.2 Building RAM-MPC
	2 Notation and Definitions
	3 Related Work
	4 Technical Overview
	5 The Arithmetic Black Box (ABB) Model
	6 QuietCache: Maliciously-Secure Oblivious Cache Construction
	7 Maliciously-Secure Oblivious Set Construction
	8 Maliciously-Secure Oblivious Hash Table Construction
	9 Maliciously-Secure Oblivious Map Construction
	References
3-Party Secure Computation for RAMs: Optimal and Concretely Efficient
	1 Introduction
		1.1 Our Contributions
		1.2 Technical Overview
	2 Comparison with ch17FalkNOSZ23
	3 Preliminaries
		3.1 Secret Sharing Schemes
		3.2 Distributed Oblivious RAM
	4 Secure Computation Building Blocks
	5 Efficient Passively Secure Distributed Oblivious Hashing
		5.1 Distributed Oblivious Permutation
		5.2 Distributed Oblivious Hashing for Short Inputs
		5.3 Distributed Oblivious Hashing for Long Inputs
	6 Optimal DORAM Against Passive Adversary
	7 Actively Secure Extension
		7.1 Secure Oblivious Permutation up to Additive Attacks
		7.2 Actively Secure Distributed Hashing
		7.3 Actively Secure Distributed ORAM
	8 Conclusion
	References
Author Index