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-03
18:52 [Job][New]

Tamesek Laboratories at Nanyang Technological University in Singapore is looking for both junior and senior researchers, to fill 3 positions of Research Scientists, or Senior Research Scientists, on the areas of symmetric key cryptography and lightweight cryptography. Both fresh PhD and experienced researchers are welcome to apply.

Salaries are globally competitive and are determined according to the successful applicants accomplishments, experience and qualifications. Review process starts immediately and will continue until all positions are filled.

00:11 [Job][New]

We are looking for outstanding candidates for a PhD position with strong interest in cryptography, and in particular practice-oriented provable security. Topics of interest may include: provable security of cryptographic implementations, security analysis of random number generators, cryptographic protocols, computer-assisted security proofs.

The PhD position is funded by the the DFG Research Training Group UbiCrypt, which is part of the Horst-Goertz-Institute. The Horst-Görtz-Institut is a leading university-based institution for interdisciplinary research in the field of IT security and cryptography and offers an attractive research environment.

Applicants are required to have completed (or be close to completing) a Bachelor, Master, or Diplom with outstanding grades in Computer Science, Mathematics, or closely related areas. Additional knowledge in related disciplines such as, e.g., complexity theory or IT security is welcome. The working and teaching language is English.

Please send your application to Sebastian Faust via e-mail. Applications should contain a CV, a short letter of motivation, copies of transcripts and certificates, and (if possible) names of references. Review of applications will start immediately until the position has been filled.

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.