Progress in Cryptology – LATINCRYPT 2010

This paper analyzes the security of sequential multiple encryptions based on asymmetric key encryptions, and shows that a sequential construction of secure multiple encryptions exists.

The sequential multiple encryption can be proved to be indistinguishable against chosen ciphertext attacks for multiple encryptions (IND-ME-CCA), where the adversary can access to the decryption oracle of the multiple encryption, even when all the component encryptions of the multiple encryption are indistinguishable against chosen plaintext attacks (IND-CPA). We present an extended security notion of sequential multiple encryptions, in which the adversary is allowed to decrypt component encryptions in addition to access to the decryption oracle of the multiple encryption, and show that our constructed scheme satisfies it.

The notion of key privacy for asymmetric encryption schemes was formally defined by Bellare, Boldyreva, Desai and Pointcheval in 2001: it states that an eavesdropper in possession of a ciphertext is not able to tell which specific key, out of a set of known public keys, is the one under which the ciphertext was created. Since anonymity can be misused by dishonest users, some situations could require a tracing authority capable of revoking key privacy when illegal behavior is detected. Prior works on traceable anonymous encryption miss a critical point: an encryption scheme may produce a covert channel which malicious users can use to communicate illegally using ciphertexts that trace back to nobody or, even worse, to some honest user.

In this paper, we examine subliminal channels in the context of traceable anonymous encryption and we introduce a new primitive termed mediated traceable anonymous encryption that provides confidentiality and anonymity while preventing malicious users to embed subliminal messages in ciphertexts. In our model, all ciphertexts pass through a mediator (or possibly several successive mediators) and our goal is to design protocols where the absence of covert channels is guaranteed as long as the mediator is honest, while semantic security and key privacy hold even if the mediator is dishonest.

We give security definitions for this new primitive and constructions meeting the formalized requirements. Our generic construction is fairly efficient, with ciphertexts that have logarithmic size in the number of group members, while preventing collusions. The security analysis requires classical complexity assumptions in the standard model.

This paper improves the price-performance ratio of ECM, the elliptic-curve method of integer factorization. In particular, this paper constructs “a = − 1” twisted Edwards curves having Q-torsion group Z/2×Z/4, Z/8, or Z/6 and having a known non-torsion point; demonstrates that, compared to the curves used in previous ECM implementations, some of the new curves are more effective at finding small primes despite being faster; and precomputes particularly effective curves for several specific sizes of primes.

Let E be a non-supersingular elliptic curve over a finite field \(\mathbb{F}_{\!q}\). At CRYPTO 2009, Icart introduced a deterministic function \(\mathbb{F}_{\!q}\to E(\mathbb{F}_{\!q})\) which can be computed efficiently, and allowed him and Coron to define well-behaved hash functions with values in \(E(\mathbb{F}_{\!q})\). Some properties of this function rely on a conjecture which was left as an open problem in Icart’s paper. We prove this conjecture below as well as analogues for other hash functions.

A common scenario in many pairing-based cryptographic protocols is that one argument in the pairing is fixed as a long term secret key or a constant parameter in the system. In these situations, the runtime of Miller’s algorithm can be significantly reduced by storing precomputed values that depend on the fixed argument, prior to the input or existence of the second argument. In light of recent developments in pairing computation, we show that the computation of the Miller loop can be sped up by up to 37% if precomputation is employed, with our method being up to 19.5% faster than the previous precomputation techniques.

This paper presents new software speed records for the computation of cryptographic pairings. More specifically, we present details of an implementation which computes the optimal ate pairing on a 257-bit Barreto-Naehrig curve in only 4,470,408 cycles on one core of an Intel Core 2 Quad Q6600 processor.

This speed is achieved by combining 1.) state-of-the-art high-level optimization techniques, 2.) a new representation of elements in the underlying finite fields which makes use of the special modulus arising from the Barreto-Naehrig curve construction, and 3.) implementing arithmetic in this representation using the double-precision floating-point SIMD instructions of the AMD64 architecture.

We describe an FPGA accelerator for the Kannan–Fincke–Pohst enumeration algorithm (KFP) solving the Shortest Lattice Vector Problem (SVP). This is the first FPGA implementation of KFP specifically targeting cryptographically relevant dimensions. In order to optimize this implementation, we theoretically and experimentally study several facets of KFP, including its efficient parallelization and its underlying arithmetic. Our FPGA accelerator can be used for both solving stand-alone instances of SVP (within a hybrid CPU–FPGA compound) or myriads of smaller dimensional SVP instances arising in a BKZ-type algorithm. For devices of comparable costs, our FPGA implementation is faster than a multi-core CPU implementation by a factor around 2.12.

Broadcast (BC) is considered as the most fundamental primitive for fault-tolerant distributed computing and cryptographic protocols. An important and practical variant of BC is Asynchronous BC (known as A-cast). An A-cast protocol enables a specific party called sender (possibly corrupted) to send some message identically to a set of parties despite the presence of an adversary who may corrupt some of the parties in a malicious manner.

Though the existing protocol for A-cast is designed for a single bit message, in real life applications typically A-cast is invoked on long message (whose size can be in gigabytes) rather than on single bit. Therefore, it is important to design efficient multi-valued A-cast protocols (i.e protocols with long message) which extract several advantages offered by directly dealing with long messages and are far better than multiple invocations to existing protocols for single bit. In this paper, we design highly efficient, communication optimal, optimally resilient multi-valued A-cast protocol for long messages, based on access to the existing A-cast protocol for short messages. Our protocol also provides better communication complexity than existing protocol for A-cast.

A cryptographic accumulator is a scheme where a set of elements is represented by a single short value. This value, along with another value called witness, allows to prove membership into the set. If new values are added or existent values are deleted from the accumulator, then the accumulated value changes and the witnesses need to be updated. In their survey on accumulators [6], Fazio and Nicolosi noted that Camenisch and Lysyanskaya’s construction [3] was such that the time to update a witness after m changes to the accumulated value was proportional to m. They posed the question whether batch update was possible, namely if a cryptographic accumulator where the time to update witnesses is independent from the number of changes in the accumulated set exists. Recently, Wang et al. answered positively by giving a construction for an accumulator with batch update [9,10]. In this work, we show that the construction is not secure by exhibiting an attack. Moreover, we prove it cannot be fixed. If the accumulated value has been updated m times then the time to update a witness must be at least Ω(m) in the worst case.

We consider the following problem: can we construct constant-round zero-knowledge proofs (with negligible soundness) for NP assuming only the existence of one-way permutations? We answer the question in the negative for fully black-box constructions (using only black-box access to both the underlying primitive and the cheating verifier) that satisfy a natural restriction on the “adaptivity” of the simulator’s queries. Specifically, we show that only languages in coAM have constant-round zero-knowledge proofs of this kind. We also give strong evidence that we are unlikely to find fully black-box constructions of constant-round zero knowledge proofs for NP, even without this restriction on adaptivity.

Hamsi is one of the second round candidates of the SHA-3 competition. In this study, we present non-random differential properties for the compression function of Hamsi-256. Based on these properties, we first demonstrate a distinguishing attack that requires a few evaluations of the compression function. Then, we present a message recovery attack with a complexity of 2^10.48 compression function evaluations. Also, we present a pseudo-preimage attack for the compression function with complexity 2^254.25.

Misty schemes are classic cryptographic schemes used to construct pseudo-random permutations from 2n bits to 2n bits by using d pseudo-random permutations from n bits to n bits. These d permutations will be called the “internal” permutations, and d is the number of rounds of the Misty scheme. Misty schemes are important from a practical point of view since for example, the Kasumi algorithm based on Misty schemes has been adopted as the standard block cipher in the third generation mobile systems. In this paper we describe the best known “generic” attacks on Misty schemes, i.e. attacks when the internal permutations do not have special properties, or are randomly chosen. We describe known plaintext attacks (KPA), non-adaptive chosen plaintext attacks (CPA-1) and adaptive chosen plaintext and ciphertext attacks (CPCA-2) against these schemes. Some of these attacks were previously known, some are new. When d = 5 rounds, it is shown in [6] that a CPA-1 exists with complexity 2 ⁿ . We will present completely different attacks with d = 5 and the same complexity. We will also present new attacks for d ≤ 4 and d ≥ 6. For d ≥ 6 the complexity will be greater than 2²ⁿ , so these attacks will be useful only when the number of rounds d is small.

In this paper, we present an efficient cryptanalysis of the so-called HM cryptosystem which was published at Asiacrypt’1999, and one perturbed version of HM. Until now, this scheme was exempt from cryptanalysis. We first present a distinguisher which uses a differential property of the public key. This distinguisher permits to break one perturbed version of HM. After that, we describe a practical message-recovery attack against HM using Gröbner bases. The attack can be mounted in few hundreds seconds for recommended parameters. It turns out that algebraic systems arising in HM are easier to solve than random systems of the same size. Note that this fact provides another distinguisher for HM. Interestingly enough, we offer an explanation why algebraic systems arising in HM are easy to solve in practice. Briefly, this is due to the apparition of many new linear and quadratic equations during the Gröbner basis computation. More precisely, we provide an upper bound on the maximum degree reached during the Gröbner basis computation (a.k.a. the degree of regularity) of HM systems. For \({\mathbb F}_{2}\), which is the initial and usual setting of HM, the degree of regularity is upper-bounded by 3. In general, this degree of regularity is upper-bounded by 4. These bounds allow a polynomial-time solving of the system given by the public equations in any case. All in all, we consider that the HM scheme is broken for all practical parameters.

In this article, we propose a new lattice-based threshold ring signature scheme, modifying Aguilar’s code-based solution to use the short integer solution (SIS) problem as security assumption, instead of the syndrome decoding (SD) problem. By applying the CLRS identification scheme, we are also able to have a performance gain as result of the reduction in the soundness error to 1/2 per round. Such gain is also maintained through the application of the Fiat-Shamir heuristics to derive signatures from our identification scheme. From security perspective we also have improvements, because our scheme exhibits a worst-case to average-case reduction typical of lattice-based cryptosystems. This gives us confidence that a random choice of parameters results in a system that is hard to break, in average.

This article aims at showing that side-channel analyses constitute powerful tools for reverse-engineering applications. We present two new attacks that only require known plaintext or ciphertext. The first one targets a stream cipher and points out how an attacker can recover unknown linear parts of an algorithm which is in our case the parameters of a Linear Feedback Shift Register. The second technique allows to retrieve an unknown non-linear function such as a substitution box. It can be applied on every kind of symmetric algorithm (typically Feistel or Substitution Permutation Network) and also on stream ciphers.

Twelve years after the first publication about side-channel attacks, we show that the potential of these analyses has been initially seriously under-estimated. Every cryptography, either public or secret, is indeed at risk when implemented in a device accessible by an attacker. This illustrates how vulnerable cryptography is without a trusted tamper-proof hardware support.

This paper discusses the security of a leakage-resilient stream cipher presented at FOCS 2008, instantiated in a practical setting. Based on a case study, we put forward implementation weaknesses that can be exploited in a key-recovery attack. We first show that in our experimental context (8-bit device, Hamming weight leakages, Gaussian noise), a successful attack against the investigated stream cipher has lower data complexity than a similar attack against an unprotected AES implementation. We then analyze the origin of the observed weaknesses and relate them with the implementation of extractor that is used in the investigated stream cipher. We finally discuss the implications of these results for the design of leakage-resilient primitives and provide guidelines to improve the construction of FOCS 2008 and its underlying components.

Different types of implementation attacks, like those based on side channel leakage and active fault injection, are often considered as separate threats. Countermeasures are, therefore, often developed and implemented accordingly. However, Amiel et al. showed that an adversary can successfully combine two attack methods to overcome such countermeasures. In this paper, we consider instances of these combined attacks applied to RSA and elliptic curve-based cryptosystems. We show how previously proposed countermeasures may fail to thwart these attacks, and propose a countermeasure that protects the variables in a generic exponentiation algorithm in the same scenario.