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-06-01
16:05 [Event][New]

Submission: 10 August 2015
From November 1 to November 3
Location: Beijing, China

2015-05-31
21:17 [Pub][ePrint]

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]

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]

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]

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.

2015-05-30
09:17 [Pub][ePrint]

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]

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]

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

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

2015-05-29
19:12 [Event][New]

Submission: 30 June 2015
From November 9 to November 12
Location: Florianopolis - SC, Brazil

09:17 [Pub][ePrint]

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

fields.

09:17 [Pub][ePrint]

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