Selected areas in cryptography : 28th international conference, virtual event, September 29 - October 1, 2021 : revised selected papers

This book contains revised selected papers from the 28th International Conference on Selected Areas in Cryptography, SAC 2021, held as a virtual event September and October 2021.\* The 23 full papers presented in this volume were carefully reviewed and selected from 60 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. \*The conference was originally planned to take place at the University of Victoria, BC, Canada. Due to the COVID-19 pandemic, it was held virtually. Preface Organization Invited Talks How Private is Secure Messaging? Privacy-Preserving Bluetooth Based Contact Tracing—One Size Does Not Fit All Contents Privacy and Applications On Evaluating Anonymity of Onion Routing 1 Introduction 2 High-Level Framework/Execution Environment 3 Security Goals and Notions 3.1 Interpreting Privacy Notions 3.2 A Taxonomy of Security Goals 4 Metrics 4.1 Input-Dependent Metrics 4.2 Output-Dependent Metrics 5 Adversarial Threat Model 6 Application of Our Framework 7 Conclusion References Revisiting Driver Anonymity in ORide 1 Introduction 1.1 Our Contribution 2 Analysis of ORide Protocol 2.1 ORide: A Privacy-Preserving Ride Hailing Service 2.2 ORide: Threat Model 2.3 Attack: Predicting Driver Locations 2.4 Implementation of Our Attack 2.5 Impact and Consequences of Our Attack 3 Mitigation of Our Attack 3.1 Anonymizing Driver Locations 3.2 Anonymity of Drivers with Respect to Rider 3.3 Accuracy of Ride-Matching 4 Related Works 5 Conclusion A Appendix: Further Attacks A.1 Homomorphic Noise Addition by SP A.2 p-norm Metric by SP References The Boneh-Katz Transformation, Revisited: Pseudorandom/Obliviously-Samplable PKE from Lattices and Codes and Its Application 1 Introduction 1.1 Our Contribution 1.2 Related Works 1.3 Organization 2 Definitions 2.1 Public-Key Encryption (PKE) 2.2 Tag-Based Encryption (TBE) 2.3 Weak Commitment also Known as Encapsulation 2.4 Message Authentication Code (MAC) 3 The Boneh-Katz Transformation, Revisited 4 Instantiations and Applications References ZKAttest: Ring and Group Signatures for Existing ECDSA Keys 1 Introduction 2 Preliminaries 3 Tom Curves 4 Proof of Point Addition 5 Proof of Scalar Multiplication 6 Proof of Knowledge of ECDSA Signature 7 Applications 7.1 Ring Signatures 7.2 Group Signatures 7.3 Non-revocation 8 Implementation 9 Related Work 10 Conclusion References Implementation, PUFs and MPC A Low-Randomness Second-Order Masked AES 1 Introduction 2 Preliminaries 2.1 The Bounded-Query Probing Model 2.2 Boolean Masking and Threshold Implementations 2.3 Changing of the Guards 2.4 Cryptanalysis of Higher-Order Threshold Implementations 3 A Low-Randomness Second-Order Secure AES 3.1 Masking Details 3.2 Optimizing the S-Box Sharing 3.3 Guards in Formation 4 Security Analysis 4.1 Single Round 4.2 Multiple Rounds 4.3 Security Claim 5 Sharpening the Glitch Model 6 Amortizing Randomness Over Multiple Queries 7 Conclusion A Trails in the Second-Order Masked Key Schedule B Walsh Spectra of the AES and XOR C Trails in the Second-Order Masked State D Trails in the Generation of Randomness References How Do the Arbiter PUFs Sample the Boolean Function Class? 1 Introduction 1.1 Contribution and Organization 1.2 Preliminaries 1.3 Motivation of Our Work 2 Relation Between BnPUF and Bn 3 On Restricted Autocorrelation of Arbiter PUF 3.1 Theoretical Analysis 4 Conclusion References MPC for Q2 Access Structures over Rings and Fields 1 Introduction 2 Preliminaries 2.1 Notation 2.2 Monotone and Extended Span Programs 2.3 Linear Secret Sharing Schemes Induced from MSPs and ESPs 3 Multiplication Check 3.1 MultCheck1 3.2 MultCheck1' 3.3 MultCheck2 3.4 MacCheck 3.5 Summary 4 Offline Preprocessing Protocols 4.1 Comparing Actively Secure Offline Protocols 5 Complete Protocols References Secret-Key Cryptography: Design and Proofs Multi-user Security of the Elephant v2 Authenticated Encryption Mode 1 Introduction 1.1 Elephant 1.2 Multi-user Security of Elephant v2 1.3 Outline 2 Security Model 2.1 Tweakable Block Ciphers 2.2 Authenticated Encryption 2.3 Authentication 3 Simplified Masked Even-Mansour 3.1 Specification 3.2 Multi-user Security of SiM 4 Elephant Authenticated Encryption 4.1 Specification of Elephant v2 4.2 Multi-user Security of Elephant v2 4.3 Comparison with Elephant v1 5 Proof of Theorem 2 (on Elephant) 5.1 First Step: Isolating SiM 5.2 Second Step: Simplifying Authentication 5.3 Third Step: Conclusion 6 Conclusion A Proof of Theorem 1 (on SiM A.1 Views A.2 Definition of Good and Bad Views A.3 Probability of Bad View in Ideal World A.4 Probability Ratio for Good Views A.5 Conclusion References Designing S-Boxes Providing Stronger Security Against Differential Cryptanalysis for Ciphers Using Byte-Wise XOR 1 Introduction 1.1 Our Contributions 2 Preliminaries 2.1 Basic Knowledge About S-Boxes 2.2 Basic Knowledge About Linear Layers 2.3 Differential Characteristics and Their Probabilities 2.4 How to Search for the Best Differential Characteristic 3 Designing S-Boxes Suited for EGFN 3.1 Extended Generalized Feistel Network 3.2 Identity-Differential Transitions 3.3 Replacing S-Box 4 Designing S-Boxes Suited for AES-bMC Ciphers 4.1 Definition of AES-bMC Ciphers 4.2 High-Probability Chain 4.3 Design of 4-Bit S-Boxes with Shortest High-Probability Chains 4.4 Case Study with Midori64 4.5 Case Study with SKINNY 4.6 Remark for Implementation Performance 5 Discussion and Conclusion 5.1 Evaluation of Differential Effect 5.2 On Application to Linear Cryptanalysis 5.3 Concluding Remarks References Parallel Verification of Serial MAC and AE Modes 1 Introduction 1.1 Related Work 2 Preliminaries 3 Pincer Verification of MAC Modes 4 Pincer Verification of AE Modes 5 Applications 5.1 MAC Modes 5.2 AE Modes 6 Case Study 1: Romulus 6.1 Pincer Verification of Romulus 6.2 ESP32 6.3 Implementation Details 7 Case Study 2: CMAC 8 Case Study 3: CCM 9 Conclusion References Secret-Key Cryptography: Cryptanalysis Related-Tweak Impossible Differential Cryptanalysis of Reduced-Round TweAES 1 Introduction 2 Preliminaries 2.1 Specification of TweAES 2.2 Notations and Definitions 2.3 Properties of TweAES 2.4 Impossible Differential Attack on TweAES Proposed by Designers 3 STP-Based Automatic Searching Algorithm for Related-Tweak Impossible Differential 4 Key Recovery Attack on 8-Round TweAES 4.1 The 5.5-Round Related-Tweak Impossible Differential Distinguisher of TweAES 4.2 The Key Recovery Attack on 8-Round TweAES 5 The Key Recovery Attack on 7-Round TweAES 5.1 The 5.5-Round Impossible Differential with Tweak Difference 10012 5.2 The Key Recovery Attack on 7-Round TweAES 6 Conclusions A Related-Tweak Impossible Differential Distinguisher of TweAES in Design Document ch11DBLP:journalsspstoscspsChakrabortiDJMN20 B 8-Round Key Recovery Attack on TweAES in Design Document ch11DBLP:journalsspstoscspsChakrabortiDJMN20 C The Algorithm for The Key Recovery Attack on 7-Round TweAES References Improved Attacks on GIFT-64 1 Introduction 1.1 Contributions 2 Preliminaries 2.1 Description of GIFT-64 2.2 Searching for Differential and Linear Distinguishers of GIFT-64 2.3 Complexity Analysis of the Differential Attack 2.4 Complexity Analysis of the Linear Attack 3 19-Round Linear Attack on GIFT-64 3.1 Selecting Linear Distinguishers 3.2 19-Round Linear Attack on GIFT-64 4 Differential Attack Without Using the Full Codebook 4.1 Selecting Differential Distinguishers 4.2 20-Round Differential Attack on GIFT-64 5 Conclusion References A Simpler Model for Recovering Superpoly on Trivium 1 Introduction 2 Some Background 2.1 Cube Attacks 2.2 Division Property 3 A Graph-Based Model for Superpoly Recovery 4 Strengthening the Graph-Based Model 4.1 Constrain the Doubling Paths 4.2 Use an Arity Approximation 5 Implementations 5.1 MILP 5.2 CP 5.3 Results 6 Conclusion References Automated Truncation of Differential Trails and Trail Clustering in ARX 1 Introduction 2 Preliminaries 3 Rules for Truncation 4 Differential Trail Truncation 5 Merging of Truncated Trails 6 Relaxed Rules 7 Application to Speck64 8 Distinguishing Advantage 9 Best Distinguisher for Speck64 10 Conclusion References Quantum Cryptanalysis Improved Quantum Algorithms for the k-XOR Problem 1 Introduction 2 Classical Algorithms for Many-Solutions k-XOR 2.1 Classical Merging 2.2 Wagner's Algorithm 3 Quantum Preliminaries 4 Quantum Algorithms for Many-Solutions k-XOR 4.1 Merging in the Quantum Setting 4.2 Definition of Merging Trees 4.3 From Trees to Algorithms 4.4 Optimal Trees for Many-Solutions k-XOR 5 Quantum Algorithms for Single-Solution k-XOR 5.1 Extended Merging Trees 5.2 New Results for Single-Solution k-XOR 6 Extension with Quantum Walks 6.1 Preliminaries 6.2 Using Quantum Walks in a Merging Tree 6.3 Results 6.4 Applications 7 Conclusion References Quantum Boomerang Attacks and Some Applications 1 Introduction 2 Preliminaries 2.1 The Classical Boomerang Attack 2.2 Mixing Boomerang Attacks 2.3 Quantum Tools 2.4 On Quantum Scenarios 3 Quantum Boomerang Attacks 3.1 Quantum Boomerang Distinguisher 3.2 Quantum Boomerang Last-Rounds Attack 3.3 Quantum Mixing Boomerang Distinguisher 4 Application to SAFER 4.1 Description of the Cipher 4.2 5-Round Classical Boomerang Attack 4.3 Quantum Boomerang Attack 5 Application to Related-Key AES 6 Conclusion References Post-quantum Cryptography MAYO: Practical Post-quantum Signatures from Oil-and-Vinegar Maps 1 Introduction 2 Preliminaries 3 The UOV Signature Scheme 3.1 UOV Trapdoor Function 4 Key Recovery Attacks Against UOV 4.1 Reconciliation Attack 4.2 Kipnis-Shamir Attack 4.3 Intersection Attack 5 Whipping Oil and Vinegar 6 Mayo Signatures 7 Security Analysis 8 Parameter Selection and Implementation A Proof of Lemma3 A.1 Proof of Lemma3 B Proof of Lemma8 C Proof of Lemma9 References Simple and Memory-Efficient Signature Generation of XMSSMT 1 Introduction 1.1 Background 1.2 Contribution 2 Preliminaries 2.1 Notation 2.2 XMSS 2.3 XMSSMT 2.4 Merkle Tree Traversal Algorithm 2.5 BDS Algorithm 2.6 Application of the BDS Algorithm to XMSSMT 2.7 Disadvantages of Existing Algorithms 3 Simple and Memory-Efficient Signature-Generation Algorithm for XMSSMT 3.1 Modification of BDS Algorithm 3.2 Memory-Efficient Merkle Tree Traversal (MMT) Algorithm 3.3 Application of Modified BDS and MMT Algorithms to XMSSMT 4 Correctness of Proposed Algorithm 5 Comparison with Existing Algorithms 6 Implementation 7 Conclusion References Zaytun: Lattice Based PKE and KEM with Shorter Ciphertext Size 1 Introduction 1.1 Motivations and Contributions 1.2 The Design Idea 1.3 Organizations 2 Preliminaries 2.1 Cryptographic Definitions 2.2 Lattices, Rings and Hardness Assumptions 3 The Encryption Scheme 3.1 Scheme Description 3.2 Correctness and Security 4 The Key Encapsulation Mechanism 4.1 KEM Description 4.2 Correctness and Security 5 Parameter Settings 5.1 Parameter Settings 5.2 Comparison with Other Schemes References A Polynomial Time Key-Recovery Attack on the Sidon Cryptosystem 1 Introduction 2 The Sidon Cryptosystem 2.1 Sidon Spaces 2.2 Description of the Cryptosystem 2.3 Equivalent Keys for the Sidon Cryptosystem 3 Analysis of the Underlying MinRank Problem 3.1 Restricting the Number of the Solutions 3.2 Generic Solutions Over Fqn 3.3 Rank 1 Codewords in Dmat from the Sidon Structure 4 Solving the MinRank Instance over Fqk 4.1 Parity-check Modeling 4.2 Complexity of Solving the System Fspec 5 Finding an Equivalent Sidon Space V' 5.1 Targeting an Element of the Form lambdauv[j] 5.2 Deducing V from t 6 Conclusion References Isogenies Verifiable Isogeny Walks: Towards an Isogeny-Based Postquantum VDF 1 Introduction 2 Background 2.1 Elliptic Curves 2.2 Time-Sensitive Cryptography and Verifiable Delay Functions 3 An Isogeny-Based Delay Function 3.1 Evaluation Overview 4 SNARG-Based Verification 4.1 Arithmetization 4.2 Overview of the SNARG Construction 4.3 Parallelization of the Proof Construction 5 Security Analysis 6 Conclusions and Future Work References Towards Post-Quantum Key-Updatable Public-Key Encryption via Supersingular Isogenies 1 Introduction 2 Preliminaries 2.1 Isogenies and Isogeny-Based Cryptography 3 Key-Updatable Public-Key Encryption (UPKE) 3.1 Security 4 Assessing Isogeny-Based UPKE 5 Symmetric UPKE via SIDH 5.1 Choosing and Getting Auxiliary Points 6 Symmetric UPKE Construction via CSIDH 7 Future Research Directions 8 Conclusion A Proof of CSIDH-Based UPKE References Secret Keys in Genus-2 SIDH 1 Preliminaries 1.1 PPSSAS 1.2 G2SIDH 2 Keyspace 2.1 Symplectic Basis 2.2 Classification of Secret Keys 2.3 New Uniform Sampling from the Keyspace 3 Adaptive Attack on G2SIDH 3.1 Attack Model and Oracle 3.2 Symplectic Transformations 3.3 Case Distinction 3.4 Kernels of Rank 2 3.5 Kernels of Rank 3 3.6 Adaptive Attack on Arbitrary Basis References Author Index