Secure Two-Party Computation

Secure Set Intersection with Untrusted Hardware Tokens

Abstract

Secure set intersection protocols are the core building block for a manifold of privacy-preserving applications.

In a recent work, Hazay and Lindell (ACM CCS 2008) introduced the idea of using trusted hardware tokens for the set intersection problem, devising protocols which improve over previous (in the standard model of two-party computation) protocols in terms of efficiency and secure composition. Their protocol uses only a linear number of symmetrickey computations and the amount of data stored in the token does not depend on the sizes of the sets. The security proof of the protocol is in the universal composability model and is based on the strong assumption that the token is trusted by both parties.

In this paper we revisit the idea and model of hardware-based secure set intersection, and in particular consider a setting where tokens are not necessarily trusted by both participants to additionally cover threats like side channel attacks, firmware trapdoors and malicious hardware. Our protocols are very efficient and achieve the same level of security as those by Hazay and Lindell for trusted tokens. For untrusted tokens, our protocols ensure privacy against malicious adversaries, and correctness facing covert adversaries.

Marc Fischlin, Benny Pinkas, Ahmad-Reza Sadeghi, Thomas Schneider, Ivan Visconti

Efficient Secure Two-Party Exponentiation

Abstract

We present a new framework to design secure two-party computation protocols for exponentiation over integers and over Z _Q where Q is a publicly-known prime. Using our framework, we realize efficient protocols in the semi-honest setting. Assuming the base is non-zero, and the exponent is at most Q/2 for the Z _Q case, our protocols consist of at most 5 rounds (each party sending 5 messages) and the total communication consists of a small constant number (≤ 18) of encrypted/encoded elements in Z _Q. Without these assumptions, our protocols are still more efficient than a protocol recently proposed by Damgård et al. in TCC 2006 (24 vs. > 114 rounds, ≈ 279ℓ + 12t for an error rate of 2^− t vs. > 110 ℓlogℓ secure multiplications, where ℓ is the bit length of the shares).

Our protocols are constructed from different instantiations of our framework with different assumptions (homomorphic encryption or oblivious transfers) to achieve different advantages. Our key idea is to exploit the properties of both additive and multiplicative secret sharing. We also propose efficient transformation protocols between these sharings, which might be of independent interest.

Ching-Hua Yu, Sherman S. M. Chow, Kai-Min Chung, Feng-Hao Liu

Cryptographic Primitives

A General, Flexible and Efficient Proof of Inclusion and Exclusion

Abstract

Inclusion proof shows that a secret committed message is in a finite group of messages, while exclusion proof shows that a secret committed message is not in a finite group of messages. A general, flexible and efficient solution to inclusion proof and exclusion proof is proposed in this paper. It overcomes the drawbacks of the existing solutions to inclusion proof and exclusion proof. It achieves all the desired security properties in inclusion proof and exclusion proof. It is the most efficient general solution to inclusion proof and exclusion proof and only costs \(O(\sqrt{n})\) for any inclusion proof and exclusion proof regarding any finite group of n messages.

Kun Peng

Non-interactive Confirmer Signatures

Abstract

The study of non-transferability of digital signatures, such as confirmer signatures, has enjoyed much interest over the last twenty years. In PKC ’08, Liskov and Micali noted that all previous constructions of confirmer signatures consider only offline untransferability – non-transferability is not preserved if the recipient interacts concurrently with the signer/confirmer and an unexpected verifier. We view this as a result of all these schemes being interactive in the confirmation step. In this paper, we introduce the concept of non-interactive confirmer signatures (which can also be interpreted as extractable universal designated-verifier signatures). Non-interactive confirmer signatures give a neat way to ensure the online untransferability of signatures. We realize our notion under the “encryption of a signature” paradigm using pairings and provide a security proof for our construction without random oracles.

Sherman S. M. Chow, Kristiyan Haralambiev

Communication-Efficient 2-Round Group Key Establishment from Pairings

Abstract

In a recent preprint, Vivek et al. propose a compiler to transform a passively secure 3-party key establishment to a passively secure group key establishment. To achieve active security, they apply this compiler to Joux’s protocol and apply a construction by Katz and Yung, resulting in a 3-round group key establishment.

In this paper we show how Joux’s protocol can be extended to an actively secure group key establishment with two rounds. The resulting solution is in the standard model, builds on a bilinear Diffie-Hellman assumption and offers forward security as well as strong entity authentication. If strong entity authentication is not required, then one half of the participants does not have to send any message in the second round, which may be of interest for scenarios where communication efficiency is a main concern.

Kashi Neupane, Rainer Steinwandt

Side Channel Attacks

Defeating RSA Multiply-Always and Message Blinding Countermeasures

Abstract

We introduce a new correlation power attack on RSA’s modular exponentiation implementations, defeating both message blinding and multiply-always countermeasures. We analyze the correlation between power measurements of two consecutive modular operations, and use this to efficiently recover individual key bits. Based upon simulation and practical application on a state-of-the-art smart card we show the validity of the attack. Further we demonstrate that cross correlation analysis is efficient on hardware RSA implementations, even in the presence of message blinding and strong hiding countermeasures.

Marc F. Witteman, Jasper G. J. van Woudenberg, Federico Menarini

Cryptanalysis of CLEFIA Using Differential Methods with Cache Trace Patterns

Abstract

In this paper we use a combination of differential techniques and cache traces to attack the block cipher CLEFIA in less than 2¹⁴ encryptions on an embedded processor with a cache line size of 32 bytes. The attack is evaluated on an implementation of CLEFIA on the PowerPC processor present in the SASEBO side channel attack evaluation board. The paper shows that although obtaining cache access patterns from the power consumption of the device may be difficult due to the non-blocking cache architectures of modern processors, still the cache trace has a distinct signature on the power profiles. Experimental results have been presented to show that the power consumption of the device reveal the cache access patterns, which are then used to obtain the CLEFIA key. Further, a simple low overhead countermeasure is implemented that is guaranteed to prevent cache attacks.

Chester Rebeiro, Debdeep Mukhopadhyay

Improving Differential Power Analysis by Elastic Alignment

Abstract

To prevent smart card attacks using Differential Power Analysis (DPA), manufacturers commonly implement DPA countermeasures that create misalignment in power trace sets and decrease the effectiveness of DPA. We design and investigate the elastic alignment algorithm for non-linearly warping trace sets in order to align them. Elastic alignment uses FastDTW, originally a method for aligning speech utterances in speech recognition systems, to obtain so-called warp paths that can be used to perform alignment. We show on traces obtained from a smart card with random process interrupts that misalignment is reduced significantly, and that even under an unstable clock the algorithm is able to perform alignment.

Jasper G. J. van Woudenberg, Marc F. Witteman, Bram Bakker

Invited Talk

NSA’s Role in the Development of DES

Abstract

38 years ago, NIST put out a call for submissions of candidates for data encryption standard to address the needs of encryption for the commercial world. Of the submissions, the IBM submission stood out as arguably the best candidate. However, before the algorithm was ready to be chosen as the Data Encryption Standard (DES), some changes were required. The National Security Agency (NSA) worked with IBM on the modification of the submitted algorithm. This talk will discuss what role NSA played in this effort, the rationale for the changes that were made, and the impact that DES had at that time.

Richard M. George

Authenticated Key Agreement

Designing Efficient Authenticated Key Exchange Resilient to Leakage of Ephemeral Secret Keys

Abstract

We investigate a sufficient condition for constructing authenticated key exchange (AKE) protocols which satisfy security in the extended Canetti-Krawczyk (eCK) model proposed by LaMacchia, Lauter and Mityagin. To the best of our knowledge, this is the first approach for providing secure protocols based on the condition. With this condition, we propose a construction of two-pass AKE protocols, and the resulting two-pass AKE protocols are constructed with a single static key and a single ephemeral. In addition, the security proof does not require the Forking Lemma, which degrades the security of a protocol relative to the security of the underlying problem where it is used in the security proof. Therefore, these imply that the protocols constructed with the condition have an advantage in efficiency such as sizes of storage and communication data. The security of the resulting protocols is proved under the gap Diffie-Hellman assumption in the random oracle model.

Atsushi Fujioka, Koutarou Suzuki

Contributory Password-Authenticated Group Key Exchange with Join Capability

Abstract

Password-based authenticated group key exchange allows any group of users in possession of a low-entropy secret key to establish a common session key even in the presence of adversaries. In this paper, we propose a new generic construction of password-authenticated group key exchange protocol from any two-party password-authenticated key exchange with explicit authentication. Our new construction has several advantages when compared to existing solutions. First, our construction only assumes a common reference string and does not rely on any idealized models. Second, our scheme enjoys a simple and intuitive security proof in the universally composable framework and is optimal in the sense that it allows at most one password test per user instance. Third, our scheme also achieves a strong notion of security against insiders in that the adversary cannot bias the distribution of the session key as long as one of the players involved in the protocol is honest. Finally, we show how to easily extend our protocol to the dynamic case in a way that the costs of establishing a common key between two existing groups is significantly smaller than computing a common key from scratch.

Michel Abdalla, Céline Chevalier, Louis Granboulan, David Pointcheval

Proofs of Security

Ideal Key Derivation and Encryption in Simulation-Based Security

Abstract

Many real-world protocols, such as SSL/TLS, SSH, IPsec, DNSSEC, IEEE 802.11i, and Kerberos, derive new keys from other keys. To be able to analyze such protocols in a composable way, in this paper we extend an ideal functionality for symmetric and public-key encryption proposed in previous work by a mechanism for key derivation. We also equip this functionality with message authentication codes (MACs), digital signatures, and ideal nonce generation. We show that the resulting ideal functionality can be realized based on standard cryptographic assumptions and constructions, hence, providing a solid foundation for faithful, composable cryptographic analysis of real-world security protocols.

Based on this new functionality, we identify sufficient criteria for protocols to provide universally composable key exchange and secure channels. Since these criteria are based on the new ideal functionality, checking the criteria requires merely information-theoretic or even only syntactical arguments, rather than involved reduction arguments.

As a case study, we use our method to analyze two central protocols of the IEEE 802.11i standard, namely the 4-Way Handshake Protocol and the CCM Protocol, proving composable security properties. As to the best of our knowledge, this constitutes the first rigorous cryptographic analysis of these protocols.

Ralf Küsters, Max Tuengerthal

Beyond Provable Security Verifiable IND-CCA Security of OAEP

Abstract

OAEP is a widely used public-key encryption scheme based on trapdoor permutations. Its security proof has been scrutinized and amended repeatedly. Fifteen years after the introduction of OAEP, we present a machine-checked proof of its security against adaptive chosen-ciphertext attacks under the assumption that the underlying permutation is partial-domain one-way. The proof can be independently verified by running a small and trustworthy proof checker and fixes minor glitches that have subsisted in published proofs. We provide an overview of the proof, highlight the differences with earlier works, and explain in some detail a crucial step in the reduction: the elimination of indirect queries made by the adversary to random oracles via the decryption oracle. We also provide—within the limits of a conference paper—a broader perspective on independently verifiable security proofs.

Gilles Barthe, Benjamin Grégoire, Yassine Lakhnech, Santiago Zanella Béguelin

(Second) Preimage Attacks on Step-Reduced RIPEMD/RIPEMD-128 with a New Local-Collision Approach

Abstract

This paper uses new types of local collisions named one-message-word local collisions to construct meet-in-the-middle preimage attacks on two double-branch hash functions RIPEMD and RIPEMD-128, and obtains the following results.

1

A pseudo-preimage and second preimage attacks on the first 47 steps of RIPEMD (full version: 48 steps) are proposed with complexities of 2¹¹⁹ and 2^124.5 compression function computations, respectively. The number of the attacked steps is greatly increased from previous preimage attacks on the first 33 steps and intermediate 35 steps.

2

A pseudo-preimage and preimage attacks on intermediate 36 steps of RIPEMD-128 (full version: 64 steps) are proposed with complexities of 2¹²³ and 2^126.5 compression function computations, respectively, while previous attacks can work at most intermediate 35 steps.

Lei Wang, Yu Sasaki, Wataru Komatsubara, Kazuo Ohta, Kazuo Sakiyama

MJH: A Faster Alternative to MDC-2

Abstract

In this paper, we introduce a new class of double-block-length hash functions. In the ideal cipher model (for n-bit blocks), we prove that these hash functions, dubbed MJH, are provably collision resistant up to \(O(2^{\frac{2n}{3}-\log n})\) queries in the iteration.

When based on n-bit key blockciphers, our construction provides better provable security than MDC-2, the only known construction of a rate-1/2 double-length hash function based on an n-bit key blockcipher with non-trivial provable security. Moreover, since key scheduling is performed only once per message block for MJH, our proposal significantly outperforms MDC-2 in efficiency.

When based on a 2n-bit key blockcipher, we can use the extra n bits of key to increase the amount of payload accordingly. Thus we get a rate-1 hash function that is much faster than existing proposals, such as Tandem-DM, at the expense of (for the moment) reduced provable security.

Jooyoung Lee, Martijn Stam

Block Ciphers

Online Ciphers from Tweakable Blockciphers

Abstract

Online ciphers are deterministic length-preserving permutations \({\mathcal E}_K : (\{0. 1\}^n)^+\rightarrow(\{0. 1\}^n)^+\) where the i-th block of ciphertext depends only on the first i blocks of plaintext. Definitions, constructions, and applications for these objects were first given by Bellare, Boldyreva, Knudsen, and Namprempre. We simplify and generalize their work, showing that online ciphers are rather trivially constructed from tweakable blockciphers, a notion of Liskov, Rivest, and Wagner. We go on to show how to define and achieve online ciphers for settings in which messages need not be a multiple of n bits.

Phillip Rogaway, Haibin Zhang

Meet-in-the-Middle Attacks on Reduced-Round XTEA

Abstract

The block cipher XTEA, designed by Needham and Wheeler, was published as a technical report in 1997. The cipher was a result of fixing some weaknesses in the cipher TEA (also designed by Wheeler and Needham), which was used in Microsoft’s Xbox gaming console. XTEA is a 64-round Feistel cipher with a block size of 64 bits and a key size of 128 bits. In this paper, we present meet-in-the-middle attacks on twelve variants of the XTEA block cipher, where each variant consists of 23 rounds. Two of these require only 18 known plaintexts and a computational effort equivalent to testing about 2¹¹⁷ keys, with a success probability of 1 − 2^− 1025. Under the standard (single-key) setting, there is no attack reported on 23 or more rounds of XTEA, that requires less time and fewer data than the above. This paper also discusses a variant of the classical meet-in-the-middle approach. All attacks in this paper are applicable to XETA as well, a block cipher that has not undergone public analysis yet. TEA, XTEA and XETA are implemented in the Linux kernel.

Gautham Sekar, Nicky Mouha, Vesselin Velichkov, Bart Preneel

Security Notions

Expedient Non-malleability Notions for Hash Functions

Abstract

Non-malleability of a cryptographic primitive is a fundamental security property which ensures some sort of independence of cryptographic values. The notion has been extensively studied for commitments, encryption and zero-knowledge proofs, but it was not until recently that the notion—and its peculiarities—have been considered for hash functions by Boldyreva et al. (Asiacrypt 2009). They give a simulation-based definition, basically saying that for any adversary mauling hash values into related ones there is a simulator which is as successful in producing such hash values, even when not seeing the original hash values. Their notion, although following previous approaches to nonmalleability, is nonetheless quite unwieldy; it is hard to achieve and, due to the existential quantification over the simulator, hard to falsify. We also note that finding an equivalent indistinguishability-based notion is still open.

Here we take a different, more handy approach to non-malleability of hash functions. Our definition avoids simulators completely and rather asks the adversary to maul the hash value and to also specify a transformation φ of the pre-image, taken from a fixed class Φ of admissible transformations. These transformations are usually determined by group operations and include such cases such as exclusive-ors (i.e., bit flips) and modular additions. We then simply demand that the probability of succeeding is negligible, as long as the original pre-image carries enough entropy. We continue to show that our notion is useful by proving that, for example, the strengthened Merkle-Damgård transformation meets our notion for the case of bit flips, assuming an ideal compression function. We also improve over the security result by Boldyreva et al., showing that our notion of non-malleability suffices for the security of the Bellare-Rogaway encryption scheme.

Paul Baecher, Marc Fischlin, Dominique Schröder

Stronger Difficulty Notions for Client Puzzles and Denial-of-Service-Resistant Protocols

Abstract

Client puzzles are meant to act as a defense against denial of service (DoS) attacks by requiring a client to solve some moderately hard problem before being granted access to a resource. However, recent client puzzle difficulty definitions (Stebila and Ustaoglu, 2009; Chen et al., 2009) do not ensure that solving n puzzles is n times harder than solving one puzzle. Motivated by examples of puzzles where this is the case, we present stronger definitions of difficulty for client puzzles that are meaningful in the context of adversaries with more computational power than required to solve a single puzzle.

A protocol using strong client puzzles may still not be secure against DoS attacks if the puzzles are not used in a secure manner. We describe a security model for analyzing the DoS resistance of any protocol in the context of client puzzles and give a generic technique for combining any protocol with a strong client puzzle to obtain a DoS-resistant protocol.

Douglas Stebila, Lakshmi Kuppusamy, Jothi Rangasamy, Colin Boyd, Juan Gonzalez Nieto

Public-Key Encryption

On Shortening Ciphertexts: New Constructions for Compact Public Key and Stateful Encryption Schemes

Abstract

We present new constructions of (conventional) public key and stateful public key encryption schemes which produce ciphertexts of compact size while providing both efficiency and strong security. Our public key encryption scheme incurs only one group element ciphertext expansion (defined as the size of the ciphertext minus the size of the plaintext message) but compared with the previous scheme in the literature, its encryption algorithm is more efficient. Our stateful encryption scheme resolves the problem of ciphertext expansion of the existing schemes in the literature and hence can be served as a favorable alternative. Both of our schemes do not depend on the external length-preserving cipher constructed from the expensive strong pseudo random permutation. We provide security analysis of our schemes against chosen ciphertext attack under the well-known computational assumptions, in the random oracle model. We envision that our schemes can serve as efficient public key primitives suitable for implementing on resource-constrained devices.

Joonsang Baek, Cheng-Kang Chu, Jianying Zhou

Better Key Sizes (and Attacks) for LWE-Based Encryption

Abstract

We analyze the concrete security and key sizes of theoretically sound lattice-based encryption schemes based on the “learning with errors” (LWE) problem. Our main contributions are: (1) a new lattice attack on LWE that combines basis reduction with an enumeration algorithm admitting a time/success tradeoff, which performs better than the simple distinguishing attack considered in prior analyses; (2) concrete parameters and security estimates for an LWE-based cryptosystem that is more compact and efficient than the well-known schemes from the literature. Our new key sizes are up to 10 times smaller than prior examples, while providing even stronger concrete security levels.

Richard Lindner, Chris Peikert

Crypto Tools and Parameters

Binary Huff Curves

Abstract

This paper describes the addition law for a new form for elliptic curves over fields of characteristic 2. Specifically, it presents explicit formulæ for adding two different points and for doubling points. The case of differential point addition (that is, point addition with a known difference) is also addressed. Finally, this paper presents unified point addition formulæ; i.e., point addition formulæ that can be used for doublings. Applications to cryptographic implementations are discussed.

Julien Devigne, Marc Joye

A Variant of the F4 Algorithm

Abstract

Algebraic cryptanalysis usually requires to find solutions of several similar polynomial systems. A standard tool to solve this problem consists of computing the Gröbner bases of the corresponding ideals, and Faugère’s F4 and F5 are two well-known algorithms for this task. In this paper, we adapt the “Gröbner trace” method of Traverso to the context of F4. The resulting variant is a heuristic algorithm, well suited to algebraic attacks of cryptosystems since it is designed to compute with high probability Gröbner bases of a set of polynomial systems having the same shape. It is faster than F4 as it avoids all reductions to zero, but preserves its simplicity and its efficiency, thus competing with F5.

Antoine Joux, Vanessa Vitse

Attribute-Based Signatures

Abstract

We introduce Attribute-Based Signatures (ABS), a versatile primitive that allows a party to sign a message with fine-grained control over identifying information. In ABS, a signer, who possesses a set of attributes from the authority, can sign a message with a predicate that is satisfied by his attributes. The signature reveals no more than the fact that a single user with some set of attributes satisfying the predicate has attested to the message. In particular, the signature hides the attributes used to satisfy the predicate and any identifying information about the signer (that could link multiple signatures as being from the same signer). Furthermore, users cannot collude to pool their attributes together.

We give a general framework for constructing ABS schemes, and then show several practical instantiations based on groups with bilinear pairing operations, under standard assumptions. Further, we give a construction which is secure even against a malicious attribute authority, but the security for this scheme is proven in the generic group model. We describe several practical problems that motivated this work, and how ABS can be used to solve them. Also, we show how our techniques allow us to extend Groth-Sahai NIZK proofs to be simulation-extractable and identity-based with low overhead.

Hemanta K. Maji, Manoj Prabhakaran, Mike Rosulek

Digital Signatures

Sub-linear Size Traceable Ring Signatures without Random Oracles

Abstract

Traceable ring signatures, proposed at PKC’07, are a variant of ring signatures, which allow a signer to anonymously sign a message with a tag behind a ring, i.e., a group of users chosen by the signer, unless he signs two messages with the same tag. However, if a signer signs twice on the same tag, the two signatures will be linked and the identity of the signer will be revealed when the two signed messages are different. Traceable ring signatures can be applied to anonymous write-in voting without any special voting authority and electronic coupon services. The previous traceable ring signature scheme relies on random oracles at its security and the signature size is linear in the number of ring members. This paper proposes the first secure traceable ring signature schemes without random oracles in the common reference string model. In addition, the proposed schemes have a signature size of \(O(\sqrt{N})\), where N is the number of users in the ring.

Eiichiro Fujisaki

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Secure Two-Party Computation

Secure Set Intersection with Untrusted Hardware Tokens

Efficient Secure Two-Party Exponentiation

Cryptographic Primitives

A General, Flexible and Efficient Proof of Inclusion and Exclusion

Non-interactive Confirmer Signatures

Communication-Efficient 2-Round Group Key Establishment from Pairings

Side Channel Attacks

Defeating RSA Multiply-Always and Message Blinding Countermeasures

Cryptanalysis of CLEFIA Using Differential Methods with Cache Trace Patterns

Improving Differential Power Analysis by Elastic Alignment

Invited Talk

NSA’s Role in the Development of DES

Authenticated Key Agreement

Designing Efficient Authenticated Key Exchange Resilient to Leakage of Ephemeral Secret Keys

Contributory Password-Authenticated Group Key Exchange with Join Capability

Proofs of Security

Ideal Key Derivation and Encryption in Simulation-Based Security

Beyond Provable Security Verifiable IND-CCA Security of OAEP

(Second) Preimage Attacks on Step-Reduced RIPEMD/RIPEMD-128 with a New Local-Collision Approach

MJH: A Faster Alternative to MDC-2

Block Ciphers

Online Ciphers from Tweakable Blockciphers

Meet-in-the-Middle Attacks on Reduced-Round XTEA

Security Notions

Expedient Non-malleability Notions for Hash Functions

Stronger Difficulty Notions for Client Puzzles and Denial-of-Service-Resistant Protocols

Public-Key Encryption

On Shortening Ciphertexts: New Constructions for Compact Public Key and Stateful Encryption Schemes

Better Key Sizes (and Attacks) for LWE-Based Encryption

Crypto Tools and Parameters

Binary Huff Curves

A Variant of the F4 Algorithm

Attribute-Based Signatures

Digital Signatures

Sub-linear Size Traceable Ring Signatures without Random Oracles

Backmatter