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).

2015-03-02
16:26 [Event][New]

Submission: 17 March 2015
From July 20 to July 22
Location: Colmar, France

10:17 [Pub][ePrint]

The availability of vast amounts of data is changing how we can make medical discoveries, predict global market trends, save energy, improve our infrastructures, and develop new educational strategies. One obstacle to this revolution is the willingness of different entities to share their data with others.

The theory of secure multiparty computation (MPC) seemingly addresses this problem in the best way possible. Namely, parties learn the minimum necessary information: the value of the function computed on their joint data and nothing else. However, the theory of MPC does not deal with an important aspect: {\\it when} do different players receive their output? In time-sensitive applications, the timing and order of output discovery may be another important deciding factor in whether parties choose to share their data via the MPC.

In this work, we incorporate time and order of output delivery into the theory of MPC. We first extend classical MPC to \\emph{ordered MPC} where different players receive their outputs according to an order which in itself is computed on the inputs to the protocol, and to refine the classical notions of guaranteed output delivery and fairness to require instead \\emph{ordered output delivery} and \\emph{prefix-fairness}. We then define {\\it timed-delay MPCs} where explicit time delays are introduced into the output delivery schedule. We show general completeness theorems for ordered MPCs and timed-delay MPCs. We also introduce a new primitive called \\emph{time-line puzzles}, which are a natural extension of classical timed-release crypto, in which multiple events can be serialized in time.

Next, we show how ordered MPC can give rise to MPCs which are provably worth\'\' joining, in competitive settings where relative time of output discovery may deter parties from joining the protocol. We formalize a model of collaboration and design a mechanism in which $n$ self-interested parties can decide, based on their inputs, on an ordering of output delivery and a distribution of outputs to be delivered in the mandated order. The mechanism guarantees a higher reward \\emph{for all participants} when joining an ordered MPC or declares that such a guarantee is impossible to achieve. We show a polynomial time algorithm to compute the mechanism for a range of model settings.

10:17 [Pub][ePrint]

Nagao had proposed a decomposition method for divisors of hyperelliptic curves defined over a field $\\rF_{q^n}$ with $n\\geq 2$.

Joux and Vitse had later proposed a variant which provided relations among the factor basis elements. Both Nagao\'s and the

Joux-Vitse methods require solving a multi-variate system of non-linear equations. In this work, we revisit Nagao\'s approach

with the idea of avoiding the requirement of solving a multi-variate system. While this cannot be done in general, we are

able to identify special cases for which this is indeed possible. Our main result is for curves $C:y^2=f(x)$ of genus $g$ defined

over $\\rF_{q^2}$ having characteristic greater than two. If $f(x)$ has at most $g$ consecutive coefficients which are

in $\\rF_{q^2}$ while the rest are in $\\rF_q$, then we show that it is possible to obtain a single relation in about

$(2g+3)!$ trials. The method combines well with a sieving method proposed by Joux and Vitse. Our implementation of the

resulting algorithm provides examples of factor basis relations for $g=5$ and $g=6$. We believe that none of the other methods

known in the literature can provide such relations faster than our method. Other than obtaining such decompositions, we

also explore the applicability of our approach for $n>2$ and also for binary characteristic fields.

2015-03-01
15:15 [Event][New]

From April 21 to April 24
Location: Providence, RI, U.S.A.

10:17 [Pub][ePrint]

We present a generalization of the Hidden Number Problem and generalize the Boneh-Venkatesan method for solving it in polynomial time. We then use this to mount a key recovery attack on LWE which runs in polynomial time using the LLL lattice basis reduction algorithm. Success can be guaranteed with overwhelming probability for narrow error distribution when $q > 2^{O(n)}$, where n is the dimension of the secret key, and we can give an explicit constant in the exponent, but in practice the performance is significantly better. The same attack can be used to break RLWE for the same parameter ranges.

Two main types of attacks are already known for LWE: the distinguishing attack [MR] and the decoding attack [LP], which uses the BKZ algorithm. Our key recovery attack is interesting because it runs in polynomial time and yields simple and concrete security estimates for a wide range of parameters depending in a clear and explicit way on the effective approximation factor in the LLL algorithm. We ran the attack for hundreds of LWE instances demonstrating successful key recovery attacks and yielding information about the effective approximation factor as the lattice dimension grows . For example, we successfully recover the secret key for an instance with n=350 in about 3.5 days on a single machine.

10:17 [Pub][ePrint]

Yang et al. have proposed an efficient group key agreement scheme for

Mobile Adhoc Networks. The scheme is efficient as only one bilinear

computation is required for group members to obtain the session key. The scheme is analyzed for security without random oracle model. However, we prove that their scheme is not secure. In particular, we show that any passive adversary (or non-group member) can compute the

session key without having access to the individual secret keys of the group members. Hence, Yang et al. scheme cannot be used for secure group communication. We also show that, the scheme cannot be used for

secure group communication unless there exists a central entity, and hence cannot be used for secure communication in mobile adhoc networks.

2015-02-28
10:17 [Pub][ePrint]

Pure OMD is an authenticated encryption mode that will be presented by Reyhanitabar et al. at FSE 2015. It is (among others) claimed to achieve authenticity against nonce-misusing adversaries. We show that this claim is incorrect, by presenting an adversary that makes 3 queries (including the forgery) of a total complexity 6.

04:17 [Pub][ePrint]

Lightweight Cryptography aims at achieving security comparable to conventional cryptography at a much lower cost. Simon is a lightweight alternative to AES, as it shares same cryptographic parameters, but has been shown to be extremely area-efficient on FPGAs. However, in the embedded setting, protection against side channel analysis is often required. In this work we present a threshold implementation of Simon. The proposed core splits the information between three shares and achieves provable security against first order side-channel attacks. The core can be implemented in less than 100 slices of a low-cost FPGA, making it the world smallest threshold implementation of a block-cipher. Hence, the proposed core perfectly suits highly-constrained embedded systems including sensor nodes and RFIDs. Security of the proposed core is validated by provable arguments as well as practical DPA attacks and tests for leakage quantification.

04:17 [Pub][ePrint]

The arrival of indistinguishability obfuscation (iO) has transformed the cryptographic landscape by enabling several security goals that were previously beyond our reach. Consequently, one of the pressing goals currently is to construct iO from well-studied standard cryptographic assumptions.

In this work, we make progress in this direction by presenting a reduction from iO to a natural form of public-key functional encryption (FE). Specifically, we construct iO for general

functions from any sub-exponentially secure, single-key compact FE scheme for NC1 that achieves selective, indistinguishability security against sub-exponential time adversaries. Further, the FE scheme should be compact, namely, the running time of the encryption algorithm must only be a polynomial in the security parameter and the input message length and not depend on the function description size or its output length.

We achieve this result by developing a novel arity amplification technique to transform FE for single-ary functions into FE for multi-ary functions (aka multi-input FE). Instantiating our approach with known, non-compact FE schemes, we obtain the first constructions of multi-input FE for constant-ary functions based on standard assumptions.

Finally, as a result of independent interest, we construct a compact FE scheme from randomized encodings for Turing machines and learning with errors assumption.

04:17 [Pub][ePrint]

The Feistel-SP structure is a commonly adopted structure in symmetric cryptography with many practical instances. Differential power analysis (DPA) has proven to be effective against these ciphers with compact implementations within these years. However, the applications of DPA on Feistel-SP ciphers with loop hardware implementations are more complicated and less evaluated in literature, mainly due to the relatively large size (32-bit or more) of the whole round key which often results in complex relations with the targeted intermediate variable. \\\\

In this paper, we propose a practical chosen message power analysis method on Feistel-SP ciphers with loop hardware implementations. The essence of the new method lies in the delicate selection of the plaintext set in a chosen message manner. Thus, the input space of the plaintext in our method is decreased from $2^{32}$ or more to $2^8$ or less, which is suitable for practical power analysis. Moreover, we show that the whitening key at the first or last round can be easily revealed with our method, thus leading to the full exposure of the master key thanks to the relations between whitening keys and the master key in many practical ciphers. In order to further manifest the validity of the new method, we carry extensive experiments on two ISO standardized and widely deployed ciphers CLEFIA and Camellia with loop implementations on FPGA, and the master keys are recovered as expected.

01:17 [Pub][ePrint]

ICEPOLE is a CAESAR candidate with the intermediate level of robustness under nonce misuse circumstances in the original document. In particular, it was claimed that key recovery attack against ICEPOLE is impossible in the case of nonce misuse. ICEPOLE is strong against the differential cryptanalysis and linear cryptanalysis. In this paper, we developed the differential-linear attacks against ICEPOLE when nonce is misused. Our attacks show that the state of ICEPOLE-128 and ICEPOLE-128a can be recovered with data complexity $2^{46}$ and time complexity $2^{46}$; the state of ICEPOLE-256a can be recovered with data complexity $2^{60}$ and time complexity $2^{60}$. For ICEPOLE-128a and ICEPOLE-256a, the secret key is recovered once the state is recovered. We experimentally verified the attacks against ICEPOLE-128 and ICEPOLE-128a.