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

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.

15:17 [Pub][ePrint] Optimized Implementation of General Secret Sharing Scheme , by Lein Harn and Ching-Fang Hsu*

  Secret sharing (SS) is one of the most important cryptographic primitives used for data outsourcing. The (t, n) SS was introduced by Shamir and Blakley separately in 1979. The secret sharing policy of the (t, n) threshold SS is far too simple for many applications because it assumes that every shareholder has equal privilege to the secret or every share-holder is equally trusted. Ito et al. introduced the concept of a general secret sharing scheme (GSS). In a GSS, a secret is divided among a set of shareholders in such a way that any \"qualified\" subset of shareholders can access the secret, but any \"unqualified\" subset of shareholders cannot access the secret. The secret access structure of GSS is far more flexible than threshold SS. In this paper, we propose an optimized implementation of GSS. Our proposed scheme first uses Boolean logic to derive two important subsets, one is called which is the minimal positive access subset and the other is called which is the maximal negative access subset, of a given general secret sharing structure. Then, condi-tions of parameters of a GSS are established based on these two important subsets. Fur-thermore, integer linear/non-linear programming is used to optimize the size of shares of a GSS. The complexity of linear/non-linear programming is where is the number of shares generated by the dealer. This proposed design can be applied to implement GSS based on any classical SS. We use two GSSs, one is based on Shamir\'s weighted SS (WSS) using linear polynomial and the other is based on Asmuth-Bloom\'s SS using Chinese Re-mainder Theorem (CRT), to demonstrate our design. In comparing with existing GSSs, our proposed scheme is more efficient and can be applied to all classical SSs.

06:17 [Pub][ePrint] Faster Private Set Intersection based on OT Extension, by Benny Pinkas and Thomas Schneider and Michael Zohner

  Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing any information about items that are not in the intersection. It is one of the best studied applications of secure computation and many PSI protocols have been proposed. However, the variety of existing PSI protocols makes it

difficult to identify the solution that performs best in a respective scenario, especially since they were not all implemented and compared in the same setting.

In this work, we give an overview on existing PSI protocols that are secure against semi-honest adversaries. We take advantage of the most recent efficiency improvements in OT extension to propose significant optimizations to previous PSI protocols and to suggest a new PSI protocol whose runtime is superior to that of existing protocols. We compare the performance of the protocols both theoretically and experimentally, by implementing all protocols on the same platform, and give recommendations on which protocol to use in a particular setting.

06:17 [Pub][ePrint] Improved Differential Attacks on Reduced SIMON Versions, by Ning Wang, Xiaoyun Wang, Keting Jia, Jingyuan Zhao

  SIMON is a family of lightweight block ciphers which are designed by the U.S National Security Agency in 2013. In this paper, we improve the previous differential attacks on SIMON family of block ciphers by considering some bit-difference equations. Combining with some new observations on key guess policies of SIMON family, we mount differential attacks on 21-round SIMON32/64, 22-round SIMON$48/72$, 22-round SIMON48/96, 28-round SIMON$64/96$ and SIMON$64/128$ with time complexity about $2^{46}$, $2^{63}$, $2^{71}$, $2^{60}$ and $2^{60}$ encryptions respectively. As far as we know, these results are the best attacks on reduced-round SIMON versions.

06:17 [Pub][ePrint] Related Key Secure PKE from Hash Proof Systems, by Dingding Jia, Bao Li, Xianhui Lu, Qixiang Mei

  In this paper, we present a construction of public key encryption

secure against related key attacks from hash proof systems in the

standard model. We show that the schemes presented by Jia et

al. (Provsec2013) are special cases of our general theory, and also

give other instantiations based on the QR and DCR assumptions. To

fulfill the related key security, we require the hash proof systems

to satisfy the key homomorphism and computational finger-printing properties. Compared with the construction given by Wee (PKC2012), our construction removed the use of one-time