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-10-24
09:17 [Pub][ePrint]

We present an Attribute Based Encryption system where access policies are expressed as polynomial size arithmetic circuits. We prove security against arbitrary collusions of users based on the learning with errors problem on integer lattices. The system has two additional useful properties: first, it naturally handles arithmetic circuits with arbitrary fan-in (and fan-out) gates. Second, secret keys are much shorter than in previous schemes: secret key size is proportional to the depth of the circuit where as in previous constructions the key size was proportional to the number of gates or wires in the circuit. The system is well suited for environments where access policies are naturally expressed as arithmetic circuits as is the case when policies capture statistical properties of the data or depend on arithmetic transformations of the data. The system also provides complete key delegation capabilities.

09:17 [Pub][ePrint]

We state a switching lemma for tests on adversarial inputs involving bilinear pairings in hard groups, where the tester can effectively switch the randomness used in the test from being given to the adversary to being chosen after the adversary commits its input.

The switching lemma can be based on any $k$-linear hardness assumptions on one of the groups. In particular, this enables convenient information theoretic arguments in the construction of sequence of games proving security of cryptographic schemes, paralleling proofs and constructions in the random oracle model.

As an immediate application, we show that the quasi-adaptive NIZK proofs of Jutla and Roy (ASIACRYPT 2013) for linear subspaces can be further shortened to \\emph{constant}-size proofs, independent of the number of witnesses and equations. In particular, under the SXDH assumption, a length $n$ vector of group elements can be proven to belong to a subspace of rank $t$ with a quasi-adaptive NIZK proof of just a single group element. Similar quasi-adaptive aggregation of proofs is also shown for Groth-Sahai NIZK proofs of linear multi-scalar multiplication equations, as well as linear pairing-product equations (equations without any quadratic terms).

09:17 [Pub][ePrint]

Let $G:\\bits^n\\to\\bits^m$ be a pseudorandom generator.

We say that a circuit implementation of $G$ is {\\em $(k,q)$-robust} if for every set $S$ of at most $k$ wires anywhere in the circuit, there is a set $T$ of at most $q|S|$ outputs, such that conditioned on the values of $S$ and $T$ the remaining outputs are pseudorandom.

We initiate the study of robust PRGs, presenting explicit and non-explicit constructions in which $k$ is close to $n$, $q$ is constant, and $m>>n$. These include unconditional constructions of robust $r$-wise independent PRGs and small-bias PRGs, as well as conditional constructions of robust cryptographic PRGs.

In addition to their general usefulness as a more resilient form of PRGs, our study of robust PRGs is motivated by cryptographic applications in which an adversary has a local view of a large source of secret randomness. We apply robust $r$-wise independent PRGs towards reducing the randomness complexity of private circuits and protocols for secure multiparty computation, as well as improving the black-box complexity\'\' of constant-round secure two-party computation.

09:17 [Pub][ePrint]

The first step in elliptic curve scalar multiplication algorithms based on scalar decompositions using efficient endomorphisms---including Gallant--Lambert--Vanstone (GLV) and Galbraith--Lin--Scott (GLS) multiplication, as well as higher-dimensional and higher-genus constructions---is to produce a short basis of a certain integer lattice involving the eigenvalues of the endomorphisms. The shorter the basis vectors, the shorter the decomposed scalar coefficients, and the faster the resulting scalar multiplication. Typically, knowledge of the eigenvalues allows us to write down a long basis, which we then reduce using the Euclidean algorithm, Gauss reduction, LLL, or even a more specialized algorithm.

In this work, we use elementary facts about quadratic rings to immediately write down a short basis of the lattice for the GLV, GLS, GLV+GLS, and Q-curve constructions on elliptic curves, and for genus 2 real multiplication constructions. We do not pretend that this represents a significant optimization in scalar multiplication, since the lattice reduction step is always an offline precomputation---but it does give a better insight into the structure of scalar decompositions. In any case, it is always more convenient to use a ready-made short basis than it is to compute a new one.

09:17 [Pub][ePrint]

In the recent breakthrough paper by Barbulescu,

Gaudry, Joux and Thom{\\\'e}, a quasi-polynomial time

algorithm (QPA) is proposed for the discrete logarithm problem over finite fields

of small characteristic. The time complexity analysis of the algorithm is

based on several heuristics presented in their paper.

We show that some of the heuristics

are problematic in their original forms,

in particular, when the field is not a Kummer extension.

We believe that the basic idea behind the new approach should still work,

and propose a fix to the algorithm in non-Kummer cases,

without altering the quasi-polynomial time complexity.

The modified algorithm is also heuristic.

Further study is required in order

to fully understand the effectiveness of the new approach.

09:17 [Pub][ePrint]

The iterated Even-Mansour (EM) scheme is a generalization of the original 1-round construction proposed in 1991, and can use one key, two keys, or completely independent keys. In this paper, we methodically analyze the security of all the possible iterated Even-Mansour schemes with two $n$-bit keys and up to four rounds, and show that none of them provides more than $n$-bit security. In particular, we can apply one of our new attacks to 4 steps of the LED-128 block cipher, reducing the time complexity of the best known attack on this scheme from $2^{96}$ to $2^{64}$. As another example of the broad applicability of our techniques, we show how to reduce the time complexity of the attack on two-key triple-DES (which is an extremely well studied and widely deployed scheme) when fewer than $2^n$ known plaintext-ciphertext pairs are given. Our attacks are based on a novel cryptanalytic technique called \\emph{multibridge} which connects different parts of the cipher such that they can be analyzed independently, exploiting its self-similarity properties. Finally, the key suggestions of the different parts are efficiently joined using a meet-in-the-middle attack.

09:17 [Pub][ePrint]

The MMB block cipher (Modular Multiplication-based Block cipher) is an iterative block cipher designed by Daemen, Govaerts, and Vandewalle in 1993 as an improvement of the PES and IPES ciphers.

In this paper we present several new related-key differential characteristics of MMB. These characteristics can be used to form several related-key boomerangs to attack the full MMB. Using 2^{20} adaptive chosen plaintexts and ciphertexts we recover all key bits in 2^{35} time for the full MMB. Our attack was experimentally verified, and it takes less than 15 minutes on a standard Intel i5 machine to recover the full MMB key.

After showing this practical attack on the full key of the full MMB, we present partial attacks on extended versions of MMB with up to 9 rounds (which is three more rounds than in the full MMB). We recover 62 out of the 128-bit key in time of 2^{29.2} for 7-round MMB, using 2^{20} adaptive chosen plaintexts and ciphertexts encrypted under 4 related-keys, and time of 2^{29} for 8-round MMB using 2^{20} adaptive chosen plaintexts and ciphertexts, encrypted under 6 related-keys. We show how an adversary can recover 31 out of the 128-bit key for the 9-round MMB in time of 2^{27.8} using 2^{19} adaptive chosen plaintexts and ciphertexts, encrypted under only 2 related-keys. We also show how the time complexity of all attacks can be reduced by partially precomputing the difference distribution table of MMB\'s components.

09:17 [Pub][ePrint]

Since AES and PRESENT are two international standard block ciphers representing the most elegant design strategies for byte-oriented and bit-oriented designs respectively, we regard AES and PRES\\-ENT the two most significant candidates to scrutinize with respect to related-key differential attack.

In EUROCRYPT 2010 and CRYPTO 2013, the security of AES with respect to related-key differential attack has been completely analyzed by Alex Biryukov et al and Pierre-Alain Fouque et al with automatic related-key differential characteristic searching tools.

In this paper, we propose two methods to describe the differential behaviour of an S-box with linear inequalities based on logical condition modelling and computational geometry.

In one method, inequalities are generated according to some conditional differential properties of the S-box; in the other method, inequalities are extracted from the H-representation of the convex hull of all possible differential patterns of the S-box.

For the second method, we develop a greedy algorithm for selecting a given number of inequalities from the convex hull. Using these inequalities combined with Mixed-Integer Linear Programming (MILP) technique, we successfully prove that the full-round PRESENT-80 is secure against standard related-key differential attack, which solves an open problem of the symmetric-key cryptography community. This proof is accomplished automatically on a workstation with 8 CPU cores in a time within 16 days. In a similar way, we also prove that the probability of the best related-key differential characteristic of full LBlock is upper bounded by $2^{-56}$, which is the first result concerning the security of full LBlock with respect to related-key differential attack.

The methodology presented in this paper is generic, automatic and applicable to lightweight constructions with small block size, small S-boxes, and bit-oriented operations, including but not limited to PRESENT, EPCBC, LBlock, etc, which opens a new interesting direction of research for bit-oriented ciphers and for the application of MILP technique in cryptography.

04:41 [Event][New]

From November 3 to November 3
Location: Berlin, Germany

04:34 [Job][New]

OVERVIEW

As an internationally active and highly growth-oriented company in the field of embedded security, ESCRYPT supports all industry segments in need of security solutions for embedded systems, including automotive, industrial control systems, energy, and consumer electronics. In this area, ESCRYPT GmbH, a 100-percent subsidiary of ETAS GmbH, a member of the Bosch Group, is a leading system house.

You will consult our customers in the areas concerning embedded and automotive cyber security. The consulting includes, but is not limited to, security analysis of existing security applications, security concepts, architecture of security solutions, and security design of secure systems. In addition, your task will be the adjustment and enhancement of existing IT security solutions. Furthermore, you will compile surveys and decision memos for new IT security technologies and products.

Depending on your background, you might also develop customized software for client projects in the area of embedded data security and engage in product development;

PROFESSIONAL REQUIREMENTS

You must have Master’s Degree in Computer Science, Information Technology or Information Security. A PhD. or experience in a position as Security Engineer, Security Consultant or Information Security Analyst is beneficial.

PERSONAL REQUIREMENTS

- Willing to work in a flexible team

- Reliability

- Independent and thoughtful

- Pleasant communication skills

WE OFFER

We offer opportunities for working independently and with self-reliance in a dynamic team whose members are highly qualified and internationally experienced. Your work environment will feature challenging and diversified tasks, flat hierarchies, and performance based-compensation in an appealing and open-minded corporate climate. We offer generous benefits.

Send us your full application with key number USA-1310S

04:33 [Job][New]

The Department of Computer Science at University College London (UCL) invites applications for a faculty position in the area of Information Security. We seek world-class talent; candidates must have an outstanding research track record. The appointment will be made at the rank of Lecturer.

We are looking to complement and strengthen our existing expertise in Information Security by recruiting in any of the following areas: computer forensics, information security risk management, economics of security, design and development of secure systems, or human factors of information security.

Since we are an experimental Computer Science department, and UCL is strongly committed to multi-disciplinary research, we are looking for researchers who conduct empirical security research, and are interested in collaboration with colleagues in the Faculty of Engineering (e.g. Crime Science, the Institute of Making) and within UCL (e.g. Transport Studies, Bartlett School of the Built Environment) and beyond (e.g. London Centre for Nanotechnology).