International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. 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).

2014-10-22
21:17 [Pub][ePrint] Differential Factors: Improved Attacks on SERPENT, by Cihangir Tezcan and Ferruh Özbudak

  A differential attack tries to capture the round keys corresponding to the S-boxes activated by a differential. In this work, we show that for a fixed output difference of an S-box, it may not be possible to distinguish the guessed keys that have a specific difference. We introduce these differences as differential factors. Existence of differential factors can reduce the time complexity of differential attacks and as an example we show that the 10, 11, and 12-round differential-linear attacks of Dunkelman et al. on SERPENT can actually be performed with time complexities reduced by a factor of 4, 4, and 8, respectively.



21:17 [Pub][ePrint] Cats and Dogs An Integrity for Voting Systems Based on Paper Ballots, by İhsan Haluk Akın

  Abstract--Voting systems based on paper ballots has a long

history with various problems. Vote-selling and correct outcome

are two major problems among many. In this work, we propose

a new solution to these problems by using UltraViolet (UV)

fiber paper Physical Unclonable Function (PUF). When applied

this solution not only prevents vote-selling but also ensures the

correctness of the outcome. With these two problems eliminated,

the voting systems based on paper ballots will have complete

integrity.



21:17 [Pub][ePrint] Low-Latency ECDSA Signature Verification - A Road Towards Safer Traffic -, by Miroslav Knezevic, Ventzislav Nikov, and Peter Rombouts

  Car-to-car and Car-to-Infrastructure messages exchanged in Intelligent Transportation Systems can reach reception rates up to and over 1000 messages per second. As these messages contain ECDSA signatures this puts a very heavy load onto the verification hardware. In fact the load is so high that currently it can only be achieved by implementations running on high end CPUs and FPGAs. These implementations are far from cost-effective nor energy efficient. In this paper we present an ASIC implementation of a dedicated ECDSA verification engine that can reach verification rates of up to 27.000 verifications per second using only 1.034 kGE.



21:17 [Pub][ePrint] A Unified Approach to Idealized Model Separations via Indistinguishability Obfuscation, by Matthew D. Green and Jonathan Katz and Alex J. Malozemoff and Hong-Sheng Zhou

  It is well known that the random oracle model is not sound in the sense that there exist cryptographic systems that are secure in the random oracle model but when instantiated by any family of hash functions become insecure. However, all known separation results require the attacker to send an appropriately crafted message to the challenger in order to break security. Thus, this leaves open the possibility that some cryptographic schemes, such as bit-encryption, are still sound in the random oracle model.

In this work we refute this possibility, assuming the existence of indistinguishability obfuscation. We do so in the following way. First, we present a random oracle separation for bit-encryption; namely, we show that there exists a bit-encryption protocol secure in the random oracle model but \\emph{completely insecure} when the random oracle is instantiated by any concrete function. Second, we show how to adapt this separation to work for most natural simulation-based and game-based definitions. Our techniques can easily be adapted to other idealized models, and thus we present a \\emph{unified approach} to showing separations for most protocols of interest in most idealized models.



21:17 [Pub][ePrint] How to Choose Interesting Points for Template Attack More Effectively?, by Guangjun Fan, Yongbin Zhou, Hailong Zhang, Dengguo Feng

  Template Attacks are widely accepted to be the most powerful side-channel attacks from an information theoretic point of view. For Template Attacks to be practical, one needs to choose some special samples as the interesting points in actual power traces. Up to now, many different approaches were introduced for choosing interesting points for Template Attacks. However, it is unknown that whether or not the pervious approaches of choosing interesting points will lead to the best classification performance of Template Attacks. In this work, we give a negative answer to this important question by introducing a practical new approach which has completely different basic principle compared with all the pervious approaches. Our new approach chooses the point whose distribution of samples approximates to a normal distribution as the interesting point. Evaluation results exhibit that Template Attacks based on the interesting points chosen by our new approach can achieve obvious better classification performance compared with Template Attacks based on the interesting points chosen by the pervious approaches. Therefore, our new approach of choosing interesting points should be used in practice to better understand the practical threats of Template Attacks.



21:17 [Pub][ePrint] Impossibility Results for Leakage-Resilient Zero Knowledge and Multi-Party Computation, by Rafail Ostrovsky and Giuseppe Persiano and Ivan Visconti

  In [AGP14] Ananth et al. showed that continual leakage-resilient non-transferable interactive proofs exist when a leak-free input-encoding phase is allowed and a common reference string is available. They left open the problem of removing the need of a common reference string.

In [BGJK12] Boyle et al. showed that for some interesting functionalities continual leakage-resilient secure computation is possible when leak-free interactive preprocessing and input-encoding phases are allowed. They left open the problem of removing the interactive preprocessing.

In this work we study the above questions. Our main contribution shows that leakage-resilient black-box zero-knowledge is impossible when relying on a leak free input-encoding phase only (i.e., without CRS/preprocessing). Additionally, we also show that leakage-resilient multi-party computation for all functionalities is impossible (regardless of the number of players assuming just one corrupted player) when relying only on a leak-free input-encoding phase (i.e., without CRS/preprocessing).

Our results are achieved by means of a new technique to prove lower bounds for leakage-resilient security. We use leakage queries to run an execution of a communication-efficient insecure (i.e., non-simulatable) protocol in the head of the adversary. Moreover our work shows an interesting connection between leakage resilience and security against reset attacks.



21:17 [Pub][ePrint] Self-Destruct Non-Malleability, by Sandro Coretti and Yevgeniy Dodis and Bj\\\"orn Tackmann and Daniele Venturi

  We introduce a new security notion for public-key encryption (PKE) that we dub non-malleability under (chosen-ciphertext) self-destruct attacks (NM-SDA), which appears to be the strongest natural PKE security notion below full-blown chosen-ciphertext (IND-CCA) security. In this notion, the adversary is allowed to ask many adaptive ``parallel\'\' decryption queries (i.e., a query consists of many ciphertexts) up to the point when the first invalid ciphertext is submitted. As such, NM-SDA security generalizes non-malleability against chosen plaintext attacks (NM-CPA, where only one parallel decryption query is allowed) and recently introduced indistinguishability against (chosen-ciphertext) self-destruct attacks (IND-SDA, where each adaptive query consists of a single ciphertext). After showing that NM-SDA is a {\\em strict} strengthening of NM-CPA and IND-SDA and allows for more applications, we establish the following two results:

Domain Extension: For any $K > 1$, there is a black-box construction of a $K$-bit NM-SDA PKE scheme from a single-bit NM-SDA PKE scheme. Moreover, this can be done using only $O(\\lambda)$ calls to the underlying single-bit NM-SDA scheme, where $\\lambda$ is the security parameter. To achieve our goal, we define and construct a novel type of continuous non-malleable code (NMC), called secret-state NMC, as we show that standard continuous NMCs are not enough for the natural ``expand-then-encrypt-bit-by-bit\'\' approach to work.

Black-Box Construction from IND-CPA: Prior work showed that NM-CPA secure PKE can be constructed from any IND-CPA secure PKE in a black-box way. Here we show that the same construction actually achieves our strictly stronger notion of NM-SDA security. (This requires a non-trivial extension of the original security proof to handle multiple parallel decryption queries.) Hence, the notions of IND-CPA, NM-CPA, IND-SDA and NM-SDA security are all equivalent, lying (plausibly, strictly?) below IND-CCA security. We also show how to improve the rate of the resulting NM-SDA scheme from quadratic to linear.



21:17 [Pub][ePrint] Random Oracle Uninstantiability from Indistinguishability Obfuscation, by Christina Brzuska and Pooya Farshim and Arno Mittelbach

  Assuming the existence of an indistinguishability obfuscator (iO), we show that a number of prominent constructions in the random-oracle model are uninstantiable in the standard model. We first show that the Encrypt-with-Hash (EwH) transform of Bellare, Boldyreva, and O\'Neill (CRYPTO 2007) for converting randomized public-key encryption (PKE) to deterministic PKE is not instantiable in the standard model. The techniques that we use to establish this result are flexible and lend themselves easily to other transformations. These include the classical Fujisaki-Okamoto transform (CRYPTO 1998) for converting CPA to CCA security, a transformation akin to that by Bellare and Keelveedhi (CRYPTO 2011) for obtaining key-dependent security, as well as the convergent encryption transform for obtaining messaged-locked encryption by Bellare, Keelveedhi, and Ristenpart (EUROCRYPT 2013). Our techniques build on the recent work of Brzuska, Farshim, and Mittelbach (CRYPTO 2014) and rely on the existence of iO for Turing machines or circuits to derive two flavors of uninstantiability. Our results call for a re-assessment of scheme design in the random-oracle model and point out the need for new transforms which do not suffer from our attacks.



21:17 [Pub][ePrint] Functional Encryption for Randomized Functionalities in the Private-Key Setting from Minimal Assumptions, by Ilan Komargodski and Gil Segev and Eylon Yogev

  We present a construction of a private-key functional encryption scheme for any family of randomized functionalities based on any such scheme for deterministic functionalities that is sufficiently expressive. Instantiating our construction with existing schemes for deterministic functionalities, we obtain schemes for any family of randomized functionalities based on a variety of assumptions (including the LWE assumption, simple assumptions on multilinear maps, and even the existence of any one-way function) offering various trade-offs between security and efficiency.

Previously, Goyal, Jain, Koppula and Sahai [Cryptology ePrint Archive, 2013] constructed a public-key functional encryption scheme for any family of randomized functionalities based on indistinguishability obfuscation.

One of the key insights underlying our work is that, in the private-key setting, a sufficiently expressive functional encryption scheme may be appropriately utilized for implementing proof techniques that were so far implemented based on obfuscation assumptions (such as the punctured programming technique of Sahai and Waters [STOC 2014]). We view this as a contribution of independent interest that may be found useful in other settings as well.



21:17 [Pub][ePrint] Exponent Blinding May Not Prevent Timing Attacks on RSA, by Werner Schindler

  The references \\cite{Schi00,BrBo03,AcSK05} treat timing attacks on RSA with CRT and Montgomery\'s multiplication algorithm in unprotected implementations.

It has been widely believed that exponent blinding would prevent any timing attack on RSA.

At cost of significantly more timing measurements this paper extends the before-mentioned attacks to RSA with CRT, Montgomery\'s multiplication algorithm and exponent blinding.

Simulation experiments are conducted, which confirm the theoretical results. Effective countermeasures exist.



21:17 [Pub][ePrint] Dynamic Behavior of RS latches using FIB processing and probe connection, by Naoya Torii ans Dai Yamamoro and Masahiko Takenaka and Tsutomu Matsumoto

  PUF (Physically Unclonable Function) technologies attract attention as a candidate to prevent counterfeit chips. A latch PUF is known as a high performance PUF among various types of proposed PUFs. In this paper we describe an experiment on a dynamic attack to a latch PUF consisting of RS latches, such as measuring the latch output by a probe connection after a FIB (Focused Ion Beam) processing. As a result, we confirmed that the latch PUF using the RS latch has a tolerance for the dynamic analysis, because the RS latch output was in influenced and changed by the FIB processing in our experiment.