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

2014-07-07
09:17 [Pub][ePrint]

Constrained pseudorandom functions (introduced independently by Boneh and Waters (CCS 2013), Boyle, Goldwasser, and Ivan (PKC 2014), and Kiayias, Papadopoulos, Triandopoulos, and Zacharias (CCS 2013)), are pseudorandom functions (PRFs) that allow the owner of the secret key $k$ to compute a constrained key $k_f$, such that anyone who possesses $k_f$ can compute the output of the PRF on any input $x$ such that $f(x) = 1$ for some predicate $f$. The security requirement of constrained PRFs state that the PRF output must still look indistinguishable from random for any $x$ such that $f(x) = 0$.

Boneh and Waters show how to construct constrained PRFs for the class of bit-fixing as well as circuit predicates. They explicitly left open the question of constructing constrained PRFs that are delegatable - i.e., constrained PRFs where the owner of $k_f$ can compute a constrained key

$k_{f\'}$ for a further restrictive predicate $f\'$. Boyle, Goldwasser, and Ivan left open the question of constructing constrained PRFs that are also verifiable. Verifiable random functions (VRFs), introduced by Micali, Rabin, and Vadhan (FOCS 1999), are PRFs that allow the owner of the

secret key $k$ to prove, for any input $x$, that $y$ indeed is the output of the PRF on $x$; the security requirement of VRFs state that the PRF output must still look indistinguishable from random, for any $x$ for which a proof is not given.

In this work, we solve both the above open questions by constructing constrained pseudorandom functions that are simultaneously verifiable and delegatable.

09:17 [Pub][ePrint]

In this work we explore new techniques for building short signatures

from obfuscation. Our goals are twofold. First, we would like to

achieve short signatures with adaptive security proofs. Second, we

would like to build signatures with fast signing, ideally

significantly faster than comparable signatures that are not based on

obfuscation. The goal here is to create an \"imbalanced\" scheme where

signing is fast at the expense of slower verification.

We develop new methods for achieving short and fully secure

obfuscation-derived signatures. Our base signature scheme is built

from punctured programming and makes a novel use of the \"prefix

technique\" to guess a signature. We find that our initial scheme has

slower performance than comparable algorithms (e.g. EC-DSA). We find

that the underlying reason is that the underlying PRG is called

l^2 times for security parameter l.

To address this issue we construct a more efficient scheme by adapting the Goldreich-Goldwasser-Micali [GGM86] construction to form the basis for a new puncturable PRF. This puncturable PRF accepts

variable-length inputs and has the property that evaluations on all

prefixes of a message can be efficiently pipelined. Calls to the

puncturable PRF by the signing algorithm therefore make fewer

invocations of the underlying PRG, resulting in reduced signing

costs.

We evaluate our puncturable PRF based signature schemes using a

variety of cryptographic candidates for the underlying PRG. We show

that the resulting performance on message signing is competitive with

that of widely deployed signature schemes.

09:17 [Pub][ePrint]

Hyper-bent functions as a subclass of bent functions attract much interest and it is elusive to completely characterize hyper-bent functions. Most of known hyper-bent functions are Boolean functions with Dillon exponents and they are often characterized by special values of Kloosterman sums.

In this paper, we present a method for characterizing hyper-bent functions

with Dillon exponents. A class of hyper-bent functions with Dillon exponents

over $\\mathbb{F}_{2^{2m}}$ can be characterized by

a Boolean function over $\\mathbb{F}_{2^m}$, whose Walsh spectrum takes the same value twice.

Further, we show several classes of

hyper-bent functions with Dillon exponents characterized by

Kloosterman sum identities and the Walsh

spectra of some common Boolean functions.

09:17 [Pub][ePrint]

The lightweight block cipher PRIDE designed by Albrecht et al., appears in CRYPTO 2014. The designers claim that their method of constructing linear layer is good both in security and efficiency. In this paper, we find 16 different 2-round iterative characteristics utilizing the weaknesses of S-box and linear layer, construct several 15-round differentials. Based on one of the differentials, we launch differential attack on 18-round PRIDE. The data, time and memory complexity are $2^{60}$, $2^{66}$ and $2^{64}$, respectively.

09:17 [Pub][ePrint]

This paper introduces constant-time ARM Cortex-A8 ECDH software that

(1) is faster than the fastest ECDH option in the latest version of OpenSSL but

(2) achieves a security level above 2^200 using a prime above 2^400.

For comparison, this OpenSSL ECDH option is not constant-time and has a security level of only 2^80.

The new speeds are achieved in a quite different way

from typical prime-field ECC software:

they rely on a synergy between Karatsuba\'s method

and choices of radix smaller than the CPU word size.

09:17 [Pub][ePrint]

We find mathematically optimal side-channel distinguishers by looking at the side-channel as a communication channel. Our methodology can be adapted to any given scenario (device, signal-to-noise ratio, noise distribution, leakage model, etc.). When the model is known and the noise is Gaussian, the optimal distinguisher outperforms CPA and covariance. However, we show that CPA is optimal when the model is only known on a proportional scale. For non-Gaussian noise, we obtain different optimal distinguishers, one for each noise distribution. When the model is imperfectly known, we consider the scenario of a weighted sum of the sensitive variable bits where the weights are unknown and drawn from a normal law. In this case, our optimal distinguisher performs better than the classical linear regression analysis.

2014-07-03
18:17 [Pub][ePrint]

This paper suggests and explores the use of UCE security for the task of

turning VIL-ROM schemes into FIL-ROM ones. The benefits we offer over

to handle multi-stage games and greater efficiency. The paradigm consists of

(1) Showing that a VIL UCE function can instantiate the VIL RO in the scheme,

and (2) Constructing the VIL UCE function given a FIL random oracle. The main

technical contributions of the paper are domain extension transforms that

implement the second step. Leveraging known results for the first step we

automatically obtain FIL-ROM constructions for several primitives whose

security notions are underlain by multi-stage games. Our first domain extender

exploits indifferentiability, showing that although the latter does not work

directly for multi-stage games it can be used indirectly, through UCE, as a

tool for this end. Our second domain extender targets performance. It is

parallelizable and shown through implementation to provide significant

performance gains over indifferentiable domain extenders.

18:17 [Pub][ePrint]

In 2011 Stajano proposed Pico, a secure and easy-to-use alternative for passwords. Among the many proposals in this category, Pico stands out by being creative and convincing. However, the description as published leaves some details unspecified, and to the best of our knowledge the complete system has not yet been tested. This work presents detailed specifications and future-proof security protocols for Pico. Moreover, we present the first robust and efficient Pico implementation. Our implementation allows to further mature the Pico concept and can be used for large scale usability evaluations at negligible cost.

18:17 [Pub][ePrint]

Given a linear code $C$, one can define the $d$-th power of $C$ as the span of all componentwise products of $d$ elements of $C$. A power of $C$ may quickly fill the whole space. Our purpose is to answer the following question: does the square of a code typically\'\' fill the whole space? We give a positive answer, for codes of dimension $k$ and length roughly $\\frac{1}{2}k^2$ or smaller. The proof uses random coding and combinatorial arguments, together with algebraic tools involving the precise computation of the number of quadratic forms of a given rank, and the number of their zeros.

15:55 [Event][New]

Submission: 15 August 2014
From December 16 to December 17
Location: Hong Kong, China

2014-07-02
21:17 [Pub][ePrint]

Most lattice-based cryptographic schemes with a security proof suffer from large key sizes and heavy computations. This is also true for the simpler case of authentication protocols which are used on smart cards, as a very-constrained computing environment.

Recent progress on ideal lattices has significantly improved the efficiency, and made it possible to implement practical lattice-based cryptography on constrained devices. However, to the best of our knowledge, no previous attempts were made to implement lattice-based schemes on smart cards.

In this paper, we provide the results of our implementation of several state-of-the-art lattice-based authentication protocols on smart cards and a microcontroller widely used in smart cards. Our results show that only a few of the proposed lattice-based authentication protocols can be implemented using limited resources of such constrained devices, however, cutting-edge ones are suitably-efficient to be used practically on smart cards.

Moreover, we have implemented fast Fourier transform (FFT) and discrete Gaussian sampling with different typical parameters sets, as well as versatile lattice-based public-key encryptions. These results have noticeable points which help to design or optimize lattice-based schemes for constrained devices.