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-01-22
19:17 [Pub][ePrint]

We prove (nearly) tight bounds on the concrete PRF-security of

two constructions of message-authentication codes (MACs):

(1) The truncated CBC-MAC construction, which operates as

plain CBC-MAC (without prefix-free encoding of messages), but

only returns a subset of the output bits.

(2) The MAC derived from the sponge hash-function family by

pre-pending a key to the message, which is the de-facto standard

method for SHA-3-based message authentication.

The tight analysis of keyed sponges is our main result

and we see this as an important step in validating SHA-3-based

authentication before its deployment. Still, our analysis crucially

relies on the one for truncated CBC as an intermediate step of

independent interest. Indeed, no previous security analysis of

truncated CBC was known, whereas only significantly weaker bounds have

been proved for keyed sponges following different approaches.

Our bounds are tight for the most relevant ranges of parameters, i.e.,

for messages of length (roughly) $\\ell \\le \\min\\{2^{n/4},2^r\\}$

blocks, where $n$ is the state size and $r$ is the desired output

length; and for $q \\ge \\ell$ queries. Our proofs rely on a novel

application of Patarin\'s H-coefficient method to iterated MAC

constructions.

2015-01-20
10:17 [Pub][ePrint]

Group signature is a class of digital signatures with enhanced privacy. By using this type of signature, a user can prove membership of a specific group without revealing his identity, but in the case of a dispute, for a given signature, an authority can expose the identity of its signer. However, in some situations wherein it is necessary to only know whether a specified user is the signer of the given signature, the naive use of a group signature may be problematic since if the specified user is NOT the actual signer, then the identity of the actual signer will be exposed.

In this paper, inspired by this problem, we propose the notion of a deniable group signature, where with respect to a signature and a user, the opener can issue a proof that the opening result of the signature is NOT the specified user without revealing the actual signer. We also describe a fairly practical construction by extending the Groth group signature scheme (ASIACRYPT 2007). In particular, a denial proof in our scheme consists of 96 group elements, which is about twice the size of a signature in the Groth scheme. The proposed scheme is provably secure under the same assumptions as those of the Groth scheme.

10:17 [Pub][ePrint]

Many cryptographic protocols derive their security from the apparent computational intractability of the integer factorization problem. Currently, the best known integer-factoring algorithms run in subexponential time. Efficient parallel implementations of these algorithms constitute an important area of practical research. Most reported implementations use multi-core and/or distributed parallelization. In this paper, we use SIMD-based parallelization to speed up the sieving stage of integer-factoring algorithms. We experiment on the two fastest variants of factoring algorithms: the number-field sieve method and the multiple-polynomial quadratic sieve method. Using Intel\'s SSE2 and AVX intrinsics, we have been able to speed up index calculations in each core during sieving. This performance enhancement is attributed to a reduction in the packing and unpacking overheads associated with SIMD registers. We handle both line sieving and lattice sieving. We also propose improvements to make our implementations cache-friendly. We obtain speedup figures in the range 5--40%. To the best of our knowledge, no public discussions on SIMD parallelization in the context of integer-factoring algorithms are available in the literature.

10:17 [Pub][ePrint]

Side-channel attacks using only a single trace crucially

rely on the capability of reliably extracting side-channel

information (e.g. Hamming weights of intermediate target values)

from traces. In particular, in original versions of simple power

analysis (SPA) or algebraic side channel attacks (ASCA) it was

assumed that an adversary can correctly extract the Hamming

weight values for all the intermediates used in an attack. Recent

developments in error tolerant SPA style attacks relax this

unrealistic requirement on the information extraction and bring

renewed interest to the topic of template building or training

suitable machine learning classifiers.

In this work we ask which classifiers or methods, if any, are

most likely to return the true Hamming weight among their first

(say $s$) ranked outputs. We experiment on two data sets with

different leakage characteristics. Our experiments show that the

most suitable classifiers to reach the required performance for

pragmatic SPA attacks are Gaussian templates, Support Vector

Machines and Random Forests, across the two data sets that we

considered. We found no configuration that was able to satisfy

the requirements of an error tolerant ASCA in case of complex

leakage.

10:17 [Pub][ePrint]

The Learning with Errors (LWE) problem has become a central building block of modern cryptographic constructions. This work collects and presents hardness results for concrete instances of LWE. In particular, we discuss algorithms proposed in the literature and give the expected resources required to run them. We consider both generic instances of LWE as well as small secret variants. Since for several methods of solving LWE we require a lattice reduction step, we also review lattice reduction algorithms and propose a refined model for estimating their running times. We also give concrete estimates for various families of LWE instances, provide a Sage module for computing these estimates and highlight gaps in the knowledge about algorithms for solving the Learning with Errors problem.

2015-01-19
09:23 [Event][New]

Submission: 25 January 2015
From May 21 to May 21
Location: San Jose, USA

2015-01-18
12:56 [Job][New]

We are looking for a research scientist (post-doc) in cryptography with a special emphasis on topics relevant in the context of security and privacy for cloud environments. Ideally you have experience in fields like multi-party computation, distributed cryptography, rational cryptography or privacy enhancing technologies.

You will be mainly involved in a EU research project on cloud cryptography with tasks related to the design of cryptography for novel distributed information sharing systems.

• Project homepage (avail. Feb. 2015): https://prismacloud.eu

• AIT Safety&Security Department: http://www.ait.ac.at/departments/digital-safety-security

2015-01-17
10:17 [Pub][ePrint]

E-voting protocols aim at achieving a wide range of sophisticated security properties and, consequently, commonly employ advanced cryptographic primitives. This makes their design as well as rigorous analysis quite challenging. As a matter of fact, existing

automated analysis techniques, which are mostly based on automated

theorem provers, are inadequate to deal with commonly used

cryptographic primitives, such as homomorphic encryption and mix-nets, as well as some fundamental security properties, such as

verifiability.

This work presents a novel approach based on refinement type systems

for the automated analysis of e-voting protocols. Specifically, we

design a generically applicable logical theory which, based on pre-

and post-conditions for security-critical code, captures and guides

the type-checker towards the verification of two fundamental

properties of e-voting protocols, namely, vote privacy and

verifiability. We further develop a code-based cryptographic

abstraction of the cryptographic primitives commonly used in

e-voting protocols, showing how to make the underlying algebraic

properties accessible to automated verification through logical

refinements. Finally, we demonstrate the effectiveness of our

approach by developing the first automated analysis of Helios, a

popular web-based e-voting protocol, using an off-the-shelf

type-checker.

10:17 [Pub][ePrint]

A few work has ever been performed in cryptanalysis of block ciphers using cube attacks. This paper presents a new framework for an efficient key recovery attack on block ciphers based on cube technique. In this method, a cube tester is positioned at the middle of the cipher which is extended in two directions over the maximum possible upper and lower rounds, given that some subkey bits are guessed. It is shown that an automated algorithm for this dynamic cube attack on block ciphers can be realized. Furthermore, we show its effectiveness on two lightweight block ciphers KATAN and SIMON. Our results shows that this method can break 117 and 152 out of 254 rounds of KATAN-32 in non-full-codebook and full-codebook attack scenarios, respectively. In the case of SIMON32/64, we succeed to cryptanalyse 16 and 18 out of 32 rounds, by the same scenarios. Both results show that although this method does not outperform all the existing attacks on these two ciphers, it can absolutely compete with the well-established and mature methods of cryptanalysis of block ciphers, such as linear, differential and meet in

the middle attack families.

10:17 [Pub][ePrint]

In this paper, we assess the practicability of HashSieve, a recently proposed sieving algorithm for the Shortest Vector Problem (SVP) on lattices, on multi-core shared memory systems. To this end, we devised a parallel implementation that scales well, and is based on a probable lock-free system to handle concurrency. The probable lock-free system, implemented with spin-locks and compare-and-swap operations, acts, likely, as a lock-free mechanism, since threads block only when strictly required and chances are that they are not required to block, because resource contention is very low. With our implementation, we were able to solve the SVP on an arbitrary lattice in dimension 96, in less than 17.5 hours, using 16 physical cores. The least squares fit of the execution times of our implementation, in seconds, lies between $2^{(0.32n-15)}$ or $2^{(0.33n-16)}$, which indicates that sieving algorithms are indeed way more practical than believed.

10:17 [Pub][ePrint]

Lattice-based encryption schemes still suffer from a low message throughput per ciphertext. This is mainly due to the fact that the underlying schemes do not tap the full potentials of LWE. Many constructions still follow the one-time-pad approach considering LWE instances as random vectors added to a message, most often encoded bit vectors. Recently, at Financial Crypto 2015 El Bansarkhani et al. proposed a novel encryption scheme based on the A-LWE assumption (Augmented LWE), where data is embedded into the error term without changing its target distributions. By this novelty it is possible to encrypt much more data as compared to the traditional one-time-pad approach and it is even possible to combine both concepts. In this paper we revisit this approach and propose amongst others several algebraic techniques in order to significantly improve the message throughput per ciphertext. Furthermore, we give a thorough security analysis as well as an efficient implementation of the CCA1-secure encryption scheme instantiated with the most efficient trapdoor construction. In particular, we attest that it even outperforms the CPA-secure encryption scheme from Lindner and Peikert presented at CT-RSA 2011.