Advances in Cryptology – ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part II

Preface
Organization
Contents – Part II
Public Key Cryptography
Incrementally Aggregatable Vector Commitments and Applications to Verifiable Decentralized Storage
1 Introduction
1.1 A New Notion for SVCs: Incremental Aggregation
1.2 Verifiable Decentralized Storage (VDS)
1.3 Concurrent Work
1.4 Preliminaries
2 Vector Commitments with Incremental Aggregation
2.1 Vector Commitments with Subvector Openings
2.2 Incrementally Aggregatable Subvector Openings
3 Applications of Incremental Aggregation
3.1 Divide-and-Conquer Extensions of Aggregation and Disaggregation
3.2 Committing and Opening with Precomputation
4 Our Realizations of Incrementally Aggregatable SVCs
4.1 Our First SVC Construction
4.2 Our Second SVC Construction
4.3 Comparison with Related Work
4.4 Experimental Evaluation
5 Verifiable Decentralized Storage
5.1 Syntax
5.2 Correctness and Efficiency of VDS
5.3 Security of VDS
5.4 Realizing VDS
References
Non-committing Encryption with Constant Ciphertext Expansion from Standard Assumptions
1 Introduction
1.1 Background
1.2 Our Contribution
1.3 Overview
1.4 Related Works on Amplification for Public-Key Encryption
2 Preliminaries
3 (Weak) Non-committing Encryption
4 Amplification for Non-committing Encryption
4.1 Wiretap Codes
4.2 Instantiation of Wiretap Codes
4.3 Full-Fledged NCE from Weak NCE
5 Construction of Weak NCE
5.1 Obliviously Sampleable Chameleon Encryption
5.2 Construction
6 Obliviously Sampleable Chameleon Encryption from Lattices
6.1 Preliminaries on Lattices
6.2 Construction
7 Conclusion
References
Collusion Resistant Trace-and-Revoke for Arbitrary Identities from Standard Assumptions
1 Introduction
1.1 Construction Overview
1.2 Related Work
2 Preliminaries
2.1 Functional Encryption
3 Revocable Predicate Encryption
3.1 Constructing Secret-Key Revocable Predicate Encryption with Broadcast
3.2 Instantiating Secret-Key Revocable Predicate Encryption with Broadcast
4 Identity-Based Trace-and-Revoke
4.1 Constructing an Identity-Based Trace-and-Revoke Scheme
4.2 Instantiating the Trace-and-Revoke Scheme
References
Subvert KEM to Break DEM: Practical Algorithm-Substitution Attacks on Public-Key Encryption
1 Introduction
1.1 Algorithm-Substitution Attacks
1.2 Our Results
2 Preliminaries
2.1 Entropy Smoothing Hash Functions
2.2 Key Encapsulation Mechanism (KEM)
3 Asymmetric ASA Model for KEMs
3.1 Asymmetric ASA on KEMs
3.2 Session Key Recovery
3.3 Undetectability
4 Mounting ASAs on KEMs
4.1 A Module-Level Syntax of KEM
4.2 Our Non-Black-Box ASA on KEMs
4.3 Formal Analysis
5 Instantiations
5.1 KEMs from Hash Proof Systems
5.2 Concrete KEMs
6 Discussions on Countermeasures
6.1 Abandoning Randomized Algorithms
6.2 Permitting Randomized Algorithms with Further Assumptions
A Omitted Definitions and Proof
A.1 Hash Proof System
A.2 Proof of Theorem 4
References
Unbounded HIBE with Tight Security
1 Introduction
1.1 Motivation
1.2 Our Contribution
1.3 Technical Overview
1.4 More Discussion on Related Work
2 Preliminaries
2.1 Pairing Groups and Matrix Diffie-Hellman Assumptions
3 Unbounded Affine MAC
3.1 Core Lemmata
3.2 An Unbounded Affine MAC
4 Transformation to Unbounded HIBE
References
Multi-client Oblivious RAM with Poly-logarithmic Communication
1 Introduction
2 Technical Overview
2.1 MCORAM with Poly-log Communication: Initial Attempts
2.2 FHE-Based Construction
2.3 DPF-Based Multi-server Construction
3 Related Work
4 Preliminaries
4.1 Constrained Pseudorandom Functions
4.2 Fully Homomorphic Encryption
4.3 Distributed Point Functions
4.4 Homomorphic Secret Sharing
5 Multi-client ORAM and Its Simulation-Based Security
5.1 Syntax
5.2 Correctness and Integrity
5.3 Obliviousness
6 FHE-based Single-Server Construction
6.1 Formal Description
6.2 Security
6.3 Access Rights Revocation
7 DPF-based Multi-server Construction
7.1 Our Distributed Point Function
7.2 Multi-client ORAM from Distributed Point Functions
8 Concluding Remarks
References
Privacy-Preserving Pattern Matching on Encrypted Data
1 Introduction
2 Related Work
3 Security Assumption
4 The Intuition
5 Sbold0mu mumu 442005/06/28 ver: 1.3 subfig package4444E Construction
5.1 Usage Scenario
5.2 Architecture
5.3 Security Requirements and Hypothesis
5.4 Definition of Sbold0mu mumu 442005/06/28 ver: 1.3 subfig package4444E
5.5 Sbold0mu mumu 442005/06/28 ver: 1.3 subfig package4444E's Security Requirements
5.6 A Trivial Protocol
5.7 The Sbold0mu mumu 442005/06/28 ver: 1.3 subfig package4444E's Protocol
5.8 Sbold0mu mumu 442005/06/28 ver: 1.3 subfig package4444E's Security Results
6 ASbold0mu mumu 332005/06/28 ver: 1.3 subfig package3333E Construction
6.1 Architecture
6.2 Security Requirements and Hypothesis
6.3 Definition of ASbold0mu mumu 332005/06/28 ver: 1.3 subfig package3333E
6.4 Security Model
6.5 The Protocol
6.6 ASbold0mu mumu 332005/06/28 ver: 1.3 subfig package3333E Security Results
7 The Complexity
8 Empirical Evaluation
9 Conclusion
References
Efficient Homomorphic Comparison Methods with Optimal Complexity
1 Introduction
1.1 Our Idea and Technical Overview
1.2 Our Results
1.3 Related Works
2 Preliminaries
2.1 Notations
2.2 Minimax Polynomial Approximation Method
2.3 Homomorphic Encryption
3 Our New Comparison Method
3.1 Composite Polynomial Approximation of Sign Function
3.2 Analysis on the Convergence of fn(d)
3.3 New Comparison Algorithm NewComp
3.4 Computational Complexity of NewComp and Its Asymptotic Optimality
3.5 Heuristic Methodology of Convergence Acceleration
4 Application to Min/Max
5 Experimental Results
5.1 Approximate HE Scheme HEAAN
5.2 Parameter Selection
5.3 Performance of NewComp and NewCompG
5.4 Performance of NewMax and NewMaxG
A Derivation of fn from Core Properties
B Convergence of 0, S and gn,
C Heuristic Properties on gn
D Convergence of fn(d) in Erroneous Case
E Script for Security Estimation
References
Lattice-Based Cryptography
Practical Exact Proofs from Lattices: New Techniques to Exploit Fully-Splitting Rings
1 Introduction
1.1 Our Approach
2 Preliminaries
2.1 Notation
2.2 Prime Splitting and Galois Automorphisms
2.3 The Number Theoretic Transform
2.4 Challenge Space
2.5 Module-SIS and Module-LWE Problems
2.6 Error Distribution, Discrete Gaussians and Rejection Sampling
2.7 Commitment Scheme
2.8 Opening and Product Proof
3 Proving Unstructured Linear Relations over Zqn
3.1 Basic Protocol
3.2 Boosting Soundness by Mapping Down
3.3 General Case
4 Main Protocol
4.1 Security Analysis
4.2 Proof Size
References
Towards Classical Hardness of Module-LWE: The Linear Rank Case
1 Introduction
2 Preliminaries
2.1 Algebraic Number Theory
2.2 Lattices
2.3 Probabilities
2.4 The Module Learning with Errors Problem
3 Hardness of Binary M-LWE
4 Classical Hardness for Linear Rank Modules
4.1 Modulus Switching
4.2 Classical Reduction for M-LWE
4.3 Adapting the Error Distribution
References
Lattice-Based E-Cash, Revisited
1 Introduction
2 Preliminaries
2.1 Lattice Preliminaries
2.2 Lossy Trapdoor Functions
2.3 Witness Extraction and Forking Lemma
2.4 E-Cash Security Definitions
3 Intuition
4 Construction
5 Zero-Knowledge Arguments with Soundness Error 1/poly() in Standard Lattices
5.1 Zero-Knowledge Arguments for the BLMR PRF
5.2 Zero-Knowledge Arguments for the Spend Protocol
6 Security Proofs
7 A More Efficient GGM-based Construction
7.1 Parameters
References
Twisted-PHS: Using the Product Formula to Solve Approx-SVP in Ideal Lattices
1 Introduction
2 Preliminaries
2.1 Number Fields, Ideals and Class Groups
2.2 The Product Formula
2.3 Unit Groups
2.4 Algorithmic Number Theory
2.5 Lattices Geometry and Hard Problems
3 The PHS Algorithm
3.1 Preprocessing of the Number Field
3.2 Query Phase: Solving id-Svp Using the Preprocessing
3.3 Optimizing PHS Parameters
4 Twisted-PHS Algorithm
4.1 Preprocessing of the Number Field
4.2 Query Phase
5 Experimental Data
5.1 Geometric Characteristics
5.2 Plotting Gram-Schmidt Log Norms
5.3 Approximation Factors
References
Simpler Statistically Sender Private Oblivious Transfer from Ideals of Cyclotomic Integers
1 Introduction
1.1 Related Work
1.2 Our Contribution
1.3 Techniques
2 Preliminaries
2.1 Oblivious Transfer
2.2 Entropy and Extractors
2.3 Lattices and Gaussian Measures
2.4 Ring-LWE
3 Oblivious Transfer Protocol
3.1 Correctness
3.2 Computational Receiver Privacy
3.3 Statistical Sender Privacy
3.4 Parameters
3.5 Choice of Extractor
4 Comparison to Related Protocols
4.1 Single Execution
4.2 O(n) Parallel Executions
References
Isogeny-Based Cryptography
Cryptographic Group Actions and Applications
1 Introduction
1.1 Isogeny-Based Cryptography
1.2 Cryptographic Group Actions
1.3 Cryptographic Group Actions and Isogenies
1.4 Our Contributions
1.5 Notation
1.6 Paper Outline
2 Cryptographic Group Actions
2.1 Effective Group Actions
2.2 Restricted Effective Group Actions
2.3 Known-Order Effective Group Action
3 Hash Proof System
4 Linear Hidden Shift (LHS) Assumption
4.1 Symmetric KDM-CPA Security from LHS
4.2 On the Security of LHS Assumption
References
B-SIDH: Supersingular Isogeny Diffie-Hellman Using Twisted Torsion
1 Introduction
1.1 Naming
1.2 Performance vs. SIDH
1.3 Related Work
2 Twist-Agnostic SIDH
2.1 Rational (p+1)-torsion
2.2 SIDH
2.3 Twist-Agnostic Isogenies
3 Using Torsion from the Quadratic Twists
3.1 B-SIDH in a Nutshell
3.2 Handling Large -degree Isogenies
4 Security Analysis
4.1 Multiple Edge Sets
4.2 Security of Non-commutative vs. Commutative Schemes
4.3 Classical Cryptanalysis
4.4 Quantum Cryptanalysis
4.5 Security Summary
5 Searching for Friendly Instances
5.1 Fast Primes: Accelerating Alice, Burdening Bob
5.2 Searching with the Extended Euclidean Algorithm
5.3 Primes of the Form p=2xn-1
5.4 Summary
References
Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices
1 Introduction
1.1 Our Contributions
1.2 Technical Overview
2 Preliminaries
2.1 Ring Signatures
2.2 Linkable Ring Signatures
2.3 Isogenies and Ideal Class Group Actions
2.4 Lattices
2.5 Index-Hiding Merkle Trees
2.6 Seed Tree
3 From Group Actions to Ring Signatures
3.1 Admissible Group Actions
3.2 From an Admissible Group Action to Base or Sigma Protocol RS-base
3.3 Security Proof for the Base OR Sigma Protocol RS-base
3.4 From Base OR Sigma Protocol RS-base to Main OR Sigma Protocol RS
3.5 Security Proof for the Main OR Sigma Protocol RS
3.6 From Main OR Sigma Protocol RS to Ring Signature
4 From a Pair of Group Actions to Linkable Ring Signatures
4.1 Admissible Pairs of Group Actions
4.2 From an Admissible Pair of Group Actions to Base or Sigma Protocol with Tag
4.3 From Base OR Sigma Protocol with Tag LRS-base to Main OR Sigma Protocol with Tag LRS
4.4 From Main OR Sigma Protocol with Tag LRS to Linkable Ring Signatures
5 Post-quantum Admissible (pair of) Group Actions from Isogeny and Lattice Assumptions
5.1 Isogeny-Based Instantiations
5.2 Lattice-Based Instantiation
6 Parameter Selection, Implementation Results and Conclusions
6.1 Implementation
6.2 Conclusions
References
Radical Isogenies
1 Introduction
2 Background
2.1 Isogenies and Vélu's Formulae
2.2 Division Polynomials
2.3 The Tate Normal Form
2.4 The Tate Pairing
2.5 Simple Radical Extensions
2.6 CSIDH
3 Existence of Radical Isogeny Formulae
4 Explicit Radical Isogeny Formulae in Low Degree
5 Isogeny Chains over Finite Fields
5.1 The Case gcd(q - 1, N) = 1
5.2 The Case gcd(q-1, N) = N
5.3 The Case gcd(q-1, N ) = 2
6 Speeding up CSIDH
7 Conclusion and Open Problems
References
Oblivious Pseudorandom Functions from Isogenies
1 Introduction
1.1 Background and Notation
1.2 Overview of Our Techniques
1.3 Additional Related Work
2 Augmentable Commitments
3 Augmentable Commitments from Supersingular Isogenies
4 Oblivious PRF from Augmentable Commitments
5 Zero-Knowledge Proof for Point Verification
6 Zero-Knowledge Proof of Equality of Isogenies
7 Putting It All Together
8 Naor-Reingold OPRF from an Abelian Group Action
9 Conclusions and Open Problems
References
SiGamal: A Supersingular Isogeny-Based PKE and Its Application to a PRF
1 Introduction
1.1 Our Results
2 Preliminaries
2.1 Basic Mathematical Concepts
2.2 Group Action of Ideal Class Group
2.3 CSIDH
2.4 Pohlig-Hellman Algorithm ch19PohligspsHellman
2.5 Public Key Encryption
2.6 Pseudo Random Function
3 SiGamal
3.1 Overview
3.2 Encryption Scheme of SiGamal
3.3 Security of SiGamal
4 C-SiGamal (Compressed-SiGamal)
4.1 Encryption Scheme of C-SiGamal
4.2 Security of C-SiGamal
4.3 Comparing Key Size of Each Scheme
5 Naor-Reingold Type PRF Based on SiGamal
5.1 Definition of Our Proposed PRF
5.2 Evaluating Cost of Computing Our Proposed PRF
6 Experimentation
6.1 Parameters
6.2 Computational Costs of SiGamal and C-SiGamal
6.3 Computational Costs of Our Proposed PRF
7 Conclusion
7.1 Future Work
A Generating Points of order 2r
References
Quantum Algorithms
Estimating Quantum Speedups for Lattice Sieves
1 Introduction
2 Preliminaries
2.1 Models of Computation
2.2 Black Box Search
2.3 Lattice Sieving and Near Neighbour Search on the Sphere
2.4 The popcount Filter
2.5 Geometric Figures on the Sphere
3 Filtered Quantum Search
4 Circuits for popcount
4.1 Quantum Circuit for popcount
4.2 RAM Program for popcount
4.3 Cost of Inner Products
5 The Accuracy of popcount
6 Tuning popcount for NNS
6.1 AllPairSearch
6.2 RandomBucketSearch
6.3 ListDecodingSearch
7 Cost Estimates
7.1 Barriers to a Quantum Advantage
7.2 Relevance to SVP
7.3 Future Work
References
A Combinatorial Approach to Quantum Random Functions
1 Introduction
1.1 What Makes QPRFs Challenging?
1.2 Our Results
1.3 Technical Overview
2 Applications
2.1 Quantum Secure MACs
2.2 Pseudorandom Quantum States
3 Preliminaries
3.1 Quantum Computing
3.2 Pseudorandom Functions
4 Bipartite Expanders
4.1 Q-unique Expanders
4.2 Parameters
5 Our Quantum Pseudorandom Function
5.1 Domain Extension
5.2 Unbounded Queries
References
Improved Classical and Quantum Algorithms for Subset-Sum
1 Introduction
2 List Merging and Classical Subset-Sum Algorithms
2.1 Notations and Conventions
2.2 Merging and Filtering
2.3 Correctness of the Algorithms
2.4 The HGJ Algorithm
2.5 The BCJ Algorithm and Our Improvements
3 Quantum Preliminaries and Previous Work
3.1 Quantum Preliminaries
3.2 Solving Subset-Sum with Quantum Walks
4 Quantum Asymmetric HGJ
4.1 Quantum Match-and-Filter
4.2 Revisiting HGJ
4.3 Improvement via Quantum Filtering
4.4 Quantum Time-Memory Tradeoff
5 New Algorithms Based on Quantum Walks
5.1 Asymmetric 5th Level
5.2 Better Setup and Updates Using Quantum Search
5.3 Parameters
6 Mitigating Quantum Walk Heuristics for Subset-Sum
6.1 New Data Structure for Storing Lists
6.2 New Data Structure for Vertices
6.3 Fraction of Marked Vertices
6.4 Time Complexities Without Heuristic 2
7 Conclusion
References
Security Limitations of Classical-Client Delegated Quantum Computing
1 Introduction
1.1 Overview of Our Contributions
1.2 Related Work
2 Preliminaries
2.1 The Constructive Cryptography Framework
2.2 Notation
3 Impossibility of Composable Classical RSP
3.1 Remote State Preparation and Describable Resources
3.2 Classically-Realizable RSP are Describable
3.3 RSP Resources Impossible to Realize Classically
3.4 Accepting the Limitations: Fully Leaky RSP Resources
4 Impossibility of Composable Classical-Client UBQC
4.1 Impossibility of Composable UBQCcc on 1 Qubit
4.2 Impossibility of Composable UBQCcc on Any Number of Qubits
5 Game-Based Security of QF-UBQC
5.1 Implementing Classical-Client UBQC with QFactory
References
Quantum Circuit Implementations of AES with Fewer Qubits
1 Introduction
2 Notations
3 The AES Block Cipher
3.1 Specification of AES
3.2 The Algebraic Structures of the S-Box of AES
3.3 Our Improved Classical Circuit of the S-Box-1 of AES
4 The Quantum Circuits for the Basic AES Operations
4.1 Quantum Circuits for Three Linear Transformations of AES
4.2 Improved Quantum Circuit Implementations of AES's S-Box
4.3 Improved Quantum Circuit Implementation of the S-Box-1
5 Our Strategies for the Zig-Zag Method and the Key Schedule of AES
5.1 Zig-Zag Method with Improved Depth-Qubit Trade-Offs
5.2 Improved Quantum Circuits for the Key Schedule of AES
Our Strategy for the Key Schedule of AES-128.
Our Strategy for the Key Schedule of AES-192 and AES-256.
6 Improved Quantum Circuit Implementations of AES
6.1 Our Improved Quantum Circuit of AES-128
The Time and Space Cost of Part 1.
The Time and Space Cost of Part 2.
The Time and Space Cost of Part 3.
6.2 Quantum Circuit Implementations of AES-192 and AES-256
7 Conclusion
References
Quantum Collision Attacks on AES-Like Hashing with Low Quantum Random Access Memories
1 Introduction
2 Preliminaries
2.1 AES-Like Hashing
2.2 Quantum Computation and Quantum RAM
3 MILP Models for the Rebound Attack
3.1 The Full-Active and Non-Full-Active Super S-Box Techniques
3.2 Searching for Exploitable Differentials in Classical and Quantum Attacks with MILP
4 Quantum Collision Attacks on 7-Round AES-MMO and AES-MP with Low qRAM
4.1 A Low-qRAM Quantum Collision Attack on 7-Round AES-MMO
4.2 Implementation of the Quantum Oracle UF
5 Quantum Attacks on 7-Round AES-MMO Without qRAM
6 Collision Attacks on Grøstl-512
6.1 Exploitable Differential Trails of Grøstl-512
6.2 Classical and Quantum Collision Attacks on 4-Round Grøstl-512
6.3 Classical and Quantum Collision Attacks on 5-Round Grøstl-512
7 Semi-Free-Start Collision Attacks on Grøstl-256
8 Conclusion
References
Authenticated Key Exchange
Fuzzy Asymmetric Password-Authenticated Key Exchange
1 Introduction
1.1 Roadmap
2 Preliminaries
2.1 Robust Secret Sharing in the Exponent
3 Security Model
4 Fuzzy aPAKE from Secret Sharing
4.1 Security
5 Fuzzy aPAKE from Standard aPAKE
6 Efficiency
7 Conclusion
References
Two-Pass Authenticated Key Exchange with Explicit Authentication and Tight Security
1 Introduction
1.1 Tightly Secure Authenticated Key Exchange
1.2 Our Approach
1.3 Our Contribution
2 Preliminaries
2.1 Digital Signature with Adaptive Corruptions
2.2 KEM and Its Security in the Multi-user Setting
2.3 Diverse Property of KEM
2.4 The Strong Twin Diffie-Hellman Assumption
3 Authenticated Key Exchange Scheme
3.1 Definition of Authenticated Key Exchange
3.2 Security Model of AKE
4 Generic Construction of AKE and Its Security Proof
4.1 Construction
4.2 Security Proof
5 Instantiations of AKE with Tight Security
5.1 Instantiations of KEM with Tight IND-mCPAreveal Security
5.2 Instantiations of SIG with Tight MU-EUF-CMAcorr Security
5.3 Instantiations of AKE
References
Author Index