Theory of cryptography : 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings

Preface
Organization
Contents – Part II
Dory: Efficient, Transparent Arguments for Generalised Inner Products and Polynomial Commitments
	1 Introduction
		1.1 Limitations of Prior Approaches
		1.2 Review of LCC-DLOG Techniques
		1.3 Core Techniques Enabling a Logarithmic Verifier in Dory
	2 Preliminaries
		2.1 Notation
		2.2 Computationally Hard Problems in Type III Pairings
		2.3 Succinct Interactive Arguments of Knowledge
		2.4 Commitments
		2.5 Polynomial Commitments and Evaluation from Vector-Matrix-Vector Products
	3 An Inner-Product Argument with a Logarithmic Verifier
		3.1 Scalar-Product
		3.2 Dory-Reduce
		3.3 Dory-Innerproduct
		3.4 Batching Inner Products
	4 Inner Products with Public Vectors of Scalars
		4.1 General Reduction with O (n) cost
		4.2 Extending Dory-Reduce
		4.3 Extending Dory-Innerproduct
		4.4 Extending Batch-Innerproduct
	5 Vector-Matrix-Vector Products
		5.1 Batching
		5.2 Concrete Costs
	6 Dory-PC
		6.1 Concrete Costs of Dory-PC-RE
		6.2 Batching
	7 Implementation
	References
On Communication-Efficient Asynchronous MPC with Adaptive Security
	1 Introduction
		1.1 Communication Complexity of Asynchronous MPC Protocols
		1.2 Contributions
	2 Preliminaries
		2.1 Communication and Adversary Model
		2.2 Zero-Knowledge Proofs of Knowledge
		2.3 Universally Composable Commitments
		2.4 Threshold Homomorphic Encryption
	3 Subprotocols
		3.1 Agreement Protocols
		3.2 Decryption Protocols
		3.3 Multiplication
		3.4 Triple Generation
	4 Asynchronous Adaptively Secure MPC Protocol
		4.1 Ideal Functionality
		4.2 Informal Explanation of the Protocol
		4.3 Main Theorem
	5 Near-Linear MPC in the Atomic Send Model
		5.1 Model
		5.2 VACS
		5.3 Triple Generation
		5.4 Main Theorem for the Atomic Send Model
	A  Details of the Subprotocols
		A.1  Decryption protocols
		A.2  Multiplication
	B  Protocol
	References
Efficient Perfectly Secure Computation with Optimal Resilience
	1 Introduction
		1.1 Our Results
		1.2 Related Work
		1.3 Open Problems
	2 Technical Overview
		2.1 Overview of the BGW Protocol
		2.2 Our Protocol
		2.3 Extensions
		2.4 Organization
	3 Preliminaries
		3.1 Definitions of Perfect Security in the Presence of Malicious Adversaries
		3.2 Robust Secret Sharing
		3.3 Bivariate Polynomial
	4 Weak Verifiable Secret Sharing and Extensions
		4.1 Verifying Shares of a (q,t)-Bivariate Polynomial
		4.2 Weak Verifiable Secret Sharing
		4.3 Evaluation with the Help of the Dealer
		4.4 Strong Verifiable Secret Sharing
		4.5 Extending Univariate Sharing to Bivariate Sharing with a Dealer
	5 Multiplication with a Constant Number of VSSs and WSSs
		5.1 Functionality – Multiplication with a Dealer
		5.2 The Protocol
	6 Extension: Arbitrary Gates with Multiplicative Depth-1
	References
On Communication Models and Best-Achievable Security in Two-Round MPC
	1 Introduction
		1.1 Our Results in Detail
		1.2 Related Work
	2 Technical Overview
		2.1 Lower Bounds in the BC only Model
		2.2 BC+P2P Model
		2.3 BC+PKI Model
	3 Preliminaries
		3.1 Oblivious Transfer (OT)
		3.2 Multi-CRS Non-interactive Zero Knowledge (m-NIZK)
	4 Broadcast Model
		4.1 Lower Bound for t=1
		4.2 Impossibility of Two-Message mR-OT in the Plain Model
	5 BC+P2P Model
		5.1 Impossibility Result for Identifiable Result
		5.2 Fail-Stop Guaranteed Output Delivery
	6 BC+PKI Model: Guaranteed Output Delivery
	References
Generalized Pseudorandom Secret Sharing and Efficient Straggler-Resilient Secure Computation
	1 Introduction
		1.1 Our Contributions
		1.2 Related Work
	2 Preliminaries
		2.1 Threshold Secret Sharing
		2.2 Computation Model: Layered Straight-Line Programs
	3 Generalized Pseudorandom Secret Sharing
		3.1 Overview
		3.2 The Gilboa-Ishai Framework
		3.3 Technical Tool: Covering Designs
		3.4 Generalized PRSS for Degree-d Polynomials
		3.5 Double Shamir Sharing
		3.6 Beyond Double Sharing
	4 Constructions for Semi-honest Security
		4.1 Baseline Protocol (with =1)
		4.2 Straggler Resilience
		4.3 Reducing Communication and Computation
	5 From Semi-honest to Malicious Security
		5.1 Privacy in the Presence of Malicious Adversaries
		5.2 Verifying Correctness of the Computation
		5.3 Putting It All Together - The Main Protocol
	References
Blockchains Enable Non-interactive MPC
	1 Introduction
		1.1 Our Results
		1.2 Technical Overview
		1.3 Related Work
	2 Preliminaries – CSaRs
	3 Our Non-interactive MPC Construction
		3.1 Construction Overview
	4 Optimizations
	5 Optimizing Communication and State Complexity in MPC
		5.1 Step. 1: MPC with Semi-malicious Security
		5.2 Step. 2: MPC with Fully Malicious Security
		5.3 Properties of the Resulting MPC Construction
	6 Guaranteed Output Delivery
	References
Multi-party PSM, Revisited:
	1 Introduction
		1.1 Our Contributions
		1.2 Proof Overview
		1.3 Related Works
	2 Preliminaries
		2.1 Tensor
		2.2 Private Simultaneous Messages
		2.3 Randomized Encoding
	3 New Multi-party PSM Protocols
		3.1 A Framework for Multi-party PSM
		3.2 The Induced PSM Protocol
		3.3 When k is Small
		3.4 When k+1 is a Prime Power
	4 Unbalanced 2-Party PSM Protocols
		4.1 A Framework for 2-Party PSM
		4.2 The Induced PSM Protocol
		4.3 When  Has a Small Denominator
	5 Open Problems
	A  Proof of Eq. (9) and (10)
	B  Auxiliary PSM Protocols for "426830A x1 …xk, Y "526930B  + s
		B.1  The Multi-party Variant
		B.2  The 2-party Variant
	References
Multi-Party Functional Encryption
	1 Introduction
		1.1 Unifying the View: Multi-Party Functional Encryption
		1.2 Comparison with Prior Work
		1.3 New Constructions
		1.4 Technical Overview
		1.5 Predicting New and Useful Primitives via MPFE
	2 Multi-Party Functional Encryption
	3 Multi-Authority ABE IPFE for LSSS Access Structures
		3.1 Specializing the MPFE Syntax
		3.2 Construction
		3.3 Correctness and Security
	4 Function-Hiding DDFE for Inner Products
		4.1 Specializing the MPFE Syntax
		4.2 Construction of Function-Hiding IP-MCFE
		4.3 Construction of Function-Hiding IP-DDFE
	References
Succinct LWE Sampling, Random Polynomials, and Obfuscation
	1 Introduction
		1.1 Our Contributions
		1.2 Technical Overview
		1.3 Discussion
	2 Preliminaries
		2.1 Notations
		2.2 Learning with Errors
		2.3 Lattice Tools
		2.4 Homomorphic Operations
		2.5 Succinct Randomized Encodings
	3 Succinct LWE Sampler: Definition and Amplification
		3.1 Definition and Discussion
		3.2 Weak Succinct LWE Samplers
		3.3 Amplification
	4 Candidate Succinct LWE Sampler
		4.1 A Basic Framework
		4.2 Correctness, Succinctness, and LWE with Respect to A*
		4.3 Instantiating the Parameters
		4.4 Alternate Candidate Construction
		4.5 Cryptanalysis
		4.6 Cryptanalytic Challenges
	5 Our Succinct Randomized Encoding Construction
		5.1 Security
	References
ABE for DFA from LWE Against Bounded Collusions, Revisited*-8pt
	1 Introduction
		1.1 Our Contributions
		1.2 Technical Overview I: T1/2
		1.3 Technical Overview II: ABE for DFA
		1.4 Prior Works
		1.5 Discussion
	2 Preliminaries
		2.1 Attribute-Based Encryption
		2.2 Lattices Background
	3 Trapdoor Sampling with T1/2 and a Computational Lemma
		3.1 LWE Implies T1/2-LWE
		3.2 Trapdoor Sampling with T1/2
	4 ABE for DFA Against Bounded Collusions
		4.1 Our Scheme
		4.2  sk-Selective Security
	5 Candidate ABE for DFA Against Unbounded Collusions
	References
Distributed Merkle's Puzzles
	1 Introduction
		1.1 Distributed Key Agreement Based on Symmetric-Key Primitives
		1.2 Our Results
		1.3 Overview of the Protocol and Its Analysis
		1.4 Previous Work
	2 Preliminaries
		2.1 Graphs
		2.2 Random Functions and Encryption
	3 Distributed Key Agreement Protocols Based on Random Oracles
	4 The Setup Protocol
		4.1 Correctness
		4.2 Query and Communication Complexity
		4.3 Connectivity
		4.4 Security
	5 The Distributed Key Agreement Protocol
		5.1 Security Analysis
		5.2 Main Theorem
	6 Optimality of the Distributed Key Agreement Protocol
	7 Extensions
		7.1 The Semi-honest Model
		7.2 Communication-Security Tradeoff
	References
Continuously Non-malleable Secret Sharing: Joint Tampering, Plain Model and Capacity
	1 Introduction
		1.1 Non-malleability Against Joint Tampering
		1.2 Our Results
		1.3 Overview of Techniques
		1.4 Related Work
	2 Standard Definitions
		2.1 Non-interactive Commitment Schemes
		2.2 Symmetric Encryption
		2.3 Information Dispersal
	3 Secret Sharing Schemes
		3.1 Tampering and Leakage Model
		3.2 Related Notions
	4 Rate-Zero Continuously Non-malleable Secret Sharing
		4.1 Induction Basis
		4.2 Inductive Step
		4.3 Putting It Together
	5 Rate Compilers and Capacity Upper Bounds
		5.1 Capacity Upper Bounds
		5.2 Rate Compiler (Plain Model)
	6 Instantiations
		6.1 Leakage-Resilient p-time Non-malleable Code
		6.2 Leakage-Resilient Continuously Non-malleable Secret Sharing
		6.3 Breaking the Rate-One Barrier
	References
Disappearing Cryptography in the Bounded Storage Model
	1 Introduction
		1.1 Motivating Examples
		1.2 Our Results
		1.3 Defining Obfuscation in the Bounded Storage Model
		1.4 Applications
		1.5 Constructing Online Obfuscation
		1.6 Related Work, Discussion, and Future Directions
	2 Preliminaries
	3 Defining Obfuscation in the Bounded Storage Model
	4 Public Key Encryption with Disappearing Ciphertext Security
		4.1 Definition
		4.2 Lossy Function
		4.3 Construction
		4.4 Proof of Security
	5 Disappearing Signature Scheme
		5.1 Definition
		5.2 Prefix Puncturable Signature
		5.3 Construction
	6 Functional Encryption
		6.1 Definition
		6.2 Construction
	7 Candidate Construction 1
		7.1 Matrix Branching Programs
		7.2 The Basic Framework
		7.3 Instantiating Convert
	8 Candidate Construction 2
	References
Trojan-Resilience Without Cryptography
	1 Hardware Trojans
		1.1 Detecting Digital Hardware Trojans
	2 Definition and Security of Simple Schemes
		2.1 Test and Deployment
		2.2 Completeness
		2.3 Security of Simple Schemes
		2.4 Lower Bounds
		2.5 Efficiency of Lower Bound vs. Constructions
		2.6 Our Results and Conjectures
		2.7 Comparison with VC and MPC
		2.8 Stateless Trojans
		2.9 History-Independent Trojans
		2.10 Proof Outline
	3 Conjectured Security of 2-Redundant Schemes
		3.1 A 2-Redundant Scheme 2
	4 A Scheme for History-Independent Trojans
		4.1 Notation
		4.2 Security of 2
		4.3 A Technical Lemma
	5 A 12-Redundant Scheme 12
		5.1 The 12 Scheme
		5.2 Security of 12
		5.3 Reapplying the Hybrid Argument
	6 Outlook and Open Problems
	References
On Derandomizing Yao's Weak-to-Strong OWF Construction
	1 Introduction
		1.1 On Security-Preserving Amplification of Weak OWFs
		1.2 Our Contribution
		1.3 Relation to Correlated-Product and Correlated-Input Security
		1.4 Related Works
		1.5 Technical Overview
		1.6 Relation to Threshold Secret Sharing
	2 Preliminaries
		2.1 Entropy Toolbox
	3 Main Results
		3.1 Black-Box Constructions and Reductions
		3.2 Theorems
	4 Oracle Distributions
	5 Proof of Theorem 14
		5.1 RA is Not a Successful Weak OWF Inverter
		5.2 A is a Successful Strong OWF Inverter
	6 Constructions with Post-processing
	A Additional Lemmas and Proofs
	B  Proof of Theorem 18 (F is a weak OWF)
	References
Simple Constructions from (Almost) Regular One-Way Functions
	1 Introduction
		1.1 Our Contribution
		1.2 Proof Overview
		1.3 Additional Related Work
		1.4 Paper Organisation
	2 Preliminaries
		2.1 Notations
		2.2 One-Way Functions
		2.3 Pseudorandom Generators
		2.4 Universal One Way Hash Function
		2.5 2-Universal Hash Families
		2.6 Useful Inequalities
	3 The PRG Construction
		3.1 Proving Lemma 3.2
	4 The UOWHF Construction
		4.1 Proving Claim 4.3
		4.2 Proving Lemma 4.2
	A  Missing Proofs
		A.1  Pseudorandom Generator
		A.2  Universal Hash Families
	References
On Treewidth, Separators and Yao's Garbling
	1 Introduction
		1.1 Our Results
		1.2 Technical Overview
		1.3 Related Work
	2 Preliminaries
		2.1 Notation
		2.2 Garbling
		2.3 Pebble Games
		2.4 Graph Theory
	3 Hybrid Argument and the BGR Pebble Game
		3.1 Pebble Configurations and Hybrids
		3.2 Indistinguishability of Neighbouring Hybrids
		3.3 Adaptive Indistinguishability via Piecewise Guessing
	4 BGR Pebbling Strategy
		4.1 BGR Pebbling via Separators
		4.2 Optimised Piecewise Guessing
	5 Conclusion and Open Problems
	References
Oblivious Transfer from Trapdoor Permutations in Minimal Rounds
	1 Introduction
		1.1 Our Results
	2 Technical Overview
		2.1 Related Work
		2.2 Organization of the Paper
	3 Background
		3.1 Injective TDFs and TDPs
		3.2 Commit-and-Open Protocols
		3.3 Oblivious Transfer and 2-PC
	4 Dual Witness Encryption (DWE)
		4.1 DWE for the Languages of DH and QR Tuples
	5 Black-Box DWE for Trapdoor Permutations
		5.1 Our Constructions
	6 Almost Secure OT Protocol
	7 Secure OT from Almost Secure OT
	8 Black-Box Round Optimal 2PC
	References
The Cost of Adaptivity in Security Games on Graphs
	1 Introduction
		1.1 Our Results
		1.2 Related Work
	2 Technical Overview
		2.1 Our Approach
		2.2 Step I: Combinatorial Upper Bounds
		2.3 Step II: From Combinatorial Upper Bounds to Cryptographic Lower Bounds
	3 Preliminaries
		3.1 Graph Theory
		3.2 Graph Pebbling
	4 The Builder-Pebbler Game
		4.1 Player Strategies
	5 Combinatorial Upper Bounds
		5.1 Unrestricted Pebblers
	6 Cryptographic Lower Bound I: Generalised Selective Decryption
		6.1 Lower Bounds for GSD
	7 Cryptographic Lower Bound II: Constrained PRF
		7.1 Definition, Construction and Security Assumption
		7.2 Lower Bound for the GGM CPRF
	References
Concurrent Composition of Differential Privacy
	1 Introduction
		1.1 Differential Privacy
		1.2 Composition of Differential Privacy
		1.3 Interactive Differential Privacy
		1.4 Our Contributions
	2 Definitions and Basic Properties
	3 Concurrent Composition for Pure Interactive Differential Privacy
	4 Concurrent Composition for Approximate Interactive Differential Privacy
	5 Characterization of ConComp for Pure Interactive Differential Privacy
	6 Experimental Results
	References
Direct Product Hardness Amplification
	1 Introduction
		1.1 Security Amplification
		1.2 Hardness of the Direct Product of Two Games
		1.3 Contributions and Outline
		1.4 Related Work
	2 Preliminaries
	3 The Amplification Theorem
		3.1 The Setting
		3.2 Amplification for Monotonic
		3.3 Amplification for Monotonic and Concave
	4 The Square Is Not (Always) Optimal
	5 Applying the Amplification Theorem
	6 Conclusions and Open Problems
	A  Proofs
	References
On the (Ir)Replaceability of Global Setups, or How (Not) to Use a Global Ledger*-10pt
	1 Introduction
	2 Preliminaries: Global Subroutines in UC
		2.1 UC Basics
		2.2 UC with Global Subroutines
	3 Replacement Theorems for a Global Subroutine
		3.1 Common Preconditions of Our Theorems
		3.2 Warm-Up: Replacing Real-World Global Setups
		3.3 Full Replacement of the Global Subroutine
		3.4 Case Study: Comparable Constructions and Random Oracles
	4 Generalization to Many Global Subroutines
	References
BKW Meets Fourier New Algorithms for LPN with Sparse Parities
	1 Introduction
		1.1 Our Results
		1.2 Technical Overview
		1.3 Related Work
	2 Preliminaries
		2.1 Notations
		2.2 Fourier Analysis
	3 Constant Noise Setting
		3.1 BKWR
		3.2 Learning Secret Coordinates
		3.3 Combining the Results
		3.4 Parameter Settings
	4 Low Noise Setting
		4.1 Sample Partition
		4.2 Learning Secret Coordinates
		4.3 Combining the Results
		4.4 Parameter Settings
	5 Learning Other Classes of Functions
	A  Appendix
		A.1  Probability Bounds
		A.2  Learning Parities
		A.3  Miscellaneous
		A.4  Proof of Lemma 3.1
		A.5  Proof of Theorem 3.2
		A.6  Proof of Lemma 3.3
		A.7  Proof of Lemma 4.1
		A.8  Proof of Theorem 4.2
		A.9  Proof of Lemma 4.3
	References
Computational Robust (Fuzzy) Extractors for CRS-Dependent Sources with Minimal Min-entropy
	1 Introduction
	2 Preliminaries
	3 CRS-Model Robust Extractor: Definitions
	4 A New Lower Bound for IT-Secure Robust Extractors
	5 Computational Robust Extractors
	6 Extension to Robust Fuzzy Extractors
	7 Conclusion and Open Problems
	References
Polynomial-Time Targeted Attacks on Coin Tossing for Any Number of Corruptions
	1 Introduction
		1.1 Technical Overview
		1.2 Further Related Work
	2 Preliminaries
		2.1 Useful Facts
	3 Attacking Protocols with Any Message Length
	4 Optimal Attacks for Uniform Binary Messages
	References
Author Index