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)

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