International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

21:17 [Pub][ePrint] Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search, by Anja Becker, Nicolas Gama, Antoine Joux

  We give a simple heuristic sieving algorithm for the $m$-dimensional

exact shortest vector problem

(SVP) which runs in time $2^{0.3112m +o(m)}$. Unlike previous time-memory

trade-offs, we do not increase the memory, which stays at its bare minimum

$2^{0.2075m +o(m)}$. To achieve this complexity, we borrow a recent tool

from coding theory, known as nearest neighbor search for binary code

words. We simplify its analysis, and show that it can be adapted to solve

this variant of the fixed-radius nearest neighbor search problem:

Given a list of exponentially many unit vectors of $\\mR^m$, and an

angle $\\gamma\\pi$, find all pairs of

vectors whose angle $\\leq\\gamma\\pi$. The complexity is sub-quadratic which leads to the improvement for lattice sieves.

21:17 [Pub][ePrint] Efficient Constant Round Multi-Party Computation Combining BMR and SPDZ, by Yehuda Lindell and Benny Pinkas and Nigel P. Smart and Avishay Yanai

  Recently, there has been huge progress in the field of concretely efficient secure computation, even while providing security in the presence of malicious adversaries. This is especially the case in the two-party setting, where constant-round protocols exist that remain fast even over slow networks. However, in the multi-party setting, all concretely efficient fully-secure protocols, such as SPDZ, require many rounds of communication.

In this paper, we present an MPC protocol that is fully-secure in the presence of malicious adversaries and for any number of corrupted parties. Our construction is based on the constant-round BMR protocol of Beaver et al., and is the first fully-secure version of that protocol that makes black-box usage of the underlying primitives, and is therefore concretely efficient.

Our protocol includes an online phase that is extremely fast and mainly consists of each party locally evaluating a garbled circuit. For the offline phase we present both a generic construction (using any underlying MPC protocol), and a highly efficient instantiation based on the SPDZ protocol. Our estimates show the protocol to be considerably more efficient than previous fully-secure multi-party protocols.

09:17 [Pub][ePrint] Subversion-Resilient Signature Schemes, by Giuseppe Ateniese and Bernardo Magri and Daniele Venturi

  We provide a formal treatment of security of digital signatures against *subversion attacks* (SAs).

Our model of subversion generalizes previous work in several directions, and is inspired by the proliferation of software attacks (e.g.,\\ malware and buffer overflow attacks), and by the recent revelations of Edward Snowden about intelligence agencies trying to surreptitiously sabotage cryptographic algorithms.

The main security requirement we put forward demands that a signature scheme should remain unforgeable even in the presence of an attacker applying SAs (within a certain class of allowed attacks) in a fully-adaptive and *continuous* fashion.

Previous notions---e.g.,\\ the notion of security against algorithm-substitution attacks introduced by Bellare et al. (CRYPTO \'14) for symmetric encryption---were non-adaptive and non-continuous.

In this vein, we show both positive and negative results for the goal of constructing subversion-resilient signature schemes.

-Negative results. As our main negative result, we show that a broad class of randomized signature schemes is unavoidably insecure against SAs, even if using just a single bit of randomness.

This improves upon earlier work that was only able to attack schemes with larger randomness space. When designing our new attack we consider undetectability as an explicit adversarial goal, meaning that the end-users (even the ones knowing the signing key) should not be able to detect that the signature scheme was subverted.

-Positive results. We complement the above negative results by showing that signature schemes with *unique* signatures are subversion-resilient against all attacks that meet a basic undetectability requirement. A similar result was shown by Bellare et al. for symmetric encryption, who proved the necessity to rely on *stateful* schemes; in contrast unique signatures are *stateless*, and in fact they are among the fastest and most established digital signatures available.

We finally show that it is possible to devise signature schemes secure against arbitrary tampering with the computation, by making use of an un-tamperable cryptographic reverse firewall (Mironov and Stephens-Davidowitz, EUROCRYPT \'15), i.e., an algorithm that \"sanitizes\" any signature given as input (using only public information). The firewall we design allows to successfully protect so-called re-randomizable signature schemes (which include unique signatures as special case).

As an additional contribution, we extend our model to consider multiple users and show implications and separations among the various notions we introduced.

While our study is mainly theoretical, due to its strong practical motivation, we believe that our results have important implications in practice and might influence the way digital signature schemes are selected or adopted in standards and protocols.

09:17 [Pub][ePrint] Broadcasting Intermediate Blocks as a Defense Mechanism Against Selfish-Mine in Bitcoin, by Ren Zhang

  The selfish-mine strategy in Bitcoin allows a miner to gain mining rewards more than her fair share. Prior defenses focus on preventing the attacker from winning a block race of equal-length chains. However, an attacker with more than one third of the computational power can still earn more block rewards even if she loses all equal-length block races. In this work we propose a novel defense mechanism. Our defense requires miners to publish intermediate blocks, or in-blocks for short, blocks that are valid with slightly lower puzzle difficulty, and mine on each others\' in-blocks. When a fork happens, the branch with most total amount of work, rather than the longest chain, will be adopted. Under our scheme, a selfish miner needs to have almost half of the computational power of the network to gain an unfair advantage, thus the selfish-mine strategy is no longer a threat to the system.

09:17 [Pub][ePrint] Notes on Two Fully Homomorphic Encryption Schemes Without Bootstrapping, by Yongge Wang

  Last week, IACR ePrint archive posted two fully homomorphic encryption schemes

without bootstrapping. In this note, we show that these schemes are trivially insecure.

19:12 [Event][New] SBSeg 2015: XV Brazilian Symposium on Information and Computational Systems Security

  Submission: 30 June 2015
Notification: 31 August 2015
From November 9 to November 12
Location: Florianopolis - SC, Brazil
More Information:

09:17 [Pub][ePrint] Computing Individual Discrete Logarithms Faster in $GF(p^n)$, by Aurore Guillevic

  The Number Field Sieve (NFS) algorithm is the best known method to

compute discrete logarithms (DL) in large characteristic finite fields

$\\FF_{p^n}$, with $p$ large and $n \\geq 1$ small. This algorithm

comprises four steps: polynomial selection, relation collection,

linear algebra and finally, individual logarithm computation. The

first step outputs two numbers fields equipped with a map to

$\\FF_{p^n}$. After the relation collection and linear algebra

phases, the (virtual) logarithm of a subset of elements in each number

field is known. The fourth step computes a preimage in one number

field of the target element in $\\FF_{p^n}$. If one can write the

target preimage as a product of elements of known (virtual) logarithm,

then one can deduce the discrete logarithm of the target.

The traditional approach for the individual logarithm step can be

extremely slow, and it is too slow especially for

$n$ greater than 3. Its asymptotic complexity is $L_Q[1/3, c]$ with $c

\\geq 1.44$. We present a new preimage computation that provides a

dramatic improvement for individual logarithm computations for small

$n$, both in practice and in asymptotic running-time: we have

$L_Q[1/3, c]$ with $c = 1.14$ for $n=2,4$, $c = 1.26$ for $n=3,6$ and

$c = 1.34$ for $n=5$. Our method generalizes to any $n$; in particular

$c < 1.44$ for the two state-of-the-art variants of NFS for extension


09:17 [Pub][ePrint] Time-Lock Puzzles from Randomized Encodings, by Nir Bitansky and Shafi Goldwasser and Abhishek Jain and Omer Paneth and Vinod Vaikuntanathan and Brent Waters

  Time-lock puzzles, introduced by May, Rivest, Shamir and Wagner, is a mechanism for sending messages ``to the future\'\'. A sender

can quickly generate a puzzle with a solution $s$ that remains hidden until a moderately large amount of time $t$ has elapsed. The solution $s$ should be hidden from any adversary that runs in time significantly less than $t$, including resourceful parallel adversaries with polynomially many processors.

While the notion of time-lock puzzles has been around for 22 years, there has only been a *single* candidate proposed. Fifteen years ago, Rivest, Shamir and Wagner suggested a beautiful candidate time-lock puzzle based on the assumption that exponentiation modulo an RSA integer is an ``inherently sequential\'\' computation.

We show that various flavors of {\\em randomized encodings} give rise to time-lock puzzles of varying strengths, whose security can be shown assuming *the existence* of non-parallelizing languages, which are languages that require circuits of depth at least $t$ to decide, in the worst-case. The existence of such languages is necessary for the existence of time-lock puzzles.

We instantiate the construction with different randomized

encodings from the literature, where increasingly better efficiency is obtained based on increasingly stronger cryptographic assumptions, ranging from one-way functions to indistinguishability obfuscation. We also observe that time-lock puzzles imply one-way functions, and thus the reliance on some cryptographic assumption is necessary.

Finally, generalizing the above, we construct other types of puzzles such as *proofs of work* from randomized encodings and a

suitable worst-case hardness assumption (that is necessary for such puzzles to exist).

09:17 [Pub][ePrint] Higher-Order Differential Meet-in-The-Middle Preimage Attacks on SHA-1 and BLAKE, by Thomas Espitau and Pierre-Alain Fouque and Pierre Karpman

  At CRYPTO 2012, Knellwolf and Khovratovich presented a differential formulation of advanced meet-in-the-middle techniques for preimage attacks on hash functions. They demonstrated the usefulness of their approach by significantly improving the previously best known attacks on SHA-1 from CRYPTO~2009, increasing the number of attacked rounds from a 48-round one-block pseudo-preimage without padding and a 48-round two-block preimage without padding to a 57-round one-block preimage without padding and a 57-round two-block preimage with padding, out of 80 rounds for the full function.

In this work, we exploit further the differential view of meet-in-the-middle techniques and generalize it to higher-order differentials. Despite being an important technique dating from the mid-90\'s, this is the first time higher-order differentials have been applied to meet-in-the-middle preimages. We show that doing so may lead to significant improvements to preimage attacks on hash functions with a simple linear message expansion. We extend the number of attacked rounds on SHA-1 to give a 62-round one-block preimage without padding, a 56-round one-block preimage with padding, and a

62-round two-block preimage with padding. We also apply our framework to the more recent SHA-3 finalist BLAKE and its newer variant BLAKE2, and give an attack for a 2.75-round preimage with padding, and a 7.5-round pseudo-preimage on the compression function.

09:17 [Pub][ePrint] Key-Recovery Attacks on ASASA, by Brice Minaud and Patrick Derbez and Pierre-Alain Fouque and Pierre Karpman

  The ASASA construction is a new design scheme introduced at ASIACRYPT 2014 by Biruykov, Bouillaguet and Khovratovich. Its versatility was illustrated by building two public-key encryption schemes, a secret-key scheme, as well as super S-box subcomponents of a white-box scheme. However one of the two public-key cryptosystems was recently broken at CRYPTO 2015 by Gilbert, Plût and Treger.

As our main contribution, we propose a new algebraic key-recovery attack able to break at once the secret-key scheme as well as the remaining public-key scheme, in time complexity 2^63 and 2^39 respectively (the security parameter is 128 bits in both cases).

Furthermore, we present a second attack of independent interest on the same public-key scheme, which heuristically reduces the problem of breaking the scheme to an LPN instance with tractable parameters. This allows key recovery in time complexity 2^56.

Finally, as a side result, we outline a very efficient heuristic attack on the white-box scheme, which breaks instances claiming 64 bits of security under one minute on a desktop computer.

06:10 [Event][New] Mycrypt 2016: Int'l Conference on Cryptology & Malicious Security hosted in Malaysia

  Submission: 15 April 2016
Notification: 1 August 2016
From December 1 to December 2
Location: Kuala Lumpur, Malaysia
More Information: