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

16:05 [Event][New] Inscrypt 2015: 11th International Conference on Information Security and Cryptology

  Submission: 10 August 2015
Notification: 8 October 2015
From November 1 to November 3
Location: Beijing, China
More Information:

21:17 [Pub][ePrint] Efficient, Pairing-Free, One Round Attribute-Based Authenticated Key Exchange, by Suvradip Chakraborty and Srinivasan Raghuraman and C. Pandu Rangan

  In this paper, we present a single round two-party attribute-based authenticated key exchange protocol. Since pairing is a costly operation and the composite order groups must be very large to ensure security, we focus on pairing free protocols in prime order groups. We propose a new protocol that is pairing free, working in prime order group and having tight reduction to Strong Diffie Hellman (SDH) problem under the Attribute-based CK model which is a natural extension of the CK model for the public key setting. Our proposed attribute based authenticated key exchange protocol (ABAKE) also does not depend on any underlying attribute based encryption schemes unlike the previous solutions for ABAKE. Ours is the first scheme that removes this restriction. Thus, the first major advantage is that smaller key sizes are sufficient to achieve comparable security. Our scheme has several other advantages. The major one being the capability to handle active adversaries. Most of the previous Attribute-Based authenticated key exchange protocols can offer security only under passive adversaries. Our protocol recognizes the corruption by an active adversary and aborts the process. In addition to this property, our scheme satisfies other security properties that are not covered by CK model such as forward secrecy, key compromise impersonation attacks and ephemeral key compromise impersonation attacks.

21:17 [Pub][ePrint] Democoin: A Publicly Verifiable and Jointly Serviced Cryptocurrency, by Sergey Gorbunov and Silvio Micali

  We present a new, decentralized, efficient, and secure digital cryptocurrency, in which the ordinary users themselves keep turns to ensure that the systems works well.

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