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

Description

Preface Organization Contents – Part I Contents – Part II Contents – Part III Secure Quantum Computation with Classical Communication 1 Introduction 1.1 Results 1.2 Technical Overview 1.3 Discussion and Open Problems 1.4 Other Related Work 2 Preliminaries 2.1 Delegation of Quantum Computation 2.2 Quantum Fully-Homomorphic Encryption 2.3 Multi-party Quantum Computation 2.4 Classical Non-interactive Secure Computation 3 Generalizing the Alagic et al. Parallel Repetition Theorem 4 Composable Blind CVQC 4.1 CVQC for Quantum-Classical Circuits 4.2 Delegation of Quantum-Classical Circuits with Quantum Verifier 4.3 Making the Verifier Classical 4.4 Four-Message CVQC 5 Secure Quantum Computation 5.1 A Generic Construction of Multi-party Quantum Computation References Secure Software Leasing from Standard Assumptions 1 Introduction 1.1 Background 1.2 Our Results 1.3 Related Work 1.4 Concurrent Work 1.5 Technical Overview 1.6 Organization 2 Preliminaries 2.1 Noisy Trapdoor Claw-Free Hash Function 2.2 Secure Software Leasing 3 Two-Tier Quantum Lightning 3.1 Two-Tier Quantum Lightning 3.2 Two-Tier Quantum Lightning with Classical Verification 3.3 Two-Tier Quantum Lightning with Classical Verification from LWE 4 Relaxed Watermarking 4.1 Definition of Relaxed Watermarking 4.2 Relaxed Watermarking for PRF 5 Secure Software Leasing from Two-Tier Quantum Lightning References Post-quantum Resettably-Sound Zero Knowledge 1 Introduction 1.1 Contributions 2 Technical Overview 2.1 Defining Post-quantum Resettable Soundness 2.2 3-Message and Constant-Round-Public-Coin Protocols Can Be Made Resettably Sound 2.3 Constructing a Resettably Sound Non-Black-Box Zero-Knowledge Protocol 2.4 From Resettable Soundness to Quantum Unobfuscatability 2.5 Related Work 3 Defining Post-Quantum Resettable Soundness 3.1 Post-Quantum Resettable Soundness 4 Transforming Protocols to Achieve Quantum Resettable Soundness 4.1 Quantum Oracle Notations 4.2 Transforming 3 Message Private Coin Protocols 4.3 Deterministic-Prefix Resetting Provers 5 A Post-Quantum Resettably Sound Zero Knowledge Protocol 5.1 Protocol Construction References Secure Software Leasing Without Assumptions 1 Introduction 1.1 Summary of Contributions 1.2 Open Problems 1.3 Outline 2 Preliminaries 2.1 Notation 2.2 Quantum Authentication 3 Definitions 3.1 Quantum Copy Protection 3.2 Secure Software Leasing 3.3 Distributions for Point Functions 4 Generic Results on Definitions 4.1 Reusability of the Program 4.2 Malicious-Malicious Security and Correctness 4.3 Secure Software Leasing and Honest-Malicious Copy Protection 4.4 Secure Software Leasing of Compute-and-Compare Circuits 5 Authentication-Based Copy Protection Scheme 5.1 Construction and Correctness 5.2 Honest-Malicious Security References The Round Complexity of Quantum Zero-Knowledge 1 Introduction 2 Technical Overview 2.1 Witness-Indistinguishable Arguments 2.2 Zero Knowledge Arguments 2.3 Zero Knowledge in the Timing Model 2.4 Related Work 3 Preliminaries 3.1 Quantum Adversaries 3.2 Learning with Errors 3.3 Pseudorandom Functions 3.4 Interactive Proofs and Sigma Protocols 3.5 Statistical ZAPs for NP 3.6 Sometimes-Binding Statistically Hiding Commitments 3.7 Quantum One-Time Pad 3.8 Homomorphic Encryption 4 Witness-Indistinguishable Arguments for QMA 4.1 Definition 4.2 Statistically Zero-Knowledge Sigma Protocol 4.3 2-Round Witness-Indistinguishable Arguments for QMA References Rate-1 Quantum Fully Homomorphic Encryption 1 Introduction 1.1 Our Results 1.2 Related Work 2 Technical Overview 2.1 Malicious Circuit Privacy 2.2 Rate-1 Quantum Fully-Homomorphic Encryption 2.3 Putting Things Together 3 Preliminaries 3.1 Quantum Adversaries 3.2 Learning with Errors 3.3 Pauli Operators 3.4 Quantum One-Time Pad 4 Homomorphic Encryption 4.1 Classical Homomorphic Encryption 4.2 Quantum Homomorphic Encryption 5 Malicious Circuit Privacy for Quantum Computation 5.1 Semi-Honest Circuit Privacy 5.2 Our Bootstrapping Theorem 6 Rate-1 Quantum Fully Homomorphic Encryption 6.1 Definition 6.2 Our Construction References Unifying Presampling via Concentration Bounds 1 Introduction 1.1 Our Results 1.2 Open Problems 2 Preliminaries 2.1 Quantum Random Oracle Model 2.2 Compressed Oracle 2.3 Security Game with Classical Advice 2.4 Presampling Techniques for Random Oracles 2.5 Aaronson-Ambainis Conjecture 2.6 Concentration Bounds 3 Barriers for Leveraging Presampling Techniques 4 Unifying Presampling via Concentration Bounds 4.1 A New Characterization of Bit-Fixing 4.2 A Simpler Proof for Theorem 3 5 Applications to AI-QROM 5.1 Presampling Techniques for Quantum Random Oracles 5.2 Post-quantum Non-uniform Security of Merkle-Damg̊ard Hash Functions (MDHF) 5.3 Post-quantum Non-uniform Security of One-Way Functions (OWF) References Quantum Key-Length Extension 1 Introduction 1.1 The FX Construction 1.2 Double Encryption 1.3 Overview 2 Preliminaries 2.1 Quantum Background 3 The FX Construction 3.1 Security of FX Against Non-adaptive Attacks 3.2 Adaptive Security of FFX 4 Double Encryption 4.1 Security Result 4.2 The Hardness of List Disjointness References Relationships Between Quantum IND-CPA Notions 1 Introduction 1.1 Previous Works 1.2 Our Contribution 1.3 Organization of the Paper 2 Preliminaries 3 Definitions 3.1 Syntax of l - The Learning Queries 3.2 Syntax of c - The Challenge Queries 3.3 Instantiation of Learning and Challenge Query Models 4 Decoherence Lemmas 5 Impossible Security Notions 6 Implications 7 Separations 7.1 Separations by Quasi-Length-Preserving Encryptions 7.2 Separations by Simon's Algorithm 7.3 Separations by Shi's SetEquality Problem 7.4 Separations by Other Arguments 8 Encryption Secure in All Notions References Classical Binding for Quantum Commitments 1 Introduction 1.1 Overview of Our Results and Techniques 1.2 Related Work 2 Preliminaries and Basic Tools 2.1 Quantum Formalism 2.2 Standard Tools 3 Classically Binding Quantum Commitments 3.1 Composition and Application 4 Construction 4.1 Split Classical Binding 4.2 Split Binding Amplification 4.3 SCBQC from Any One-Way Function 5 Classical Binding Is Impossible with Statistical Hiding References Unclonable Encryption, Revisited 1 Introduction 1.1 Our Work 1.2 Technical Overview 1.3 Structure of This Paper 2 Preliminaries 2.1 Notation 2.2 Quantum Computing 2.3 Post-Quantum Digital Signatures 2.4 Functional Encryption 2.5 Quantum Copy-Protection 2.6 Copy-Protection of Point Functions 3 Private-Key and Public-Key Unclonable Encryption: Definition 3.1 Unclonable Encryption 3.2 Private-Key and Public-Key Unclonable Encryption 4 Private-Key Unclonable Encryption (PK-UE) 4.1 Private-Key Encryption with Fake-Key Property 4.2 Construction 5 Public-Key Unclonable Encryption 5.1 Construction 6 Additional Results on Unclonable Encryption 6.1 Generalized Conjugate Encryption 6.2 A Lower Bound for Conjugate Encryption 7 Construction of Copy-Protection from Unclonable Encryption References Somewhere Statistical Soundness, Post-Quantum Security, and SNARGs 1 Introduction 1.1 Multi-extractable Somewhere Statistically Binding (meSSB) Hash Families 1.2 Somewhere Statistically Sound (SSS) Interactive Arguments 1.3 SNARGs: From BatchNP to ¶ and Beyond 2 Preliminaries 2.1 Straight-Line Reductions 2.2 Probabilistically Checkable Proofs (PCP) 2.3 Hash Function Families with Local Opening 2.4 Kilian's Protocol 2.5 The BMW Heuristic 3 Somewhere Statistically Binding Hash Functions 3.1 Extractable Somewhere Statistically Binding (eSSB) Hash Functions 3.2 Multi-Extractable SSB (meSSB) Hash Functions 3.3 The BMW Protocol with meSSB Hash Families 4 Somewhere Statistically Sound Interactive Arguments 4.1 Defining SSS Arguments 4.2 SSS Implies Straight-Line Soundness 4.3 SSS Implies Post-Quantum Soundness 5 Kilian's Protocol Is Somewhere Statistically Sound 6 SNARG for Languages with Non-Signaling PCPs 6.1 BatchNP 6.2 SNARG for Languages with a Non-Signaling PCP A Proof of Theorem7 References Black-Box Impossibilities of Obtaining 2-Round Weak ZK and Strong WI from Polynomial Hardness 1 Introduction 1.1 Our Results 2 Our Techniques 2.1 BB Impossibility of 2-Round Delayed-Input Weak ZK 2.2 BB Impossibility of 2-Round Strong WI 3 Preliminaries 3.1 (, )-Approximation 3.2 2-Round Interactive Argument 3.3 Falsifiable Assumption and Black-Box Reduction 3.4 Puncturable (CCA-Secure) Public-Key Encryption 4 From 2-Round Delayed-Input Strong WI to 2-Round Special-Purpose Weak ZK 5 From Special-Purpose Weak ZK to Special-Purpose Pre-Processing ZK 6 BB Impossibility of 2-Round Special-Purpose Pre-Processing ZK 7 Obtaining Main Results References Tight Security Bounds for Micali's SNARGs 1 Introduction 1.1 Our Contributions 1.2 Concrete Improvements in Argument Size 1.3 Related Work 2 Techniques 2.1 Prior Analysis of the Micali Construction 2.2 The Prior Analysis Is Not Tight 2.3 A Tree Soundness Game 2.4 PCPs Are Secure Against Collisions and Inversions 2.5 Scoring Oracle Queries 2.6 Concluding the Proof of Theorem 1 3 Definitions 3.1 Probabilistically Checkable Proofs 3.2 Non-interactive Arguments in the Random Oracle Model 3.3 Micali's Construction 4 Reverse Soundness for a PCP 5 Tree Soundness for a PCP 6 Upper Bound on the Soundness Error of Micali 6.1 Proof of Theorem 5 References Acyclicity Programming for Sigma-Protocols 1 Introduction 1.1 Sigma-Protocol Composition 1.2 Our Contributions 1.3 Technical Overview 1.4 Potential Applications 2 Preliminaries 2.1 Sigma-protocols 2.2 Non-interactive Arguments 2.3 Graphs 3 ACP Composition 3.1 Construction 3.2 Security 3.3 Security in the Non-programmable Random Oracle Model 4 The Expressive Power of Acylicity Programs 4.1 Polynomial Equivalence with Branching Programs 4.2 Acyclicity Programs for Monotone Formulas 5 Composition for Predicates Represented by Circuits 5.1 Restrictive sampling from the Discrete Logarithm Assumption 5.2 Security in the Non-programmable Random Oracle Model 6 Concluding Remarks References Statistical ZAPs from Group-Based Assumptions 1 Introduction 1.1 Our Result 1.2 Our Techniques 1.3 A Direct Construction Using Pairings 2 Preliminaries 2.1 Hardness Assumptions 2.2 ZAP 2.3 NIZKs in the Hidden-Bits Model 2.4 Correlation-Intractable Hash Functions 3 Interactive Hidden-Bits Generating Protocol and ZAPs for NP 3.1 Definition 3.2 ZAPs for NP from Interactive Hidden-Bits Generating Protocols 3.3 Security 4 The LPWW Language LLPWW 4.1 Definition 4.2 IHBG-Friendly Statistical ZAPs for the LPWW Language LLPWW 4.3 -protocols for the LPWW Language LLPWW 5 Interactive Hidden-Bits Generating Protocols from the Explicit Hardness of DDH and an IHBG-Friendly Statistical ZAPs for LLPWW 5.1 Constructing the IHBG Protocol 5.2 Security 6 IHBG-Friendly Statistical ZAPs for LLPWW 6.1 First Construction: A Statistical ZAP for LLPWW in Pairing Groups 6.2 Second Construction: A Statistical ZAP for LLPWW in Pairing-Free Groups References Generalized Proofs of Knowledge with Fully Dynamic Setup 1 Introduction 1.1 Our Contributions 1.2 Extended Overview of Results 2 Agree-and-Prove: Definition 2.1 The Scenario 2.2 The Protocols 2.3 The Basic Security Notion 2.4 Zero Knowledge 2.5 On the Composability of the Notion 3 Application to Proof-of-Ownership of Files 3.1 Proof-of-Ownership with a Local RO 3.2 Proof-of-Ownership with a Global RO 3.3 On Including Privacy and Zero-Knowledge 4 Application to Client Authentication References Fully-Succinct Publicly Verifiable Delegation from Constant-Size Assumptions 1 Introduction 1.1 Our Results 2 Technical Overview 2.1 No-Signaling Somewhere Statistically Binding Commitments/Hashing 2.2 Pairing-Based Quasi-Arguments 2.3 From Our Quasi-Arguments to Delegation 2.4 NIZK, SNARKs and Compact NIZK References On Expected Polynomial Runtime in Cryptography 1 Introduction 1.1 Obstacles 1.2 Motivation: Reproving Zero-Knowledge of Graph 3-Colouring 1.3 Contribution 1.4 Technical Overview and Results 1.5 Related Work 1.6 Separations 1.7 Structure of the Paper 2 Preliminaries 3 Computationally Expected Polynomial Time 4 Application to Zero-Knowledge Arguments 4.1 Zero-Knowledge 4.2 Application to Graph 3-Colouring 5 Hybrid Argument and Sequential Composition 5.1 Hybrid Lemma 5.2 Sequential Zero-Knowledge References Information-Theoretically Secure MPC Against Mixed Dynamic Adversaries 1 Introduction 1.1 Our Contribution 1.2 On Modeling of Fail-Stop Corruptions 1.3 Technical Overview 1.4 Related Work 1.5 Overview of the Document 2 Preliminaries 2.1 Notation 2.2 Security Model 2.3 Definitions 3 Impossibility Results for Statistical Security 3.1 Secure Function Evaluation 3.2 Reactive MPC 4 Impossibility Results for Perfect Security 4.1 Secure Function Evaluation 4.2 Reactive MPC 5 Positive Results 5.1 SFE with Statistical Security 5.2 Fair VSS with Statistical Security 5.3 Fair VSS with Perfect Security References Round-Efficient Byzantine Agreement and Multi-party Computation with Asynchronous Fallback 1 Introduction 1.1 Motivation 1.2 Contributions 1.3 Related Work 2 Model 2.1 Communication and Adversarial Models 2.2 Cryptographic Primitives 3 Definitions 3.1 Agreement Primitives 3.2 Broadcast Primitives 3.3 Multi-party Computation 4 Round-Efficient Byzantine Agreement with Asynchronous Weak Validity 4.1 Weak Consensus with Asynchronous Weak Validity 4.2 Fixed-Round Synchronous BA with Asynchronous Weak Validity 4.3 Optimality of Synchronous BA with Asynchronous Weak Validity 5 Synchronous BA with Asynchronous Fallback 6 Round-Efficient MPC with Asynchronous Fallback 6.1 Multi-party Garbled Circuits 6.2 MPC with Linear Round Complexity in d and and Asynchronous Fallback 6.3 Protocol Description A Additional Definitions B Gradecast with Asynchronous Weak Validity C Proof of Lemma 1 D A Simpler Weak-Consensus with Asynchronous Weak Validity for ta + 2ts