Catálogo de publicaciones - libros

At Financial Crypto 2006, Golle presented a novel framework for the privacy preserving computation of a stable matching (stable marriage). We show that the communication complexity of Golle’s main protocol is substantially greater than what was claimed in that paper, in part due to surprising pathological behavior of Golle’s variant of the Gale-Shapley stable matching algorithm. We also develop new protocols in Golle’s basic framework with greatly reduced communication complexity.

Known compact e-cash schemes are constructed from signature schemes with efficient protocols and verifiable random functions. In this paper, we introduce a different approach. We construct compact e-cash schemes from bounded accumulators. A bounded accumulator is an accumulator with a limit on the number of accumulated values. We show a generic construction of compact e-cash schemes from bounded accumulators and signature schemes with certain properties and instantiate it using an existing pairing-based accumulator and a new signature scheme. Our scheme revokes the secret key of the double-spender directly and thus supports more efficient coin tracing. The new signature scheme has an interesting property that is has the message space of a cyclic group equipped with a bilinear pairing, with efficient protocol to show possession of a signature without revealing the signature nor the message. We show that the new scheme is secure in the generic group model. The new signature scheme may be of independent interest.

We present a new design principle for building a batch processing protocol for interactive proofs. First, a generic method to achieve batch processing is proposed when dealing with an NP-relation with certain homomorphicity. It is shown that the method preserves zero-knowledgeness and knowledge-soundness. Second, for some NP-relation that has no such homomorphicity, we illustrate that the relation can be decomposed into a homomorphic relation(hence we have a batch process) and another NP-relation that is proven using an efficient protocol. Such a decomposition provides an advantage in terms of efficiency.

This report studies timing attacks on NTRUEncrypt based on variation in the number of hash calls made on decryption. The attacks apply to the parameter sets of [8,6]. To mount the attacker, an attacker performs a variable amount of precomputation, then submits a relatively small number of specially constructed ciphertexts for decryption and measures the decryption times. Comparison of the decryption times with the precomputed data allows the attacker to recover the key in greatly reduced time compared to standard attacks on NTRUEncrypt. The precomputed data can be used for all keys generated with a specific parameter set and tradeoffs exist that increase the amount of precomputation in order to decrease the time required to recover an individual key. For parameter sets in [3] that claim -bit security but are vulnerable to this attack, we find that an attacker can typically recover a single key with about /2 bits of effort.

Finally, we describe a simple means to prevent these attacks by ensuring that all operations take a constant number of SHA calls. The recommended countermeasure does not break interoperability with the parameter sets of [8,6] and has only a slight effect on performance.

This paper announces a new software side-channel attack — enabled by the branch prediction capability common to all modern high-performance CPUs. The penalty paid (extra clock cycles) for a mispredicted branch can be used for cryptanalysis of cryptographic primitives that employ a data-dependent program flow. Analogous to the recently described cache-based side-channel attacks our attacks also allow an unprivileged process to attack other processes running in parallel on the same processor, despite sophisticated partitioning methods such as memory protection, sandboxing or even virtualization. In this paper, we will discuss several such attacks for the example of RSA, and experimentally show their applicability to real systems, such as OpenSSL and Linux. Moreover, we will also demonstrate the strength of the branch prediction side-channel attack by rendering the obvious countermeasure in this context as useless. Although the deeper consequences of the latter result make the task of writing an efficient and secure modular exponentiation (or scalar multiplication on an elliptic curve) a challenging task, we will eventually suggest some countermeasures to mitigate branch prediction side-channel attacks.

In this article we discuss different types of template attacks on masked implementations. All template attacks that we describe are applied in practice to a masked AES software implementation on an 8-bit microcontroller. They all break this implementation. However, they all require quite a different number of traces. It turns out that a template-based DPA attack leads to the best results. In fact, a template-based DPA attack is the most natural way to apply a template attack to a masked implementation. It can recover the key from about 15 traces. All other attacks that we present perform worse. They require between about 30 and 1800 traces. There is no difference between the application of a template-based DPA attack to an unmasked and to a masked implementation. Hence, we conclude that in the scenario of template attacks, masking does not improve the security of an implementation.

Side-channel attacks on block ciphers and public key algorithms have been discussed extensively. However, there is only sparse literature about side-cannel attacks on stream ciphers. The few existing references mainly treat timing [8] and template attacks [10], or provide a theoretical analysis [6], [7] of weaknesses of stream cipher constructions. In this paper we present attacks on two focus candidates, Trivium and Grain, of the eSTREAM stream cipher project. The attacks exploit the resynchronization phase of ciphers. A novel concept for choosing initial value vectors is introduced, which totally eliminates the algorithmic noise of the device, leaving only the pure side-channel signal. This attack allows to recover the secret key with a small number of samples and without building templates. To prove the concept we apply the attack to hardware implementations of the ciphers. For both stream ciphers we are able to reveal the complete key.

We introduce a new robust cache-based timing attack on AES. We present experiments and concrete evidence that our attack can be used to obtain secret keys of remote cryptosystems if the server under attack runs on a multitasking or simultaneous multithreading system with a large enough workload. This is an important difference to recent cache-based timing attacks as these attacks either did not provide any supporting experimental results indicating if they can be applied remotely, or they are not realistically remote attacks.

Privacy concerns in many aspects of electronic communication trigger the need to re-examine – with privacy in mind – familiar security services, such as authentication and key agreement.

An Group Key Agreement (AH-AGKA) protocol (also known as ) allows a set of participants, each with a certificate issued by the same authority, to establish a common authenticated secret key. In contrast to standard AGKA protocols, an AH-AGKA protocol has the following privacy feature: If Alice, who is a member of a group , participates in an AH-AGKA protocol, none of the other protocol participants whether Alice is a member of , unless these participants are themselves members of group . Such protocols are useful in suspicious settings where a set of members of a (perhaps secret) group need to authenticate each other and agree on a common secret key, without revealing their affiliations to outsiders.

In this paper we strengthen the prior definition of AH-AGKA so that the security and privacy properties are maintained under any composition of protocol instances. We also construct two novel AH-AGKA protocols secure in this new and stronger model under the RSA and Gap Diffie-Hellman assumptions, respectively. Each protocol involves only two communication rounds and few exponentiations per player (e.g., no bilinear map operations). Interestingly, these costs are essentially the same as those of the underlying () group key agreement protocol. Finally, our protocols, unlike prior results, retain their security and privacy properties without the use of one-time certificates.

In this paper, we propose an efficient password-authenticated key exchange (PAKE) based on RSA, called RSA-EPAKE. Unlike SNAPI using a prime pubic key greater than an RSA modulus , RSA-EPAKE uses the public key of a 96-bit prime, where  = 2(, ) + 1 for some . By the Prime Number Theorem, it is easy to find such an . But the probability that an adversary finds and with is less than 2. Hence, in the same as SNAPI, RSA-EPAKE is also secure against -residue attacks. The computational load on Alice (or Server) and Bob (or Client) in RSA-EPAKE is less than in the previous RSA-based PAKEs such as SNAPI, PEKEP ,CEKEP, and QR-EKE. In addition, the computational load on Bob in RSA-EPAKE is less than in PAKEs based on Diffie-Hellman key exchange (DHKE) with a 160-bit exponent. If we exclude perfect forward secrecy from consideration, the computational load on Alice is a little more than that in PAKEs based on DHKE with a 160-bit exponent. In this paper, we compare RSA-EPAKE with SNAPI, PEKEP, and CEKEP in computation and the number of rounds, and provide a formal security analysis of RSA-EPAKE under the RSA assumption in the random oracle model.