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 get this service 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-02-14
19:17 [Pub][ePrint] Space-efficient, byte-wise incremental and perfectly private encryption schemes, by Kévin Atighehchi

  The problem raised by incremental encryption is the overhead due to the larger storage space required by the provision of random blocks together with the ciphered versions of a given document. Besides,

permitting variable-length modifications on the ciphertext leads to privacy preservation issues. In this paper we present incremental encryption schemes which are space-efficient, byte-wise incremental and which preserve perfect privacy in the sense that they hide the fact that an update operation has been performed on a ciphered document. For each scheme, the run time of updates performed turns out to be very efficient and we discuss the statistically adjustable trade-off between computational cost and storage space required by the produced ciphertexts.



19:17 [Pub][ePrint] Reducing the Overhead of Cloud MPC, by Ashish Choudhury and Arpita Patra and Nigel P. Smart

  We present a secure multi-party computation (MPC) protocol in the honest-majority setting, which aims to reduce the communication costs in the situation where there are a large number of parties (as in a cloud scenario). Our goal is to reduce the usage of point-to-point channels, so as to enable the cloud to be used for multiple different protocol executions. We assume that the number of adversarially controlled parties is relatively small, and that an adversary is unable to target the proactive corruption of a subset of the parties (technically we assume a static corruption model for simplicity). As well as enabling a cloud provider to run multiple MPC protocols, our protocol also has highly efficient theoretical communication costs as a general MPC protocol when compared with other protocols in the literature; in particular the communication cost, for circuits of a suitably large depth, is $\\Order(|\\Circuit| \\cdot \\kappa^7)$, for security parameter $\\kappa$~and circuit size $|\\Circuit|$.



19:17 [Pub][ePrint] Algorithms in HElib, by Shai Halevi and Victor Shoup

  HElib is a software library that implements homomorphic encryption (HE), specifically the Brakerski-Gentry-Vaikuntanathan (BGV) scheme, focusing on effective use of the Smart-Vercauteren ciphertext packing techniques and the Gentry-Halevi-Smart optimizations. The underlying cryptosystem serves as the equivalent of a \"hardware platform\" for HElib, in that it defines a set of operations that can be applied homomorphically, and specifies their cost. This \"platform\" is a SIMD environment (somewhat similar Intel SSE and the like), but with a unique cost metrics and parameters. In this report we describe some of the algorithms and optimization techniques that are used in HElib for data movement and simple linear algebra over this \"platform.\"



16:17 [Pub][ePrint] Unified, Minimal and Selectively Randomizable Structure-Preserving Signatures, by Masayuki Abe and Jens Groth and Miyako Ohkubo and Mehdi Tibouchi

  We construct a structure-preserving signature scheme that is selectively randomizable and works in all types of bilinear groups. We give matching lower bounds showing that our structure-preserving signature scheme is optimal with respect to both signature size and public verification key size.

State of the art structure-preserving signatures in the asymmetric setting consist of 3 group elements, which is known to be optimal. Our construction preserves the signature size of 3 group elements and also at the same time minimizes the verification key size to 1 group element.

Depending on the application, it is sometimes desirable to have strong unforgeability and in other situations desirable to have randomizable signatures. To get the best of both worlds, we introduce the notion of selective randomizability where the signer may for specific signatures provide randomization tokens that enable randomization.

Our structure-preserving signature scheme unifies the different pairing-based settings since it can be instantiated in both symmetric and asymmetric groups. Since previously optimal structure-preserving signatures had only been constructed in asymmetric bilinear groups this closes an important gap in our knowledge. Having a unified signature scheme that works in all types of bilinear groups is not just conceptually nice but also gives a hedge against future cryptanalytic attacks. An instantiation of our signature scheme in an asymmetric bilinear group may remain secure even if cryptanalysts later discover an efficiently computable homomorphism between the source groups.



16:17 [Pub][ePrint] Tight security bounds for multiple encryption, by Yuanxi Dai, John Steinberger

  Multiple encryption---the practice of composing a blockcipher several

times with itself under independent keys---has received considerable

attention of late from the standpoint of provable security. Despite

these efforts proving definitive security bounds (i.e., with matching

attacks) has remained elusive even for the special case of triple

encryption. In this paper we close the gap by improving both the best

known attacks and best known provable security, so that both bounds

match. Our results apply for arbitrary number of rounds and show that

the security of $\\ell$-round multiple encryption is precisely

$\\exp(\\kappa + \\min\\{\\kappa (\\ell\'-2)/2), n (\\ell\'-2)/\\ell\'\\})$ where

$\\exp(t) = 2^t$ and where $\\ell\' = 2\\lceil \\ell/2\\rceil$ is the even

integer closest to $\\ell$ and greater than or equal to $\\ell$, for all

$\\ell \\geq 1$. Our technique is based on Patarin\'s H-coefficient

method and reuses a combinatorial result of Chen and Steinberger

originally required in the context of key-alternating ciphers.



16:17 [Pub][ePrint] A Simple Framework for Noise-Free Construction of Fully Homomorphic Encryption from a Special Class of Non-Commutative Groups, by Koji Nuida

  We propose a new and simple framework for constructing fully homomorphic encryption (FHE) which is completely different from the previous work. We use finite non-commutative (a.k.a., non-abelian) groups which are \"highly non-commutative\" (e.g., the special linear groups of size two) as the underlying structure. We show that, on such groups, the AND and NOT operations on plaintext bits (which are sufficient to realize an arbitrary operation by composing them) can be emulated by a \"randomized commutator\" (which essentially requires the non-commutativity) and division operations on ciphertext elements, respectively. Then we aim at concealing the \"core structure\" of ciphertexts by taking conjugation by a secret element (where the non-commutativity is again essential), rather than adding noise to the ciphertext as in the previous FHE schemes. The \"noise-freeness\" of our framework yields the fully-homomorphic property directly, without the bootstrapping technique used in the previous schemes to remove the noise amplified by the homomorphic operations. This makes the overall structure of the FHE schemes significantly simpler and easier to understand. Although a secure instantiation based on the framework has not been found, we hope that the proposed framework itself is of theoretical value, and that the framework is flexible enough to allow a secure instantiation in the future.



16:17 [Pub][ePrint] Towards Characterizing Complete Fairness in Secure Two-Party Computation, by Gilad Asharov

  The well known impossibility result of Cleve (STOC 1986) implies that in general it is impossible to securely compute a function with \\emph{complete fairness} without an honest majority. Since then, the accepted belief has been that \\emph{nothing} non-trivial can be

computed with complete fairness in the two party setting. The surprising work of Gordon, Hazay, Katz and Lindell (STOC 2008) shows that this belief is false, and that there exist \\emph{some} non-trivial (deterministic, finite-domain) boolean functions that can be computed fairly. This raises the fundamental question of characterizing complete fairness in secure two-party computation.

In this work we show that not only that some or few functions can be computed fairly, but rather an \\emph{enormous number} of functions can be computed fairly. In fact, \\emph{almost all} boolean functions with distinct domain sizes can be computed with complete fairness (for instance, more than $99.999\\%$ of the boolean functions with domain sizes $31 \\times 30$). The class of functions that is shown to be possible includes also rather involved and highly non-trivial tasks, such as set-membership, evaluation of a private (boolean) function, private matchmaking and set-disjointness.

In addition, we demonstrate that fairness is not restricted to the class of symmetric boolean functions where both parties get the same output, which is the only known feasibility result. Specifically, we show that fairness is also possible for asymmetric boolean functions where the output of the parties is not necessarily the same. Moreover, we consider the class of functions with \\emph{non-binary} output, and show that fairness is possible \\emph{for any finite range}.

The constructions are based on the protocol of Gordon et.~al, and its analysis uses tools from convex geometry.



16:17 [Pub][ePrint] Indistinguishability Obfuscation and UCEs: The Case of Computationally Unpredictable Sources, by Christina Brzuska and Pooya Farshim and Arno Mittelbach

  Random oracles are powerful cryptographic objects. They facilitate the security proofs of an impressive number of practical cryptosystems ranging from KDM-secure and deterministic encryption to point-function obfuscation and many more. However, due to an uninstantiability result of Canetti, Goldreich, and Halevi (STOC 1998) random oracles have become somewhat controversial. Recently, Bellare, Hoang, and Keelveedhi (BHK; CRYPTO 2013 and ePrint 2013/424, August 2013) introduced a new abstraction called Universal Computational Extractors (UCEs), and showed that they suffice to securely replace random oracles in a number of prominent applications, including all those mentioned above, without suffering from the aforementioned uninstantiability result. This, however, leaves open the question of constructing UCEs in the standard model.

We show that the existence of indistinguishability obfuscation (iO) implies (non-black-box) attacks on all the definitions that BHK proposed within their UCE framework in the original version of their paper, in the sense that no concrete hash function can satisfy them. We also show that this limitation can be overcome, to some extent, by restraining the class of admissible adversaries via a statistical notion of unpredictability. Following our attack, BHK (ePrint 2013/424, September 2013), independently adopted this approach in their work.

In the updated version of their paper, BHK (ePrint 2013/424, September 2013) also introduce two other novel source classes, called bounded parallel sources and split sources, which aim at recovering the computational applications of UCEs that fall outside the statistical fix. These notions keep to a computational notion of unpredictability, but impose structural restrictions on the adversary so that our original iO attack no longer applies. We extend our attack to show that indistinguishability obfuscation is sufficient to also break the UCE security of any hash function against bounded parallel sources. Towards this goal, we use the randomized encodings paradigm of Applebaum, Ishai, and Kushilevitz (STOC 2004) to parallelize the obfuscated circuit used in our attack, so that it can be computed by a bounded parallel source whose second stage consists of constant-depth circuits. We conclude by discussing the composability and feasibility of hash functions secure against split sources.



06:38 [PhD][New] Nizamuddin: On the Design of signcryption Schemes

  Name: Nizamuddin
Topic: On the Design of signcryption Schemes
Category: public-key cryptography





2014-02-13
05:56 [Job][New] Research Scientists, PhD, Institute for Infocomm Research, Singapore

  We are looking for research scientists on cyber-physical security, mobile security, and web security. The candidates should have PhD in computer science or computer engineering, and preferably on infocomm security, be highly motivated with strong R&D capability and also a good team player, have good presentation and communication skills, be able to perform deep system-level investigations of security mechanisms. The candidates are expected to create valuable intellectual properties, publish papers at top security conferences, and produce project deliverables in time.

Interested candidates please send CV to Jianying Zhou {jyzhou (at) i2r.a-star.edu.sg}. Fresh PhD is welcome to apply. Review of applications will begin immediately and will continue until the positions are filled. Short-listed candidates will be contacted for interview.



2014-02-11
09:02 [Job][Update] 1 PhD student in Information Security, Chalmers University of Technology, Gothenburg, Sweden

  We are looking for an excellent PhD candidate to work in the area of information and communication security with a focus on authentication problems in constrained settings. This is particularly important for applications involving mobile phones, wireless communication and RFID systems, which suffer from restrictions in terms of power resources, network connectivity, computational capabilities, as well as potential privacy issues. The overall aim of the project will be to develop nearly optimal algorithms for achieving security and privacy while minimising resource use.

More concretely, part of the research will involve the analysis and development of authentication protocols in specific settings. This will include investigating resistance of both existing and novel protocols against different types of attacks, theoretically and experimentally. In addition to investigating established settings, such as RFID authentication, the research will also explore more general authentication problems, such as those that arise in the context of trust in social networks, smartphone applications and collaborative data processing. This will be done by grounding the work in a generalised decision-making framework. The project should result in the development of theory and authentication mechanisms for noisy, constrained settings that strike an optimal balance between reliable authentication, privacy-preservation and resource consumption. Some previous research related to this research project can be found here: http://lasecwww.epfl.ch/~katerina/Publications.html

Applicants for the position shall have a Master’s Degree or corresponding in Computer Science, Informatics, Telecommunications or in a related discipline. A master\\\'s degree in information security or cryptography is a bonus.