Selected Areas in Cryptography: 27th International Conference, Halifax, NS, Canada (Virtual Event), October 21-23, 2020, Revised Selected Papers (Lecture Notes in Computer Science)

This book contains revised selected papers from the 27th International Conference on Selected Areas in Cryptography, SAC 2020, held in Halifax, Nova Scotia, Canada in October 2020. The 27 full papers presented in this volume were carefully reviewed and selected from 52 submissions. They cover the following research areas: design and analysis of symmetric key primitives and cryptosystems, including block and stream ciphers, hash functions, MAC algorithms, and authenticated encryption schemes, efficient implementations of symmetric and public key algorithms, mathematical and algorithmic aspects of applied cryptology, and secure elections and related cryptographic constructions Preface Organization Invited Talks What’s So Hard About Internet Voting? Trustless Groups of Unknown Order Contents Public-Key Cryptography Efficient Lattice-Based Polynomial Evaluation and Batch ZK Arguments 1 Introduction 1.1 Our Contribution 1.2 Application 2 Preliminaries 3 Lattice-Based Polynomial Zero-Knowledge Argument 3.1 Commitments to Polynomials (PolyCom) 3.2 Polynomial Evaluation Protocol PEv 3.3 Efficiency Analysis 4 Batch Polynomial Evaluation 4.1 Preliminaries of the Protocol 4.2 Detailed Protocol 4.3 Efficiency Analysis 5 Application to Range Proof 5.1 Comparison A Example to Batch Technique References FROST: Flexible Round-Optimized Schnorr Threshold Signatures 1 Introduction 2 Background 2.1 Threshold Schemes 2.2 Distributed Key Generation 2.3 Schnorr Signatures 2.4 Attacks on Parallelized Schnorr Multisignatures 3 Related Work 4 Preliminaries 5 FROST: Flexible Round-Optimized Schnorr Threshold Signatures 5.1 Key Generation 5.2 Threshold Signing with Unrestricted Parallelism 6 Security 6.1 Correctness 6.2 Security Against Chosen Message Attacks 6.3 Aborting on Misbehaviour 7 Implementation and Operational Considerations 8 Conclusion A Proof of Security A.1 Preliminaries A.2 Proof of Security for FROST-Interactive A.3 Extension of FROST-Interactive to FROST References Algorithmic Acceleration of B/FV-Like Somewhat Homomorphic Encryption for Compute-Enabled RAM 1 Introduction 2 Preliminaries 2.1 Notations 2.2 The Original B/FV Scheme ch3fan2012somewhat 2.3 The Full-RNS Variant of the B/FV Scheme 2.4 NTT 2.5 Compute-Enabled RAM 3 Novel Optimizations Using Special Moduli 3.1 NTT Implementation with CE-RAM 3.2 Choosing Special Moduli for Optimization 3.3 Optimizing Modular Reduction 3.4 Optimizing FastBConv 3.5 Extended Base 3.6 Finding NTT Parameters 4 Experimental Evaluation 4.1 CE-RAM Environment and Parameters 4.2 Comparison to CE-RAM Implementation of B/FV 4.3 Comparison to CPU Implementation of B/FV 4.4 Considering Throughput with Projection 4.5 Comparison to Other Hardware Accelerators of B/FV 5 Related Work 6 Conclusion A Proofs for Novel Optimizations A.1 Proof of Theorem 1 A.2 Proof of Lemma 2 A.3 Proof of Theorem 2 B Proofs for Fermat-like Coprimes C NTT Algorithm References Obfuscating Finite Automata 1 Introduction 2 Obfuscation Definitions 3 Matrix (Graded) Encoding Schemes 3.1 HAO15 4 HAO15 Zero-Testing and Computational Assumptions 5 Finite Automata and Transition Matrices 5.1 General Safeguards 6 Obfuscated Finite Automata 6.1 Obfuscator and Obfuscated Program 6.2 Obfuscated Program Evaluation 6.3 Security 7 Parameters 8 Conclusion A Matrix (Graded) Encoding Scheme B GGH15 C General Encoding Schemes References On Index Calculus Algorithms for Subfield Curves 1 Introduction 2 Index Calculus 2.1 Framework of Index Calculus 2.2 Index Calculus for Elliptic Curves 2.3 Breaking Symmetries 3 Index Calculus for Koblitz Curves 3.1 Improved Symmetry Breaking for Koblitz Curves 3.2 Frobenius Invariant Factor Bases 3.3 Comparison of Different Variants 4 Frobenius Invariant Factor Bases 4.1 Linearised Polynomials 4.2 Factor Bases from Isogenies Between Algebraic Groups 5 Experimental Results 5.1 Frobenius Invariant Vector Spaces 5.2 Factor Bases from Isogenies Between Algebraic Tori 6 Conclusion References Symmetric-Key Analysis Weak-Key Distinguishers for AES 1 Introduction 2 Weak-Key (Invariant) Subspace Trails 2.1 Subspace Trails 2.2 Invariant Subspace Attacks 2.3 Weak-Key Subspace Trails 3 Preliminary – Subspace Trail Properties of the AES 3.1 Subspace Trails of AES 3.2 (Weak-Key) Invariant Subspace Trail for AES 4 Weak-Key Secret-Key Distinguishers for AES 4.1 Subspace Trail Distinguishers 4.2 Weak-Key ``Multiple-of-n'' Property for 5-/6-Round AES-128 4.3 Practical Experiments 5 New Chosen-Key Distinguishers for AES 5.1 Open-Key Distinguishers – State of the Art for AES 5.2 The ``Simultaneous Multiple-of-n'' Property 5.3 9-Round Chosen-Key Distinguisher for AES-128 5.4 Achieving the ``Simultaneous Multiple-of-n'' Property Generically A Generic Subspace Trail (of Length 1) for AES – Proof B Weak-Key Invariant Subspace Trails of AES-256 B.1 AES-256 Key-Schedule B.2 Invariant Subspace – Weak-Keys of AES-256 B.3 Chosen-Key Distinguisher for 12-Round AES-256 C Practical Collisions for 7-Round AES-256 Compressing Modes D Proofs of Results Given in Sect.4 D.1 Proofs of Proposition 1 D.2 Proofs of Weak-Key ``Multiple-of-n'' – Theorem 4 E Gilbert's Known-Key Distinguisher for AES F Proof of Proposition 2 G On the Difficulty to Set Up ``Multiple-of-n'' Open-Key Distinguishers Without Relying on Weak-Keys References Algebraic Key-Recovery Attacks on Reduced-Round Xoofff 1 Introduction 1.1 State of the Art 1.2 Our Contribution 2 Preliminaries 2.1 Farfalle Construction 2.2 Specification of Xoofff 2.3 Linearization Attack 3 Distinguisher and Attack on Xoofff (1-Round Xoodoo) 3.1 Symmetry Property of the State Rolling Function 3.2 Secret-Key Distinguisher (1-round Xoodoo) 3.3 Attack on Xoofff Instantiated with 1-round Xoodoo in the Expansion Part 3.4 Experimental Results 4 Distinguisher and Attack on Xoofff Instantiated with 2-round Xoodoo in the Expansion Part 4.1 First Secret-Key Distinguisher 4.2 Second Secret-Key Distinguisher 4.3 Attack on Xoofff Instantiated with 2-round Xoodoo in the Expansion Part 4.4 Experimental Results 5 Linearization MitM Attack on Xoofff (Instantiated with 3-/4-round Xoodoo in the Expansion Part) 5.1 Idea of the MitM Linearization Attack 5.2 Attacks on Xoofff Instantiated with 2-round Xoodoo in the Expansion Part 5.3 Attacks on Xoofff Instantiated with 3-/4-round Xoodoo in the Expansion Part 5.4 Experiment Results 6 Summary and Possible Countermeasures A Attack on Xoofff (2-round Xoodoo): Details for Step 2 B Specification of Toy-Version Xoofff C Attack on Full-Round Xoofff without Constants D Different Constant Addition (Equivalently, ) Operation E Higher-Order Differential on Xoofff E.1 Idea of the Attack E.2 Cost of the Attack References Improved (Related-key) Differential Cryptanalysis on GIFT 1 Introduction 2 Preliminaries 2.1 Description of GIFT 2.2 Definitions and Notations 2.3 Three Methods to Speed up Matsui's Algorithm 2.4 Related-key Boomerang Attack and Rectangle Attack 3 Searching Related-key Differential Trails 3.1 Applying Matsui's Algorithm in Related-key Scenario 3.2 Results on Related-Key Differential Trails of GIFT 4 Increasing the Probability of the Distinguisher Utilizing Clustering Effect 4.1 Single-key Scenario 4.2 Related-key Scenario 5 Attacks on GIFT-64 5.1 Related-key Rectangle Attack on 25-Round GIFT-64 5.2 Related-key Rectangle Attack on 24-Round GIFT-64 6 Attacks on GIFT-128 6.1 Single-Key Differential Attack on 26-Round GIFT-128 6.2 Related-Key Rectangle Attack on 23-Round GIFT-128 7 Conclusion and Future Work A Improved Matsui's Algorithm for GIFT B Related-key Boomerang Attack on 22-round GIFT-128 B.1 Determining the Related-key Boomerang Distinguisher B.2 Data Collection B.3 Key Recovery B.4 Complexity and Success Probability C Analyzing the Probability of the 19-round Distinguisher Proposed in ch8DBLP:journalsspscjspsChenWZ19 D (Related-key) Differential Trails References Boolean Polynomials, BDDs and CRHS Equations - Connecting the Dots with CryptaPath 1 Introduction 1.1 Our Contribution 2 Preliminaries 2.1 Binary Decision Diagrams and Boolean Functions 2.2 Compressed Right-Hand Sides and Boolean Equations 2.3 Basic Operations on CRHS Equations 3 Modelling Cryptographic Primitives as System of CRHS Equations 3.1 The Structure of SPN Block Ciphers 3.2 Variables 3.3 Constructing CRHS Equations and the Complete System 4 Solving a System of CRHS Equations 4.1 Finding the Solution 4.2 Supporting Techniques 4.3 Complexity 5 CryptaPath 5.1 Example Usage and Results 6 Conclusions and Further Work A Overview of the Code and Usage of CryptaPath A.1 Usage References Boolean Ring Cryptographic Equation Solving 1 Introduction 2 Cryptographic Equation Systems and the Boolean Ring 3 The XL and EGHAM Processes 3.1 XL-Type Algorithms 3.2 The EGHAM Process 3.3 A Boolean View of the EGHAM process 4 A Boolean EGHAM process: EGHAM2 4.1 The Kernel of the Boolean Mapping 4.2 The R2-Criterion for a Quadratic Boolean Element 4.3 Finding Quadratic Elements Satisfying the R2-Criterion 4.4 Probabilistic Linear Expressions 4.5 Boolean Ring Equation Solving as an LPN Problem 4.6 Required Degree for the EGHAM2 Process to Succeed 4.7 An Example of the EGHAM2 Process 5 Conclusions References Interpolation Cryptanalysis of Unbalanced Feistel Networks with Low Degree Round Functions 1 Introduction 1.1 Related Work 2 Preliminaries 2.1 Background 2.2 Low Memory Interpolation 3 Analysis of Output Polynomials 3.1 ERF Analysis 3.2 CRF Analysis 4 Low Memory Interpolation Cryptanalysis of UFNs 4.1 Analysis Outline 5 Cryptanalysis of UFNerf 5.1 Algebraic Expression of Second Highest Coefficient 5.2 Value of Second Highest Coefficient 5.3 Key Recovery with a Single Key 5.4 Complexity Improvements via Branch Subtraction 5.5 Key Recovery with Multiple Keys 5.6 Summary of Complexities 5.7 Experimental Verification 6 Cryptanalysis of UFNcrf 7 Cryptanalysis of UFN Based Sponge Hash 7.1 Experimental Verification 8 Attacks on Reduced Round GMiMC A Proofs A.1 Proof of Proposition1 A.2 Proof of Proposition2 A.3 Proof of Proposition4 B Reduced Round Instances of UFNerfand UFNcrf C Plots and runtime summaries for GMiMCHash Experiments D Roots of Random Polynomials over a Finite Field References Unintended Features of APIs: Cryptanalysis of Incremental HMAC 1 Introduction 1.1 Authentication of Fragmented Messages 1.2 IncMACs (Incremental MACs) 1.3 The Common (Native) API of Hash Functions and HMAC 1.4 HMAC-Based IncMAC Variants 1.5 Related Work 1.6 Our Results 1.7 Notations 1.8 Structure of the Paper 2 Key-Independent Collision Attacks on the OpenSSL Implementation (NIPO) 2.1 The Padded Inner Stream of NIPO 2.2 Collisions (Key-Independent) 2.3 Linear Multi-collisions (Key-Independent) 2.4 Exponential Multi-collisions (Key-Independent) 3 Forgery Attacks Against NIPO HMAC Implementation 3.1 A Simple Forgery Attack 3.2 Chosen Plaintext Forgery Attack 3.3 Known Plaintext Forgery Attack 4 Cryptanalysis of the Naive HMAC Implementation 4.1 Key Recovery Attack 4.2 A Simple Message Extension Attack 4.3 A More Efficient Message Extension Attack 4.4 Forgery Attack 5 The PIPO HMAC Implementation 6 Secure IncMACs 6.1 PIPO and LAPIPO 7 Summary References Quantum Cryptanalysis Low-Gate Quantum Golden Collision Finding 1 Introduction 2 Preliminaries 2.1 Computational Model 2.2 Problem Description 2.3 Previous Works 3 Golden Collision Finding with Random Walks 3.1 Random Walk Search 3.2 Ambainis' Algorithm 3.3 Iteration-Based Walk 3.4 Quantum Iteration-Based Walk 3.5 Prefix-Based Walk 4 Parallelization 4.1 Prefix-Based Walk 4.2 Multi-grover Search 5 Quantum (Parallel) Collision Search 6 Security of SIKE 7 Conclusion A Quantum Circuits for Iterations A.1 Iterating the Function A.2 Finding Collisions A.3 Finding Underlying Collisions A.4 Detecting Marked Vertices B Probability Analysis References Improvements to Quantum Search Techniques for Block-Ciphers, with Applications to AES 1 Introduction 1.1 The Key-Search Problem for Block-Ciphers 1.2 Outline of This Paper 1.3 Contributions 2 Background 2.1 Quantum Computation and Quantum Algorithms 2.2 Quantum Search via Amplitude Amplification 2.3 Cryptanalysis of Blockciphers via Search and the AES 3 Exploiting the Search with Two Oracles Technique 3.1 Oracle Design Patterns for Attacking Block-Ciphers with STO 4 New Quantum Circuits and Resource Estimates for AES 4.1 Refinements to the Quantum Oracle O Specific to AES 4.2 On the Probability of Success and Introducing False-Positives 4.3 On the Level of Inner Amplification 4.4 Reducing the Cost of Partial MixColumns 4.5 Quantum Resource Estimates via Q# 5 Conclusions A Code and Disclaimer B Error Bounds for Amplitude Amplification C Oracle Costs References Post-Quantum Constructions Not Enough LESS: An Improved Algorithm for Solving Code Equivalence Problems over Fq 1 Introduction 1.1 Previous Work 1.2 Our Contributions 2 Preliminaries 2.1 Notation 2.2 Information Set Decoding 3 New Algorithm for Permutation Equivalences over Fq 4 New Algorithm for Linear Equivalences over Fq 4.1 The Algorithm in Practice 5 Conclusion References Towards Post-Quantum Security for Signal's X3DH Handshake 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries 2.1 Notation 2.2 Key Encapsulation Mechanisms 3 Instantiating Signal's X3DH Key Exchange with KEMs 3.1 X3DH: The Initial Key Agreement in Signal 3.2 A KEM-based X3DH Variant 4 Split Key Encapsulation Mechanisms 4.1 Definition of Split KEMs 4.2 X3DH with Split KEMs 4.3 Security of Split KEMs 4.4 Instantiations of Split KEMs 5 Conclusion References Trapdoor DDH Groups from Pairings and Isogenies 1 Introduction 2 Preliminaries 2.1 Computational Assumptions 2.2 Trapdoor DDH Groups 2.3 Previous Constructions 2.4 Seurin's Open Problems 3 New Trapdoor DDH Groups from Pairings and Isogenies 3.1 Our Construction 3.2 Trapdoor Pairings 3.3 Security of Our New Construction 3.4 Applications 4 Two Concrete Instantiations 4.1 Curves over Fp2 4.2 Curves over Fp 4.3 Parameter Choices 4.4 Comparison with Previous Constructions 5 Partial Attacks on Dent–Galbraith's Construction 5.1 Case r1r2 Known and Small, r1=r2 5.2 Case r1=r2 a Known Prime 6 Conclusion and Further Work References Practical Isogeny-Based Key-Exchange with Optimal Tightness 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries 2.1 Tight Reductions 2.2 Elliptic Curves, Isogenies and Endomorphism Rings 2.3 The Ideal Class Group Action 3 Isogeny-Based Key-Exchange Protocols 3.1 CSIDH 3.2 Our Protocol: -SIDE 3.3 The SIDH Case 4 Random Self-reducibility 4.1 Random Self-reducibility on CSIDH 5 Security of -SIDE 5.1 Hard Problems 6 Comparison 7 Conclusions and Open Problems A Security Model B The Security Proof References Symmetric-Key Design PRINCEv2 1 Introduction 2 Specification 2.1 PRINCE 2.2 PRINCEv2 2.3 Encryption vs. Decryption 3 Design Rationale 4 Implementation 5 Security Analysis 6 Conclusion A Code B Test Vectors References Nonce-Misuse Security of the SAEF Authenticated Encryption Mode 1 Introduction 2 Preliminaries 2.1 Coefficient H Technique 2.2 Syntax of AEAD 2.3 OAE Security 2.4 Forkcipher 3 SAEF and Its OAE Security 3.1 Security of SAEF 3.2 Integrity 3.3 Confidentiality 4 Conclusion A Appendix: Proof of Proposition 1 References WARP : Revisiting GFN for Lightweight 128-Bit Block Cipher 1 Introduction 2 Specification 3 Design Rationale 3.1 Branch Size and Permutation 3.2 S-Box 3.3 Key Schedule 3.4 Round Constants 4 Security Evaluation 5 Hardware Performance 5.1 Nibble Serial Architecture 5.2 Performance Results 5.3 Round Based and Round Unrolled Designs 6 Software Performance 6.1 On 8-Bit AVR Microcontrollers 6.2 On High-End Processors 7 Conclusion A Test Vector B Security Evaluation B.1 Differential/Linear Attack B.2 Impossible Differential Attack B.3 Integral Attack B.4 Meet-in-the Middle Attack B.5 Invariant Subspace Attack C 32-Branch Permutations with 9-Round Full Diffusion ch21ToSC:DFLM19 D More Details About Hardware Implementations D.1 Bit Serial Architecture D.2 Unified Circuit for Encryption and Decryption D.3 Threshold Implementations E More Details of Software Implementations E.1 Details of Software Implementations on 8-Bit AVR E.2 Details of Software Implementations on x64 CPUs References Side Channel Attacks Subsampling and Knowledge Distillation on Adversarial Examples: New Techniques for Deep Learning Based Side Channel Evaluations 1 Introduction, Related Work and Contributions 1.1 Introduction 1.2 Related Work 1.3 Main Contributions 2 Our Attack on the AES Implementation 2.1 Data 2.2 Attack Overview 2.3 Predicting the Hamming Weight 2.4 Combining and Post-processing Trace Predictions 2.5 Full Key Recovery 2.6 Results 3 Adversarial Examples 4 Anatomy of Our Classifiers 5 Stability Against Non-adversarial Changes in the Trace 6 Conclusions A Choice of Network Topology: Background and Intuitions References Correlation Power Analysis and Higher-Order Masking Implementation of WAGE 1 Introduction 2 Preliminaries 2.1 Description of WAGE 2.2 Adversarial Model 2.3 Masking Schemes for Side-Channel Countermeasures 3 Correlation Power Analysis of WAGE 3.1 Experimental Setup 3.2 The CPA Attack 4 The Masking Scheme for WAGE 4.1 Construction of an SNI-Secure SB 4.2 Construction of an SNI-Secure WGP 4.3 Putting All Together 5 Hardware Implementation Results 6 Conclusion and Future Work A Details on Correlation Power Analysis of WAGE References On the Influence of Optimizers in Deep Learning-Based Side-Channel Analysis 1 Introduction 2 Background 2.1 Profiling SCA and Deep Learning 2.2 Optimizers 2.3 Datasets 3 Related Works 4 The General Behavior of Optimizers in Profiling SCA 4.1 Stochastic Gradient Descent Optimizers 4.2 Adaptive Gradient Descent Methods 5 Optimizers and Specific Profiling Models 5.1 SGD Optimizers on Small MLP and CNN 5.2 SGD Optimizers on Large MLP and CNN 5.3 Adaptive Optimizers on Small MLP and CNN 5.4 Adaptive Optimizers on Large MLP and CNN 6 Conclusions A Machine Learning Classifiers B Neural Networks Hyperparameter Ranges References Cryptographic Applications On Self-equivalence Encodings in White-Box Implementations 1 Introduction 2 Preliminaries 2.1 Basics 2.2 Self-equivalences 2.3 Affine Equivalence Problems 3 CEJO Implementations 3.1 Security of CEJO Implementations 4 Self-equivalence Implementations 5 Diagonal Self-equivalences 6 Security of Self-equivalence Implementations 6.1 The Centralizer Problems 6.2 The Asymmetric Problems 7 Conclusion A Proof of Proposition 1 B Proof of Theorem 1 C Proof of Proposition 2 D Proof of Proposition 3 E Example of the Centralizer Problem F Example of the Asymmetric Problem References Protecting the Privacy of Voters: New Definitions of Ballot Secrecy for E-Voting 1 Introduction 1.1 Our Contributions 2 Preliminaries 3 Ballot Secrecy in the Honest Model 3.1 Our Balancing Condition 3.2 Satisfiability of BS 3.3 Limitation of BS 4 Extending BS to the Malicious Setting 4.1 Malicious Ballot Box Manager 4.2 Distributed and Malicious Tallier 5 A Comparison of Ballot Secrecy Definitions 5.1 Tally the `Real' Election 5.2 Tallying the Viewed Election 5.3 Summarising Our Contributions A Building Blocks for our Constructions A.1 Public-Key Encryption A.2 Threshold Public Key Encryption A.3 Signature of Knowledge B Ballot Secrecy of our Constructions B.1 Proof of Theorem 1 B.2 Proof of Theorem 2 B.3 Proof of Theorem 3 References High-Throughput Elliptic Curve Cryptography Using AVX2 Vector Instructions 1 Introduction 2 The AVX2 Instruction Set 3 Vectorized Prime-Field Arithmetic 3.1 Radix-229 Limb Vector Set 3.2 AVX2 Implementation of Field-Operations 4 (4 1)-Way Parallel Scalar Multiplication 4.1 Variable-Base Scalar Multiplication 4.2 Fixed-Base Scalar Multiplication 5 Performance Evaluation and Comparison 6 Conclusions A Source Code of Vectorized Field Operations B Source Code of (4 1)-Way Point Operations References Author Index