nach oben

2018 | Buch

Kapitel lesen Erstes Kapitel lesen

Progress in Cryptology – AFRICACRYPT 2018

10th International Conference on Cryptology in Africa, Marrakesh, Morocco, May 7–9, 2018, Proceedings

herausgegeben von: Antoine Joux, Abderrahmane Nitaj, Tajjeeddine Rachidi

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the refereed proceedings of the 10th International Conference on the Theory and Application of Cryptographic Techniques in Africa, AFRICACRYPT 2018, held in Marrakesh, Morocco, in May 2018.

The 19 papers presented in this book were carefully reviewed and selected from 54 submissions. 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).

Inhaltsverzeichnis

Frontmatter

Symmetric Cryptography

Frontmatter

A Complete Characterization of Plateaued Boolean Functions in Terms of Their Cayley Graphs

Abstract

In this paper we find a complete characterization of plateaued Boolean functions in terms of the associated Cayley graphs. Precisely, we show that a Boolean function f is s-plateaued (of weight \(=2^{(n+s-2)/2}\)) if and only if the associated Cayley graph is a complete bipartite graph between the support of f and its complement (hence the graph is strongly regular of parameters \(e=0,d=2^{(n+s-2)/2}\)). Moreover, a Boolean function f is s-plateaued (of weight \(\ne 2^{(n+s-2)/2}\)) if and only if the associated Cayley graph is strongly 3-walk-regular (and also strongly \(\ell \)-walk-regular, for all odd \(\ell \ge 3\)) with some explicitly given parameters.

Constanza Riera, Patrick Solé, Pantelimon Stănică

Chameleon-Hashes with Dual Long-Term Trapdoors and Their Applications

Abstract

A chameleon-hash behaves likes a standard collision-resistant hash function for outsiders. If, however, a trapdoor is known, arbitrary collisions can be found. Chameleon-hashes with ephemeral trapdoors (\(\mathsf {CHET}\); Camenisch et al., PKC 17) allow prohibiting that the holder of the long-term trapdoor can find collisions by introducing a second, ephemeral, trapdoor. However, this ephemeral trapdoor is required to be chosen freshly for each hash.

We extend these ideas and introduce the notion of chameleon-hashes with dual long-term trapdoors (\(\mathsf {CHDLTT}\)). Here, the second trapdoor is not chosen freshly for each new hash; Rather, the hashing party can decide if it wants to generate a fresh second trapdoor or use an existing one. This primitive generalizes \(\mathsf {CHET}\)s, extends their applicability and enables some appealing new use-cases, including three-party sanitizable signatures, group-level selectively revocable signatures and break-the-glass signatures. We present two provably secure constructions and an implementation which demonstrates that this extended primitive is efficient enough for use in practice.

Stephan Krenn, Henrich C. Pöhls, Kai Samelin, Daniel Slamanig

Ubiquitous Weak-Key Classes of BRW-Polynomial Function

Abstract

BRW-polynomial function is suggested as a preferred alternative of polynomial function, owing to its high efficiency and seemingly non-existent weak keys. In this paper we investigate the weak-key issue of BRW-polynomial function as well as BRW-instantiated cryptographic schemes. Though, in BRW-polynomial evaluation, the relationship between coefficients and input blocks is indistinct, we give out a recursive algorithm to compute another \((2^{v+1}-1)\)-block message, for any given \((2^{v+1}-1)\)-block message, such that their output-differential through BRW-polynomial evaluation, equals any given s-degree polynomial, where \(v\ge \lfloor \log _2(s+1)\rfloor \). With such algorithm, we illustrate that any non-empty key subset is a weak-key class in BRW-polynomial function. Moreover any key subset of BRW-polynomial function, consisting of at least 2 keys, is a weak-key class in BRW-instantiated cryptographic schemes like the Wegman-Carter scheme, the UHF-then-PRF scheme, DCT, etc. Especially in the AE scheme DCT, its confidentiality, as well as its integrity, collapses totally, when using weak keys of BRW-polynomial function, which are ubiquitous.

Kaiyan Zheng, Peng Wang, Dingfeng Ye

Lightweight MDS Serial-Type Matrices with Minimal Fixed XOR Count

Abstract

Many block ciphers and hash functions require the diffusion property of Maximum Distance Separable (MDS) matrices. Serial matrices with the MDS property obtain a trade-off between area requirement and clock cycle performance to meet the needs of lightweight cryptography. In this paper, we propose a new class of serial-type matrices called Diagonal-Serial Invertible (DSI) matrices with the sparse property. These matrices have a fixed XOR count (contributed by the connecting XORs) which is half that of existing matrices. We prove that for matrices of order 4, our construction gives the matrix with the lowest possible fixed XOR cost. We also introduce the Reversible Implementation (RI) property, which allows the inverse matrix to be implemented using the similar hardware resource as the forward matrix, even when the two matrices have different finite field entries. This allows us to search for serial-type matrices which are lightweight in both directions by just focusing on the forward direction. We obtain MDS matrices which outperform existing lightweight (involutory) matrices.

Dylan Toh, Jacob Teo, Khoongming Khoo, Siang Meng Sim

Two Simple Composition Theorems with H-coefficients

Abstract

We will present two new and simple theorems that show that when we compose permutation generators with independent keys, then the “quality” of CCA security increases. These theorems (Theorems 2 and 5 of this paper) are written in terms of H-coefficients (which are nothing else, up to some normalization factors, than transition probabilities). Then we will use these theorems on the classical analysis of Random Feistel Schemes (i.e. Luby-Rackoff constructions) and we will compare the results with the coupling technique. Finally, we will show an interesting difference between 5 and 6 Random Feistel Schemes. With 5 rounds on 2n bits \(\rightarrow 2n\) bits, when the number of q queries satisfies \(\sqrt{2^n} \ll q \ll 2^n\), we have some “holes” in the H-coefficient values, i.e. some H values are much smaller than the average value of H. This property for 5 rounds does not exist any more on 6 rounds.

Jacques Patarin

Improved Related-Tweakey Boomerang Attacks on Deoxys-BC

Abstract

This paper improves previous distinguishers and key recovery attacks against Deoxys-BC that is a core primitive of the authenticated encryption scheme Deoxys, which is one of the remaining candidates in CAESAR. We observe that previous attacks by Cid et al. published from ToSC 2017 have a lot of room to be improved. By carefully optimizing attack procedures, we reduce the complexities of 8- and 9-round related-tweakey boomerang distinguishers against Deoxys-BC-256 to \(2^{28}\) and \(2^{98}\), respectively, whereas the previous attacks require \(2^{74}\) and \(2^{124}\), respectively. The distinguishers are then extended to 9-round and 10-round boomerang key-recovery attacks with a complexity \(2^{112}\) and \(2^{170}\), respectively, while the previous rectangle attacks require \(2^{118}\) and \(2^{204}\), respectively. The optimization techniques used in this paper are conceptually not new, yet we believe that it is important to know how much the attacks are optimized by considering the details of the design.

Yu Sasaki

SCA-Resistance for AES: How Cheap Can We Go?

Abstract

This paper introduces a novel AES structure capable of improving the robustness against power analysis attacks while allowing for a very compact structure with a potentially negligible area and performance impact. The proposed design is based on a low entropy masking scheme, where half of the time the true value and half of the time the complemented value are used to mask the power consumption variation. The obtained experimental results suggest that the area overhead for the protection against power analysis is as low as 5% LUT increase with a performance degradation of about 10%. When compared with the state of the art supported on FPGAs, efficiency improvements above 6 times and a throughput improvement of at least two times higher are achieved.

Ricardo Chaves, Łukasz Chmielewski, Francesco Regazzoni, Lejla Batina

Cryptanalysis of 1-Round KECCAK

Abstract

In this paper, we give the first pre-image attack against 1-round KECCAK-512 hash function, which works for all variants of 1-round KECCAK. The attack gives a preimage of length less than 1024 bits by solving a system of 384 linear equations. We also give a collision attack against 1-round KECCAK using similar analysis.

Rajendra Kumar, Mahesh Sreekumar Rajasree, Hoda AlKhzaimi

Asymmetric Cryptography

Frontmatter

Performing Computations on Hierarchically Shared Secrets

Abstract

Hierarchical secret sharing schemes distribute a message to a set of shareholders with different reconstruction capabilities. In distributed storage systems, this is an important property because it allows to grant more reconstruction capability to better performing storage servers and vice versa. In particular, Tassa’s conjunctive and disjunctive hierarchical secret sharing schemes are based on Birkhoff interpolation and perform equally well as Shamir’s threshold secret sharing scheme. Thus, they are promising candidates for distributed storage systems. A key requirement is the possibility to perform function evaluations over shared data. However, practical algorithms supporting this have not been provided yet with respect to hierarchical secret sharing schemes. Aiming at closing this gap, in this work, we show how additions and multiplications of shares can be practically computed using Tassa’s conjunctive and disjunctive hierarchical secret sharing schemes. Furthermore, we provide auditing procedures for operations on messages shared hierarchically, which allow to verify that functions on the shares have been performed correctly. We close this work with an evaluation of the correctness, security, and efficiency of the protocols we propose.

Giulia Traverso, Denise Demirel, Johannes Buchmann

Development of a Dual Version of DeepBKZ and Its Application to Solving the LWE Challenge

Abstract

Lattice basis reduction is a strong tool in cryptanalysis. In 2017, DeepBKZ was proposed as a new variant of BKZ, and it calls LLL with deep insertions (DeepLLL) as a subroutine alternative to LLL. In this paper, we develop a dual version of DeepBKZ (which we call “Dual-DeepBKZ”), to reduce the dual basis of an input basis. For Dual-DeepBKZ, we develop a dual version of DeepLLL, and then combine it with the dual enumeration by Micciancio and Walter. It never computes the dual basis of an input basis, and it is as efficient as the primal DeepBKZ. We also demonstrate that Dual-DeepBKZ solves several instances in the TU Darmstadt LWE challenge. We use Dual-DeepBKZ in the bounded distance decoding (BDD) approach for solving an LWE instance. Our experiments show that Dual-DeepBKZ reduces the cost of Liu-Nguyen’s BDD enumeration more effectively than BKZ. For the LWE instance of \((n, \alpha ) = (40, 0.015)\) (resp., \((n, \alpha ) = (60, 0.005)\)), our results are about 2.2 times (resp., 4.0 times) faster than Xu et al.’s results, for which they used BKZ in the fplll library and the BDD enumeration with extreme pruning while we used linear pruning in our experiments.

Masaya Yasuda, Junpei Yamaguchi, Michiko Ooka, Satoshi Nakamura

Unified Formulas for Some Deterministic Almost-Injective Encodings into Hyperelliptic Curves

Abstract

Recently, efficient deterministic and invertible encodings on some hyperelliptic curves in genus 1 and 2 using the technique in Elligator 2 (ACM CCS 2013) have been proposed. We have successfully generalized their encodings for hyperelliptic curves of genus 3, 4 and 5. We have found unified formulas (using Mersenne numbers) for the encodings into the hyperelliptic curves of genus \(g\le 5\): \( \mathbb {H}_g : y^2=f_{g}(x)=x^{(2g+1)}+a_{(2g-1)}x^{(2g-1)} + a_{(2g-3)}x^{(2g-3)}+\ldots +a_1x+a_0\). We have conjectured that our method works on arbitrary genus.

Michel Seck, Nafissatou Diarra

HILA5 Pindakaas: On the CCA Security of Lattice-Based Encryption with Error Correction

Abstract

We show that the NISTPQC submission HILA5 is not secure against chosen-ciphertext attacks. Specifically, we demonstrate a key-recovery attack on HILA5 using an active attack on reused keys. The attack works around the error correction in HILA5. The attack applies to the HILA5 key-encapsulation mechanism (KEM), and also to the public-key encryption mechanism (PKE) obtained by NIST’s procedure for combining the KEM with authenticated encryption. This contradicts the most natural interpretation of the IND-CCA security claim for HILA5.

Daniel J. Bernstein, Leon Groot Bruinderink, Tanja Lange, Lorenz Panny

Large FHE Gates from Tensored Homomorphic Accumulator

Abstract

The main bottleneck of all known Fully Homomorphic Encryption schemes lies in the bootstrapping procedure invented by Gentry (STOC’09). The cost of this procedure can be mitigated either using Homomorphic SIMD techniques, or by performing larger computation per bootstrapping procedure.

In this work, we propose new techniques allowing to perform more operations per bootstrapping in FHEW-type schemes (EUROCRYPT’13). While maintaining the quasi-quadratic \(\tilde{O}(n^2)\) complexity of the whole cycle, our new scheme allows to evaluate gates with \(\varOmega (\log n)\) input bits, which constitutes a quasi-linear speed-up. Our scheme is also very well adapted to large threshold gates, natively admitting up to \(\varOmega (n)\) inputs. This could be helpful for homomorphic evaluation of neural networks.

Our theoretical contribution is backed by a preliminary prototype implementation, which can perform 6-to-6 bit gates in less than 10 s on a single core, as well as threshold gates over 63 input bits even faster.

Guillaume Bonnoron, Léo Ducas, Max Fillinger

Two-Face: New Public Key Multivariate Schemes

Abstract

We present here new multivariate schemes that can be seen as HFE generalization having a property called ‘Two-Face’. Particularly, we present five such families of algorithms named ‘Dob’, ‘Simple Pat’, ‘General Pat’, ‘Mac’, and ‘Super Two-Face’. These families have connections between them, some of them are refinements or generalizations of others. Notably, some of these schemes can be used for public key encryption, and some for public key signature. We introduce also new multivariate quadratic permutations that may have interest beyond cryptography.

Gilles Macario-Rat, Jacques Patarin

Cryptanalysis of RSA Variants with Modified Euler Quotient

Abstract

The standard RSA scheme provides the key equation \(ed\equiv 1\pmod {\varphi (N)}\) for \(N=pq\), where \(\varphi (N)=(p-1)(q-1)\) is Euler quotient (or Euler’s totient function), e and d are the public and private keys, respectively. It has been extended to the following variants with modified Euler quotient \(\omega (N)=(p^2-1)(q^2-1)\), which in turn indicates the modified key equation is \(ed\equiv 1\pmod {\omega (N)}\).

An RSA-type scheme based on singular cubic curves \(y^2\equiv x^3+bx^2\pmod {N}\) for \(N=pq\).
An extended RSA scheme based on the field of Gaussian integers for \(N=PQ\), where P, Q are Gaussian primes with \(p=|P|\), \(q=|Q|\).
A scheme working in quadratic field quotients using Lucas sequences with an RSA modulus \(N=pq\).

In this paper, we investigate some key-related attacks on such RSA variants using lattice-based techniques. To be specific, small private key attack, multiple private keys attack, and partial key exposure attack are proposed. Furthermore, we provide the first results for multiple private keys attack and partial key exposure attack when analyzing the RSA variants with modified Euler quotient.

Mengce Zheng, Noboru Kunihiro, Honggang Hu

Saber: Module-LWR Based Key Exchange, CPA-Secure Encryption and CCA-Secure KEM

Abstract

In this paper, we introduce Saber, a package of cryptographic primitives whose security relies on the hardness of the Module Learning With Rounding problem (Mod-LWR). We first describe a secure Diffie-Hellman type key exchange protocol, which is then transformed into an IND-CPA encryption scheme and finally into an IND-CCA secure key encapsulation mechanism using a post-quantum version of the Fujisaki-Okamoto transform. The design goals of this package were simplicity, efficiency and flexibility resulting in the following choices: all integer moduli are powers of 2 avoiding modular reduction and rejection sampling entirely; the use of LWR halves the amount of randomness required compared to LWE-based schemes and reduces bandwidth; the module structure provides flexibility by reusing one core component for multiple security levels. A constant-time AVX2 optimized software implementation of the KEM with parameters providing more than 128 bits of post-quantum security, requires only 101K, 125K and 129K cycles for key generation, encapsulation and decapsulation respectively on a Dell laptop with an Intel i7-Haswell processor.

Jan-Pieter D’Anvers, Angshuman Karmakar, Sujoy Sinha Roy, Frederik Vercauteren

Practical Fault Injection on Deterministic Signatures: The Case of EdDSA

Abstract

After recent vulnerabilities of implementations of deterministic signatures e.g. EdDSA have been revealed, it became evident that a secure deployment of those will require additional countermeasures. Nevertheless, this is not a simple task, as we show in this work. We demonstrate the easiness of fault attacks on EdDSA as implemented in the lightweight cryptographic library WolfSSL on a 32-bit micro-controller. We achieve a success rates of almost 100% by voltage glitching and electromagnetic fault injection. Even after adding certain checks as a countermeasure, the implementation remains vulnerable to fault injection. As only a single successful fault is needed to recover the key, this kind of implementation is an easy target for the attackers.

Niels Samwel, Lejla Batina

Authentication with Weaker Trust Assumptions for Voting Systems

Abstract

Some voting systems are reliant on external authentication services. Others use cryptography to implement their own. We combine digital signatures and non-interactive proofs to derive a generic construction for voting systems with their own authentication mechanisms, from systems that rely on external authentication services. We prove that our construction produces systems satisfying ballot secrecy and election verifiability, assuming the underlying voting system does. Moreover, we observe that works based on similar ideas provide neither ballot secrecy nor election verifiability. Finally, we demonstrate applicability of our results by applying our construction to the Helios voting system.

Elizabeth A. Quaglia, Ben Smyth

Shorter Double-Authentication Preventing Signatures for Small Address Spaces

Abstract

A recent paper by Derler, Ramacher, and Slamanig (IEEE EuroS&P 2018) constructs double-authentication preventing signatures (“DAP signatures”, a specific self-enforcement enabled variant of signatures where messages consist of an address and a payload) that have—if the supported address space is not too large—keys and signatures that are considerably more compact than those of prior work. We embark on their approach to restrict attention to small address spaces and construct novel DAP schemes that beat their signature size by a factor of five and reduce the signing key size from linear to constant (the verification key size remains almost the same). We construct our DAP signatures generically from identification protocols, using a transform similar to but crucially different from that of Fiat and Shamir. We use random oracles. We don’t use pairings.

Bertram Poettering

Backmatter

Titel: Progress in Cryptology – AFRICACRYPT 2018
herausgegeben von: Antoine Joux
Abderrahmane Nitaj
Tajjeeddine Rachidi
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-89339-6
Print ISBN: 978-3-319-89338-9
DOI: https://doi.org/10.1007/978-3-319-89339-6