Theory of Cryptography : 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part II

The three-volume set LNCS 13747, LNCS 13748 and LNCS 13749 constitutes the refereed proceedings of the 20th International Conference on Theory of Cryptography, TCC 2022, held in Chicago, IL, USA, in November 2022. The total of 60 full papers presented in this three-volume set was carefully reviewed and selected from 139 submissions. They cover topics on post-quantum cryptography; interactive proofs; quantum cryptography; secret-sharing and applications; succinct proofs; identity-based encryption and functional encryption; attribute-based encryption and functional encryption; encryption; multi-party computation; protocols: key agreement and commitments; theory: sampling and friends; lattices; anonymity, verfiability and robustness; ORAM, OT and PIR; and theory. Preface Organization Contents – Part II Encryption Forward-Secure Encryption with Fast Forwarding 1 Introduction 1.1 Basic Solutions and a New Dimension 1.2 Our Contributions 1.3 Related Work 2 Preliminaries 3 Fast-Forwarding in the Bulletin Board Model 3.1 Bulletin Board 3.2 Fast-Forwardable Stream Ciphers 3.3 Fast-Forwardable Updatable Public-Key Encryption 4 Constructing a Fast-Forwardable PRNG 4.1 The Basic Construction 4.2 Supporting an Unbounded Number of Epochs 5 Fast-Forwardable Updatable Public-Key Encryption 5.1 Update-Homomorphic UPKE 5.2 Update Graphs 5.3 A Generic Construction 6 Conclusions and Open Problems References Rate-1 Incompressible Encryption from Standard Assumptions 1 Introduction 1.1 Our Results 1.2 Comparison with Previous Work 2 Technical Overview 2.1 The Scheme of GWZ 2.2 The Big Picture 2.3 Rate-1 Incompressible Symmetric-Key Encryption 2.4 From Symmetric-Key to Public-Key Incompressible Encryption via Hash Proof Systems 2.5 Extension to CCA Security 3 Preliminaries 3.1 Decisional Diffie-Hellman Assumption 3.2 Public-Key Encryption 3.3 HILL-Entropic Encodings 4 Incompressible Symmetric-Key Encryption 4.1 Definition 4.2 Construction 5 Programmable Hash Proof Systems 5.1 Definitions 5.2 Programmable Hash Proof System from DDH 5.3 2-Smooth Hash Proof System from DDH 6 Incompressible PKE from Incompressible SKE and HPS 6.1 CCA Incompressible Encryption 6.2 Construction References Achievable CCA2 Relaxation for Homomorphic Encryption 1 Introduction 2 Preliminaries 3 A Sufficient and Achievable Relaxation of CCA2 3.1 funcCPA-Security: A Sufficient Relaxation of CCA2 3.2 Sanitized HE Schemes are funcCPA-Secure 3.3 funcCPA Security of leveled HE Schemes 3.4 Barriers on Proving funcCPA for Existing HE Schemes 4 CPA Insufficiency Against Malicious Adversaries 5 CPA Implies Privacy Against Semi-honest Adversaries 6 Conclusions A Proof of Lemma 2 References Multi-party Computation I Round-Optimal Honest-Majority MPC in Minicrypt and with Everlasting Security 1 Introduction 1.1 Our Contribution 2 Technical Overview 2.1 Main Theorem 2.2 Strong Honest-Majority MPC with Everlasting Security from OWF References Sublinear Secure Computation from New Assumptions 1 Introduction 1.1 Our Results 2 Technical Overview 2.1 Sublinear 2PC for Layered Circuits from Decomposable Batch OT 2.2 Polylogarithmic PIR from CDH 3 Sublinear Computation for loglog-Depth Circuits 3.1 Decomposable Two-Round Batch Oblivious Transfer 3.2 Instantiation Under QR +LPN, Adapted from ch5EC:BBDP22 3.3 Bounded Query Repetitions 3.4 Two-Round Batch SPIR with Correlated Queries 3.5 Sublinear Computation of loglog-Depth Circuits from corrSPIR 3.6 Extension to Layered Circuits 4 Polylogarithmic PIR from CDH 4.1 Laconic Private Set Intersection 4.2 From Laconic PSI to Half-PIR 4.3 From Polylogarithmic Half-PIR to Polylogarithmic PIR References How to Obfuscate MPC Inputs 1 Introduction 1.1 Overview of Our Results 1.2 Related Work 2 Preliminaries 2.1 Idealized Models 2.2 Obfuscation 3 Defining io2PC 3.1 Simulation Rate 3.2 Server Compromise and Offline Evaluation 3.3 Preventing Precomputation 4 io2PC for Random-Oracle-Model Obfuscation 4.1 Oblivious PRF 4.2 io2PC Protocol 5 io2PC for Generic-Group Obfuscations 5.1 Generic Groups 5.2 Personalized Generic Group 5.3 Protocol for Personalized Generic Groups 5.4 io2PC Protocol for Generic-Group Obfuscation 6 Compatible Obfuscations 6.1 Point Functions 6.2 Hyperplane Membership References Statistical Security in Two-Party Computation Revisited 1 Introduction 1.1 Our Contributions 2 Technical Overview 2.1 One-Sided Statistical Two-Party Computation Protocol 2.2 Constructing Our Ingredients from eOT 3 Preliminaries 3.1 Notations 3.2 Oblivious Transfer Protocols 3.3 Additional Preliminaries 4 Three Round Oblivious Transfer Protocols 4.1 Statistically Receiver Private Indistinguishability-Based OT 4.2 Three Round Statistically Sender Private OT 5 One-Sided Statistically Secure 2PC Against Explainable Parties 5.1 Protocol exp 5.2 Two Round Statistically Hiding Commitment 6 One-Sided Statistically Secure 2PC Against Malicious Corruptions 6.1 Conditional Disclosure of Secrets in the Preprocessing Model 6.2 Protocol mal 7 Instantiations of eOT References Protocols: Key Agreement and Commitments On the Worst-Case Inefficiency of CGKA 1 Introduction 1.1 Our Results 1.2 Compact Key Exchange 1.3 Standard Security of Continuous Group Key Agreement 1.4 Equivalence of CKE and CGKA Worst-Case Communication Complexity 1.5 Black-Box Compact Key Exchange Lower Bound 1.6 No Single Optimal CGKA Protocol Exists 1.7 Lessons Learned for Practice 2 Definitions 2.1 Continuous Group Key Agreement 2.2 Compact Key Exchange 3 From CGKA to CKE Tightly 3.1 Embedding CGKA Ciphertexts in CKE Ciphertexts 4 CKE Lower Bound from PKE 4.1 Proof Outline 4.2 Attack for (CRSGeng, Initg, Comme, Derived) 5 No Single Optimal CGKA Protocol Exists 5.1 Bad Sequences of Operations 5.2 Suboptimality of All CGKA Protocols References Adaptive Multiparty NIKE 1 Introduction 1.1 Prior Work and Motivation 1.2 Technical Challenges 1.3 Result Summary 1.4 Technical Overview 1.5 Organization 2 Preliminaries 2.1 Multiparty NIKE 2.2 Constrained PRFs 3 Enhancing Multi-party NIKE 3.1 Achieving Adversarial Correctness 3.2 Removing the CRS 3.3 Adding Shared Key Queries 3.4 Putting It All Together 4 The Equivalence of Multiparty NIKE and 1-SF-PRF 4.1 From 1-SF-PRF to Special Constrained PRF 4.2 From Special Constrained PRF to Multiparty NIKE with Setup 5 Construction of 1-SF-PRFs 5.1 Construction 5.2 Security Proof References On the Impossibility of Algebraic Vector Commitments in Pairing-Free Groups 1 Introduction 1.1 Our Results 1.2 Our Techniques 1.3 Interpretation of Our Impossibility and Further Implications 1.4 Related Work 1.5 Organization of the Paper 2 Preliminaries 2.1 Vector Commitments 2.2 Digital Signatures 3 Algebraic Vector Commitments 3.1 Generic Transformation from VCs to Signatures 3.2 -Unforgeability 4 Algebraic Signatures 4.1 Attack to Schemes with Strictly Linear Verification 4.2 Attack to Schemes with Generic Verification 5 Conclusions 5.1 Impossibility of Algebraic Vector Commitments 5.2 Impossibility of Algebraic Signatures References Four-Round Black-Box Non-malleable Schemes from One-Way Permutations 1 Introduction 1.1 Our Contributions 2 Overview of Techniques 2.1 Our NMZKC Protocol and New Commitment Schemes 2.2 4-Round Non-malleable Commitment nmc 3 Preliminaries 3.1 Commitment Schemes 3.2 Non-malleable Commitments 3.3 -Commitments 3.4 Adaptive-Input SHVZK 3.5 One-of-Two Binding Commitments 3.6 MPC Definitions 3.7 Verifiable Secret Sharing (VSS) 4 Non-malleable HVZK with Respect to Commitment 5 Our Delayed-Input MPC-in-the-Head Protocol AI 6 The Building Blocks of the 4-Round Black-Box Non-malleable Commitment Scheme 6.1 Commitment from Verifiable Secret Sharing 6.2 Commit-and-Prove 6.3 The 4-Round Non-malleable Commitment Scheme of ch11FOCS:GRRV14 7 Our 4-Round Black-Box Non-malleable Commitment Scheme 7.1 Formal Description of nmc = ((Snmc , Rnmc ), Decnmc ) 8 Comparison with Previous Non-black-box Approaches to Four-Round Non-malleable Commitments References Theory I: Sampling and Friends A Tight Computational Indistinguishability Bound for Product Distributions 1 Introduction 1.1 Related Work 1.2 Organization 2 Definitions 2.1 Notation 3 The Non-uniform Bounds and Tightness 3.1 The N-Fold Case 3.2 Tightness 4 The Uniform Variant 5 Applications 6 Open Questions References Secure Sampling with Sublinear Communication 1 Introduction 1.1 Our Work 1.2 Technical Overview 1.3 Related Work 2 Two-Party L1 Sampling 2.1 A Toy Protocol Towards Securely Realizing FL1 2.2 Secure L1 Sampling Protocol 3 Two Party L2 Sampling 3.1 A Non-private L2 Sampling Protocol with (1) Communication 3.2 Secure L2 Sampling from FHE 3.3 A Non-private Lp Sampling Protocol with (1) Communication 4 Two-Party Product Sampling 4.1 Impossibility of Sublinear Product Sampling 4.2 Product Sampling While Leaking at Most the Inner Product 5 Product Sampling in Constant Rounds 5.1 Secure Approximation of the Inner Product 5.2 Constant-Round Protocol for Product Sampling References Secure Non-interactive Simulation from Arbitrary Joint Distributions 1 Introduction 2 Overview of Our Contributions 2.1 Overview of Our Results 2.2 Overview of Our Technical Contributions 3 Preliminaries 3.1 Notation 3.2 Maximal Correlation 3.3 Fourier Analysis Basics 3.4 Markov Operator 3.5 Efron-Stein Decomposition 3.6 Imported Theorems 4 Characterization of SNIS from Arbitrary Sources 4.1 Statistical to Perfect: BSS Target 4.2 Statistical to Perfect: BES Target 5 Estimation of Rate from Arbitrary Sources 6 Characterization of BSS or BES from 2-by-2 Distributions 6.1 Statistical to Perfect 6.2 Perfect-SNIS Characterization 6.3 Proof Outline of Theorem 7 7 Additional Results and Discussions 7.1 Necessary Condition on Eigenvalues 7.2 Decidability 7.3 On Power of Non-linear Constructions 7.4 Incompleteness of String-ROT References Secure Non-interactive Reducibility is Decidable 1 Introduction 2 Technical Overview 3 Preliminaries 3.1 Generalized Fourier Transform 3.2 Secure Non-interactive Reduction 4 Decidability of SNIR 4.1 Statistical to Perfect Security 4.2 An Algorithm for the SNIR Problem 4.3 More Necessary Conditions 5 Generalized Junta Theorem 5.1 Tools: Influence, Hypercontractivity and Invariance Principle 5.2 Main Proof References Multi-party Computation II Round-Optimal Black-Box Secure Computation from Two-Round Malicious OT 1 Introduction 1.1 Our Contribution 1.2 Related Work 2 Technical Overview 2.1 Black-Box Two-Sided NISC 2.2 Black-Box Three-Round MPC 2.3 Another Perspective 3 Two-Party Inner Protocol 3.1 Definition 3.2 Construction from One-Sided NISC 4 Two-Sided Black-Box NISC 4.1 Building Blocks 4.2 Construction 4.3 Proof of Security 5 Multiparty Inner Protocol 5.1 Definition 6 Round-Optimal Black-Box MPC References Fully-Secure MPC with Minimal Trust 1 Introduction 1.1 Our Results 1.2 Open Directions 1.3 Technical Highlights and Discussion 1.4 Related Work 2 Security Model 3 Fully-Secure MPC with Single Call to Small TP 3.1 Laconic Function Evaluation (LFE) 3.2 Succinct Single-Key Functional Encryption 3.3 Fully-secure MPC from Laconic Cryptography 3.4 Fully-Secure MPC from Single-Key Succinct FE 4 Impossibilities in the Non-colluding Model 4.1 Impossibility in the Correlated Randomness Model for Protocols with Universal Output Decoder 4.2 Impossibility in the Plain Model 5 Impossibility of Fair MPC in the Colluding Model References SCALES 1 Introduction 1.1 Summary of Our Contributions 1.2 Our Main Contribution: SCALES MPC 1.3 Other Contributions in More Detail 1.4 Related Work 1.5 Technical Overview 2 Preliminaries 2.1 Garbled Circuits 2.2 Randomized Encodings 2.3 Oblivious Transfer 3 MPC with Small Clients and Larger Ephemeral Servers 4 Rerandomizable Garbling Schemes 4.1 Strong Key and Message Homomorphic Encryption 4.2 A Gap in the Proof of ch18GentryHV10 4.3 Constructing Rerandomizable Garbled Circuits 5 Incremental Decomposable Randomized Encodings 5.1 Realizing iDRE Using RGS 6 Realizing SCALES 7 Applications of RGS and iDRE 7.1 RGS for Outsourced Re-Garbling 7.2 iDRE for MPC References On Perfectly Secure Two-Party Computation for Symmetric Functionalities with Correlated Randomness 1 Introduction 1.1 Our Contribution 1.2 Our Techniques 1.3 Additional Related Work 1.4 Organization 2 Preliminaries 2.1 Notations 2.2 Security Model 3 Analyzing Symmetric Functionalities 3.1 Characterization of Four-Output Functionalities 3.2 Characterization of Boolean and Ternary-Output Functionalities 3.3 Impossibility of Embedded XOR and Embedded AND 4 A General Impossibility Result for Perfect Security 5 An Impossibility Result for Perfect Security for Four-Output Functionalities 6 Positive Results for Perfect Security 6.1 Computing Spiral Functionalities 6.2 Computing Transparent Transfer Functionalities References Lattices Public-Key Encryption from Homogeneous CLWE 1 Introduction 1.1 Our Contributions 1.2 Related Work 1.3 CLWE, SZK, and Statistical-Computational Gaps 2 Technical Overview 2.1 ``Pancake'' Encryption 2.2 ``Bimodal'' Encryption 2.3 ``Discretized'' Encryption 2.4 ``Baguette'' Encryption 2.5 SZK Membership 3 The (homogeneous) CLWE Distribution 4 Scheme 1: Pancake Encryption 4.1 Rounding into Buckets of Equal Measure 4.2 The Encryption Scheme 4.3 Correctness 4.4 Security 4.5 Precision 5 The s-hCLWE and (0,1/2)-hCLWE Distributions 5.1 The s-hCLWE Distribution 5.2 The (0,1/2)-hCLWE Distribution 5.3 A Reduction from 1/2-hCLWE to hCLWE 6 Scheme 2: Bimodal Encryption 6.1 The Encryption Scheme 6.2 Correctness 6.3 Security 7 Scheme 3: Discretized Encryption 7.1 The Parallelepiped Technique and Zq 7.2 The Encryption Scheme 7.3 Correctness 7.4 Security 7.5 Precision 8 Scheme 4: Baguette Encryption 8.1 The hCLWE() Distribution 8.2 Encryption Scheme 8.3 Correctness 8.4 Security 9 hCLWE and hCLWE() are in SZK References PPAD is as Hard as LWE and Iterated Squaring 1 Introduction 1.1 Our Results 1.2 Technical Overview 1.3 Organisation 2 Preliminaries 2.1 Search Problems, TFNP, and Reductions 2.2 Learning with Errors 2.3 Correlation-Intractable Hash Families 2.4 Interactive Proofs and the Fiat-Shamir Heuristic 3 The Outline-and-Batch Protocol 3.1 Instantiations of Outline-and-Batch 4 Non-interactive Argument for Iterated Squaring in a Trapdoor Group of Unknown Order 4.1 Iterated Squaring Modulo N 4.2 Trapdoor Groups with Unknown Order 4.3 Interactive Iterated Squaring Protocol 5 PPAD Hardness 6 Conclusion and Open Problems References Parallelizable Delegation from LWE 1 Introduction 1.1 Our Results in More Detail 1.2 Related Work 1.3 Organization 2 Techniques 2.1 SPARGs from LWE 2.2 SPARGs for Parallel Computations 2.3 Time-Independent SPARGs 3 Preliminaries 3.1 RAM Model 3.2 Universal Languages 3.3 RAM Delegation 3.4 SPARGs 4 Updatable RAM Delegation 4.1 The CJJ Delegation Scheme 4.2 Updatable Delegation with Quasilinear Overhead 4.3 Local Opening 5 SPARGs for P 6 Application to Verifiable Delay Functions References How to Sample a Discrete Gaussian (and more) from a Random Oracle 1 Introduction 1.1 Our Contributions 2 Preliminaries 3 Explainable Sampling 3.1 Explainability in Cryptographic Games 4 Explaining Sampling over Small Ranges with Respect to Discrete Gaussian Samplers 5 Sampling and Explaining Conforming Distributions 5.1 Explainable Sampling Through Heavy Element Samplers 5.2 Instantiation on Discrete Gaussians 5.3 Impossibility of Generic Sampling Without Heavy Element Samplers 6 Explaining Discrete Gaussian Samplers 6.1 Miccancio-Walter '17 References Anonymity, Verifiability and Robustness Anonymous Whistleblowing over Authenticated Channels 1 Introduction 1.1 Undetectable Secure Computation 1.2 Defining Anonymous Transfer 1.3 Impossibility Result 1.4 A Candidate Fine-Grained Anonymous Transfer 1.5 Discussions and Implications 1.6 Further Results and Open Questions 2 Preliminaries 2.1 Notations 2.2 Distribution Testing 3 Anonymous Transfer 3.1 Network Model and Non-participating Parties 3.2 The Model 3.3 Fine-Grained Anonymous Transfer 3.4 Trivial Anonymous Transfers 3.5 Reductions Among AT Protocols 4 Impossibility of Anonymous Transfer 4.1 The Attacker 4.2 Putting the Pieces Together 4.3 Extensions and Limitations 5 Fine-Grained AT from Ideal Obfuscation 5.1 Security Analysis 5.2 Final Result References Poly Onions: Achieving Anonymity in the Presence of Churn 1 Introduction 2 Modeling the problem 3 Onion Encryption for Churn 3.1 I/O syntax 3.2 Correctness 3.3 Security 4 Our Poly Onion Encryption Scheme 4.1 Overview of Poly Onion Encryption 4.2 Analysis of Poly Onion Encrypion 5 Anonymity in the Setting with Churn 5.1 Definitions of Anonymity 5.2 Simulatable Onion Routing Protocols 5.3 From Single-Run to Multi-run Anonymity 6 Multi-run Strongly Anonymous Onion Routing with Churn 6.1 Insufficiencies of Previous Solutions 6.2 Poly p is Multi-run Anonymous in the Presence of Churn References The Price of Verifiability: Lower Bounds for Verifiable Random Functions 1 Introduction 1.1 High-Level Technical Overview 2 Detailed Technical Overview 2.1 First Result: Connecting the Proof Size with the Evaluation Degree 2.2 Second Result: Security of Univariate Polynomial-Degree VRFs Requires Complex Assumptions 2.3 Third Result: Security of Low-Degree VRFs Requires Complex Assumptions 2.4 Organization of This Work 3 Preliminaries 3.1 Notation 3.2 Mathematical Foundations 3.3 Cryptographic Groups 3.4 Verifiable Unpredictable Functions 3.5 Reductions 4 Proof Size 4.1 Classes of VUFs over Pairing-Friendly Groups 4.2 From Consecutively Verifiable Pairing-Based VUFs to Rational VUFs 5 Algebraic Attacks on Rational VUFs 6 Generic Attacks on Parametrized Rational VUFs References Bet-or-Pass: Adversarially Robust Bloom Filters 1 Introduction 1.1 Our Contributions 1.2 Related Work 1.3 Open Problems 2 Model and Problem Definition 2.1 Prediction and Pseudorandomness 3 Defining Robust Bloom Filters 3.1 Background 3.2 Robustness in All Shapes and Forms 4 Relationships Between the Various Notions of Robustness 4.1 Implications 4.2 Separations 4.3 Conclusions 5 Computational Assumptions and One-Way Functions 5.1 Constructions of BP Resilient Filters Using One-Way Functions References Author Index