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-06-17
15:17 [Pub][ePrint]

In this paper, we report that we have solved the shortest vector problem (SVP) over a 128-dimensional lattice, which is currently the highest dimension of the SVP that has ever been solved. The security of lattice-based cryptography is based on the hardness of solving the SVP in lattices. In 2010 Micciancio \\textit{et al.} proposed a Gauss Sieve algorithm for heuristically solving the SVP using list $L$ of Gauss-reduced vectors. Milde \\textit{et al.} proposed a parallel implementation method for the Gauss Sieve algorithm. However, the efficiency of more than 10 threads in their implementation decreases due to a large number of non-Gauss-reduced vectors appearing in the distributed list of each thread. In this paper, we propose a more practical parallelized Gauss Sieve algorithm. Our algorithm deploys an additional Gauss-reduced list $V$ of sample vectors assigned to each thread, and all vectors in list $L$ remain Gauss-reduced by mutually reducing them using all sample vectors in $V$. Therefore, our algorithm enables the Gauss Sieve algorithm to run without excessive overhead even in a large-scale parallel computation of more than 1,000 threads. Moreover, for speed-up, we use the bi-directional rotation structure of an ideal lattice that makes the generation of additional vectors in the list with almost no additional overhead. Finally, we have succeeded in solving the SVP over a 128-dimensional ideal lattice generated by cyclotomic polynomial $x^{128}+1$ using about 30,000 CPU hours.

15:17 [Pub][ePrint]

We investigate alternative suspicion functions for bias-based traitor tracing schemes, and present a practical construction of a simple decoder that attains capacity in the limit of large coalition size $c$.

We derive optimal suspicion functions in both the Restricted-Digit Model and the Combined-Digit Model. These functions depend on information that is usually not available to the tracer -- the attack strategy or the tallies of the symbols received by the colluders. We discuss how such results can be used in realistic contexts.

We study several combinations of coalition attack strategy versus suspicion function optimized against some attack (another attack or the same). In many of these combinations the usual codelength scaling $\\ell \\propto c^2$ changes to a lower power of $c$, e.g. $c^{3/2}$. We find that the interleaving strategy is an especially powerful attack. The suspicion function tailored against interleaving is the key ingredient of the capacity-achieving construction.

2013-06-15
01:51 [Job][New]

Hochschule Furtwangen University, Germany Full-time Ph.D. Position

The Chair for Security in Distributed Systems, computer science Hochschule Furtwangen, Germany, offers a full-time PhD/Postdoc position.

The position involves research in the area of IT-Security/applied cryptography within the BMBF project UNIKOPS - Universell konfigurierbare Sicherheitslösung für Cyber-Physikalische heterogene Systeme. The successful candidate is expected to contribute to research in IT-Security and applied cryptography for CPS.

The position is available immediately and is fully funded. The salary scale for the position is TV-L E13. The gross income depends on the candidate\\\'s experience level. At the lowest level it corresponds to approx. 40,000 EUR per year. Contracts are initially offered for two years. An extension is possible.

He or she is given the possiblity to carry out a Ph.D.

The successful candidate should have a Master\\\'s degree in Computer Science, Mathematics, Information Security, or a related field. Knowledge in cryptography is an asset.

The deadline for applications is July 31, 2013. However, late applications will be considered until the position is filled.

http://www.hs-furtwangen.de/studierende/fakultaeten/informatik/forschung/universell-konfigurierbare-sicherheitsloesung-fuer-cyber-physikalische-heterogene-systeme-unikops/601-dirkwesthoff.html

2013-06-12
20:02 [PhD][Update]

19:45 [Job][New]

The Deutsche Telekom Chair of Mobile Business & Multilateral Security at Goethe University Frankfurt offers a position of a Scientific Assistant (m/f, E13 TV-G-U). To strengthen our team we are looking for a committed, creative and flexible PhD candidate (male/female) with advanced professional knowledge in Information Technology and interest in the current development in business informatics.

We are looking for people with advanced knowledge and special skills in at least three of the following areas:

- Network and System Security

- Privacy-Enhancing Technologies and data protection

- Identity Management

- Mobile Platforms, Smartcards and Trusted Computing

- Mobile Application Development (e.g. in Android, etc.)

- Cryptography

- Programming languages and experiences in software projects

- Administration skills in different platforms (e.g. UNIX, Linux, Windows)

- Web technologies and development

- Project management

The position is available immediately and has a fixed-term of 3 years with an extension option. Deadline for applications: 1st of July 2013 Please see our job advertisement for the full details on our career site at:

http://www.m-chair.net/wps/wse/home/rannenberg/career/

15:26 [Job][New]

15:17 [Pub][ePrint]

The design and analysis of lightweight block ciphers has been a very active research area over the last couple of years, with many innovative proposals trying to optimize different performance figures. However, since these block ciphers are dedicated to low-cost embedded devices, their implementation is also a typical target for side-channel adversaries. As preventing such attacks with countermeasures usually implies significant performance overheads, a natural open problem is to propose new algorithms for which physical security is considered as an optimization criteria, hence allowing better performances again. We tackle this problem by studying how much we can tweak standard block ciphers such as the AES Rijndael in order to allow efficient masking (that is one of the most frequently considered solutions to improve security against side-channel attacks). For this purpose, we first investigate alternative S-boxes and round structures. We show that both approaches can be used separately in order to limit the total number of non-linear operations in the block cipher, hence allowing more efficient masking. We then combine these ideas into a concrete instance of block cipher called Zorro. We further provide a detailed security analysis of this new cipher taking its design specificities into account, leading us to exploit innovative techniques borrowed from hash function cryptanalysis (that are sometimes of independent interest). Eventually, we conclude the paper by evaluating the efficiency of masked Zorro implementations in an 8-bit microcontroller, and exhibit their interesting performance figures.

15:17 [Pub][ePrint]

Leakage-resilient cryptography aims at formally proving the security of cryptographic implementations against large classes of side-channel adversaries. One important challenge for such an approach to be relevant is to adequately connect the formal models used in the proofs with the practice of side-channel attacks. It raises the fundamental problem of finding reasonable restrictions of the leakage functions that can be empirically verified by evaluation laboratories. In this paper, we first argue that the previous bounded leakage\" requirements used in leakage-resilient cryptography are hard to fulfill by hardware engineers. We then introduce a new, more realistic and empirically verifiable assumption of simulatable leakage, under which security proofs in the standard model can be obtained. We finally illustrate our claims by analyzing the physical security of an efficient pseudorandom generator (for which security could only be proven under a random oracle based assumption so far). These positive results come at the cost of (algorithm-level) specialization, as our new assumption is specifically defined for block ciphers. Nevertheless, since block ciphers are the main building block of many leakage-resilient

cryptographic primitives, our results also open the way towards more realistic constructions and proofs for other pseudorandom objects.

15:17 [Pub][ePrint]

15:17 [Pub][ePrint]

Gentry\'s bootstrapping\'\' technique (STOC 2009) constructs a fully

homomorphic encryption (FHE) scheme from a somewhat homomorphic\'\'

one that is powerful enough to evaluate its own decryption function.

To date, it remains the only known way of obtaining unbounded FHE.

Unfortunately, bootstrapping is computationally very expensive,

despite the great deal of effort that has been spent on improving its

efficiency. The current state of the art, due to Gentry, Halevi, and

Smart (PKC 2012), is able to bootstrap packed\'\' ciphertexts (which

encrypt up to a linear number of bits) in time only \\emph{quasilinear}

$\\Otil(\\lambda) = \\lambda \\cdot \\log^{O(1)} \\lambda$ in the security

parameter. While this performance is \\emph{asymptotically} optimal up

to logarithmic factors, the practical import is less clear: the

procedure composes multiple layers of expensive and complex

operations, to the point where it appears very difficult to implement,

and its concrete runtime appears worse than those of prior methods

(all of which have quadratic or larger asymptotic runtimes).

In this work we give \\emph{simple}, \\emph{practical}, and entirely

\\emph{algebraic} algorithms for bootstrapping in quasilinear time, for

both packed\'\' and non-packed\'\' ciphertexts. Our methods are easy

to implement (especially in the non-packed case), and we believe that

they will be substantially more efficient in practice than all prior

realizations of bootstrapping. One of our main techniques is a

substantial enhancement of the ring-switching\'\' procedure of Gentry

et al.~(SCN 2012), which we extend to support switching between two

rings where neither is a subring of the other. Using this procedure,

we give a natural method for homomorphically evaluating a broad class

of structured linear transformations, including one that lets us

evaluate the decryption function efficiently.

15:17 [Pub][ePrint]

For a number of elliptic curve-based cryptographic protocols, it is useful and sometimes necessary to be able to encode a message (a bit string) as a point on an elliptic curve in such a way that the message can be efficiently and uniquely recovered from the point. This is for example the case if one wants to instantiate CPA-secure ElGamal encryption directly in the group of points of an elliptic curve. More practically relevant settings include Lindell\'s UC commitment scheme (EUROCRYPT 2011) or structure-preserving primitives.

It turns out that constructing such an encoding function is not easy in general, especially if one wishes to encode points whose length is large relative to the size of the curve. There is a probabilistic, folklore\'\' method for doing so, but it only provably works for messages of length less than half the size of the curve.

In this paper, we investigate several approaches to injective encoding to elliptic curves, and in particular, we propose a new, essentially optimal geometric construction for a large class of curves, including Edwards curves; the resulting algorithm is also quite efficient, requiring only one exponentiation in the base field and simple arithmetic operations (however, the curves for which the map can be constructed have a point of order two, which may be a limiting factor for possible applications). The new approach is based on the existence of a covering curve of genus 2 for which a bijective encoding is known.