International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2013-05-28
05:22 [Pub][ePrint]

This paper describes new algorithm for breaking McEliece cryptosystem, built on Reed-Muller binary code $RM(r, m)$, which receives the private key from the public key. The algorithm has complexity $O(n^d+n^4log_2n)$ bit operations, where $n=2^m, d=\\text{GCD}(r,m-1).$ In the case of $\\text{GCD}(r,m-1)$ limitation, attack has polynomial complexity. Practical results of implementation show that McEliece cryptosystems, based on the code with length $n=65536$ bits, can be broken in less than 7 hours on a personal computer.

05:22 [Pub][ePrint]

In this paper, security analysis of block ciphers with key length greater than block length is proposed. For a well-designed block cipher with key length k and block length n s.t. k>n and for all P, C, there are 2^{k-n} keys which map P to C. For given block cipher, if there is an efficient algorithm that can classify such keys, we propose an algorithm will be able to recover the secret key with complexity O(max{2^n, 2^{k-n}}). We apply this method on 2-round block cipher KASUMI.

05:22 [Pub][ePrint]

We present novel security requirements for second price auctions and a

simple, efficient and practical protocol that provably maintains these

requirements. Novel requirements are needed because commonly used requirements,

such as the indistinguishability-based secrecy requirement of encryption schemes

presented by \\cite{goldwasser1982pep}, do not fit properly in the second price

auctions context. Additionally, the presented protocol uses a trustworthy

supervisor that checks if the auctioneer deviated from the protocol and fines

him accordingly. By making sure the expected utility of the auctioneer when

deviating from the protocol is lower than his expected utility when abiding by

the protocol we ascertain that a {\\em rational} auctioneer will abide by the

protocol. This allows the supervisor to optimize by performing

(computationally-intensive) inspections of the auctioneer with only low

probability.

05:22 [Pub][ePrint]

We present and implement schemes for authenticating messages from a

group of users to a recipient, with revocable anonymity and massive (very high) message rate. Our implementations present a trade-off between the efficiency and the security required: from online group managers that participate in every message sent to offline managers, from assuming a trusted group manager and a trusted recipient to securing against both entities. All implementations have the {\\em traceablity} feature, allowing to distributively and efficiently trace

all messages that originated from a specific group member without violating anonymity of other members. In addition, our schemes are efficient and practical.

05:22 [Pub][ePrint]

Over the past decade bilinear maps have been used to build a large variety of cryptosystems. In parallel to new functionalities, we have also seen the emergence of many security assumptions. This leads to the general question of comparing two such assumptions. Boneh, Boyen and Goh introduced the Uber assumption as an attempt to offer a general framework for security assessment. Their idea is to propose a generic security assumption that can be specialized to suit the needs of any proof of protocols involving bilinear pairing. Even though the Uber assumption has been only stated in the bilinear setting, it can be easily restated to deal with ordinary Diffie-Hellman groups and assess other type of protocols.

In this article, we explore some particular cases of the Uber assumption; namely the n-CDH-assumption, the nth-CDH- assumption and the Q-CDH-assumption. We analyse the relationships between those cases and more precisely from a security point of view. Our analysis does not rely on any special property of the considered group(s) and does not use the generic group model.

05:22 [Pub][ePrint]

We put forward a message authentication code (MAC) for which we claim a high degree of resilience against a key-recovering attacker expoiting practical side channels. We achieve this by blending

the lessons learned from many years of engineering with the scientific

approach provided by leakage resilience. This highlights how the two often disparate fields can benefit from each other.

Our MAC is relatively simple and intuitive: we essentially base our construction on bilinear groups and secret share out our key. The shares are then refreshed before each time they are used and the algebraic properties of the bilinear pairing are used to compute the tag without the need to reconstruct the key.

This approach allows us to prove (in the random oracle model) existential unforgability of the MAC under chosen message attacks in the presence of (continuous) leakage, based on two novel assumptions:

a bilinear Diffie--Hellman variant and an assumption related to how leaky performing a group operation is.

In practice we envision our scheme would be implemented using pairings on some pairing friendly elliptic curve, where the leakiness of the group operation can be experimentally estimated. This allows us to argue about practical implementation aspects and security considerations of our scheme.

We compare our scheme against other leakage resilient MACs (or related schemes) that have appeared in the literature and conclude ours is both the most efficient and by far the most practical.

05:21 [Pub][ePrint]

Recent advances in lattice cryptography, mainly stemming from the

development of ring-based primitives such as ring-$\\lwe$, have made it

possible to design cryptographic schemes whose efficiency is

competitive with that of more traditional number-theoretic ones, along

with entirely new applications like fully homomorphic encryption.

Unfortunately, realizing the full potential of ring-based cryptography

has so far been hindered by a lack of practical algorithms and

analytical tools for working in this context. As a result, most

previous works have focused on very special classes of rings such as

power-of-two cyclotomics, which significantly restricts the possible

applications.

We bridge this gap by introducing a toolkit of fast, modular

algorithms and analytical techniques that can be used in a wide

variety of ring-based cryptographic applications, particularly those

built around ring-\\lwe. Our techniques yield applications that work

in \\emph{arbitrary} cyclotomic rings, with \\emph{no loss} in their

underlying worst-case hardness guarantees, and very little loss in

computational efficiency, relative to power-of-two cyclotomics. To

demonstrate the toolkit\'s applicability, we develop two illustrative

applications: a public-key cryptosystem and a somewhat homomorphic\'\'

symmetric encryption scheme. Both apply to arbitrary cyclotomics, have

tight parameters, and very efficient implementations.

05:21 [Pub][ePrint]

Measuring power consumption for side-channel analysis typically uses an oscilloscope, which measures the data relative to an internal timebase. By synchronizing the sampling clock to the clock of the target device, the data storage and sampling requirements are considerably relaxed; the attack will succeed with a much lower sample rate. Previous work has demonstrated this on a system with a fixed and easily available clock; but real devices will often have an inaccessible internal oscillator, and may purposely vary the frequency this oscillator runs at (the Varying Clock countermeasure).

This work measures the performance of a synchronous sampling system attacking a modern microcontroller running a software AES implementation. This attack is characterized under three conditions: with a stable clock, with a clock that randomly varies between 4.5~MHz--12.7~MHz, and with an internal oscillator that randomly varies between 7.41~MHz--7.49~MHz.

Traces captured with the synchronous sampling technique can be processed with a standard Differential Power Analysis (DPA) style attack in all three cases, whereas when an oscilloscope is used only the stable oscillator setup is successful. This work also develops the required hardware to recover the internal clock of a device which does not have an externally available clock.

05:21 [Pub][ePrint]

For security applications in wireless sensor networks (WSNs), choosing best algorithms in terms of energy-efficiency and of small memory requirements is a real challenge because the sensor networks must be autonomous. In \\cite{EisenbarthGGHIKKNPRSO12,LawDH06}, the authors have benchmarked on a dedicated platform some block-ciphers and have deduced the best candidates to use in the context of small embedded platforms.

This article proposes to study on a dedicated platform of sensors most of the recent lightweight block ciphers as well as some conventional block ciphers. First, we describe the design of the chosen block ciphers with a security summary and we then present some implementation tests performed on our platform.

05:21 [Pub][ePrint]

We consider a class of two-party function evaluation protocols in which the parties are allowed to use ideal functionalities as well as a set of powerful primitives, namely commitments, homomorphic encryption, and certain zero-knowledge proofs. We illustrate that with these it is possible to capture protocols for oblivious transfer, coin-flipping, and generation of multiplication-triple.

We show how any protocol in our class can be compiled to a symbolic representation expressed as a process in an abstract process calculus, and prove a general computational soundness theorem implying that if the protocol realises a given ideal functionality in the symbolic setting, then the original version also realises the ideal functionality in the standard computational UC setting. In other words, the theorem allows us to transfer a proof in the abstract symbolic setting to a proof in the standard UC model.

Finally, we show that the symbolic interpretation is simple enough in a number of cases for the symbolic proof to be partly automated using the ProVerif tool.

05:21 [Pub][ePrint]

Lattice-based signature schemes constitute an interesting alternative to RSA and discrete logarithm based systems which may become insecure in the future, for example due to the possibility of quantum attacks. A particularly interesting scheme in this context is the GPV signature scheme [GPV08] combined with the trapdoor construction from Micciancio and Peikert [MP12] as it admits strong security proofs and is believed to be very efficient in practice. This paper confirms this belief and shows how to improve the GPV scheme in terms of space and running time and presents an implementation of the optimized scheme. A ring variant of this scheme is also introduced which leads to a more efficient construction. Experimental results show that GPV with the new trapdoor construction is competitive to the signature schemes that are currently used in practice.