Progress in Cryptology - AFRICACRYPT 2023: 14th International Conference on Cryptology in Africa, Sousse, Tunisia, July 19–21, 2023, Proceedings (Lecture Notes in Computer Science, 14064)

This volume contains the papers accepted for presentation at Africacrypt 2023, the 14th International Conference on the Theory and Application of Cryptographic Techniques in Africa. The 21 full papers included in this book were carefully reviewed and selected from 59 submissions. They were organized in topical sections as follows: Post-quantum cryptography; Symmetric cryptography; Cryptanalysis; Blockchain; Lattice-based cryptography; Implementations; Theory. Preface Organization Contents Post-quantum Cryptography MinRank in the Head 1 Introduction 2 Preliminaries 2.1 Commitment Schemes 2.2 Digital Signature Schemes 2.3 5-Pass Identification Schemes 2.4 The MinRank Problem 2.5 Multi-party Computation 3 Exceptional Sets of Matrices over a Finite Fields 4 Matrix-Multiplication Triple Verification 5 A Zero-Knowledge Protocol on the MinRank Problem 5.1 Description of the Protocol 5.2 Security Proofs 5.3 Complexity of the MinRank Problem 6 The Signature Scheme 6.1 Non-interactive Zero-Knowledge Proofs 6.2 Description of the Signature Scheme 6.3 EUF-CMA Security of the Signature Scheme 6.4 Parameters and Signature Size 7 Comparisons with Other Signatures Schemes 8 Conclusions and Future Work A Proof of Theorem 2 (Soundness) B Proof of Theorem 3 (Zero-Knowledge) C Proof of Theorem 4 (EUF-CMA) References Take Your MEDS: Digital Signatures from Matrix Code Equivalence 1 Introduction 2 Preliminaries 2.1 Cryptographic Group Actions 2.2 Protocols 3 The Matrix Code Equivalence Problem 4 Protocols from Matrix Code Equivalence 5 Matrix Equivalence Digital Signature—MEDS 6 Concrete Security Analysis 6.1 Birthday-Based Graph-Theoretical Algorithms for Solving MCE 6.2 Algebraic Attacks 6.3 Leon-Like Algorithm Adapted to the Rank Metric 7 Implementation and Evaluation 7.1 Parameter Choice and Evaluation 7.2 Comparison to Related Signature Schemes References Efficient Computation of (3n,3n)-Isogenies 1 Introduction 2 Preliminaries 2.1 Genus-2 Curves and Their Jacobians 2.2 Torsion Subgroups and Isogenies of p.p.a.s. 2.3 The Quartic Model of the Kummer Surface 3 (3,3)-Isogenies Between Jacobians 3.1 BFT Approach 3.2 Improvements 4 Non-generic (3,3)-Isogeny Formulae 4.1 (3,3)-Isogenies Between Elliptic Products 4.2 Splitting 4.3 Gluing 5 Coordinate Transformations 5.1 Explicit Formulae for Transformations 5.2 Finding the Correct Transformation 6 A (3,3)-Variant of the CGL Hash Function 6.1 Starting p.p.a.s 6.2 Optimal Strategies for (3n,3n)-Isogeny Computations 6.3 Implementation 7 Recovering Alice's Private Key in SIKE 8 Auxiliary Code References On the Post-quantum Security of Classical Authenticated Encryption Schemes 1 Introduction 2 Definitions 2.1 Notation 2.2 Symmetric Schemes 2.3 Quantum Attacks and Types of Adversaries 2.4 A Wicked PRP 3 Known Ideas and Results 3.1 Simon's Problem, -subprogram, and -algorithm 3.2 Counter- and CBC-Mode Under Superposition Queries ch4DBLP:confspspqcryptospsAnandTTU16 3.3 Quantum Period Finding Attacks ch4DBLP:confspscryptospsKaplanLLN16 3.4 Quantum Linearization for Beyond-Birthday MACs ch4DBLP:confspsasiacryptspsBonnetainLNS21 4 Privacy Under Q2 Attacks (or Lack Theorof) 4.1 GCM-SIV2 4.2 GCM 4.3 EAX 5 Accidential Protection from Q2 Attacks 5.1 The Nonce-Prefix MAC from the CCM Mode 5.2 Key Derivation, as in AES-GCM-SIV 6 Generic Approaches for Q2d and Q2 Security 6.1 Intuition 6.2 The O2H (``One-Way to Hiding'') Lemma 6.3 From Q1 Security to Q2d Security 6.4 Transitioning Q2d Security into Q2 Security 6.5 On the Tightness of the Reductions 7 Final Remarks References A Side-Channel Attack Against Classic McEliece When Loading the Goppa Polynomial 1 Introduction 2 Theoretical Background 2.1 Preliminaries 2.2 Code-Base Cryptography 3 Template Attack on Classic McEliece 3.1 Template Attacks 3.2 Measurement Setup and Leakage Analysis 3.3 Principle and Results 4 Complexity of the Goppa Polynomial Search 5 Comparison with Other Key Recovery Attacks 6 Conclusion References Symmetric Cryptography Universal Hashing Based on Field Multiplication and (Near-)MDS Matrices 1 Introduction 1.1 Our Contribution 1.2 Outline of the Paper 2 Preliminaries 2.1 and -universality 2.2 Key-then-Hash Functions 3 Parallel Universal Hashing 3.1 Construction 3.2 Propagation Probabilities of Fixed-Length Functions 3.3 Differentials over Parallel[f] and Their Differential Probability 4 Notations 5 Differential Properties of Field Multiplication 6 Duplicated Multiplication as Public Function 7 The Multiply-Transform-Multiply Construction 7.1 Maximum Image Probability of f[,] 7.2 Maximum Differential Probability of f[,] 7.3 -universality of Parallel[f[,]] 8 Multi-265 8.1 Maximum Image Probability of f-265 8.2 Maximum Differential Probability of f-265 8.3 -universality of Multi-265 8.4 Implementation Aspects References Invertible Quadratic Non-linear Functions over Fpn via Multiple Local Maps 1 Introduction 1.1 Related Works: Shift-Invariant Lifting Functions Induced by a Local Map 1.2 Our Contribution 2 Preliminary: Notation and Related Works 2.1 Notation 2.2 Related Works: Invertibility of SF over Fpn via a Quadratic Local Map F:FpmFp 3 Alternating/Cyclic Shift-Invariant Lifting Functions via Multiple Local Maps 3.1 Balanced Functions and Class of Equivalence 3.2 Necessary Conditions for Quadratic Functions F0, F1, ..., Fh-1:Fp2Fp 4 Invertible Functions SF0, F1 over Fpn via Quadratic F0, F1 : Fp2 Fp 4.1 Proof of Proposition 3 for the Case n Even 4.2 Proof of Proposition 3 for the Case n Odd 5 Invertible Functions SF0, F1 over Fpn via Linear F0 and Quadratic F1 (or Vice-Versa) 5.1 Proof of Proposition 4 for the Case n Even 5.2 Proof of Proposition 4 for the Case n3 Odd 6 Summary and Open Problems for Future Work References Poseidon2: A Faster Version of the Poseidon Hash Function 1 Introduction 1.1 Our Goals 1.2 Our Contributions and Results 2 Preliminaries: Modern Arithmetization Techniques 3 Preliminaries: ZK-Friendly Symmetric Primitives 3.1 Modes of Operation 3.2 The Poseidon Permutation 4 Security: Initial and Final Matrix Multiplications 5 More Efficient Linear Layers 5.1 Matrix for the External Round 5.2 Matrix for the Internal Round 5.3 Preventing Arbitrarily Long Subspace Trails 6 POSEIDON Specification 7 Security Analysis 7.1 Statistical Attacks 7.2 Algebraic Attacks 7.3 Attack from Bariant et al. ch8DBLP:journalsspstoscspsBariantBLP22 8 Performance Evaluation 8.1 Theoretical Comparison 8.2 Implementation and Benchmarks 8.3 Efficient Plonkish Version References From Unbalanced to Perfect: Implementation of Low Energy Stream Ciphers 1 Introduction 2 Preliminaries 2.1 Circuit Strand 2.2 Unrolled Strand Tree and Perfect m-ary Tree 2.3 Energy Consumption in Semiconductor Circuits 3 Redundant Design for Reducing Glitches 3.1 Glitches and Unbalanced Unrolled Strand Tree 3.2 Redundant Modules with the Same Delay 4 Search Algorithm 5 Applications to Stream Ciphers 5.1 Application to Trivium 5.2 Application to Kreyvium 6 Conclusion References Cryptanalysis The Special Case of Cyclotomic Fields in Quantum Algorithms for Unit Groups 1 Introduction 2 Our Improvement Seen as a Lattice Problem 2.1 Informal Presentation 2.2 Precise Statement 3 Previous Results on the Quantum Unit-Group Calculation 3.1 A Summary on CHSP 3.2 Reduction of the Computation of the Unit Group to CHSP 3.3 Exploiting Automorphisms 4 A New Algorithm Using Cyclotomic Units 4.1 Unconditional Results 4.2 Consequences of a Recent Conjecture for Cyclotomic Fields 5 Conclusion and Open Questions A An Alternative Function Hiding the Units B A Discussion on Quantum Security Levels References Improved Cryptanalysis of the Multi-Power RSA Cryptosystem Variant 1 Introduction 2 Preliminaries 3 Useful Lemmas 4 Solving the Polynomial Equation 5 Comparison with Former Methods 5.1 Comparison with the Original Method of Coppersmith 5.2 Comparison with the Method of Blömer and May 5.3 Comparison with the Method of Lu et al. 5.4 Comparison with the Method of Lu, Peng, and Sarkar 6 Applications of the New Method 6.1 Application to the Small RSA Private Exponents 6.2 Application to the Small RSA Private Exponents with Specific Prime Factors 6.3 Application for Known Most Significant Bits of the RSA Private Exponent 6.4 Application with Known Least Significant Bits of the RSA Private Exponent 6.5 Application to the Small Private Exponent in Two Variants of RSA Based on Elliptic and Edwards Curves 7 Conclusion References Blockchain The Curious Case of the Half-Half Bitcoin ECDSA Nonces 1 Introduction 2 Background and Related Work 2.1 Bitcoin 2.2 ECDSA 2.3 Lattice Problems and Algorithms 2.4 Hidden Number Problem 2.5 ECDSA as a Hidden Number Problem 3 Half Nonce Attack 3.1 Setup and Main Attack 3.2 Optimizations 4 Implementation 5 Analysis 5.1 Source Address Analysis 5.2 Attribution 6 Conclusion References Maravedí: A Secure and Practical Protocol to Trade Risk for Instantaneous Finality 1 Introduction 2 Preliminaries 2.1 Pseudorandom Function 2.2 Digital Signature Schemes 2.3 The UTXO Model 2.4 The Lightning Network 3 Desiderata 4 Outline of the Construction 5 Our Protocol: Maravedí 5.1 Intuition 5.2 Concrete Construction 6 Security Analysis 6.1 Online Security and Performance 6.2 Risk Trade Security 6.3 Desiderata 7 Final Remarks References Lattice-Based Cryptography ComBo: A Novel Functional Bootstrapping Method for Efficient Evaluation of Nonlinear Functions in the Encrypted Domain 1 Introduction 2 TFHE 2.1 Notations 2.2 TFHE Structures 2.3 TFHE Bootstrapping 3 TFHE Functional Bootstrapping 3.1 Encoding and Decoding 3.2 Functional Bootstrapping Idea 3.3 Example of Functional Bootstrapping in Z4 3.4 Multi-value Functional Bootstrapping 4 Look-Up-Tables over a Single Ciphertext 4.1 Partial Domain Functional Bootstrapping – Half-Torus 4.2 Full Domain Functional Bootstrapping – FDFB 4.3 Full Domain Functional Bootstrapping – TOTA 4.4 Full Domain Functional Bootstrapping with Composition - ComBo 5 Error Rate and Noise Variance 5.1 Noise Variance 5.2 Probability of Error 6 Experimental Results 6.1 Parameters 6.2 Error Rate 6.3 Time Performance 6.4 Wrapping-Up: Time-Error Trade-Offs 7 Conclusion References Concrete Security from Worst-Case to Average-Case Lattice Reductions 1 Introduction 1.1 Our Contributions 1.2 Overview 2 Background 2.1 Notation 2.2 Gaussian Distributions 2.3 Lattices 2.4 Learning with Errors 3 Cryptosystem 3.1 OW-CPA Secure Public Key Encryption 3.2 Correctness of Decryption 3.3 QROM IND-CCA Secure KEM 4 Proof of Security 4.1 Solving DLWE with the Help of an Adversary 4.2 Solving LWE with a DLWE Oracle 4.3 Solving SIVP with the Help of an LWE Oracle 4.4 Security Based on Hardness of SIVPR 5 Hardness Estimate 6 Parametrization 7 Conclusion A More Parametrizations References Finding and Evaluating Parameters for BGV 1 Introduction 2 Preliminaries and Mathematical Background 2.1 Cyclotomic Polynomials 2.2 Canonical Embedding and Norm 2.3 Lattices and Hermite Factor 2.4 Security of RLWE-Based Schemes 2.5 The BGV Scheme 3 Improving the Parameter Generation Process 3.1 New DCRT Bounds for Modulus Switching 3.2 New DCRT Bounds for Key Switching 3.3 Modeling the Homomorphic Circuit 3.4 Determining Modulus Sizes 3.5 Computing the Noise Bound B 3.6 Security Analysis 3.7 A Parameter Generator for BGV 4 Results 4.1 Security Parameter Evaluation 4.2 Parameter Generation 5 Conclusion References Quantum Search-to-Decision Reduction for the LWE Problem 1 Introduction 1.1 Our Contribution 1.2 Technical Overview 2 Preliminaries 2.1 Notation and Definitions 2.2 Quantum Computing 3 Search-to-Decision Reduction for the Learning with Errors Problem 3.1 Sample-Preserve Reduction 3.2 Amplify the Success Probability 4 Conclusion A Search-to-Decision Reduction for the LPN problem B Classical Search-to-Decision Reduction for the LWE B.1 A Simple Reduction B.2 Complexity of MM11 ch17MM11 References Implementations Fast Falcon Signature Generation and Verification Using ARMv8 NEON Instructions 1 Introduction 2 Previous Work 3 Background 3.1 Falcon 3.2 Dilithium 3.3 XMSS 3.4 SPHINCS+ 3.5 Hawk 4 Number Theoretic Transform Implementation 4.1 Barrett Multiplication 4.2 Montgomery Multiplication 4.3 Minimizing the Number of Barrett Reductions 4.4 Forward and Inverse NTT Implementation 5 Fast Fourier Transform Implementation 5.1 Compressed Twiddle Factor Table 5.2 Improved Forward FFT Implementation 5.3 Improved Inverse FFT Implementation 5.4 Floating-Point Complex Instructions and Data Storage 5.5 Floating-Point to Integer Conversion 5.6 Rounding Concern in Floating-Point Fused Multiply-Add 6 Results 7 Conclusions A Visualizing Complex Point Multiplication References Benchmarking and Analysing the NIST PQC Lattice-Based Signature Schemes Standards on the ARM Cortex M7 1 Introduction 1.1 Contributions 2 Background 3 Benchmarking on ARM Cortex M7 3.1 Stack Usage and RAM Size 4 Profiling on ARM Cortex M7 4.1 Rate of Acceptance in Dilithium and Falcon 4.2 Profiling Results of Dilithium and Falcon 5 Constant-Time Validation of Falcon's Floating-Point Operations 5.1 STM32 Development Boards 5.2 Raspberry Pi 3 6 Results and Discussions A The Dilithium Signature Scheme B The Falcon Signature Scheme References Theory Impossibilities in Succinct Arguments: Black-Box Extraction and More 1 Introduction 1.1 Technical Overview 1.2 Related Work 2 Preliminaries 2.1 Continuous Leakage-Resilient OWFs 2.2 Argument System 3 On Adaptively-Secure Black-Box Extraction 4 Non-adaptive Black-Box Knowledge Soundness 4.1 A Construction for FewP 4.2 Impossibility for All NP 5 GW Impossibility for Preprocessing SNARGs 6 Understanding SNARG Impossibilities 6.1 Impossibility of Gentry-Wichs References Applications of Timed-Release Encryption with Implicit Authentication 1 Introduction 1.1 Technical Overview 1.2 Related Work 2 Timed-Release Encryption with Implicit Authentication 3 Construction of a TRE-IA Scheme 4 Security Analysis 5 Performance and Integration with SecureDrop 5.1 Performance Analysis 5.2 Using TRE-IA with SecureDrop 6 Conclusion References Author Index