Progress in Cryptology - AFRICACRYPT 2020: 12th International Conference on Cryptology in Africa, Cairo, Egypt, July 20 – 22, 2020, Proceedings (Lecture Notes in Computer Science (12174), Band 12174)

This book constitutes the refereed proceedings of the 12th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2020, held in Cairo, Egypt, in July 2020. The 21 papers presented in this book were carefully reviewed and selected from 49 submissions. The papers are organized in topical sections on zero knowledge, symmetric key cryptography, elliptic curves, post quantum cryptography, lattice based cryptography, side channel attacks, cryptanalysis and new algorithms and schemes. AFRICACRYPT is a major scientific event that seeks to advance and promote the field of cryptology on the African continent. The conference has systematically drawn some excellent contributions to the field. The conference has always been organized in cooperation with the International Association for Cryptologic Research (IACR). Preface Organization Contents Zero Knowledge QA-NIZK Arguments of Same Opening for Bilateral Commitments 1 Introduction 1.1 Our Results 1.2 Our Techniques 2 Preliminaries 2.1 Quasi-Adaptive Non-interactive Zero-Knowledge Proofs 2.2 Assumptions 3 Linear Relations in a Bilinear Group 3.1 Algebraic Commitment Schemes 3.2 Linear Equations in a Bilinear Group 4 Non-aggregated Scheme 5 Aggregated Scheme 6 Optimality of Our Constructions References Signatures of Knowledge for Boolean Circuits Under Standard Assumptions 1 Introduction 1.1 Our Contribution 2 Preliminaries 2.1 Definitions 2.2 Boolean Circuits 2.3 Aggregated Proofs of Quadratic Equations 2.4 Aggregated Proofs of Linear Equations 3 SE NIZK Argument for Boolean CircuitSat 3.1 Concrete USES QA-NIZK for Boolean CircuitSat 3.2 Universally Composable Signature of Knowledge 4 USS QA-NIZK Arguments of Knowledge Transfer for Linear Spaces 4.1 USS LinDk Argument 4.2 USS BLinDk Argument References LESS is More: Code-Based Signatures Without Syndromes 1 Introduction 2 Preliminaries 2.1 Coding Theory 2.2 Identification Schemes and Zero-Knowledge Protocols 3 The Code Equivalence Problem 3.1 Hardness 4 Protocol Description 5 Security Analysis 5.1 Leon's Algorithm 5.2 The Support Splitting Algorithm 5.3 Application to Linear Code Equivalence 6 Quantum Attacks on the Code Equivalence Problem 7 Signature Scheme 8 Concrete Instances 8.1 Choice of Parameters 8.2 Performance and Comparison 9 Conclusion References UC Updatable Databases and Applications 1 Introduction 2 Modular Design and FNIC 3 Functionality FUD 4 Construction UD 4.1 Building Blocks 4.2 Description of UD 5 Instantiation and Efficiency Analysis 5.1 UC ZK Proof for Relation R 5.2 Efficiency Analysis 5.3 Implementation and Efficiency Measurements 6 Modular Design with FUD and Applications 7 Related Work 8 Conclusion and Future Work References Symmetric Key Cryptography Impossible Differential Cryptanalysis of Reduced-Round Tweakable TWINE 1 Introduction 2 Specifications of T-TWINE 3 An Impossible Differential Distinguisher of T-TWINE 3.1 Observations 4 Impossible Differential Key-Recovery Attack on 27-Round T-TWINE-128 5 Impossible Differential Key-Recovery Attack on 25-Round T-TWINE-80 6 Conclusion A 18-round Impossible Differential Characteristic as Depicted in Figure8 of ch510.1007sps978sps3sps030sps26834sps3sps8 References MixColumns Coefficient Property and Security of the AES with A Secret S-Box 1 Introduction 1.1 Our Contribution 2 Preliminary 2.1 Description of the AES 2.2 Notations 2.3 Exchange Attack 3 Improved Key-Recovery Attack Based on Property 1 4 Improved Key-Recovery Attack Based on Property 2 5 Conclusion References New Results on the SymSum Distinguisher on Round-Reduced SHA3 1 Introduction 2 Preliminaries 2.1 The Keccak Hash Function 2.2 SymSum Distinguishers on SHA3 2.3 Linear Structures 3 Investigating Effect of Linear Structures on SymSum 4 Augmenting the SymSum Distinguisher 4.1 Extending SymSum Using 1-Round Linearization and -1 Trick 4.2 Extension of SymSum Distinguisher up to 3 Rounds: 5 Experimental Validation 6 Discussion 7 Conclusion References Cryptanalysis of 1 Introduction 2 Preliminaries 2.1 Internal keyed Permutation PFk 2.2 Yoyo Game 3 Iterated Truncated Differential Attacks on PFk 3.1 One Round Probabilistic Iterated Truncated Differential 3.2 Key Recovery Using Iterated Truncated Differential 3.3 Complexity Evaluation 3.4 Experimental Verification 4 Yoyo Attacks on PFk 4.1 4.2 Deterministic Distinguisher for r-round Flex-x 4.3 Key Recovery for (r+1)-round Flex-x 5 Success Probability of Distinguishing Attacks 6 Forgery Attacks on 6.1 Differential Characteristics in Sequence Generation 7 Conclusion References BBB Secure Nonce Based MAC Using Public Permutations 1 Introduction 1.1 Permutation Based Cryptography 2 Preliminaries 2.1 Public Permutation Based Nonce Based MAC 2.2 Almost Xor Universal and Almost Regular Hash Function 2.3 Expectation Method 2.4 Sum-Capture Lemma 3 Solving a System of Affine (Non)-equations 4 Security of nEHtM in Public Permutation Model 4.1 Security of nEHtMp 4.2 Matching Attack on nEHtMp 5 Proof of Theorem 2: MAC Security of nEHtMp 5.1 Definition and Probability of Bad Transcripts 5.2 Analysis of Good Transcripts 6 Proof of Lemma 2 References Elliptic Curves On Adaptive Attacks Against Jao-Urbanik's Isogeny-Based Protocol 1 Introduction 2 Preliminaries 2.1 Isogenies 2.2 SIDH 2.3 k-SIDH 2.4 The GPST Attack on Static SIDH 3 The DGLTZ Attack 4 The Jao-Urbanik Protocol 4.1 Parameter Selection 4.2 Current Impact of DGLTZ on Jao-Urbanik Protocol 5 Adaptive Attack Against the Jao-Urbanik Scheme 5.1 Attack Model: A New Oracle 5.2 Exploiting the Additional Structure: First Step 5.3 Intermediate Bit and Pullback Computation 5.4 Attack Costs for General 5.5 Comparison of k'-SIDH and Jao-Urbanik's Protocol 6 Conclusion A Querying with EB References A SAT-Based Approach for Index Calculus on Binary Elliptic Curves 1 Introduction 2 An Overview of Index Calculus 2.1 Solving the Decomposition Problem Using SAT Solvers 3 Model Description 3.1 The Algebraic Model 3.2 The CNF-XOR Model 3.3 The CNF Model 4 Breaking Symmetry 5 Time Complexity Analysis 6 Experimental Results 7 Conclusions and Future Work A Appendix References Post Quantum Cryptography Hash-Based Signatures Revisited: A Dynamic FORS with Adaptive Chosen Message Security 1 Introduction 2 Preliminaries 2.1 Notation 2.2 Hash to Obtain Random Subset (HORS) Few-Time Digital Signature Scheme 3 FORS Security Analysis 3.1 FORS in a Non-adaptive Setting 3.2 Adaptive Chosen Message Attack Against FORS 4 Dynamic Forest of Random Subsets (DFORS) 4.1 DFORS Parameters 4.2 Key Generation 4.3 Signing and ORS Generation 4.4 Signature Verification 5 Security and Efficiency 5.1 DFORS Security Analysis 5.2 Theoretical Efficiency 5.3 Comparison with HORS Variants 6 Conclusion A HORS Specification B Adaptive Chosen Message Attack against HORS References LMS vs XMSS: Comparison of Stateful Hash-Based Signature Schemes on ARM Cortex-M4 1 Introduction 2 Hash-Based Signature Schemes 2.1 One-Time Signature Schemes 2.2 Many-Time Signature Schemes 3 Comparison 3.1 Prefixes and Bitmasks 3.2 WOTS Public Key Compression 4 LMS and XMSS on the Cortex-M4 4.1 Implemented Hash Functions 4.2 Speeding up XMSS 5 Evaluation 6 Conclusion A Further Results A.1 Speed and Stack Memory References Lattice Based Cryptography Round Optimal Secure Multisignature Schemes from Lattice with Public Key Aggregation and Signature Compression 1 Introduction 2 Preliminaries 2.1 Multisignature - Syntax, Definition and Security Model 3 The MS 3.1 Security Proof 4 Accountable Subgroup Multisignature 4.1 The ASM References Sieve, Enumerate, Slice, and Lift: 1 Introduction 2 Preliminaries 2.1 Lattice Problems 2.2 Heuristic Assumptions 2.3 Lattice Enumeration 2.4 Lattice Sieving 2.5 The Randomized Slicer 2.6 Babai Lifting 3 Sieve, Enumerate, Slice, and Lift! 3.1 Hybrid 1: Sieve, Enumerate–and–Slice 3.2 Hybrid 2: Sieve, Enumerate, Slice 3.3 Hybrid 3: Sieve, Enumerate–and–Slice, Lift 3.4 Hybrid 4: Sieve, Enumerate, Slice, Lift 4 Sieve, Enumerate, Slice, Repeat! 5 Experimental Results 5.1 Verifying Assumption 4 5.2 Assessing the Sieve, Enumerate–and–Slice Hybrid A Figures and Tables B The Number of Nodes in the Enumeration Tree C Asymptotics of the Hybrid Algorithms References Side Channel Attacks Online Template Attack on ECDSA: 1 Introduction 1.1 Related Work 1.2 Contributions 2 Background 2.1 ECDSA 2.2 Double-and-Add 2.3 Montgomery Ladder 2.4 Online Template Attack 3 Spotting the Attack Vector 3.1 Finding the Similarity 3.2 Preparing the Input 4 Exploiting the Attack Vector 4.1 Measurement Setup 4.2 Bit Extraction 4.3 Countermeasures 5 Conclusion References When Similarities Among Devices are Taken for Granted: Another Look at Portability 1 Introduction 2 State of the Art 2.1 Template Attacks 2.2 Portability 3 The Issue of Portability 4 Similarity Assessment 4.1 Dynamic Time Warping 4.2 Similarity Assessment Technique 5 Experimental Results 5.1 Setup 5.2 Use Case 1: Template Attack Using One Device in Profiling Phase 5.3 Use Case 2: Template Attack Using Two Devices in Profiling Phase 6 Conclusions References Cryptanalysis A Tale of Three Signatures: Practical Attack of ECDSA with wNAF 1 Introduction 2 Preliminaries 2.1 Elliptic Curves Digital Signature Algorithm 2.2 WNAF Representation 2.3 Lattice Reduction Algorithms 3 Attacking ECDSA Using Lattices 3.1 The Extended Hidden Number Problem 3.2 Using EHNP to Attack ECDSA 3.3 Constructing the Lattice 4 Improving the Lattice Attack 4.1 Reducing the Lattice Dimension: The Merging Technique 4.2 Preprocessing the Traces 5 Performance Analysis 6 Error Resilience Analysis 7 Conclusion and Countermeasures References Attacking RSA Using an Arbitrary Parameter 1 Introduction 2 Preliminaries 3 The First Attack 3.1 Estimating Numbers of (N,e)'s Satisfying eX - uY= Z-b 4 The Second Attack 5 Comparative Analysis 6 Conclusion References New Algorithms and Schemes A New Encoding Algorithm for a Multidimensional Version of the Montgomery Ladder 1 Introduction 2 Preliminaries and Our Contributions 2.1 Preliminaries 2.2 Contributions and Organization 3 Theoretical Results 3.1 Determining the Bits of an Extension Sequence 3.2 Determining the Column Sequence and Bitstring from an Extension Matrix 3.3 Alternative Construction of an Extension Sequence 4 Optimized d-MUL 4.1 Differential Additions 5 Conclusions References New Ideas to Build Noise-Free Homomorphic Cryptosystems 1 Introduction 2 Overview 3 Some Security Results Under the Factoring Assumption 3.1 Roots of Polynomials 3.2 Symmetry 4 An Additively Homomorphic Private-Key Encryption Scheme 4.1 Externalizing the Generation of n 4.2 A Basic Attack 4.3 The Additive Operator 4.4 Efficiency 4.5 Discussion 5 Security Analysis 5.1 Knowledge of the CPA Attacker 5.2 A Fundamental Result Based on Symmetry 5.3 Attacks by Linearization 5.4 Generic IND-CPA Security 6 Perspectives 6.1 A Naive/Toy Construction of Mult 6.2 Overview 6.3 Our Proposal 6.4 Security Analysis A Implementation of Add in the Case =1 B Removing the Factoring Assumption? C Proof of Proposition 1 D Proof of Lemma 1 D.1 The Proof D.2 Extension E Proof of Lemma 2 F Proof of Proposition 5 G Proofs of Sect.5.4 G.1 Proof of Proposition 6 G.2 Proof of Proposition 7 G.3 Proof of Proposition 8 References Author Index