International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service via

To receive your credentials via mail again, please click here.

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] A Novel Proof on Weil Pairing, by Sutirtha Sanyal

  In this paper we will prove a basic property of weil pairing which helps in evaluating its value. We will show that the weil pairing value as

computed from the definition is equivalent with the ratio formula based on the miller function. We prove a novel theorem (Theorem 2) and use it

to establish the equivalence. We further validate our claims with actual random examples.



05:22 [Pub][ePrint] Salvaging Indifferentiability in a Multi-stage Setting, by Arno Mittelbach

  Ristenpart, Shacham and Shrimpton (Eurocrypt 2011) recently presented schemes which are provably secure in the random-oracle model (ROM),

but easily broken if the random oracle is replaced by typical indifferentiable hash constructions such as chop-MD or prefix-free-MD.

They found that the indifferentiability framework, due to Maurer, Renner and Holenstein (TCC 2004), does not

necessarily allow composition in multi-stage settings, that is, settings consisting of multiple disjoint adversarial stages. On the positive

side, they prove that the non-adaptive chosen distribution attack (CDA) game of Bellare et al.~(Asiacrypt 2009), a multi-stage game capturing the security of deterministic encryption schemes,

remains secure if the random oracle is implemented by an NMAC-like hash function.

In this paper we introduce a framework to work with the indifferentiability notion in multi-stage scenarios. For this we provide

a model for iterative hash functions which is general enough to cover not only NMAC-like functions, but also functions such as chop-MD

or even hash trees. We go on to define a property on multi-stage games called \\emph{unsplittability} which intuitively captures that

adversaries cannot split the computation of a single hash value over several stages. We present a composition theorem for

unsplittable multi-stage games which generalizes the single-stage composition theorem for indifferentiable hash functions. We then show that

the CDA game (adaptive or non-adaptive) is unsplittable for \\emph{any} iterative hash function (thereby extending the preliminary results

by Ristenpart et al.). Finally, we prove that the \\emph{proof-of-storage} game presented by Ristenpart et al.~as a counterexample to

the general applicability of the indifferentiability framework is unsplittable for any multi-round iterative hash function, such as

Liskov\'s Zipper Hash (SAC~2006).



05:22 [Pub][ePrint] The failure of McEliece PKC based on Reed-Muller codes., by I. V. Chizhov and M. A. Borodin

  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] Key Classification Attack on Block Ciphers, by Maghsoud Parviz and Seyed Hassan Mousavi and Saeed Mirahmadi

  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] Secure Second Price Auctions with a Rational Auctioneer, by Boaz Catane and Amir Herzberg

  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] Massive Group Message Authentication with Revocable Anonymity, by Boaz Catane and Amir Herzberg

  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] On Diffie-Hellman-like Security Assumptions, by Antoine Joux and Antoine Rojat

  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] A Leakage Resilient MAC, by Dan Martin and Elisabeth Oswald and Martijn Stam

  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] A Toolkit for Ring-LWE Cryptography, by Vadim Lyubashevsky and Chris Peikert and Oded Regev

  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] Synchronous Sampling and Clock Recovery of Internal Oscillators for Side Channel Analysis, by Colin O\'Flynn and Zhizhang (David) Chen

  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] Survey and Benchmark of Lightweight Block Ciphers for Wireless Sensor Networks, by Micka\\\"el Cazorla and Kevin Marquet and Marine Minier

  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.