Selected Areas in Cryptography SAC 2023: 30th International Conference, Fredericton, Canada, August 1418, 2023, Revised Selected Papers (Lecture Notes in Computer Science Book 14201)

This book contains revised selected papers from the 30th International Conference on Selected Areas in Cryptography, SAC 2023, held in Fredericton, New Brunswick, Canada, in August 2023.The 21full papers presented in these proceedings were carefully reviewed and selected from 45 submissions. The papers are organized in the following topical sections: Cryptanalysis of Lightweight Ciphers; Side-Channel Attacks and Countermeasures; Post-Quantum Constructions; Symmetric cryptography and fault attacks; Post-Quantum Analysis and Implementations; Homomorphic encryption; Public-Key Cryptography; and Differential Cryptanalysis. Preface Organization Invited Talks Hardware Security—Directions and Challenges Robust and Non-malleable Threshold Schemes, AMD Codes and External Difference Families A Geometric Approach to Symmetric-Key Cryptanalysis Contents Cryptanalysis of Lightweight Ciphers More Balanced Polynomials: Cube Attacks on 810- And 825-Round Trivium with Practical Complexities 1 Introduction 1.1 Our Contributions 1.2 Outline 2 Preliminaries 2.1 Notation 2.2 Boolean Functions and Algebraic Degree 2.3 Pseudo-code of Trivium 2.4 Cube Attack 2.5 The Bit-Based Division Property and Monomial Prediction 3 Obtain More Balanced Polynomials 3.1 Variable Substitutions 3.2 More Balanced Polynomials by Canceling Quadratic Terms 3.3 Relationship Between a Cube and Its Subcubes 4 Application 4.1 A Key-Recovery Attack on 810-Round Trivium with Practical Complexity 4.2 A Key-Recovery Attack on 825-Round Trivium with Practical Complexity 5 Conclusion References A Closer Look at the S-Box: Deeper Analysis of Round-Reduced ASCON-HASH 1 Introduction 2 Preliminaries 2.1 Notations 2.2 Description of ASCON-HASH 3 The Attack Frameworks 3.1 The Literature and Our New Strategy 4 Collision Attacks on 2-Round ASCON-HASH 4.1 Optimizing Tk Using Simple Linear Algebra 4.2 Finding Valid (M1,M2) with Advanced Techniques 4.3 Further Optimizing the Guessing Strategy 5 Conclusion A The Algorithmic Description of ASCON-HASH B On Degree-2 S-Box References Improving the Rectangle Attack on GIFT-64 1 Introduction 2 Preliminary 2.1 Description of GIFT-64 2.2 The Rectangle Attack 2.3 The Rectangle Distinguisher of GIFT-64 3 New Rectangle Key Recovery Attack on GIFT-64 3.1 The Dedicated Model and New Key Guessing Strategy 3.2 New Rectangle Attack on GIFT-64 3.3 Complexity Analysis 4 Discussion and Conclusion References Side-Channel Attacks and Countermeasures Mask Compression: High-Order Masking on Memory-Constrained Devices 1 Introduction 2 Mask Compression 3 Security Arguments 4 Experiment: Order-31 Lattice Signatures 4.1 SampleG(z) in Hardware 4.2 Implementation Details and Basic Leakage Assessment 5 Conclusions and Open Problems References Not so Difficult in the End: Breaking the Lookup Table-Based Affine Masking Scheme 1 Introduction 2 Preliminaries 2.1 Notation 2.2 Side-Channel Analysis 2.3 Side-Channel Collision Attack 2.4 The ANSSI's AES Implementation: ASCADv2 3 Related Works 4 Vulnerability Analysis 4.1 Constant Affine Mask Shares for an Encryption 4.2 Zero Input of Affine Masking Scheme 5 Attack Results 5.1 Side-Channel Collision Attack on Canceling Mask Shares 5.2 Correlation Attack on GF(0) 6 Discussion and Protection Methods 7 Conclusions and Future Work References Threshold Implementations with Non-uniform Inputs 1 Introduction 2 Preliminaries 2.1 Glitch-Extended Bounded-Query Probing Security 2.2 Boolean Masking and Threshold Implementations 2.3 Linear Cryptanalysis of Maskings 3 Analysis of TIs with Non-uniform Inputs 3.1 Masked Prince with Non-uniform Inputs 3.2 Masked Midori64 with Non-uniform Inputs 4 Practical Evaluation and Efficiency 4.1 PROLEAD Experiments 4.2 FPGA Experiments 4.3 Efficiency Comparison 5 Conclusion A Prince S-Box Masking B Midori64 S-Box Masking C PROLEAD Experiments C.1 Designs with Uniform Randomness C.2 Midori64, Non-uniform Randomness C.3 Prince, Non-uniform Randomness C.4 Midori64, ``Secure'' Non-uniform Case, Column-Wise References Post-Quantum Constructions SMAUG: Pushing Lattice-Based Key Encapsulation Mechanisms to the Limits 1 Introduction 1.1 Our Results 2 Preliminaries 2.1 Notation 2.2 Public Key Encryption and Key Encapsulation Mechanism 2.3 Fujisaki-Okamoto Transform 3 Design Choices 3.1 MLWE Public Key and MLWR Ciphertext 3.2 Sparse Secret 3.3 Discrete Gaussian Noise 3.4 Polynomial Multiplication Using Sparsity 3.5 FO Transform, FOm 4 The SMAUG 4.1 Specification of SMAUG.PKE 4.2 Specification of SMAUGKEM 4.3 Security Proof 5 Parameter Selection and Concrete Security 5.1 Concrete Security Estimation 5.2 Parameter Sets 5.3 Decryption Failure Probability 6 Implementation 6.1 Performance 6.2 Comparison to Prior/Related Work 6.3 Security Against Physical Attacks References A Post-Quantum Round-Optimal Oblivious PRF from Isogenies 1 Introduction 2 Preliminaries 3 Oblivious Pseudorandom Functions 3.1 Security Assumptions 4 Countermeasures Against the Unpredictability Attacks 5 Countermeasures Against the SIDH Attacks 5.1 Adapting the Proof of Isogeny Knowledge 6 Verifiability 7 A New OPRF Protocol 8 Conclusion References Traceable Ring Signatures from Group Actions: Logarithmic, Flexible, and Quantum Resistant 1 Introduction 1.1 Related Work on Post Quantum Ring Signature 1.2 Contribution 1.3 Overview of Results 2 Preliminaries 2.1 Traceable Ring Signature 2.2 Security Model 2.3 Restricted Pair of Group Actions 2.4 Collision-Resistant Hash Function 2.5 Sigma Protocol 3 General Construction of Traceable Ring Signature 3.1 Our Special or Sigma Protocol for Traceable Ring Signature 3.2 Traceable Ring Signature from or Sigma Protocol 4 Analysis of Our Traceable Ring Signature Scheme 4.1 Correctness 4.2 Security 5 Instantiations 5.1 Implementation and Performance 6 Conclusion References Symmetric Cryptography and Fault Attacks The Random Fault Model 1 Introduction 2 Background 2.1 Notation 2.2 Algorithmic Representation 2.3 Random Probing Model 3 Random Fault Model 3.1 Random Fault Adversary 3.2 Security Model: Correctness 3.3 Security Model: Privacy 4 Case Studies: Random Probing Model 4.1 Influence of Duplication 4.2 Influence of Masking 4.3 Influence of Masked Duplication 4.4 Influence of Shuffling 5 Case Studies: Random Fault Correctness 5.1 Influence of Masking 5.2 Influence of Duplication 5.3 Influence of Triplication 5.4 Influence of Masked Duplication 5.5 Influence of Multiplicative Tags 5.6 Influence of Shuffling 6 Case Studies: Random Fault Privacy 6.1 Influence of Duplication 6.2 Influence of Masked Duplication 6.3 Influence of Shuffling 7 Conclusion References Probabilistic Related-Key Statistical Saturation Cryptanalysis 1 Introduction 2 Preliminaries 3 Probabilistic Related-Key Statistical Saturation Attack 3.1 Introducing a Statistical Model into RKSS Cryptanalysis 3.2 Experimental Verification of the Statistical Model 4 Improved Key Recovery Attacks on Piccolo Considering Pre- And Post-whitening 4.1 Probabilistic RKSS Attack on 10-Round Piccolo-80 4.2 Probabilistic RKSS Attack on 16-Round Piccolo-128 4.3 Probabilistic RKSS Attack on 17-Round Piccolo-128 5 Conclusion and Future Work References Compactly Committing Authenticated Encryption Using Encryptment and Tweakable Block Cipher 1 Introduction 2 Preliminaries 2.1 Tweakable Block Cipher 2.2 ccAEAD 2.3 Encryptment 3 ccAEAD Using Encryptment and TBC 3.1 Scheme 3.2 Security 4 Remotely Keyed ccAEAD 4.1 Syntax 4.2 Security Requirement 5 ECT as RK ccAEAD 5.1 Scheme 5.2 Security 6 Conclusions References Post-Quantum Analysis and Implementations Bit Security Analysis of Lattice-Based KEMs Under Plaintext-Checking Attacks 1 Introduction 2 Preliminaries 3 Side-Channel Information in Plaintext-Checking Attacks 3.1 The Meta-Structure of IND-CPA Secure KEM 3.2 Model of Plaintext-Checking Attack 3.3 Secret Leakage Model in Plaintext-Checking Attack 4 Reducing PC-Hint to Perfect Inner-Product Hint 4.1 Practical Plaintext-Checking Attack with Theoretical Lower Bound 4.2 Message Leakage in Each Query 4.3 Integrating Plaintext-Checking Hints into Lattice 5 Experiment Results 5.1 Kyber 5.2 Saber 5.3 Frodo 5.4 NewHope 6 Conclusions and Discussions References Quantum Cryptanalysis of OTR and OPP: Attacks on Confidentiality, and Key-Recovery 1 Introduction 1.1 Our Contributions 2 Preliminaries 3 Quantum Attacks on Confidentiality of OTR 3.1 Specifications of AES-OTR 3.2 IND-qCPA Attack on AES-OTR with Parallel AD Processing 3.3 IND-qCPA Attack on AES-OTR with Serial AD Processing 4 Quantum Key-Recovery Attack on OPP 4.1 Specification of OPP 4.2 Our Quantum Key-Recovery Attack References Fast and Efficient Hardware Implementation of HQC 1 Introduction 1.1 Open-Source Design 2 Hardware Design of HQC 2.1 Modules Common Across the Design 2.2 Encode and Decode Modules 2.3 Encrypt and Decrypt Modules 2.4 Key Generation 2.5 Encapsulation Module 2.6 Decapsulation Module 3 HQC Joint Design and Related Work 3.1 HQC Joint Design 3.2 Evaluation and Comparison to Existing HQC Hardware Designs 4 Conclusion References Homomorphic Encryption On the Precision Loss in Approximate Homomorphic Encryption 1 Introduction 2 Preliminaries 3 Encoding Analysis 3.1 Mapping Theory 3.2 Application to Encoding 4 Noise Analysis Methods 4.1 Bounding Noise Random Variables 4.2 Worst-Case Noise Analysis Methods 4.3 Average-Case Noise Analysis Method 4.4 Summary of Textbook Noise Heuristics 5 Application of Methods to RNS-CKKS 5.1 Differences from Textbook CKKS 5.2 Distribution of Noise Polynomials for the RNS Variant ch16SAC:CHKKS18 5.3 Summary Tables of Noise Bounds 6 Experimental Results References Secure Function Extensions to Additively Homomorphic Cryptosystems 1 Introduction 2 Related Work 3 Cryptographic Preliminaries 3.1 Linear Embeddings of Boolean Functions in Residue Sequences 3.2 Prime Numbers with Chosen Residue Symbol Sequences 4 Our Cryptosystem 4.1 Key Generation 4.2 Encryption and Decryption 4.3 Correctness of the Evaluation Function 5 Semantic Security of CS 6 Protocol 6.1 Participant Privacy During the Protocol 6.2 PB's Privacy 7 Results and Discussion 7.1 Experiments 7.2 An Example Case of Secure Function Evaluation Using 8 Conclusion References Public-Key Cryptography Generalized Implicit Factorization Problem 1 Introduction 2 Notations and Preliminaries 2.1 Lattices, SVP, and LLL 2.2 Coppersmith's Method 3 Generalized Implicit Factorization Problem 3.1 Description of GIFP 3.2 Algorithm for GIFP 4 Experimental Results 5 Conclusion and Open Problem A Details of calculations in Section3.2 References Differential Cryptanalysis CLAASP: A Cryptographic Library for the Automated Analysis of Symmetric Primitives 1 Introduction 1.1 Related Works 1.2 Our Contribution 2 Symmetric Primitives in CLAASP 2.1 The Component Class 2.2 The Cipher Class 3 Library: Evaluation Modules 4 Library: Test Modules 4.1 Component Analysis 4.2 Statistical and Avalanche Tests 4.3 Constraint Solvers for Differential and Linear Cryptanalysis 4.4 Continuous Diffusion Tests 4.5 Algebraic Module 4.6 Neural Aided Cryptanalysis Module 5 Benchmark Comparison with Other Libraries 5.1 TAGADA 5.2 CASCADA 6 Conclusion References Parallel SAT Framework to Find Clustering of Differential Characteristics and Its Applications 1 Introduction 2 Preliminaries 2.1 Definitions of Differential Characteristic and Differential 2.2 SAT-Based Automatic Search for Differential Characteristics 3 A New SAT Framework to Find the Best Differential 3.1 Our Approach 3.2 Incremental SAT Problem 3.3 Finding a Good Differential 3.4 Optimizing the Efficiency by a Multi-threading Technique 3.5 A More Efficient Algorithm to Find a Good Differential 4 Applications to PRINCE and QARMA 4.1 Good Differentials for PRINCE 4.2 Good Differentials for QARMA 4.3 Discussion: Comparison with PRINCE and QARMA 5 Conclusion References Deep Learning-Based Rotational-XOR Distinguishers for AND-RX Block Ciphers: Evaluations on Simeck and Simon 1 Introduction 1.1 Related Works 1.2 Our Contribution 1.3 Outline 2 Preliminaries 2.1 AND-RX Ciphers 2.2 Rotational-XOR (RX) Cryptanalysis 2.3 Deep Learning and Its Application on Symmetric Cryptography 3 Identification of Optimal RX Distinguishers in Cryptanalysis with Evolutionary Algorithm 3.1 AI Tools and Model Development 3.2 Training DL-Based RX Distinguishers 3.3 Evolutionary Optimization of Deep Learning RX Differential Distinguishers 4 Results and Discussion 4.1 Simeck Cipher 4.2 Simon Cipher 5 Impact of the Diffusion Layer and Optimal Rotation Parameters 6 Conclusion References Author Index