*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]
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]
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 Makingat 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