Advances in Cryptology – CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part III (Lecture Notes in Computer Science, 12827)

✍ Scribed by Tal Malkin (editor), Chris Peikert (editor)

• Publisher: Springer
• Year: 2021
• Tongue: English
• Leaves: 820
• Edition: 1st ed. 2021
• Category: Library

✦ Synopsis

The four-volume set, LNCS 12825, LNCS 12826, LNCS 12827, and LNCS 12828, constitutes the refereed proceedings of the 41st Annual International Cryptology Conference, CRYPTO 2021. Crypto has traditionally been held at UCSB every year, but due to the COVID-19 pandemic it was an online event in 2021.

The 103 full papers presented in the proceedings were carefully reviewed and selected from a total of 426 submissions. The papers are organized in the following topical sections:

Part I: Award Papers; Signatures; Quantum Cryptography; Succinct Arguments.

Part II: Multi-Party Computation; Lattice Cryptography; and Lattice Cryptanalysis.

Part III: Models; Applied Cryptography and Side Channels; Cryptanalysis; Codes and Extractors; Secret Sharing.

Part IV: Zero Knowledge; Encryption++; Foundations; Low-Complexity Cryptography; Protocols.

✦ Table of Contents

Preface
Organization
Contents – Part III
Models
A Rational Protocol Treatment of 51% Attacks
1 Introduction
1.1 Related Literature
1.2 Our Results
2 Preliminaries
2.1 The Bitcoin Backbone Protocol
2.2 Rational Protocol Design
2.3 Utility of the Attacker From ch1EC:BGMTZ18
3 Artifacts of Unbounded Incentives
3.1 Demonstrating the Artifact
3.2 A First Attempt to Eliminate the Artifact
3.3 The Source of the Artifact: Unbounded Incentives
4 An RPD Analysis of Forks
4.1 Addressing Technical Issue of Non-constant Payoff for Block Rewards
4.2 Optimal Utility of Front-Running, Passive Adversaries
5 Analyzing 51% Attacks
5.1 Time to Fork
5.2 Payoff of 51% Double-Spending Attacks
5.3 Visualizations with Concrete Values
6 Mitigating 51% Attacks
6.1 Budget to Vulnerability Period
6.2 Attack-Payoff Security
References
MoSS: Modular Security Specifications Framework
1 Introduction
2 Execution Process
2.1 ExecAP: An Adversary-Driven Execution Process
2.2 The Extendable Execution Process
2.3 Using X to Define Specification and Entity-Faults Operations
3 Models
3.1 Specifications
3.2 Model-Satisfying Adversary
3.3 Example: The Bounded-Clock-Drift Model M-drift-clk
4 Requirements
4.1 Model-Secure Requirements
4.2 Example: The No False Accusations Requirement R-NFA
4.3 Supporting Confidentiality and Indistinguishability
5 Modularity Lemmas
5.1 Asymptotic Security Model Modularity Lemmas
5.2 Asymptotic Security Requirement Modularity Lemmas
6 Using MoSS for Applied Specifications
6.1 AuthBroadcast: Authenticated Broadcast Protocol
6.2 Specifications for PKI Scheme
7 Concrete Security and Ensuring Polytime Interactions
7.1 The CS Compiler
7.2 Concrete Security
7.3 Ensuring Polytime Interactions
8 Conclusions and Future Work
References
Tight State-Restoration Soundness in the Algebraic Group Model
1 Introduction
1.1 Overview of Our Techniques
2 Preliminaries
3 Interactive Proofs and State-Restoration Soundness
4 Proofs of Knowledge in the AGM
4.1 The Basic Framework
4.2 The Fiat-Shamir Transform
5 Online srs-wee Security of Bulletproofs
5.1 Inner Product Argument InPrd
5.2 Online srs-wee Security of RngPf
5.3 Online srs-wee Security for ACSPf
6 Online srs-wee Security of Sonic
References
Separating Adaptive Streaming from Oblivious Streaming Using the Bounded Storage Model
1 Introduction
1.1 Streaming Against Adaptive Adversaries
1.2 Our Results
2 Preliminaries
2.1 Adaptive Data Analysis
2.2 Transcript Compressibility
2.3 Pseudorandom Generators in the Bounded Storage Model
3 The Streaming Adaptive Data Analysis (SADA) Problem
4 An Oblivious Algorithm for the SADA Problem
5 An Impossibility Result for Adaptive Streaming
6 A Computational Separation
6.1 The SADA2 Problem
6.2 An Oblivious Algorithm for the SADA2 Problem
6.3 A Negative Result for the SADA2 Problem
References
Applied Cryptography and Side Channels
Provable Security Analysis of FIDO2
1 Introduction
2 Preliminaries
3 Execution Model
4 Passwordless Authentication
4.1 Protocol Syntax
4.2 Security Model
5 The W3C Web Authentication Protocol
6 PIN-Based Access Control for Authenticators
6.1 Protocol Syntax
6.2 Security Model
7 The Client to Authenticator Protocol V2.0
8 The Secure PACA Protocol
9 Composed Security of PlA and PACA
10 Conclusion
References
SSE and SSD: Page-Efficient Searchable Symmetric Encryption
1 Introduction
1.1 Overview of Contributions
1.2 Technical Overview
1.3 Related Work
2 Background
2.1 Notation
2.2 Searchable Symmetric Encryption
2.3 Locality and Page Efficiency
3 SSE from Data-Independent Packing
3.1 Data-Independent Packing
4 Efficient Data-Independent Packing
4.1 Stash Size Analysis
5 Experimental Evaluation
5.1 Stash Size
5.2 Performance
6 Conclusion
References
Towards Tight Random Probing Security
1 Introduction
2 Background
3 Random Probing Security of Small Circuits
3.1 Derivation of a Random Probing Security Bound
3.2 Security of Some Simple Gadgets
4 New Composition Results
4.1 Definitions
4.2 Simulatability
4.3 Probe Distributions
4.4 Composition Rules
5 Practical Security of Composite Circuits
5.1 Bounding PDTs
5.2 From PDT Bound to Security Level Bound
5.3 Tool
5.4 Experiments and SOTA Comparison
References
Secure Wire Shuffling in the Probing Model
1 Introduction
2 Preliminaries
2.1 The ISW Model for Perfect Security
2.2 The ISW Construction for Perfect Privacy
2.3 The Region Probing Model and t-SNI Security
2.4 Security in the Random Probing Model
2.5 Worst-Case Statistical Security Model
2.6 The ISW Construction for Statistical Privacy
2.7 Random Gate-Probing Model
3 Our New Shuffling Countermeasure
3.1 Description
3.2 Shuffling Security of a Gadget and Composition
3.3 Improved Time Complexity
3.4 Pure Circuit Description
4 Statistical Security in the Stateful Model
4.1 Perfect Privacy for Stateful Circuits
4.2 Worst-Case Statistical Privacy in the Stateful Model and the ISW Construction
5 Our Construction in the Statistical Stateful Model
5.1 First Construction: Iterated Cyclic Shifts
5.2 Second Construction: Randomizing Network
5.3 Composition in the Statistical Stateful Model
6 Implementation
7 Conclusion
References
Cryptanalysis
Differential-Linear Cryptanalysis from an Algebraic Perspective
1 Introduction
2 Differential-Linear Cryptanalysis
3 Algebraic Perspective of Differential-Linear Cryptanalysis
3.1 Basic Concepts and Facts
3.2 Calculation of the Differential-Linear Bias
3.3 Key Recovery in Differential-Linear Cryptanalysis
4 Applications to Ascon
4.1 Differential-Linear Bias of Ascon
4.2 Differential-Linear Cryptanalysis of Ascon
5 Applications to Serpent
5.1 A Brief Description of Serpent
5.2 Differential-Linear Bias of Serpent
5.3 Differential-Linear Cryptanalysis of 11-Round and 12-Round Serpent
6 Applications to Grain v1
6.1 Searching the Differences of Round-Reduced Grain v1
6.2 Analysis of 125-Round Grain v1
7 Discussions and Open Problems
8 Conclusion
References
Meet-in-the-Middle Attacks Revisited: Key-Recovery, Collision, and Preimage Attacks
1 Introduction
2 A Formal Description of the MITM Technique
3 Automatic MITM Key-Recovery Attacks
4 MITM Attacks on SKINNY and ForkSkinny
4.1 Programming the MITM Attacks on SKINNY-n-3n with MILP
4.2 The MITM Key-Recovery Attack on SKINNY-n-3n
5 Exploiting Nonlinearly Constrained Neutral Words in MITM Attacks and Its Applications
6 MITM-Based Collision Attacks and Its Applications
6.1 Automatic Search for MITM-Based Collision Attacks
6.2 Collision Attacks on WHIRLPOOL and Grøstl
7 Conclusion and Open Problems
References
Revisiting the Security of DbHtS MACs: Beyond-Birthday-Bound in the Multi-user Setting
1 Introduction
2 Preliminaries
3 Multi-user Security Proof Framework for DbHtS MACs
4 Multi-user Security of Three Constructions
4.1 Security of 2k-SUM-ECBC
4.2 Security of 2k-LightMAC_Plus
4.3 Security of 2k-PMAC_Plus
5 Attack on 2kf9 Construction
5.1 Attack on 2kf9 Without Domain Separation
5.2 Attack on 2kf9 with Domain Separation
References
Thinking Outside the Superbox
1 Introduction
1.1 Outline and Contributions
1.2 Notation and Conventions
2 Differential and Linear Cryptanalysis
2.1 Differential Cryptanalysis
2.2 Linear Cryptanalysis
3 Box Partitioning and Alignment
4 The Ciphers We Investigate
4.1 Rijndael
4.2 Saturnin
4.3 Spongent
4.4 Xoodoo
4.5 Round Cost
5 Huddling
5.1 Definitions of Bit Weight, Box Weight and Their Histograms
5.2 Bit and Box Weight Histograms
5.3 Two-Round Trail Weight Histograms
5.4 Three-Round Trail Weight Histograms
5.5 Four Rounds and Beyond
6 Clustering
6.1 The Cluster Histogram
6.2 The Cluster Histograms of Our Ciphers
6.3 Two-Round Trail Clustering
6.4 Three-Round Trail Clustering in Xoodoo
7 Dependence of Round Differentials
7.1 Masks for Differentials over Nonlinear Components
7.2 Independence of Masks over a Nonlinear Layer
7.3 Application to Xoodoo
8 Conclusion
References
Cryptanalysis of Full LowMC and LowMC-M with Algebraic Techniques
1 Introduction
2 Preliminaries
2.1 Notation
2.2 Description of LowMC
3 The Difference Enumeration Techniques
3.1 The Extended Framework
4 Observations on the S-Box
5 Reducing the Memory Complexity
6 Efficient Algebraic Techniques for Key Recovery
6.1 Exploiting the Leaked Linear Relations
6.2 Linearizing the Inactive S-Boxes
6.3 Further Improvement
7 Applications
7.1 Applications to LowMC with a Partial S-Box Layer
7.2 Applications to LowMC-M
8 A Refined Attack Framework for the Full S-Box Layer
8.1 Maximizing the Number of Inactive S-Boxes
8.2 Enumerating Differences via Solving Equations
8.3 Applications to 4-Round LowMC with a Full S-Box Layer
9 Experiments
10 Conclusion
A Description of LowMC-M
B Exploiting the Tweak to Maximize r0 for LowMC-M
C Explanation of the Attacks on LowMC with a Full S-box Layer
D A Table
References
The Cost to Break SIKE: A Comparative Hardware-Based Analysis with AES and SHA-3
1 Introduction
2 Preliminaries
2.1 SIKE and the CSSI Problem
2.2 The vOW Parallel Collision Finding Algorithm
3 Budget-Based Cost Model
4 Cost of Attacking SIKE
4.1 vOW on SIKE
4.2 Hardware Implementation of the Attack
5 Cost of Attacking Symmetric Primitives
5.1 Cost of Attacking AES
5.2 Cost of Attacking SHA-3
6 Security Estimation: A Comparative Analysis
A Price Data
B Security Estimates
References
Improved Torsion-Point Attacks on SIDH Variants
1 Introduction
1.1 Our Contributions
1.2 Comparison to Earlier Work
1.3 Outline
2 Preliminaries
2.1 The Supersingular Isogeny Diffie–Hellman Protocol Family
2.2 Notation
2.3 Quantum Computation Cost Assumptions
3 Overview
3.1 Hard Isogeny Problems
3.2 Petit's Torsion-Point Attack
3.3 Technical Preview
4 Improved Torsion-Point Attacks
4.1 Improved Torsion-Point Attacks
4.2 Solving Norm Equations
4.3 Runtime and Justification for Algorithms 1 and 2
5 Backdoor Instances
5.1 Backdoor Curves
5.2 Counting Backdoor Curves
5.3 Backdoored TEXT for Given TEXT and TEXT with Starting Vertex TEXT
5.4 Backdoored p for Given TEXT with Starting Vertex TEXT
6 Non-polynomial-time Attacks
6.1 Non-polynomial Time Dual Isogeny Attack for E0: y2=x3+x
6.2 Non-polynomial Time Frobenius Isogeny Attack for E0: y2 = x3 + x
6.3 Non-polynomial Time Dual Isogeny Attack for Backdoor Curves
7 Impact on Unbalanced SIDH, Group Key Agreement, and B-SIDH
7.1 Frobenius Isogeny Attack on Group Key Agreement and Unbalanced SIDH
7.2 Dual Isogeny Attack Applied to B-SIDH
7.3 Impact on B-SIDH Group Key Exchange
8 Open Question
References
Codes and Extractors
Smoothing Out Binary Linear Codes and Worst-Case Sub-exponential Hardness for LPN
1 Introduction
1.1 Learning Parity with Noise
1.2 Nearest Codeword Problem and Worst-Case Hardness
1.3 Worst-Case to Average-Case Reductions for LPN
1.4 Our Contributions
2 Preliminaries
2.1 Notations, Definitions and Inequalities
2.2 Binary Linear Codes
2.3 The NCP and LPN Problem
3 Worst-Case to Average-Case Reductions for LPN
3.1 Worst-Case Hardness for Large-Field LPN
3.2 The Worst-Case to Average-Case Reduction from ch16EC:BLVW19
3.3 On the Non-triviality of Code Smoothing
3.4 Worst-Case Sub-exponential Hardness for LPN
3.5 Smoothing Balanced Codes
3.6 Smoothing Independent Codes
3.7 Discussions
4 Concluding Remarks
A Proofs Omitted
B Inequalities, Theorems and Lemmas
References
Silver: Silent VOLE and Oblivious Transfer from Hardness of Decoding Structured LDPC Codes
1 Introduction
1.1 Our Results
1.2 Philosophy of Our Approach
1.3 Overview of Our Methodology
1.4 Our Design Criteria
1.5 Efficiency
2 Preliminaries
2.1 Preliminaries on Bias
2.2 Syndrome Decoding and Learning Parity with Noise
3 On the Hardness of LPN for Structured LDPC Codes
3.1 The Linear Test Framework
3.2 Dual Distance and Security Against Linear Tests
3.3 SOT from Asymptotically Good Linear-Time Encodable Codes
3.4 Most Sparse Matrices Have Linear Dual Distance
4 Fast LDPC Encoding
5 Estimating the Minimum Distance Empirically
5.1 Exact Minimum Distance
5.2 Upper Bounding the Minimum Distance
6 Code Design
6.1 Uniform LDPC
6.2 Tillich-Zémor Codes
6.3 LDPC Silver Codes
7 Performance Evaluation
References
Non-malleable Codes for Bounded Parallel-Time Tampering
1 Introduction
1.1 Our Results
1.2 Related Work
2 Technical Overview
2.1 Overview of the Proof
3 Preliminaries
4 Definition of Non-Malleable Codes
5 The Building Blocks
5.1 Time-Lock Puzzle
5.2 Non-malleable Commitment
5.3 One-Message Zero-Knowledge
6 The Non-malleable Code
6.1 Efficiency Analysis
6.2 Proof of Non-malleability
7 The Case of Uniform Tampering
References
Improved Computational Extractors and Their Applications
1 Introduction
1.1 Our Results
2 Technical Overview
2.1 Improved Two-Source and Non-malleable Extractors
2.2 Network Extractor Protocol
2.3 Extractors for Adversarial Sources
3 Preliminaries
3.1 Computational Extractors: Definitions
4 Computational Strong Two-Source Extractors in the CRS Model
4.1 Construction
5 Network Extractor Protocol in the CRS Model
5.1 Building Blocks
5.2 Construction
5.3 Instantiation
6 Extractor for Adversarial Sources in the CRS Model
6.1 Building Blocks
6.2 Construction
6.3 Instantiation
References
Adaptive Extractors and Their Application to Leakage Resilient Secret Sharing
1 Introduction
1.1 Our Results
1.2 Our Techniques
1.3 Related Work
1.4 Organization of the Paper
2 Preliminaries and Definitions
2.1 Notation
2.2 Secret Sharing Schemes
3 Adaptive Extractors
3.1 Definition
3.2 Construction
4 Leakage Resilient Secret Sharing
4.1 Leakage Models
4.2 LRSS Construction for the Adaptive Leakage and Reveal Model
4.3 Proof of Leakage Resilience in the Adaptive Leakage and Reveal Model
4.4 Parameters
4.5 LRSS for Joint Leakage and Reveal Model
References
Secret Sharing
Upslices, Downslices, and Secret-Sharing with Complexity of 1.5n
1 Introduction
2 Our Contribution
2.1 Upslice and Downslices
2.2 Worst-Case Downslices
2.3 Random Upslices and Mixed DNFs
3 Preliminaries
3.1 Covers
4 General Secret-Sharing for Downslices
4.1 Low-Density Downslices via Multislices
4.2 Reducing High-Density Downslices to Low Downslices
4.3 Proof of the Cover Reduction
5 Linear Secret Sharing for Downslices
5.1 Exploiting Duality
5.2 High-Density Downslices from Low-Density Upslices and Mid-Range Multislices
5.3 Bootstrapping downslices
5.4 Proof of Theorem 5.1
6 Random Upslices
6.1 Proof of Theorem 6.2
6.2 Proof of Theorem 6.3
A Omitted Preliminaries
References
Asymptotically-Good Arithmetic Secret Sharing over Z/pZ with Strong Multiplication and Its Applications to Efficient MPC
1 Introduction
1.1 Related Works
1.2 Our Focus
1.3 Our Contributions
1.4 Difficulties and Intuitions of the Constructions
1.5 Roadmap
2 LSSS from Free Codes have Optimal Complexity
2.1 Optimal Complexities in Galois Rings Extensions
2.2 General LSSS and ASSSM over Rings
2.3 Complexity of Sharing
2.4 Privacy (with Uniformity) and Efficient Reconstruction from Free Codes
2.5 (Free) Generation from Any Lift of Any Basis
3 Main Theorem 1
3.1 A Random Free Lift of a Code of Small Square Mostly Fails to Have a Small Square
3.2 A Technique to Find Them When They Exist, Illustrated on the Toy Example
3.3 Proof of Main Theorem 1
3.4 Reminders on the Asymptotic Parameters
4 Computing Hensel Lift of a Code with a Small Square
4.1 Example of a Multiplication Friendly Lift Modulo 2100
5 Applications to MPC
5.1 Proof of Main Theorem 2
5.2 Existence of Lifts of RMFE over Rings, with Constant Rate
5.3 Proof of Main Theorem 3
5.4 An Analogous Efficient Hensel Lift for RMFE
References
Large Message Homomorphic Secret Sharing from DCR and Applications
1 Introduction
1.1 Our Results
1.2 Technical Overview
1.3 Other Related Work
1.4 Concurrent Result
2 Preliminaries
2.1 Notation
2.2 Damgård–Jurik Encryption
2.3 Universal Hashing
3 Circuit Homomorphic Secret Sharing
3.1 Restricted Multiplication Circuits
3.2 Homomorphic Secret Sharing
4 Main Construction
4.1 Distance Function
4.2 HSS Construction
4.3 Additive Decoding
5 Distributed Oblivious RAM
5.1 Definition: Distributed ORAM
5.2 An Overview of Bounded Feedback and Onion ORAM
5.3 Our HSS Based ORAM Construction
5.4 Proof of Security
5.5 Complexity Analysis
6 Trapdoor Hash Functions
6.1 Generalizations
References
Traceable Secret Sharing and Applications
1 Introduction
1.1 Our Results
1.2 Related Work
2 Technical Overview
2.1 Our First Construction
2.2 Boosting Tracing Probability
2.3 Traceable Delegation
2.4 Extensions
3 Preliminaries
3.1 Goldreich-Levin Lemma
4 Traceable Secret Sharing
4.1 Definition
4.2 Construction
5 Traceable Multi-server Delegation of Computation
5.1 The Protocol
References
Quadratic Secret Sharing and Conditional Disclosure of Secrets
1 Introduction
1.1 Our Contributions and Techniques
1.2 Open Questions
1.3 Additional Related Works
2 Preliminaries
3 Degree-d Secret Sharing and Degree-d CDS Protocols
3.1 CDS with Degree-3 Encoding for the Non-quadratic Residues Function
4 Lower Bounds for Secret Sharing with Degree-d Reconstruction
4.1 Lower Bounds for 1-Bit Secrets for Implicit Access Structures
4.2 A Transformation from Secret Sharing with Degree-d Reconstruction into a Linear Secret Sharing
4.3 Lower Bounds for 1-Element Secrets for Explicit Access Structures
5 Quadratic CDS Protocols
6 A Quadratic Robust CDS Protocol
6.1 An Improved Analysis of the Transformation of ch25ABNP20
6.2 The Construction of the Quadratic t-RCDS Protocol
7 A Quadratic Secret Sharing for General Access Structures
References
Constructing Locally Leakage-Resilient Linear Secret-Sharing Schemes
1 Introduction
1.1 Our Contributions
1.2 Prior Works
2 Preliminaries and Notations
2.1 General Notation: Vectors, Random Variables, Sets
2.2 Matrices
2.3 Codes and Massey Secret-Sharing Schemes
2.4 Locally Leakage-Resilient Secret-Sharing Scheme
3 Leakage-Resilience of Random Linear Codes
3.1 Parameter Setting for Corollary 1
3.2 Proof of Lemma 2
3.3 Proof of Lemma 1
4 The k>n/2 Barrier
5 Leakage-Resilience of Shamir's Secret-Sharing
References
Author Index