International Association
for Cryptologic Research

Remote Attestation (RA) is a popular means of detecting malware presence (or verifying its absence) on embedded and IoT devices. It is especially relevant to low-end devices that are incapable of protecting themselves against infection. Malware that is aware of ongoing or impending attestation and aims to avoid detection can relocate itself during computation of the attestation measurement. In order to thwart such behavior, prior RA techniques are either non-interruptible or explicitly forbid modification of storage during measurement computation. However, since the latter can be a time-consuming task, this curtails availability of device's other (main) functions, which is especially undesirable, or even dangerous, for devices with time- and/or safety-critical missions.

In this paper, we propose SMARM, a light-weight technique, based on shuffled measurements, as a defense against roving malware. In SMARM, memory is measured in a randomized and secret order. This does not impact device's availability -- the measurement process can be interrupted, even by malware, which can relocate itself at will. We analyze various malware behaviors and show that, while malware can escape detection in a single attestation instance, it is highly unlikely to avoid eventual detection.

Public key Encryption with Keyword Search (PEKS) aims in mitigating the impacts of data privacy versus utilization dilemma by allowing any user in the system to send encrypted files to the server to be searched by a receiver. The receiver can retrieve the encrypted files containing specific keywords by providing the corresponding trapdoors of these keywords to the server. Despite their merits, the existing PEKS schemes introduce a high end-to-end delay that may hinder their adoption in practice. Moreover, they do not scale well for large security parameters and provide no post-quantum security promise. In this paper, we propose novel lattice-based PEKS schemes that offer a high computational efficiency along with better security assurances than that of existing alternatives. Specifically, our NTRU-PEKS scheme achieves 18 times lower end-to-end delay than the most efficient pairing-based alternatives. Our LWE-PEKS offers provable security in the standard model with a reduction to the worst-case lattice problems. We fully implemented our NTRU-PEKS on embedded devices with a deployment on real cloud infrastructures to demonstrate its effectiveness.

We show that 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.

Supersingular isogeny Diffie-Hellman (SIDH) is a proposal for a quantum-resistant key exchange. The state-of-the-art implementation works entirely with Montgomery curves and basically can be divided into elliptic curve arithmetic and isogeny arithmetic. It is well known that twisted Edwards curves can provide a more efficient elliptic curve arithmetic. Therefore it was hinted by Costello and Hisil, that by using only Edwards curves for isogeny and curve arithmetic, or a hybrid scheme, that uses Edwards curve arithmetic and switches between the models whenever needed, a speedup in the computation may be gained.

Following the latter case, we investigated how to efficiently switch between Montgomery and twisted Edwards curves in SIDH, and how to insert Edwards arithmetic in the current state-of-the-art implementation. We did not gain a speedup compared to the results of Costello, Longa, and Naehrig, but in some cases the performance of Edwards arithmetic is almost equally fast. Thus, we suppose that a hybrid scheme does not improve the performance of SIDH, but still can be interesting for platforms having special hardware acceleration for Edwards curves. However, a full Edwards SIDH version may give a speedup, if fast Edwards isogeny formulas can be found.

Smart Cities draw a nice picture of a connected city where useful services and data are ubiquitous, energy is properly used and urban infrastructures are well orchestrated. Fulfilling this vision in our cities implies unveiling citizens data and assets. Thus, security and data privacy appear as crucial issues to consider. In this paper, we study a way of offering a secured energy management service for diagnosis and classification of buildings in a district upon their energy efficiency. Our remote service can be beneficial both for local authorities and householders without revealing private data. Our framework is designed such that the private data is permanently encrypted and that the server performing the labeling algorithm has no information about the sensitive data and no capability to decrypt it. The underlying cryptographic technology used is homomorphic encryption, allowing to perform calculations directly on encrypted data. We present here the prototype of a crypto-classification service for energy consumption profiles involving different actors of a smart city community, as well as the associated performances results. We assess our proposal atop of real data taken from an Irish residential district and we show that our service can achieve acceptable performances in terms of security, execution times and memory requirements.

We describe an approach to zero-sum partitions using Todo's division property at EUROCRYPT 2015. It follows the inside-out methodology, and includes MILP-assisted search for the forward and backward trails, and subspace approach to connect those two trails that is less restrictive than commonly done.

As an application we choose PHOTON, a family of sponge-like hash function proposals that was recently standardized by ISO. With respect to the security claims made by the designers, we for the first time show zero-sum partitions for almost all of those full 12-round permutation variants that use a 4-bit S-Box. As with essentially any other zero-sum property in the literature, also here the gap between a generic attack and the shortcut is small.

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.

In this paper we improve Wu and Wang's method for finding impossible differentials of block cipher structures. This improvement is more general than Wu and Wang's method that it can find more impossible differentials with less time. We apply it on Gen-CAST256, Misty, Gen-Skipjack, Four-Cell, Gen-MARS, SMS4, MIBS, Camellia*, LBlock, E2 and SNAKE block ciphers. All impossible differentials discovered by the algorithm are the same as Wu's method. Besides, for the 8-round MIBS block cipher, we find 4 new impossible differentials, which are not listed in Wu and Wang's results. The experiment results show that the improved algorithm can not only find more impossible differentials, but also largely reduce the search time.

Cloud storage is in widespread use by individuals and enterprises but introduces a wide array of attack vectors. A basic step for users is to encrypt their data, but it is not obvious what precise security properties are required for encryption. Furthermore, cloud storage providers often use techniques such as data deduplication for improving efficiency which restricts the application of semantically-secure encryption. Generic security goals and attack models have thus far proved elusive: primitives are considered in isolation and protocols are often proved secure under ad hoc models for restricted classes of adversaries.

We provide a generic syntax for storage systems that allows us to formally model natural security notions for cloud storage and deduplication. We define security notions for confidentiality and integrity in encrypted cloud storage and determine relations between these notions. We show how to build cloud storage systems that satisfy our defined security notions using generic cryptographic components.

A new unconditionally secure multi-party quantum commitment is proposed in this paperby encoding the committed message to the phase of a quantum state. Multi-party means that there are more than one recipient in our scheme. We show that our quantum commitment scheme is unconditional hiding and binding, and hiding is perfect. Our technique is based on the interference of phase-encoded coherent states of light. Its security proof relies on the no-cloning theorem of quantum theory and the properties of quantum information.

This paper designs and analyzes a quantum algorithm to solve a system of $m$ quadratic equations in $n$ variables over a finite field ${\bf F}_q$. In the case $m=n$ and $q=2$, under standard assumptions, the algorithm takes time $2^{(t+o(1))n}$ on a mesh-connected computer of area $2^{(a+o(1))n}$, where $t\approx 0.45743$ and $a\approx 0.01467$. The area-time product has asymptotic exponent $t+a\approx 0.47210$.

For comparison, the area-time product of Grover's algorithm has asymptotic exponent $0.50000$. Parallelizing Grover's algorithm to reach asymptotic time exponent $0.45743$ requires asymptotic area exponent $0.08514$, much larger than $0.01467$.

Scalar multiplication on Legendre form elliptic curves can be speeded up in two ways. One can perform the bulk of the computation either on the associated Kummer line or on an appropriate twisted Edwards form elliptic curve. This paper provides details of moving to and from between Legendre form elliptic curves and associated Kummer line and moving to and from between Legendre form elliptic curves and related twisted Edwards form elliptic curves. Further, concrete twisted Edwards form elliptic curves are identified which correspond to known Kummer lines at the 128-bit security level which provide very fast scalar multiplication on modern architectures supporting SIMD operations.

Side-channel attacks are a threat to cryptographic algorithms running on embedded devices. Public-key cryptosystems, including elliptic curve cryptography (ECC), are particularly vulnerable because their private keys are usually long-term. Well known countermeasures like regularity, projective coordinates and scalar randomization, among others, are used to harden implementations against common side-channel attacks like DPA. Horizontal clustering attacks can theoretically overcome these countermeasures by attacking individual side-channel traces. In practice horizontal attacks have been applied to overcome protected ECC implementations on FPGAs. However, it has not been known yet whether such attacks can be applied to protected implementations working on embedded devices, especially in a non-profiled setting. In this paper we mount non-profiled horizontal clustering attacks on two protected implementations of the Montgomery Ladder on Curve25519 available in the µNaCl library targeting electromagnetic (EM) emanations. The first implementation performs the conditional swap (cswap) operation through arithmetic of field elements (cswap-arith), while the second does so by swapping the pointers (cswap-pointer). They run on a 32-bit ARM Cortex-M4F core. Our best attack has success rates of 97.64% and 99.60% for cswap-arith and cswap-pointer, respectively. This means that at most 6 and 2 bits are incorrectly recovered, and therefore, a subsequent brute-force can fix them in reasonable time. Furthermore, our horizontal clustering framework used for the aforementioned attacks can be applied against other protected implementations.

Double-authentication-preventing signatures (DAPS) are signatures designed with the aim that signing two messages with an identical first part (called address) but different second parts (called payload) allows to publicly extract the secret signing key from two such signatures. A prime application for DAPS is disincentivizing and/or penalizing the creation of two signatures on different payloads within the same address, such as penalizing double spending of transactions in Bitcoin by the loss of the double spender's money.

So far DAPS have been constructed from very specific signature schemes not used in practice and using existing techniques it has proved elusive to construct DAPS schemes from signatures widely used in practice. This, unfortunately, has prevented practical adoption of this interesting tool so far. In this paper we ask whether one can construct DAPS from signature schemes used in practice. We affirmatively answer this question by presenting novel techniques to generically construct provably secure DAPS from a large class of discrete logarithm based signatures. This class includes schemes like Schnorr, DSA, EdDSA, and, most interestingly for practical applications, the widely used ECDSA signature scheme. The resulting DAPS are highly efficient and the shortest among all existing DAPS schemes. They are nearly half of the size of the most efficient factoring based schemes (IACR PKC'17) and improve by a factor of 100 over the most efficient discrete logarithm based ones (ACM CCS'15). Although this efficiency comes at the cost of a reduced address space, i.e., size of keys linear in the number of addresses, we will show that this is not a limitation in practice. Moreover, we generalize DAPS to any N>2, which we denote as N-times-authentication-preventing signatures (NAPS). Finally, we also provide an integration of our ECDSA-based DAPS into the OpenSSL library and perform an extensive comparison with existing approaches.

We propose a variant of the CGL hash, Charles et al. 2009, that is significantly faster than the original algorithm, and prove that it is preimage and collision resistant. For $n = \log p$ where $p$ is the characteristic of the finite field, the performance ratio between CGL and the new proposal is $(2n + 104.8) / (1.8\log n + 12.6)$. Assuming the best quantum preimage attack on the hash has complexity $O(p^{\frac{1}{4}})$, we attain a concrete speed-up for a 256-bit quantum preimage security level by a factor 70.35. For a 384-bit quantum preimage security level, the speed-up is by a factor 100.36.

A cryptographic watermarking scheme embeds message into a program while preserving its functionality. Essential security of the watermarking schemes requires that no one could remove the marking message of a marked program without substantially changing its functionality. In practical applications, it is common to mark a program with multiple different messages, e.g. in the secret leaker tracing scenarios. Thus, it is usually required that the watermarking scheme should be secure against the “collusion attacks”, where the adversary can obtain multiple watermarked programs embedded with different messages for the same functionality. However, current works in this area have not formally considered this requirement.

In this paper, we formally address the problem and give new security definition for watermarking schemes that captures the collusion attacks. Then we explore the existence of watermarking schemes secure under our new security defjnition:

– On the negative side, we observe that all current watermarking schemes either do not support multi-message embedding inherently or are vulnerable to the collusion attacks.

– On the positive side, we construct watermarking scheme secure against the collusion attacks for pseudorandom function (PRF). This is achieved by introducing a new message-embedding technique in the watermarking settings and is built on a newly presented primitive, namely, private multi-programmable PRF. Based on our watermarking scheme for PRF, we also construct watermarking schemes for various other cryptographic functionalities.

In this paper, we present new key-recovery attacks on AES with a single secret S-Box. Several attacks for this model have been proposed in literature, the most recent ones at Crypto’16 and FSE’17. Both these attacks exploit a particular property of the MixColumns matrix to recover the secret-key.

In this work, we show that the same attacks work exploiting a weaker property of the MixColumns matrix. As first result, this allows to (largely) increase the number of MixColumns matrices for which it is possible to set up all these attacks. As a second result, we present new attacks on 5-round AES with a single secret S-Box that exploit the new multiple-of-n property recently proposed at Eurocrypt’17. This property is based on the fact that choosing a particular set of plaintexts, the number of pairs of ciphertexts that lie in a particular subspace is a multiple of n.

Post-quantum cryptography has attracted much attention from worldwide cryptologists. At Asiacrypt 2017, Leander and May combines Grover and Simon algorithms to quantumly break FX-based block ciphers. In this paper, we study the Feistel constructions with Grover and Simon algorithms and give some new quantum key-recovery attacks on different rounds of Feistel constructions. Our attacks requires $2^{nr/4-3n/4}$ quantum queries. When comparing with the quantum brute force search, the time complexity is reduced by a factor of $2^{0.75n}$. When comparing with the best classical attacks, the time complexity is reduced by a factor $2^{0.5n}$ without any memory cost.

A recent paper by Costello and Hisil at Asiacrypt'17 presents efficient formulas for computing isogenies with odd-degree cyclic kernels on Montgomery curves. We provide a constructive proof of a generalization of this theorem which shows the connection between the shape of the isogeny and the simple action of the point (0,0). This generalization removes the restriction of a cyclic kernel and allows for any separable isogeny whose kernel does not contain (0,0). As a particular case, we provide efficient formulas for 2-isogenies between Montgomery curves and show that these formulas can be used in isogeny-based cryptosystems without expensive square root computations and without knowledge of a special point of order 8. We also consider elliptic curves in triangular form containing an explicit point of order 3.

The Camenisch-Lysyanskaya (CL) signature is a very popular tool in cryptography, especially among privacy-preserving constructions. Indeed, the latter benefit from their numerous features such as randomizability. Following the evolution of pairing-based cryptography, with the move from symmetric pairings to asymmetric pairings, Pointcheval and Sanders (PS) proposed at CT-RSA '16 an alternative scheme which improves performances while keeping the same properties. Unfortunately, CL and PS signatures raise concerns in the cryptographic community because they both rely on interactive assumptions that essentially state their EUF-CMA security. This lack of precise security assessment is obviously a barrier to a widespread use of these signatures and a reason for preferring other constructions, such as the ones relying on $q$-type assumptions.

In this paper, we study more thoroughly the security of these signatures and prove that it actually relies, for both constructions, on simple variants of the $\textsf{SDH}$ assumption, assuming a slight modification of the original constructions. Our work thus shows that the CL and PS signature schemes offer similar security guarantees as those provided by several other constructions using bilinear groups, and so that one can benefit from their interesting features without jeopardizing security.