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-10-07
03:17 [Pub][ePrint]

In this paper we present a new attack on the polynomial version of the Ring-LWE assumption, for certain carefully chosen number fields. This variant of RLWE, introduced in [BV11] and called the PLWE assumption, is known to be as hard as the RLWE assumption for 2-power cyclotomic number fields, and for cyclotomic number fields in general with a small cost in terms of error growth. For general number fields, we articulate the relevant properties and prove security reductions for number fields with those properties. We then present an attack on PLWE for number fields satisfying certain properties.

03:17 [Pub][ePrint]

Divisible E-cash systems allow users to withdraw a unique coin of value $2^n$ from a bank, but then to spend it in several times to distinct merchants. In such a system, whereas users want anonymity of their transactions, the bank wants to prevent, or at least detect, double-spending, and trace the defrauders. While this primitive was introduced two decades ago, quite a few (really) anonymous constructions have been introduced. In addition, all but one were just proven secure in the random oracle model, but still with either weak security models or quite complex settings and thus costly constructions.

The unique proposal, secure in the standard model, appeared recently and is unpractical. As evidence, the authors left the construction of an efficient scheme secure in this model as an open problem.

In this paper, we answer it with the first efficient divisible E-cash system secure in the standard model.

It is based on a new way of building the coins, with a unique and public global tree structure for all the coins. Actually, we propose two constructions: a very efficient one in the random oracle model and a less efficient, but still practical, in the standard model. They both achieve constant time for withdrawing and spending coins, while allowing the bank to quickly detect double-spendings by a simple comparison of the serial numbers of deposited coins to the ones of previously spent coins.

03:17 [Pub][ePrint]

Feistel constructions have been shown to be indifferentiable

from random permutations (STOC 2011). Whereas how to properly

mix the keys into an un-keyed Feistel construction (without

appealing to domain separation technique) to obtain a block

cipher which resists known-key and chosen-key attacks remains

an open problem. We study this. NSA\'s SIMON family of block

ciphers takes a construction which has the subkey xored into a

halve of the state at each round. More clearly, at the $i$-th

round, the state is updated according to

$$(x_i,x_{i-1})\\mapsto(x_{i-1}\\oplus F_i(x_i)\\oplus k_i,x_i)$$

For such key-alternating Feistel ciphers, we show that 21

rounds are sufficient to achieve indifferentiability from ideal

ciphers with $2n$-bit blocks and $n$-bit keys, assuming the

$n$-to-$n$-bit round functions $F_1,\\ldots,F_{21}$ to be random

and public and an identical user-provided $n$-bit key to be

applied at each round. This gives a solution to the problem

mentioned before, and is the first to study the

indifferentiability of key-alternating Feistel ciphers to our

knowledge.

03:17 [Pub][ePrint]

The aim of this paper is to introduce some modifications in Tor, in order to improve user\'s anonymity and relay\'s security. Thus, we introduced a system that will ensure anonymity for all users, while

maintaining the ability to break the anonymity of a sender in case of misconduct. The revocation of the anonymity will require the use of secret sharing schemes, since we assume that, the lifting of the

anonymity of the dishonest user should not depend on a single entity, but on a consensus within the network. In addition to the revocation of the anonymity, we propose in this paper further improvements

such as mixing Tor traffic with those of the major internet groups, using the camouflage, or introducing a honeypot in the network.

00:17 [Pub][ePrint]

State-of-the-art fault-based cryptanalysis methods are capable of breaking most

recent ciphers after only a few fault injections. However, they require temporal

and spatial accuracies of fault injection that were believed to rule out

low-cost injection techniques such as voltage, frequency or temperature

manipulation. We investigate selection of supply-voltage and temperature values

that are suitable for high-precision fault injection even up to a single bit.

The object of our studies is an ASIC implementation of the recently presented

block cipher PRINCE, for which a two-stage fault attack scheme has been

suggested lately. This attack requires, on average, about four to five fault

injections in well-defined locations. We show by electrical simulations that

voltage-temperature points exist for which faults show up at locations required

for a successful attack with a likelihood of around 0.1\\%. This implies that the

complete attack can be mounted by approximately 4,000 to 5,000 fault injection

attempts, which is clearly feasible.

00:17 [Pub][ePrint]

We propose two extremely stealthy hardware Trojans that facilitate

fault-injection attacks in cryptographic blocks. The Trojans are carefully

inserted to modify the electrical characteristics of predetermined transistors

in a circuit by altering parameters such as doping concentration and dopant

area. These Trojans are activated with very low probability under the presence

of a slightly reduced supply voltage (0.001 for 20\\% $V_{dd}$ reduction). We

demonstrate the effectiveness of the Trojans by utilizing them to inject faults

into an ASIC implementation of the recently introduced lightweight cipher %ip

PRINCE. Full circuit-level simulation followed by differential cryptanalysis

demonstrate that the secret key can be reconstructed after around 5

fault-injections.

2014-10-06
12:52 [Event][New]

Submission: 31 October 2014
From October 31 to October 31

2014-10-05
06:17 [Pub][ePrint]

Identity Based Encryption (IBE) has been constructed from bilinear pairings, lattices and quadratic residuosity. The latter is an attractive basis for an IBE owing to the fact that it is a well-understood hard problem from number theory. Cocks constructed the first such scheme, and subsequent improvements have been made to achieve anonymity and improve space efficiency. However, the anonymous variants of Cocks\' scheme thus far are all less efficient than the original. In this paper, we present a new universally-anonymous IBE scheme based on the quadratic residuosity problem. Our scheme has better performance than the universally anonymous scheme from Ateniese and Gasti (CT-RSA 2009) at the expense of more ciphertext expansion. Another contribution of this paper is a modification to a variant of the space-efficient scheme by Boneh, Gentry and Hamburg (FOCS 07) that results in an IND-ID-CPA secure IBE scheme with comparable efficiency to Cocks, but with reduced ciphertext expansion.

06:17 [Pub][ePrint]

Program obfuscation is the process of making a program \"unintelligible\" without changing the program\'s underlying input/output behavior. Although there is a long line of work on heuristic techniques for obfuscation, such approaches do not provide any cryptographic guarantee on their effectiveness. A recent result by Garg et al. (FOCS 2013), however, shows that cryptographic program obfuscation is indeed possible based on a new primitive called a \\emph{graded encoding scheme}.

In this work, we present the first implementation of such an obfuscator. We describe several challenges and optimizations we made along the way, present a detailed evaluation of our implementation, and discuss research problems that need to be addressed before such obfuscators can be used in practice.

06:17 [Pub][ePrint]

Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O\'Neill (CRYPTO 2007), is an important database encryption technique which allows quick, logarithmic-time, search over encrypted data items. The technique is most effective in scenarios where frequent search queries are performed over a huge database of highly sensitive, yet unpredictable, data items such as credit card or social security numbers. Such databases, however, are also the ideal target for hackers since even partial data leaks may reveal significantly damaging information to the attacker.

Motivated by the goal of limiting the damage in such scenarios, we apply the ideas from leakage resilient cryptography to deterministic public-key encryption (D-PKE). We formulate appropriate security notions for D-PKE in the presence of leakage, and present constructions that achieve them in the standard model. We work in the *continual* leakage model, where the secret-key is updated at regular intervals and an attacker can learn arbitrary but bounded leakage during each time interval. We, however, do not consider leakage during the updates. Our main construction is based on the (standard) linear assumption in bilinear groups, tolerating up to $0.5-o(1)$ fraction of arbitrary leakage. The leakage rate can be improved to $1-o(1)$ by relying on the SXDH assumption.

At a technical level, we propose and construct a continual leakage resilient\'\' version of the *all-but-one* lossy trapdoor functions, introduced by Peikert and Waters (STOC 2008). Our formulation and construction of leakage-resilient lossy-TDFs is of independent general interest for leakage-resilient cryptography.

06:17 [Pub][ePrint]

The topic of this paper is collusion resistant watermarking, a.k.a. traitor tracing, in particular bias-based traitor tracing codes as introduced by G.Tardos in 2003. The past years have seen an ongoing effort to construct efficient high-performance decoders for these codes.

In this paper we construct a score system from the Neyman-Pearson hypothesis test (which is known to be the most powerful test possible)

into which we feed all the evidence available to the tracer, in particular the codewords of *all* users. As far as we know, until now similar efforts have taken into consideration only the codeword of a single user, namely the user under scrutiny.

The Neyman-Pearson score needs as input the attack strategy of the colluders, which typically is not known to the tracer.

We insert the Interleaving attack, which plays a very special role in the theory of bias-based traitor tracing by virtue of being part of the asymptotic (i.e. large coalition size) saddlepoint solution.

The score system obtained in this way is universal: effective not only against the Interleaving attack, but against all other attack

strategies as well. Our score function for one user depends on the other users\' codewords in a very simple way: through the symbol tallies, which are easily computed.

We present bounds on the False Positive and False Negative error probability, yielding a.o. a prescription for setting the accusation threshold. We investigate the probability distribution of the score.

Finally we apply our construction to the area of (medical) Group Testing, which is related to traitor tracing.