[Lecture Notes in Computer Science] Selected Areas in Cryptography – SAC 2019 Volume 11959 (26th International Conference, Waterloo, ON, Canada, August 12–16, 2019, Revised Selected Papers) ||

This book contains revised selected papers from the 26th International Conference on Selected Areas in Cryptography, SAC 2019, held in Waterloo, ON, Canada, in August 2019. The 26 full papers presented in this volume were carefully reviewed and selected from 74 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, cryptography for the Internet of Things. Preface Organization Block Cipher Modes of Operation and Provable Security (Abstract of Invited Talk) Contents Invited Talks Looking Back—My Life as a Mathematician and Cryptographer 1 Overview 2 SAC and Me 3 Cribbage 4 Math Contests 5 Ross Honsberger 6 From High School to University 7 The 1974 ``Special K'' Math Contest 8 Ron Mullin 9 Graduate Studies 10 Easing into the World of Computer Science 11 Cryptography 12 What Is Combinatorial Cryptography? 13 Shannon and the One-Time Pad 14 My Paper with Jim Massey 15 Research Philosophy 16 Some Influential Books 17 Mathematical Exposition 18 How to Turn a Complex Mystery into a Simple Truth 19 Photo 20 Dedications References Supersingular Isogeny Key Exchange for Beginners 1 Introduction 2 The Set of Supersingular j-invariants 3 Isogenies 4 Isogeny Graphs 5 Walking Through the Protocol 6 SIDH in Practice 7 Security and Cryptanalysis References Differential Cryptanalysis Probabilistic Mixture Differential Cryptanalysis on Round-Reduced AES 1 Introduction 1.1 A New Secret-Key Distinguisher for up to 5-Round AES 1.2 New Key-Recovery Attack on 6-Round AES-128 2 Preliminary – Description of AES 3 Subspace Trail Cryptanalysis 3.1 Subspace Trails of AES 3.2 Intersections of Subspaces and Useful Probabilities 4 ``Multiple-of-8'' and Mixture Differential Cryptanalysis 5 A New 5-Round Secret-Key Distinguisher for AES 5.1 5-Round Probabilistic Mixture Differential Distinguisher 5.2 Data and Computational Complexity 5.3 Practical Verification on Small Scale AES 6 Key-Recovery Attack on 6 Rounds of AES-128 A Subspace Trails for AES B Proof – Probabilities of Sect.3.2 B.1 Pairs with n Equal Generating ``Variables in (F28)|I|'' C Distinguisher on 5-Round AES – Cost D Variant of the 5-Round AES Distinguisher of Sect.5 E Key-Recovery Attack on 6-Round AES – Cost References Iterative Differential Characteristic of TRIFLE-BC 1 Introduction 2 Preliminaries 2.1 Notation 2.2 Specification of TRIFLE 2.3 Security Claim of TRIFLE 3 1-Round Iterative Differential Characteristic of TRIFLE-BC 4 Application 4.1 Distinguishing Attack on Reduced TRIFLE-BC 4.2 Forgery Attack on Reduced TRIFLE 4.3 Key-Recovery Attack on Reduced TRIFLE 4.4 Experiments 5 Conclusion References Tweakable Block Ciphers Plaintext Recovery Attacks Against XTS Beyond Collisions 1 Introduction 2 Preliminaries 2.1 Basic Notations 2.2 Tweakable Block Cipher 3 Specification of XTS 3.1 LRW Mode 4 Attack Model 5 Overview of Our Attacks 6 Collision Attack at Reference Sector 7 Plaintext-Recovery Attacks at Target Sector 7.1 Partially-Known Plaintext Attack 1 7.2 Partially-Known Plaintext Attack 2 7.3 Ciphertext-Only Attack 8 Practical Impact 9 Conclusion References Cryptanalysis of SKINNY in the Framework of the SKINNY 2018–2019 Cryptanalysis Competition 1 Introduction 2 A Brief Description of SKINNY 3 Remark on the Provided Messages 4 Mining Truncated Differentials in the Provided Datasets 4.1 Search Strategy 4.2 Truncated Distinguishers of SKINNY Instances 5 Attacking 12-Round SKINNY-64-128 5.1 Our Truncated Differential Trail 5.2 From the Truncated Differential Path to the Attack: The Key Recovery Part 5.3 Details on the Practical Execution of the Attack 5.4 On the Choice of the Distinguisher 6 Attacking 10-Round SKINNY-128-128 6.1 Key-Recovery Using Truncated Differentials 6.2 Details on the Practical Execution of the Attack 6.3 On the Choice of the Distinguisher 7 Conclusion References Block Ciphers and Permutations Algebraic Cryptanalysis of Variants of Frit 1 Introduction 2 Description of Frit 3 Algebraic Degree of Frit and Frit-1 3.1 Designers' Analysis of Frit 3.2 Algebraic Degree of Frit-1 3.3 (Conditional) Initial Structures and Integral Distinguishers 4 Key-Recovery Attacks on Keyed Frit 4.1 Simple Key-Recovery Attack Using Chosen Ciphertexts 4.2 Optimized Interpolation Attack Using Chosen Plaintexts 4.3 Key Recovery and Attack Complexity 5 Conclusion A Symbolic Evaluation with Sage References Improved Interpolation Attacks on Cryptographic Primitives of Low Algebraic Degree 1 Introduction 2 Preliminaries 2.1 Basic Constructions for Block Ciphers 2.2 Polynomial Algorithms 3 Low-Memory Interpolation Attacks 3.1 Interpolation Attacks 3.2 Leading Terms of the Output 3.3 New Attacks 4 Attacks on Block Ciphers with Simple Key Schedules 4.1 Iterative Low-Memory Interpolation Attacks 4.2 Attacks Based on Guess-and-Determine Strategies 5 Applications to MiMC 5.1 Description of MiMC 5.2 Attacks on a Variant with Low Memory Complexity 5.3 Attacks on Larger Key Versions 5.4 Verification on MiMC over Small Fields 6 Concluding Remarks A Algorithm for Computing E(K,xi)-yi References A General Frameworkfor the Related-Key Linear Attack Against Block Ciphers with Linear Key Schedules 1 Introduction 1.1 Our Contributions 1.2 Related Works 1.3 Organization of the Paper 2 Terminology and Notations 3 Description of the Framework 3.1 A Related-Key Linear Approximation 3.2 Description of Algorithm RKLC-1 3.3 Description of Algorithm RKLC-2 3.4 Statistical Model, Success Probability and Attack Complexities 4 Related-Key Linear Attacks on Round-Reduced Simon 4.1 The Simon Family of Block Ciphers 4.2 Related-Key Linear Approximations of Simon 4.3 Adding Outer Rounds 4.4 Attacks on Round-Reduced Simon 5 Experiments 5.1 Experiments with Variants of Simon 5.2 Experiments with a Variant of Present-128 6 Discussions 6.1 Statistical Models 6.2 Linear Trails, Linear Hulls, and Multiple Linear Approximations 6.3 Comparison with Single-Key Linear Attacks 6.4 Application to Tweakable Blockciphers 7 Conclusions A Searching Method for the Linear Trails of SIMON B Linear Trails of Simon C Adding More Rounds to Related-Key Linear Approximations of Simon C.1 Adding 3+3 Rounds C.2 Adding 4+4 Rounds C.3 Adding 5+5 Rounds D Application of FWHT to Related-key Linear Attacks E Additional Results with Present-L F Keys and Data Used in the Experiments F.1 Experiments with the Small-scale Simon F.2 Experiments with Present-L References Real-World Cryptography Towards a Practical Cluster Analysis over Encrypted Data 1 Introduction 1.1 This Work 1.2 Related Works 2 Backgrounds 2.1 Notations 2.2 Approximate Homomorphic Encryption HEAAN 2.3 Non-polynomial Operations in HEAAN 2.4 Mean-Shift Clustering 2.5 Clustering Quality Evaluation Criteria 3 HE-Friendly Modified Mean-Shift Clustering 3.1 HE-Friendly Kernel 3.2 Mode-Seeking Phase 3.3 Point-Labeling Phase 3.4 Our Modified Mean-Shift Clustering Algorithm 4 Experimental Results 4.1 Dataset Description 4.2 Parameter Selection 4.3 Experimental Results References Breaking the Bluetooth Pairing – The Fixed Coordinate Invalid Curve Attack 1 Introduction 1.1 Bluetooth Versions 1.2 The Elliptic Curve Diffie-Hellman Protocol 1.3 Previous Work 1.4 Our Results 1.5 Structure of the Paper 2 Bluetooth Pairing 2.1 LE Secure Connections 2.2 Secure Simple Pairing (SSP) 3 The Invalid Curve Attack 3.1 The Group Operation 3.2 Private Key Retrieval 4 Our Attack 4.1 A Semi-Passive Attack 4.2 Fully-Active MitM Attack 4.3 Success Rate 5 Design Flaws and Mitigations 5.1 Design Flaws 5.2 Mitigations 5.3 Insufficient Mitigation 6 Vulnerable Platforms 6.1 Vulnerable Bluetooth Low Energy Platforms 6.2 Vulnerable Bluetooth BR/EDR Platforms 7 Practical Considerations 7.1 Over the Air Implementation 7.2 Public Key Manipulation 7.3 Encoding of the Point-at-Infinity 8 Summary A Bluetooth Versions References Using TopGear in Overdrive: A More Efficient ZKPoK for SPDZ 1 Introduction 2 Preliminaries 3 n-Prover Zero Knowledge-Protocols 4 A n-Prover ZKPoK for SPDZ 5 SPDZ Offline Phase 6 Results A Parameter Size Table B Experimental Data C Run Time Graphs References On the Real-World Instantiability of Admissible Hash Functions and Efficient Verifiable Random Functions 1 Introduction 2 Admissible Hash Functions 2.1 Instantiating AHFs from Error Correcting Codes 2.2 Efficiency Bounds on Admissible Hash Functions 3 Computational Admissible Hash Functions 3.1 cAHFs from Truncation Collision Resistant Hash Functions 4 Verifiable Random Functions from cAHFs 4.1 VRF Construction 4.2 Comparison of VRF Instantiations A Verifiable Random Functions and Their Security B Proof of Theorem 5 C Full Proof of VRF Security D Further comparisons References Stream Ciphers and Lightweight Cryptography Tight Security Bounds for Generic Stream Cipher Constructions 1 Introduction 2 Stream Cipher Basics 2.1 Keystream Generation 2.2 Large-State-Small-Key Ciphers 2.3 Continous-IV-Use Ciphers 3 Time-Memory-Data Tradeoff Attacks and Small State Ciphers 3.1 The TMD-TO Attack of Babbage and Golić 3.2 New Stream Cipher Constructions 4 Overview of the Model and Results 4.1 Main Results 5 A Random Oracle Model for Stream Ciphers 6 Analysis 6.1 Near Collision and the Friendly Alice 6.2 Formalizing Computations by Transcripts 6.3 Bad Elementary Events and Bad Transcripts and the Idea of the Proof of Theorem 1 6.4 The Structure of the Probability Space Omega(tau) 6.5 The Proof of Lemma 4 7 Conclusion A Comparison of the Two Schemes References On the Data Limitation of Small-State Stream Ciphers: Correlation Attacks on Fruit-80 and Plantlet 1 Introduction 2 Correlation Attacks on Grain-Based Stream Ciphers 2.1 Notations 2.2 Grain-Based Stream Ciphers 2.3 Linear Approximations for Correlation Attacks 2.4 Key-Recovery Algorithm Based on FWHT 2.5 Use of Multiple Linear Masks 3 Correlation Attacks on Small-State Stream Ciphers 3.1 Involving Round Keys 3.2 Finding Multiple Linear Approximations with High Correlation 3.3 Exploiting Keystream Generated from Different IVs 4 Cryptanalysis on Full Fruit-80 4.1 Specification of Fruit-80 4.2 Enumerating Linear Masks with High Correlation 4.3 Correlation Attack against Fruit-80 5 Plantlet 5.1 Specification 5.2 Enumerating Linear Masks with High Correlation 5.3 Correlation Attack Against Plantlet 6 Conclusion A Correlation of g't "426830A L(t), "526930B on Fruit-80 B Correlation of gt'' "426830A L(t), ' "526930B of Plantlet References A Lightweight Alternative to PMAC 1 Introduction 2 Preliminaries 3 Our Proposal 3.1 Description of LAPMAC 3.2 Security of LAPMAC 3.3 Instantiations of Tweak Function 4 Security Proof 4.1 Proof of Theorem1 4.2 Proof of Lemma2 5 Conclusions A Proof of Lemma3 References Post-quantum Analysis An Improved Security Analysis on an Indeterminate Equation Public Key Cryptosystem by Evaluation Attacks 1 Introduction 1.1 Our Contribution 1.2 Remark 1.3 Organization 2 Preliminary 2.1 IE-LWE Problem 2.2 Smallest-Solution Problem 3 Description of Giophantus and Known Attacks 3.1 Giophantus and IE-LWE Problem 3.2 Linear Algebra Attack 3.3 Vercauteren et al.'s Evalution Attack 4 Our Evaluation Attack 5 Experiments on Our Attack 6 Modification of IE-LWE Problem 7 Conclusion References Ternary Syndrome Decoding with Large Weight 1 Introduction 1.1 Binary vs. Ternary Case 1.2 State of the Art for q 3 1.3 Our Contributions 1.4 Notations 2 A General Framework for Solving the Syndrome Decoding Problem 2.1 The Syndrome Decoding Problem 2.2 The PGE+SS Framework in Fq 2.3 Analysis of the Algorithm 2.4 Reduction to the Subset Sum Problem 2.5 Application to the PGE+SS Framework with High Weight 3 Ternary Subset Sum with the Generalized Birthday Algorithm 3.1 A Brief Description of Wagner's Algorithm 3.2 Smoothing of Wagner's Algorithm 4 Ternary Subset Sum Using Representations 4.1 Basic Idea 4.2 Partial Representations 4.3 Presentation of Our Algorithm 4.4 Application to the Syndrome Decoding Problem 4.5 Summary of Our Results 5 New Parameters for the WAVE Signature Scheme 6 Hardest Instances of Ternary Syndrome Decoding 7 Conclusion A Appendix: Ternary Representations A.1 Notations A.2 Main Result A.3 A Simple Example A.4 Typical Case A.5 Computation of the Typical Case A.6 Number of Representations and Badly-formed Elements References Exploring Trade-offs in Batch Bounded Distance Decoding 1 Introduction 2 Preliminaries 2.1 The Geometric Series Assumption and `Z-Shaped' Bases 2.2 Decoding Small-Secret LWE 2.3 The Hybrid Meet-in-the-Middle and Lattice Reduction Attack 3 A Spectrum of Decoding Approaches 4 Estimates A Meet-in-the-Middle B Case Study: NTRU LPrime References On Quantum Slide Attacks 1 Introduction 2 Preliminaries 2.1 Classical Slide Attacks 2.2 The Attack Model 2.3 Quantum Slide Attacks 2.4 Quantum Hidden Shift Algorithms 3 Quantum Slide-Shift Attacks 3.1 Key-Alternating Cipher with Modular Additions 3.2 Feistel Scheme with One Round Self-similarity and Modular Additions 3.3 The Quantum Complementation Slide Attack 3.4 Sliding with a Twist 4 Composing Quantum Attacks: Key-Recovery with Strong Round Functions 4.1 General Attack 4.2 With the Same Branch and Key Addition 5 Advanced Quantum Slide Attacks on Feistels 5.1 Mirror Slidex Attack on 2k-WFeistel 5.2 Attacking 4k-Feistel and 4k-WFeistel 5.3 Enhanced Reflection Attack 6 On Quantum Attacks Exploiting Cycle Finding 6.1 Definition of a Cycle Slide Attack 6.2 Quantization of a Cycle-Based Slide Attack 7 Conclusion A Summary of Classical Slide Attacks B Quantum Cycle-Based Slide Attacks C Slide Attack on a Four-Round Self-similar Feistel References Post-quantum Implementations XMSS and Embedded Systems 1 Introduction 2 Preliminaries 2.1 XMSS 2.2 SHA-256 3 RISC-V 4 Software Implementation and Optimization 5 Hardware Acceleration 5.1 General-Purpose SHA-256 Accelerator 5.2 XMSS-Specific SHA-256 Accelerator 5.3 WOTS-chain Accelerator 5.4 XMSS-leaf Generation Accelerator 6 Performance Evaluation 7 Related Work 8 From XMSS to SPHINCS 9 Conclusion References A Timing Attack on the HQC Encryption Scheme 1 Introduction 2 Background 3 The HQC Encryption Scheme 3.1 Setup 3.2 Key Generation 3.3 Encryption 3.4 Decryption 3.5 Security and Instantiation 4 Timing Attack Against HQC 4.1 Spectrum Recovery 4.2 Reconstructing y from Partial Information on Its Spectrum 5 Analysis 5.1 Distinguishing Distances Inside and Outside the Spectrum 5.2 Probabilistic Analysis of the Key Reconstruction Algorithm 6 Experimental Results 6.1 Performance of the Key Reconstruction Algorithm 6.2 Communication Cost 7 Discussion on Countermeasures 8 Conclusion References Block-Anti-Circulant Unbalanced Oil and Vinegar 1 Introduction 2 Preliminaries 3 Multivariate Quadratic Signature Schemes 3.1 Unbalanced Oil and Vinegar 3.2 Petzoldt's Compression Technique 3.3 Field Lifting 3.4 Irredundant S 4 Compression with Block-Anti-Circulant Matrices 4.1 Description 4.2 Security 4.3 Parameters and Comparison 4.4 Implementation 5 Conclusion References Symmetric Cryptography A DFA Attack on White-Box Implementations of AES with External Encodings 1 Introduction 2 Preliminaries 2.1 The Advanced Encryption Standard 2.2 Assumptions 3 The New Attack 3.1 Overview of the Attack 3.2 Step 1: Pre-compute Sets of Inputs 3.3 Step 2: Determine a State up to Affine Functions 3.4 Step 3: From Functions over F28 to Functions over F28 3.5 Step 4: Determine a Non-encoded State 3.6 Step 5: Standard DFA 4 Conclusions A Finding the Location to Inject Faults in Step 2 B Reducing the Number of Variables C Work Factor References Parallelizable Authenticated Encryption with Small State Size 1 Introduction 2 Preliminaries 2.1 Notation 2.2 (Tweakable) Blockcipher 2.3 Authenticated Encryption 2.4 Computation on Galois Field 3 Review of OCB and OTR 3.1 OCB 3.2 OTR 4 Our Proposals 4.1 Overview 4.2 OCB-hc 4.3 Security of OCB-hc 4.4 OTR-hc 4.5 Security of OTR-hc 5 Extensions 5.1 Arbitrary Tag Length 5.2 OCB-hc with AD 5.3 Security of OCB-hc-AD 6 Discussion on the Security Bounds of Proposals 7 Conclusion A Proof of Security of Phash-hc B Proof of the Security of OCB-hc-AD References Deep Neural Network Attribution Methods for Leakage Analysis and Symmetric Key Recovery 1 Introduction 1.1 Contribution 1.2 Related Work 1.3 Structure of the Paper 2 Preliminaries 2.1 Deep Learning-Based Profiled Side-Channel Analysis 2.2 Deep Neural Network Attribution Methods 3 Attribution for POI Analysis 3.1 Side-Channel Heatmaps 3.2 Experimental Results 4 Evaluating Side-Channel Heatmaps 4.1 KRPC 4.2 ZB-KGE 4.3 Limitations 5 Attribution as a Distinguisher 6 Conclusion A Network Parameters References Post-quantum Constructions BBQ: Using AES in Picnic Signatures 1 Introduction 2 Preliminaries 2.1 Efficient NIZKPoK in the MPC-in-the Head Paradigm 2.2 The Picnic Signature Scheme 2.3 The Advanced Encryption Standard 3 Computing the S-Box 3.1 Computing the Inversion 3.2 Need for Non-Zero Input 3.3 Application to Picnic Signatures 4 Alternative Computations of the AES S-Box References Towards Practical GGM-Based PRF from (Module-)Learning-with-Rounding 1 Introduction 1.1 Tools and Techniques 1.2 Optimized Implementations 2 Preliminaries 2.1 GGM Construction 2.2 Hardness Assumptions 3 Our Construction 3.1 Lower-Depth GGM-based PRF 3.2 (M)LWR-based PRG 3.3 Construction Outline 4 Security Analysis 4.1 GGM 4.2 LWE and (M)LWR 5 Implementation 5.1 Design 5.2 Parameters 5.3 Performance A LWR-based PRG A.1 Construction A.2 Implementation References Author Index