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

Preface
Organization
Contents – Part III
Anonymity, Surveillance and Tampering
Lower Bounds on Anonymous Whistleblowing
	1 Introduction
	2 Technical Overview
	3 Preliminaries and Definitions
		3.1 Anonymous Transfer
	4 Identifying Covert Cheaters
		4.1 Covert Cheating Game
		4.2 Attack 1: Free-Lunch Attack with Weak Distinguishing Guarantees
		4.3 Attack 2.1: A Strong Attack Given Direct Access to States
		4.4 Attack 2.2: A Strong Attack Given Sampling Access to States
	5 Lower Bounds on Anonymous Transfer
		5.1 Reducing Anonymous Transfer to Covert Cheating Games
		5.2 Lower Bounds on Anonymous Transfer
		5.3 Extension to Anonymous Transfer with Many Parties
	References
Anonymous Permutation Routing
	1 Introduction
		1.1 Technical Challenges
		1.2 Overview of Our Results
	2 Previous Work
		2.1 Permutation Routing
		2.2 PIR
		2.3 Comparison with Other Results in NIAR Model
	3 Preliminaries
		3.1 Beneš Network
		3.2 Non-Interactive Anonymous Routing (NIAR)
		3.3 Emulating Oblivious Routing in a Virtual Routing Network
	4 Our Protocol
		4.1 Overview of Our Solution
		4.2 Analysis of Our Protocol
	5 Correctness and Security
		5.1 Probabilities in a Beneš Network
		5.2 Permutation Routing Problem
		5.3 Security
	References
Non-Interactive Anonymous Router with Quasi-Linear Router Computation
	1 Introduction
		1.1 Main Result
		1.2 Additional Results
		1.3 Related Work and Open Questions
	2 Technical Roadmap
		2.1 Single Selective Challenge and Static Corruptions
		2.2 Removing the Selective Challenge Restriction
		2.3 Achieving Security for Adaptive Corruptions
		2.4 SSU Signature Construction
	3 Definitions for NIAR
		3.1 Syntax
		3.2 NIAR Full Security
	4 Preliminaries
		4.1 Notations
	5 Somewhere Statistically Unforgeable (SSU) Signatures
		5.1 Definition
		5.2 SSU Signatures: Informal Construction
	6 NIAR for a Static and All-Receiver-Corrupting Adversary
		6.1 Construction
		6.2 Efficiency Analysis
		6.3 Static Security Theorem
	References
Multi-instance Randomness Extraction and Security Against Bounded-Storage Mass Surveillance
	1 Introduction
		1.1 Our Results
		1.2 Concurrent Work
		1.3 Our Techniques: Multi-instance Randomness Extraction
		1.4 Our Techniques: Multi-incompressible Encryption
	2 Preliminaries
	3 Multi-instance Randomness Extraction
		3.1 Defining Multi-instance Extraction
		3.2 Hinting Extractors
		3.3 Hinting-Extractors Are Multi-instance-Extracting
	4 Multi-user Security for Incompressible Encryption
	5 Symmetric Key Incompressible Encryption
		5.1 Low Rate Incompressible SKE
		5.2 Rate-1 Incompressible SKE
		5.3 Dealing with Multiple Messages per User
	6 Public Key Incompressible Encryption
		6.1 Low Rate Incompressible PKE
		6.2 Rate-1 Incompressible PKE
	References
Efficiently Testable Circuits Without Conductivity
	1 Introduction
	2 ETC Compilers and Their Security
		2.1 The Construction from ch5ETC Using Conductivity
		2.2 Our Construction Without Conductivity
		2.3 More Related Work
	3 Preliminaries
		3.1 Notation for Circuits
		3.2 Tampering Model
	4 Gate Covering Sets
	5 Information Loss in Gate-Covered Circuits
		5.1 Routing the Information Loss in Gate-Covered Circuits
	6 Minimizing the Number of External Wires
		6.1 Construction of One Layer Compression
		6.2 Composing the Layers
		6.3 Information Losing Tuples
		6.4 Algebraic Values on the Wires
		6.5 Information Loss Survival for Sd
	7 The Compiler
	8 Conclusions and Open Problems
	References
Immunizing Backdoored PRGs
	1 Introduction
		1.1 Our Questions: Immunization Countermeasures
		1.2 Related Immunization Settings
		1.3 Our Results for 2-Immunizers
		1.4 Further Related Work
	2 Definitions
		2.1 Pseudorandom Generators
		2.2 2-Immunizers
	3 Counterexamples for Simple 2-Immunizers
		3.1 Public Key Encryption
		3.2 Strong 2-Immunizers
		3.3 Weak 2-Immunizers
	4 Positive Result in Random Oracle Model
		4.1 Random Oracle Model Definitions
		4.2 Random Oracle is a 2-Immunizer
	5 Black Box Separation (with Limitations)
		5.1 Proof Sketch for Theorem 12
	References
Lower Bounds
Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments
	1 Introduction
		1.1 Proof Overview
		1.2 Discussions and Open Problems
	2 Preliminary
		2.1 Notations
		2.2 Key-Agreement Protocols
		2.3 Basic Information Theory
	3 Communication Complexity of Key-Agreement Protocols
		3.1 Description of the Attacker
		3.2 Success Probability of the Attacker
		3.3 Efficiency of the Attacker
	References
Searching for ELFs in the Cryptographic Forest
	1 Introduction
		1.1 Our Contributions
		1.2 Our Techniques
		1.3 Related Work
	2 Preliminaries
		2.1 Lossy Functions
		2.2 Oraclecrypt
	3 On the Impossibility of Building (E)LFs in Oraclecrypt
		3.1 Introducing the Oracles
		3.2 Approximating the Set of Heavy Queries
		3.3 Distinguishing Lossiness from Injectivity
		3.4 Fixing an Oracle
	4 On the Impossibility of Building Key Agreement Protocols from (Extremely) Lossy Functions
		4.1 Lossy Function Oracle
		4.2 Key Exchange
		4.3 ELFs
	5 Relationship of Lossy Functions to Statistical Zero-Knowledge
	References
On Time-Space Lower Bounds for Finding Short Collisions in Sponge Hash Functions
	1 Introduction
		1.1 Our Results
		1.2 Technical Overview
		1.3 Discussions and Open Problems
	2 Preliminaries
		2.1 Notations
		2.2 Random Permutation Model
		2.3 Sponge Hash Functions
		2.4 Definitions
		2.5 Relevant Results
	3 Improved Bound for B=1 (Optimal When ST2C)
		3.1 Proof of Lemma 1
	4 A Simpler Proof for B=2
	5 Limitations for the Multi-instance Model
		5.1 Attacks for Sponge in Multi-instance Model When B=1
		5.2 Attacks for Sponge in Multi-instance Model When B=2
		5.3 Attacks for Sponge in Multi-instance Model When B3
	References
On the Cost of Post-compromise Security in Concurrent Continuous Group-Key Agreement
	1 Introduction
		1.1 Our Bounds
		1.2 Our Proofs
		1.3 Overcoming Lower Bounds
		1.4 Related Work
	2 Preliminaries
		2.1 Definitions and Results from Combinatorics
		2.2 Continuous Group-Key Agreement
	3 Lower Bounds in the Combinatorial Model
		3.1 The Combinatorial Model
		3.2 Lower Bound in the Combinatorial Model
	4 Lower Bounds in the Symbolic Model
		4.1 The Symbolic Model
	5 Upper Bound on the Update Cost
	References
Generic-Group Lower Bounds via Reductions Between Geometric-Search Problems: With and Without Preprocessing
	1 Introduction
		1.1 Our Contributions
	2 Preliminaries
		2.1 Notation
		2.2 Generic-Group Model
		2.3 Search-by-Hypersurface Problem
	3 From Generic Group Problems to Geometric Search-Problems
		3.1 From GGM to Geometric Search-Problems
		3.2 Extension to the Bit-Fixing Generic-Group Model
		3.3 Extension to the GGM for Bilinear Groups
	4 Reductions Between Geometric Search-Problems
		4.1 Reductions between geometric search-problems in the GGM and AIGGM
		4.2 Reductions Between Geometric Search-Problems Corresponding to the Bilinear GGM
	References
IOPs and Succinctness
Holographic SNARGs for P and Batch-NP from (Polynomially Hard) Learning with Errors
	1 Introduction
		1.1 Our Results
		1.2 Related Work
	2 Technical Overviews
		2.1 Holographic SNARG for P
		2.2 Holographic SNARG for Batch-NP
	3 Preliminaries
		3.1 Hash Functions
		3.2 Correlation-Intractable Hash Functions
		3.3 Somewhere Extractable Hash Functions
		3.4 SNARGs for P (a.k.a. Non-Interactive TM Delegations)
		3.5 SNARGs for Batch-NP (a.k.a Non-Interactive BARGs)
		3.6 Holographic SNARGs for P and Batch-NP
	4 Somewhere-Sound Holographic SNARG for SE Hash
	5 Holographic SNARG for Tree-Hash
	6 Holographic SNARG for Batch-NP
	7 Holographic SNARG for P
	8 Application: Public-Coin Three-Round Zero-Knowledge
	References
Chainable Functional Commitments for Unbounded-Depth Circuits
	1 Introduction
		1.1 Our Contribution
		1.2 Related and Concurrent Work
	2 A Technical Overview of Our Work
		2.1 (C)FC for Circuits from CFCs for Quadratic Functions
		2.2 A Framework for CFCs for Quadratic Functions
	3 Preliminaries
		3.1 Functional Commitments
		3.2 Additional Properties of FCs
	4 Chainable Functional Commitments
	5 FC for Circuits from CFC for Quadratic Polynomials
	6 Paring-Based CFC for Quadratic Functions
		6.1 Preliminaries on Bilinear Groups and Assumption
		6.2 Our CFC Construction
		6.3 Resulting Instantiations of FC for Circuits
		6.4 Proof of Security
	7 Lattice-Based CFC for Quadratic Functions
		7.1 Lattice Preliminaries
		7.2 Hardness Assumptions
		7.3 Construction
		7.4 Resulting Instantiations of FC for Circuits
		7.5 Proof of Security
	References
Multilinear Schwartz-Zippel Mod N and Lattice-Based Succinct Arguments
	1 Introduction
		1.1 Bulletproofs for Short Pre-images
		1.2 Related Work
	2 Technical Overview
		2.1 Bulletproofs for Short Pre-Images and Almost Special Soundness
	3 Main Theorem Statement (LCSZ)
	4 Inverse LCSZ
	5 Definitions and Notations
		5.1 Integer Polynomials
		5.2 Groups of Unknown Order
		5.3 Knowledge Soundness
	6 Almost-Special-Soundness
	7 Argument of Knowledge of ``short\" Rational Opening
		7.1 Interactive Protocol for Short Rational Openings
		7.2 Almost Special Soundness Analysis
	References
Generalized Special-Sound Interactive Proofs and Their Knowledge Soundness
	1 Introduction
	2 Preliminaries
		2.1 Interactive Proofs
		2.2 Geometric Distribution
	3 A Generalized Notion of Special-Soundness for Sigma-Protocols
	4
	5 Examples
	6 Knowledge Extraction for Multi-round Interactive Proofs
	7 Analysis of the FRI-Protocol
		7.1 Preliminaries on Reed-Solomon Codes
		7.2 FRI-Protocol
		7.3 Analyzing the FRI-Protocol
		7.4 Additional Folding Iterations
	References
From Polynomial IOP and Commitments to Non-malleable zkSNARKs
	1 Introduction
		1.1 Our Work
		1.2 Our Techniques
		1.3 Related Work
		1.4 Open Problems
	2 Preliminaries
	3 Policy-Based Simulation-Extractable NIZKs
		3.1 Policy-Based Simulation Extractability
	4 Simulation Extractability of KZG in AGM
	5 Simulation-Extractable Universal zkSNARKs
	References
How to Compile Polynomial IOP into Simulation-Extractable SNARKs: A Modular Approach
	1 Introduction
		1.1 Our Contribution
		1.2 Technical Overview
		1.3 Related Work
	2 Preliminaries
		2.1 Relations
		2.2 Polynomial Interactive Oracle Proofs
		2.3 Non-interactive Argument and Simulation-Extractability in ROM
		2.4 Simulation-Extractability of Fiat-Shamir Non-interactive Arguments
		2.5 Polynomial Commitment Scheme
	3 Analysis of PIOP Compiled into Non-interactive Argument
		3.1 Trapdoor-Less Non-interactive Zero Knowledge of Compiled NARG
		3.2 Weak Unique Response of Compiled NARG
	References
Author Index