Progress in Cryptology - AFRICACRYPT 2022: 13th International Conference on Cryptology in Africa, AFRICACRYPT 2022 Fes, Morocco, July 18–20, 2022 Proceedings

Description

This book constitutes the refereed proceedings of the 13th International Conference on Progress in Cryptology in Africa, AFRICACRYPT 2022, held in Fes, Morocco, from July 18th - 20th, 2022.  The 25 papers presented in this book were carefully reviewed and selected from 68 submissions. The papers are organized in topical sections on symmetric cryptography; attribute and identity based encryption; symmetric cryptanalysis; post-quantum cryptography; post-quantum (crypt)analysis; side-channel attacks; protocols and foundations; public key (crypt) analysis. Preface Organization Contents Symmetric Cryptography Construction of Recursive MDS Matrices Using DLS Matrices 1 Introduction 2 Definition and Preliminaries 2.1 Finite Fields and MDS Matrices 2.2 XOR Count 3 Construction of MDS Matrices from DLS Matrices 3.1 Diagonal-Like Sparse (DLS) Matrices 3.2 Equivalence Classes of DLS Matrices to Construct Recursive MDS Matrices 3.3 Equivalence of DLS Matrices with Sparse DSI Matrices 4 Construction of MDS Matrices from Generalized DLS Matrices 4.1 Construction of 44 Recursive MDS Matrices 4.2 Construction of 55 Recursive MDS Matrices 4.3 Construction of 66 Recursive MDS Matrices 4.4 Construction of 77 Recursive MDS Matrices 4.5 Importance of GDLS Matrices 5 Conclusion and Future Work References FUTURE: A Lightweight Block Cipher Using an Optimal Diffusion Matrix 1 Introduction 2 Definition and Preliminaries 2.1 MDS Matrix 2.2 Boolean Function and Sbox 3 Structure of FUTURE 3.1 Round Function 4 Design Decision 4.1 SubCell 4.2 MixColumn 4.3 Round Key 5 Security Analysis 5.1 Differential and Linear Cryptanalysis 5.2 Impossible Differential Attacks 5.3 Boomerang Attack 5.4 Integral Attack 5.5 Invariant Subspace Attacks 5.6 Meet-in-the-Middle Attacks 5.7 Algebraic Attacks 6 Hardware Implementations, Performance and Comparison 6.1 FPGA Implementation 6.2 ASIC Implementation 7 Conclusions A Test Vectors References A Small GIFT-COFB: Lightweight Bit-Serial Architectures 1 Introduction 1.1 Contributions 1.2 Roadmap 2 Preliminaries 2.1 GIFT-COFB 2.2 Swap-and-Rotate Methodology 3 GIFT-COFB-SER-S 3.1 Implementing the Feedback Function 3.2 Multiplication by 2 and 3 3.3 GIFT-COFB-SER-S Total Latency 4 GIFT-COFB-SER-F 4.1 Tweaking the Feedback Function 4.2 Reordering Data Bits 4.3 Enhancing the Multiplier 4.4 GIFT-COFB-SER-F Total Latency 5 First-Order Threshold Implementation 5.1 GIFT-COFB-SER-TI First-Order Threshold Implementation 5.2 Evaluation 6 Implementation 7 Conclusion A Swap-and-Rotate GIFT-128 State Pipeline B ANF Equations of the 3-Share GIFT-128S-Box References Attribute and Identity Based Encryption Identity-Based Encryption in DDH Hard Groups 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries 2.1 Notations and Conventions 2.2 Identity-Based Key Encryption 2.3 Signature Schemes 2.4 Witness Encryption 2.5 Smooth Projective Hash Functions 2.6 The Generic Group Model 3 Construction 3.1 Unique Signatures Based on DDH 3.2 Witness Encryption Based on DDH 3.3 Modified Generic Construction 4 Discussion 4.1 The PVR Impossibility Result ch4EPRINT:PapRacVah12 4.2 Shortcomings of the PVR Impossibility Result 5 Conclusions References TinyABE: Unrestricted Ciphertext-Policy Attribute-Based Encryption for Embedded Devices and Low-Quality Networks 1 Introduction 1.1 Our Contributions 2 High-level Overview and Details About TinyABE 3 Preliminaries 3.1 Notation 3.2 Access Structures 3.3 Ciphertext-policy ABE 3.4 Security Model 3.5 Pairings (or Bilinear Maps) 3.6 Pair Encoding Schemes 4 Our Construction: TinyABE 4.1 Removing the Bounds from AC16 4.2 The Scheme 4.3 The Associated Pair Encoding Scheme 5 Security Proof 5.1 ``Unbounding'' the AC17 Proof of AC16 5.2 The Selective Property 5.3 The Co-selective Property 6 Performance Analysis 6.1 Computational Costs of TinyABE 6.2 Comparison with RW13 and AC16/Att19 6.3 Advantages in Low-Quality Networks and Constrained Devices 7 Future Work References Symmetric Cryptanalysis Cryptanalysis of Reduced Round SPEEDY 1 Introduction 2 Preliminaries 2.1 Specification of SPEEDY 2.2 SPEEDY Instances and Security Claims 2.3 Cube Attacks 3 Practical Distinguishers for Two Rounds SPEEDY 3.1 Core Idea of Distinguishers 3.2 Distinguishers with 214 Data 3.3 Distinguishers with 213 Data 3.4 Discussion on the Proofs of Distinguishers 4 Key Recovery Attacks 4.1 3-Round Key Recovery Attack 4.2 On Improving Number of Rounds for Key Recovery 5 Conclusion A SPEEDY Round Constants References And Rijndael? 1 Introduction 2 Rijndael 3 The Solving Process 3.1 Constraint Programming 3.2 Two-Step Solving Process 3.3 Step 1 3.4 Step 2 4 Results 5 Attacks 5.1 Attack on 12 Rounds of Rijndael-128-224 5.2 Attack on 12 Rounds of Rijndael-160-256 6 Conclusion References Breaking Panther 1 Introduction 2 Specification of Panther 2.1 State Update Function F 3 Main Observation on Panther 3.1 An Observation on F4 3.2 Consequences in a Known Ciphertext only Setting 4 Cryptanalysis of Panther 4.1 Key-Recovery Attack with One Plaintext/Ciphertext Pair 4.2 Plaintext-Recovery Attack with One Known Ciphertext 4.3 Forging Attacks 5 Implementation 5.1 Repairing Panther 6 Conclusion References Automated Key Recovery Attacks on Round-Reduced Orthros 1 Introduction 2 Preliminaries 2.1 Specification of Orthros 2.2 Differential Cryptanalysis 2.3 Differential-Linear Cryptanalysis 3 Differential-Linear Attack on 7-Round Orthros 3.1 Previous Approaches for Automated Key Recovery Attacks 3.2 Framework of Mounting Key Recovery Attacks on Orthros 3.3 Implement Our Framework with STP 3.4 Key Recovery Attack on 7-Round Orthros 4 Differential Attack on Orthros 5 Conclusion and Future Work A Integral Key Recovery Attacks on Orthros B Differential-Like Attacks Considering Two Rounds Prepended C Permutations Adopted in Orthros D DDT, LAT and DLCT for the Sbox of Orthros References Post-quantum Cryptography Dilithium for Memory Constrained Devices 1 Introduction 2 Preliminaries 2.1 Dilithium 3 Dilithium Signature Generation 3.1 Streaming A and y 3.2 Compressing w 3.3 Compressing cs1, cs2, and ct0 3.4 Variable Allocation 3.5 Summary of Optimizations 4 Dilithium Key Generation and Signature Verification 4.1 Key Generation 4.2 Signature Verification 5 Results and Discussion 6 Conclusions and Future Work References Lattice-Based Inner Product Argument 1 Introduction 2 Preliminaries 3 Lattice-Based Inner Product 3.1 The Protocol 3.2 Security Analysis 3.3 Efficiency Analysis and Parameters Setting 4 Optimized Inner Product Argument 4.1 Splitting Rings 4.2 Ring Isomorphism 4.3 Algebraic Structure of Our Commitment 4.4 Correctness of the Inner Product 4.5 Zero-Knowledge Inner Product Argument over Splitting Rings 4.6 Efficiency Analysis and Parameters Setting References Streaming SPHINCS+ for Embedded Devices Using the Example of TPMs 1 Introduction 2 Preliminaries 2.1 SPHINCS+ 2.2 Trusted Platform Modules 3 Design and Implementation 3.1 Streaming Interface 3.2 TPM Prototype and Streaming Extension 3.3 Considerations on Fault Attacks 4 Evaluation 4.1 Streaming Interface 4.2 TPM Integration 5 Conclusion References Post-quantum (Crypt)analysis Solving the Learning Parity with Noise Problem Using Quantum Algorithms 1 Introduction 2 Preliminaries 2.1 Fourier Analysis over Finite Abelian Groups 2.2 Significant Fourier Coefficients 2.3 Quantum Computing 2.4 Learning Parity with Noise 3 Solving Techniques 3.1 Gaussian Elimination and Information Set Decoding 3.2 Exhaustive Search 3.3 Walsh-Hadamard Transform 3.4 Quantum Complexity Analysis for EXH and WHT Solvers 3.5 Significant Fourier Transform 4 Results 5 Conclusion A Reductions A.1 Reduction: Sparse-Secret A.2 Reduction: Part-Reduce (LF1) and Xor-Reduce (LF2) A.3 Reduction: Drop-Reduce A.4 Reduction: Code-Reduce A.5 Reduction: Guess-Reduce B Graph of Reductions B.1 Finding Optimal -valid Chains B.2 Optimizing the build() Algorithm References An Estimator for the Hardness of the MQ Problem 1 Introduction 2 Preliminaries 2.1 General Notation 2.2 Computational Complexity 2.3 The MQ Problem 2.4 General Strategies for Underdetermined Systems 3 Algorithms for Solving MQ 3.1 Exhaustive Search 3.2 Algorithms Designed for Underdetermined Systems 3.3 Gröbner Basis 3.4 Hybrid Algorithms 3.5 Probabilistic Algorithms 4 Algorithms Not Considered in Our Estimator 5 The Estimator 5.1 Description/Usage 5.2 Numerical Results 5.3 Security of MPKCs Against the Direct Attack References Recovering Rainbow's Secret Key with a First-Order Fault Attack 1 Introduction 1.1 Organization 2 Background 2.1 The Rainbow Signature Scheme 2.2 Conventions in the Specification 2.3 Fault Attacks 3 Full Key Recovery Attacks 3.1 Attack 1: Full Key Recovery from Fixed Vinegar Variables 3.2 Attack 2: Secret Key Recovery by Skipping the Linear Transformation S 4 Code Analysis and Simulation 4.1 Attack 1: Fixing the Vinegar Variables 4.2 Attack 2: Skipping the Linear Transformation S 4.3 Simulation 4.4 Applicability to Other Implementations 5 Countermeasures 5.1 Countermeasures for Attack 1 5.2 Countermeasures for Attack 2 6 Conclusion References Side-Channel Attacks TransNet: Shift Invariant Transformer Network for Side Channel Analysis 1 Introduction 2 Preliminaries 2.1 Notations 2.2 Profiling SCA Using Deep Learning 3 Transformer Network 3.1 Embedding Layer 3.2 Multi-head Self-attention Layer 3.3 Position-Wise Feed-Forward Layer 3.4 Positional Encoding 3.5 Layer Normalization 4 TransNet: A Transformer Network for SCA 5 Long Distance Dependency and Shift-Invariance 5.1 Learning Long Distance Dependency Using TN 5.2 Shift-Invariance of Transformer Network 6 Experimental Results 6.1 Datasets Details 6.2 Other State-of-the-Art Methods 6.3 Hyper-parameter Setting of TransNet 6.4 Results on ASCAD Datasets 6.5 Experimental Results on the Other Datasets 6.6 Verifying the Shift Invariance of TransNet 7 Discussion 8 Conclusion A Proof of Lemma 1 B Proof of Proposition 1 C Comparison with CNN Using Global Pooling Model D Sensitivity of EffCNN to Profiling Desynchronization References To Overfit, or Not to Overfit: Improving the Performance of Deep Learning-Based SCA 1 Introduction 2 Background 2.1 Profiling SCA 2.2 Overfitting and Underfitting 2.3 Deep Double Descent Phenomenon 2.4 Overfitting and Generalization in Side-channel Analysis 3 Experimental Setup 3.1 Datasets 3.2 Analysis Methodology 4 Experimental Results 4.1 ASCAD Random Keys Dataset 4.2 AES_HD Dataset 4.3 Influence of Regularization Techniques 4.4 Reducing Assumption Error by Changing Hyperparameters 4.5 General Observations 5 Conclusions and Future Work References Protocols and Foundations A Secure Authentication Protocol for Cholesteric Spherical Reflectors Using Homomorphic Encryption 1 Introduction 2 Background and Related Work 3 The Proposed Protocol 3.1 Extraction of Robust Features 3.2 Protocol Description 3.3 Enrollment Phase 3.4 Authentication Phase 4 Security Analysis 5 Implementation 5.1 Dataset 5.2 Homomorphic Encryption Implementation 5.3 Performance of Enrollment and Authentication Phases 6 Conclusions and Future Work References Card-Minimal Protocols for Three-Input Functions with Standard Playing Cards 1 Introduction 1.1 Card-Based Protocols with a Standard Deck of Cards 1.2 Existing Protocols 1.3 Contribution 1.4 Related Work 1.5 Outline 2 Preliminaries 2.1 Operations 2.2 Random Cut 2.3 Random Bisection Cut (RBC) 2.4 The Niemi–Renvall AND Protocol 2.5 Swapping by Commitment Value 3 Three-Input Majority Protocol 3.1 Two-Input or Protocol 3.2 Idea 3.3 Description of Protocol 3.4 Correctness and Security 4 Generic Protocol for Three-Input Functions 4.1 Idea 4.2 Generalizing the Niemi–Renvall and Protocol 4.3 Generalizing Swap Operation by Commitment Value 4.4 Description of Protocol 4.5 Covered Functions 5 Conclusion References A Random Oracle for All of Us 1 Introduction 1.1 The Universal Random Oracle Model 1.2 Defining Universal Random Oracles 1.3 Relationship to Auxiliary-Input Random Oracles 1.4 Relationship to Global Random Oracles 1.5 Proving Security in the UROM 2 Preliminaries 2.1 Negligible Functions 2.2 Security Games 2.3 The Random Oracle Model 2.4 One-Wayness in the Random Oracle Model 3 The Universal Random Oracle Model UROM 4 UROM vs. AI-ROM 4.1 AI-ROM 4.2 AI-ROM Implies UROM 4.3 UROM Implies AI-ROM 4.4 Advantages of UROM 5 Universal Random Oracles are One-Way Functions 6 Conclusion A Defining Universal Random Oracles References Public Key (Crypt)analysis DiSSECT: Distinguisher of Standard and Simulated Elliptic Curves via Traits 1 Introduction 2 Background 2.1 Overview of Standard Curve Generation 3 Methodology 3.1 Standard Curve Database 3.2 Simulations 3.3 Outlier Detection 4 Traits 4.1 Notable Findings 5 Our Tool DiSSECT 6 Conclusions A List of traits References Co-factor Clearing and Subgroup Membership Testing on Pairing-Friendly Curves 1 Introduction 2 Preliminaries 3 Polynomial Families of Pairing-Friendly Curves, and Faster Co-factor Clearing 3.1 Faster Co-factor Clearing 3.2 Construction 6.6 3.3 Constructions 6.2, 6.3, 6.4, and 6.5 with D=1 3.4 Construction 6.7 with D=2 3.5 Other Constructions 4 Subgroup Membership Testing 4.1 G1 and GT Membership 4.2 G2 Membership 4.3 A Generalisation of G1 and G2 Membership Tests 5 Conclusion References A Generalized Attack on the Multi-prime Power RSA 1 Introduction 2 Preliminaries 3 The New Attack 4 Comparison with Former Methods 4.1 Comparison with Factorization Methods 4.2 Comparison with the Method of Lu et al. 5 Estimating the Number of Weak Keys 6 Conclusion References Finding Low-Weight Polynomial Multiples Using the Rho Method 1 Introduction 1.1 Variants of the Low-Weight Polynomial Multiple Problem 1.2 Previous Work 1.3 Contributions 2 Preliminaries 3 Foundational Work: Distribution of weight(X1+…+Xk) 3.1 Expectation of weight(X1+…+Xk) 3.2 PMF of weight(X1+…+Xk) 3.3 CDF of weight(X1+…+Xk) 4 Solving SWPM Using the Rho Technique 4.1 Overview of the Algorithms in ch24ElAimani2021 4.2 First Algorithm for SWPM 4.3 Second Algorithm for SWPM 5 Solving SWPM Using the Nested Rho Method 5.1 Overview of the Idea 5.2 The Algorithm 6 Performance and Extensions 6.1 Comparison with the State-of-the-Art 6.2 Time/Memory Trade-Off Algorithms 6.3 Deeper Nesting of Rho References EHNP Strikes Back: Analyzing SM2 Implementations 1 Introduction 1.1 Background 1.2 Our Results 2 Preliminaries 2.1 SM2 Digital Signature 2.2 Scalar Multiplication and Side-Channel Attack 2.3 EHNP 2.4 Lattice 2.5 Lattice Reduction and Sieve 3 Generic EHNP Attack on SM2 Implementations 3.1 EHNP from Sliding-Window 3.2 EHNP from wNAF 3.3 Modifying EHNP 3.4 EHNP to SVP in Sublattice 3.5 SVP with Predicate 3.6 Attack Algorithm for SM2 4 Analysis of SM2-EHNP 4.1 Expected Norm of Target Vector 4.2 Data-Probability Tradeoff 4.3 Non-shortness of Target Vector 4.4 Experiments and Performance 5 Conclusion References Author Index