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

15:17 [Pub][ePrint] On a new properties of number sequences ,a randomness test and a new RC4\'s key scheduling algorithm., by Samir Bouftass and Abdelhak Azhari

  In this paper, we introduce the concept of the derivative of sequence of numbers and define new statistical indices by which we discoverd new properties of randomly generated number sequences.

We also build a test for pseudo random generators based on these properties and use it to confirm the weakness of RC4 key scheduling algorithm that has been reported in the litterature.

In this rescpect we publish a new RC4\'s key scheduling algorithm that don\'t have this weakness.

12:17 [Pub][ePrint] Single-shot security for one-time memories in the isolated qubits model, by Yi-Kai Liu

  One-time memories (OTM\'s) are simple, tamper-resistant cryptographic devices, which can be used to implement sophisticated functionalities such as one-time programs. Can one construct OTM\'s whose security follows from some physical principle? This is not possible in a fully-classical world, or in a fully-quantum world, but there is evidence that OTM\'s can be built using \"isolated qubits\" -- qubits that cannot be entangled, but can be accessed using adaptive sequences of single-qubit measurements.

Here we present new constructions for OTM\'s using isolated qubits, which improve on previous work in several respects: they achieve a stronger \"single-shot\" security guarantee, which is stated in terms of the (smoothed) min-entropy; they are proven secure against adversaries who can perform arbitrary local operations and classical communication (LOCC); and they are efficiently implementable.

These results use Wiesner\'s idea of conjugate coding, combined with error-correcting codes that approach the capacity of the q-ary symmetric channel, and a high-order entropic uncertainty relation, which was originally developed for cryptography in the bounded quantum storage model.

12:17 [Pub][ePrint] Verified Implementations for Secure and Verifiable Computation, by José Bacelar Almeida and Manuel Barbosa and Gilles Barthe and Guillaume Davy and François Dupressoir and Benjamin Grégoire and Pie

  Formal verification of the security of software systems is gradually moving from the traditional focus on idealized models, to the more ambitious goal of producing verified implementations. This trend is also present in recent work targeting the verification of cryptographic software, but the reach of existing tools has so far been limited to cryptographic primitives, such as RSA-OAEP encryption, or standalone protocols, such as SSH. This paper presents a scalable

approach to formally verifying implementations of higher-level cryptographic systems, directly in the computational model.

We consider circuit-based cloud-oriented cryptographic protocols for secure and verifiable computation over encrypted data. Our examples share as central component Yao\'s celebrated transformation of a boolean circuit into an equivalent garbled form that can be evaluated securely in an untrusted environment. We leverage the foundations of garbled circuits set forth by Bellare, Hoang, and Rogaway (CCS 2012, ASIACRYPT 2012) to build verified implementations of garbling schemes, a verified implementation of Yao\'s secure

function evaluation protocol, and a verified (albeit partial) implementation of the verifiable computation protocol by Gennaro, Gentry, and Parno (CRYPTO 2010). The implementations are formally verified using EasyCrypt, a tool-assisted framework for building high-confidence cryptographic proofs, and critically rely on two novel features: a module and theory system that supports compositional reasoning, and a code extraction mechanism for generating

implementations from formalizations.

12:17 [Pub][ePrint] Transcript Secure Signatures Based on Modular Lattices, by Jeff Hoffstein and Jill Pipher and John M. Schanck and Joseph H. Silverman and William Whyte

  We introduce the notion of a class of lattice-based digital signature schemes based on modular properties of the coordinates of lattice vectors. We also suggest a method of making such schemes transcript secure via a rejection sampling technique of Lyubashevsky (2009). A particular instantiation of this approach is given, using NTRU lattices. Although the scheme is not supported by a formal security reduction, we present arguments for its security and derive concrete parameters based on the performance of state-of-the-art lattice reduction and enumeration techniques.

12:17 [Pub][ePrint] Automated Analysis of Cryptographic Assumptions in Generic Group Models, by Gilles Barthe and Edvard Fagerholm and Dario Fiore and John Mitchell and Andre Scedrov and Benedikt Schmidt

  We initiate the study of principled, automated, methods for analyzing hardness assumptions in generic group models, following the approach of symbolic cryptography. We start by defining a broad class of generic and symbolic group models for different

settings---symmetric or asymmetric (leveled) k-linear groups---and by

proving \"computational soundness\" theorems for the symbolic models.

Based on this result, we formulate a very general master theorem that formally relates the hardness of a (possibly interactive) assumption in these models to solving problems in polynomial algebra. Then, we systematically analyze these problems. We identify different classes of assumptions and obtain decidability and undecidability results.

Then, we develop and implement automated procedures for verifying the conditions of master theorems, and thus the validity of hardness assumptions in generic group models. The concrete outcome of this work is an automated tool which takes as input the statement of an assumption, and outputs either a proof of its

generic hardness or shows an algebraic attack against the assumption.

12:17 [Pub][ePrint] Template Attacks on Different Devices, by Omar Choudary and Markus G. Kuhn

  Template attacks remain a most powerful side-channel technique to

eavesdrop on tamper-resistant hardware. They use a profiling step to

compute the parameters of a multivariate normal distribution from a

training device and an attack step in which the parameters obtained

during profiling are used to infer some secret value (e.g.

cryptographic key) on a target device. Evaluations using the same

device for both profiling and attack can miss practical problems

that appear when using different devices. Recent

studies showed that variability caused by the use of either

different devices or different acquisition campaigns on the same

device can have a strong impact on the performance of template

attacks. In this paper, we explore further the effects that lead to

this decrease of performance, using four different Atmel XMEGA 256

A3U 8-bit devices. We show that a main difference between devices is

a DC offset and we show that this appears even if we use the same

device in different acquisition campaigns. We then explore several

variants of the template attack to compensate for these differences.

Our results show that a careful choice of compression method and

parameters is the key to improving the performance of these attacks

across different devices. In particular we show how to maximise the

performance of template attacks when using Fisher\'s Linear

Discriminant Analysis or Principal Component Analysis. Overall, we

can reduce the entropy of an unknown 8-bit value below 1.5 bits even

when using different devices.

12:17 [Pub][ePrint] FleXOR: Flexible garbling for XOR gates that beats free-XOR, by Vladimir Kolesnikov and Payman Mohassel and Mike Rosulek

  Most implementations of Yao\'s garbled circuit approach for 2-party secure computation use the {\\em free-XOR} optimization of Kolesnikov \\& Schneider (ICALP 2008). We introduce an alternative technique called {\\em flexible-XOR} (fleXOR) that generalizes free-XOR and offers several advantages. First, fleXOR can be instantiated under a weaker hardness assumption on the underlying cipher/hash function (related-key security only, compared to related-key and circular security required for free-XOR) while maintaining most of the performance improvements that free-XOR offers. Alternatively, even though XOR gates are not always ``free\'\' in our approach, we show that the other (non-XOR) gates can be optimized more heavily than what is possible when using free-XOR. For many circuits of cryptographic interest, this can yield a significantly (over 30\\%) smaller garbled circuit than any other known techniques (including free-XOR) or their combinations.

06:17 [Pub][ePrint] Leveled Fully Homomorphic Signatures from Standard Lattices, by Daniel Wichs

  In a homomorphic signature scheme, a user Alice signs some large data $x$ using her secret signing key and stores the signed data on a server. The server can then run some computation $y=g(x)$ on the signed data and homomorphically produce a short signature $\\sigma$. Anybody can verify the signature using Alice\'s public verification key and become convinced that $y$ is the correct output of the computation $g$ over Alice\'s data, without needing to have the underlying data itself.

In this work, we construct the first leveled fully homomorphic signature schemes that can evaluate arbitrary circuits over signed data, where only the maximal depth $d$ of the circuit needs to be fixed a priori. The size of the evaluated signature grows polynomially in $d$, but is otherwise independent of the circuit size or the data size. Our solutions are based on the hardness of the small integer solution (SIS) problem, which is in turn implied by the worst-case hardness of problems in standard lattices. We get a scheme in the standard model, albeit with large public parameters whose size must exceed the total size of all signed data. In the random-oracle model, we get a scheme with short public parameters. These results offer a significant improvement in capabilities and assumptions over the best prior homomorphic signature scheme due to Boneh and Freeman (Eurocrypt \'11).

As a building block of independent interest, we introduce a new notion called homomorphic trapdoor functions (HTDF). We show to how construct homomorphic signatures using HTDFs as a black box. We construct HTDFs based on the SIS problem by relying on a recent technique developed by Boneh et al. (Eurocrypt \'14) in the context of attribute based encryption.

06:17 [Pub][ePrint] Proof of Activity: Extending Bitcoin\'s Proof of Work via Proof of Stake, by Iddo Bentov and Charles Lee and Alex Mizrahi and Meni Rosenfeld

  We propose a new protocol for a cryptocurrency, that builds upon the Bitcoin protocol by combining its Proof of Work component with a Proof of Stake type of system. Our Proof of Activity (PoA) protocol offers good security against possibly practical future attacks on Bitcoin, and has a relatively low penalty in terms of network communication and storage space. We explore various attack scenarios and suggest remedies to potential vulnerabilities of the PoA protocol, as well as evaluate the performance of its core subroutine.

06:17 [Pub][ePrint] Block Ciphers - Focus On The Linear Layer (feat. PRIDE): Full Version, by Martin R. Albrecht and Benedikt Driessen and Elif Bilge Kavun and Gregor Leander and Christof Paar and Tolga Yalçın

  The linear layer is a core component in any substitution-permutation network block cipher. Its design significantly influences both the security and the efficiency of the resulting block cipher. Surprisingly, not many general constructions are known that allow to choose trade-offs between security and efficiency. Especially, when compared to Sboxes, it seems that the linear layer is crucially understudied. In this paper, we propose a general methodology to construct good, sometimes optimal, linear layers allowing for a large variety of trade-offs. We give several instances of our construction and on top underline its value by presenting a new block cipher. PRIDE is optimized for 8-bit micro-controllers and significantly outperforms all academic solutions both in terms of code size and cycle count.

06:17 [Pub][ePrint] Early Propagation and Imbalanced Routing, How to Diminish in FPGAs, by Amir Moradi and Vincent Immler

  This work deals with DPA-resistant logic styles, i.e., cell-level countermeasures against power analysis attacks that are known as a serious threat to cryptographic devices. Early propagation and imbalanced routings are amongst the well-known issues of such countermeasures, that - if not considered during the design process - can cause the underlying cryptographic device to be vulnerable to certain attacks. Although most of the DPA-resistant logic styles target an ASIC design process, there are a few attempts to apply them in an FPGA platform. This is due to the missing freedom in FPGA design tools required to deal with the aforementioned problems. Our contribution in this work is to provide solutions for both early propagation and imbalanced routings considering a modern Xilinx FPGA as the target platform. Foremost, based on the WDDL concept we design a new FPGA-based logic style without early propagation in both precharge and evaluation phases. Additionally, with respect to the limited routing resources within an FPGA we develop a customized router to nd the best appropriate dual-rail routes for a given dual-rail circuit. Based on practical experiments on a Virtex-5 FPGA our evaluations verify the efficiency of each of our proposed approaches. They significantly improve the resistance of the design compared to cases not benefiting from our schemes.