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



21:17 [Pub][ePrint] An algorithm for MD5 single-block collision attack using high-performance computing cluster, by Anton A. Kuznetsov

  The parallel algorithm and its implementation for performing a single-block collision attack on MD5 are described. The algorithm is implemented as MPI program based upon the source code of Dr Marc Stevens\' collision search sequential program. In this paper we present a parallel single-block MD5 collision searching algorithm itself and details of its implementation. We also disclose a pair of new single-block messages colliding under MD5 that were found using our algorithm on the high-performance computing cluster.



21:17 [Pub][ePrint] Recent Results in Scalable Multi-Party Computation, by Jared Saia and Mahdi Zamani

  Secure multi-party computation (MPC) allows multiple parties to compute a known function over inputs held by each party, without any party having to reveal its private input. Unfortunately, traditional MPC algorithms do not scale well to large numbers of parties. In this paper, we describe several recent MPC algorithms that are designed to handle large networks. All of these algorithms rely on recent techniques from the Byzantine agreement literature on forming and using quorums. Informally, a quorum is a small set of parties, most of which are trustworthy. We describe the advantages and disadvantages of these scalable algorithms, and we propose new ideas for improving practicality of current techniques. Finally, we conduct simulations to measure bandwidth cost for several current MPC algorithms.



21:17 [Pub][ePrint] Bootstrapping for HElib, by Shai Halevi and Victor Shoup

  Gentry\'s bootstrapping technique is still the only known method of obtaining fully homomorphic encryption where the system\'s parameters do not depend on the complexity of the evaluated functions. Bootstrapping involves a recryption procedure where the scheme decryption is evaluated homomorphically. So far, there have been precious few implementations of recryption, and none that could handle

\"packed ciphertexts\" that encrypt vectors of elements.

In the current work we implemented recryption of fully-packed ciphertexts using the HElib library for somewhat-homomorphic encryption. This required extending the recryption algorithms from the literature, as well as many aspects of the HElib library.

Our implementation supports bootstrapping of packed ciphertexts over

many extension fields/rings. One example that we tested involves

ciphertexts that encrypt vectors of 1024 elements from GF(2^{16}). In that setting, the recryption procedure takes under 5.5 minutes (at security-level ~ 76) on a single core, and allows a depth-9

computation before the next recryption is needed.



20:56 [Job][New] PhD student, Chalmers University of Technology, Sweden

  PhD position in Secure and Private Machine Learning and Decision Making

at the Department of Computer Science and Engineering, Chalmers University of Technology

Application deadline: November 21, 2014

Expected starting date: January 2015

Job description

We are looking for an excellent, motivated, self-driven doctoral student to work in the area of machine learning and decision theory with a focus on security and privacy. The position is for five years at the Department of Computer Science and Engineering, within the division of Computing Science and the group of Algorithms, Learning and Computational Biology (http://www.cse.chalmers.se/research/lab/), who are doing research on fields ranging from machine learning, statistics, algorithms, optimisation, reinforcement learning to computational biology, text and massive data analysis.

The student will be expected to develop and analyse state-of-the-art algorithms for distributed machine learning and decision making that provide users with strong privacy guarantees. In particular, the research will be focused on machine learning and differential privacy for distributed systems, but some aspects of the work will involve recent advances in cryptography. The student will be supervised by Dr. Christos Dimitrakakis (Machine learning, decision theory and differential privacy - see http://www.cse.chalmers.se/~chrdimi/ ) and co-supervised by Dr. Katerina Mitrokotsa (Cryptography and security - see http://www.cse.chalmers.se/~aikmitr/ ).

Employment will be in the scope of the Swiss Sense Synergy project, whose aim is to develop intelligent location-based networking protocols and crowdsourcing applications, in collaboration with three Swiss universities. Further info about the Swiss Sense Synergy project can be found here http://goo.gl/tmQ9NJ

Details about Employment

PhD student positions are limited to five years and no

18:17 [Pub][ePrint] BRUTUS: Identifying Cryptanalytic Weaknesses in CAESAR First Round Candidates, by Markku-Juhani O. Saarinen

  This ``half-year\'\' report summarizes our results from security

analysis covering all 57 CAESAR first round candidates. We have manually

identified security issues with three candidates, two of which are

more serious, and these ciphers been withdrawn from the competition.

We have developed a testing

framework, BRUTUS, to facilitate automatic detection of simple security

lapses and susceptible statistical structures across all ciphers.

From this testing we have security usage notes on four submissions and

statistical notes on a further four. We highlight that some of the CAESAR

algorithms pose an elevated risk if employed in real-life protocols due

to a class of adaptive chosen plaintext attacks. Although AEADs are often

defined (and are best used) as discrete primitives that authenticate and

transmit only complete messages, in practice these algorithms are

easily implemented in a fashion that outputs observable ciphertext data

when the algorithm has not received all of the (attacker-controlled)

plaintext. For an implementor, this strategy

appears to offer seemingly harmless and compliant storage and latency

advantages. If the algorithm uses the same state for secret

keying information, encryption, and integrity protection, and the

internal mixing permutation is not cryptographically strong, an attacker

can exploit the ciphertext-plaintext feedback loop to to reveal secret

state information or even keying material. We conclude that

the main advantages of exhaustive, automated cryptanalysis is that it

acts as a very necessary sanity check for implementations and gives the

cryptanalyst insights that can be used to focus more specific attack

methods on given candidates.



18:17 [Pub][ePrint] Near Optimal Rate Homomorphic Encryption for Branching Programs, by Aggelos Kiayias and Nikos Leonardos and Helger Lipmaa and Kateryna Pavlyk and Qiang Tang

  We initiate the study of good rate homomorphic encryption schemes.

Based on previous work on securely evaluating (binary I/O) branching programs, we propose a leveled homomorphic encryption scheme

for {\\em large-output} polynomial-size branching programs (which we call $\\mathbf{L/poly}$) that possesses near optimal-rate. The rate analysis of the new scheme is intricate: the best rate is achieved if a certain parameter $s$ is set equal to the only positive root of a degree-$m$ polynomial, where $m$ is the length of the branching program. We employ the Newton-Puiseux algorithm to find a Puiseux series for this parameter, and based on this, propose a $\\Theta (\\log m)$-time algorithm to find an integer approximation to $s$.

We also describe a rate-optimal 1-out-of-$n$ CPIR based on rate-optimal homomorphic encryption. In concrete terms, when applied to say, a movie database with $n = 2^{16}$ elements of $\\ell = 3.8 \\cdot 10^{9}$-bits, the client can privately download a movie with a communication rate of almost $0.99$, hence sacrificing only about $1\\%$ of bandwidth for privacy.

We also analyze the optimality of the rate efficiency of our scheme in a novel model that may be of independent interest. Our $1$-out-of-$n$ CPIR has rate $ 1- 1.72 \\sqrt{k / \\ell} \\cdot \\log_{2} n + O_\\ell(\\ell^{-1})$, while we show that no black-box construction surpasses $1 - \\sqrt{k / \\ell} (\\log n/ \\log \\log n) + O_\\ell(\\ell^{-1})$ in terms of rate, where $\\ell$ is the length of the database elements and $k$ the security parameter.