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

2013-07-03
11:51 [PhD][Update] Alexander Meurer: A Coding-Theoretic Approach to Cryptanalysis

  Name: Alexander Meurer
Topic: A Coding-Theoretic Approach to Cryptanalysis
Category:foundations

Description: In this thesis we study the applicability of coding-theoretic algorithms to cryptanalysis and provide new insights into the practical security of different cryptographic primitives. The main results can be summarised as follows:
  • We introduce a new generalised framework for the class of "Information Set Decoding" (ISD) algorithms. This class contains all instantiations of the best-known generic decoding algorithms for random linear codes to date.
  • By applying the so-called representation technique, we design a new ISD algorithm which asymptotically achieves an exponential improvement over all known methods. Within the generalised ISD framework we provide a rigorous formal proof of superiority of the new algorithm for arbitrary code rates.
  • We discuss different practical applications, e.g. we study the security of concrete parameter sets for the McEliece one-way function and we efficiently break all low-noise instances of the "Learning Parities with Noise" (LPN) problem. The main technical contribution of this part is a refined non-asymptotic analysis of the proposed algorithm.
  • A new algorithm that allows for error correction in RSA private keys is presented. This algorithms allows to recover the original RSA secret key in polynomial time (w.r.t. the bit length of the modulus) given a noisy copy, i.e. given a copy very every individual bit is independently flipped with (unknown) p[...]


  • 10:03 [PhD][New] Alexander Meurer: A Coding-Theoretic Approach to Cryptanalysis

      Name: Alexander Meurer
    Topic: A Coding-Theoretic Approach to Cryptanalysis
    Category: foundations

    Description: In this thesis we study the applicability of coding-theoretic algorithms to cryptanalysis and provide new insights into the practical security of different cryptographic primitives. We introduce a new generalised framework for the class of \"Information Set Decoding\" (ISD) algorithms. By applying the so-called representation technique, we design a new ISD algorithm which asymptotically achieves an exponential improvement over all known methods. Within the generalised ISD framework we provide a rigorous formal proof of superiority of the new algorithm for arbitrary code rates 0[...]


    09:17 [Pub][ePrint] Toeplitz matrix-vector product based GF(2^n) shifted polynomial basis multipliers for all irreducible pentanomials, by Jiangtao Han and Haining Fan

      Besides Karatsuba algorithm, optimal Toeplitz matrix-vector product (TMVP) formulae is another approach to design GF(2^n) subquadratic multipliers. However, when GF(2^n) elements are represented using a shifted polynomial basis, this approach is currently appliable only to GF(2^n)s generated by all irreducible trinomials and a special type of irreducible pentanomials, not all general irreducible pentanomials. The reason is that no transformation matrix, which transforms the Mastrovito matrix into a Toeplitz matrix, has been found. In this article, we propose such a transformation matrix and its inverse matrix for an arbitrary irreducible pentanomial. Because there is no known value of n for which either an irreducible trinomial or an irreducible pentanomial does not exist, this transformation matrix makes the TMVP approach a universal tool, i.e., it is applicable to all practical GF(2^n)s.



    09:17 [Pub][ePrint] Faster 128-EEA3 and 128-EIA3 Software, by Roberto Avanzi and Billy Bob Brumley

      The 3GPP Task Force recently supplemented mobile LTE network security with an additional set of confidentiality and integrity algorithms, namely 128-EEA3 and 128-EIA3 built on top of ZUC, a new keystream generator. We propose two novel techniques to improve the software performance of these algorithms. We show how delayed modular reduction increases the efficiency of the LFSR feedback function, yielding performance gains for ZUC and thus both 128-EEA3 and 128-EIA3. We also show how to leverage carryless multiplication to evaluate the universal hash function making up the core of 128-EIA3. Our software implementation results on Qualcomm\'s Hexagon DSP architecture indicate significant performance gains when employing these techniques: up to roughly a 2-fold and 2.5-fold throughput improvement for 128-EEA3 and 128-EIA3, respectively.



    09:17 [Pub][ePrint] DupLESS: Server-Aided Encryption for Deduplicated Storage, by Mihir Bellare and Sriram Keelveedhi and Thomas Ristenpart

      Cloud storage service providers such as Dropbox, Mozy, and others perform deduplication to save space by only storing one copy of each file uploaded. Should clients conventionally encrypt their files, however, savings are lost. Message-locked encryption (the most prominent manifestation of which is convergent encryption) resolves this tension. However it is inherently subject to brute-force attacks that can recover files falling into a known set. We propose an architecture that provides secure deduplicated storage resisting brute-force attacks, and realize it in a system called DupLESS. In DupLESS, clients encrypt under message-based keys obtained from a key-server via an oblivious PRF protocol. It enables clients to store encrypted data with an existing service, have the service perform deduplication on their behalf, and yet achieves strong confidentiality guarantees. We show that encryption for deduplicated storage can achieve performance and space savings close to that of using the storage service with plaintext data.





    2013-07-02
    21:17 [Pub][ePrint] How to Share a Lattice Trapdoor: Threshold Protocols for Signatures and (H)IBE, by Rikke Bendlin and Sara Krehbiel and Chris Peikert

      We develop secure \\emph{threshold} protocols for two important

    operations in lattice cryptography, namely, generating a hard lattice

    $\\Lambda$ together with a ``strong\'\' trapdoor, and sampling from a

    discrete Gaussian distribution over a desired coset of $\\Lambda$ using

    the trapdoor. These are the central operations of many cryptographic

    schemes: for example, they are exactly the key-generation and signing

    operations (respectively) for the GPV signature scheme, and they are

    the public parameter generation and private key extraction operations

    (respectively) for the GPV IBE. We also provide a protocol for

    trapdoor delegation, which is used in lattice-based hierarchical IBE

    schemes. Our work therefore directly transfers all these systems to

    the threshold setting.

    Our protocols provide information-theoretic (i.e., statistical)

    security against adaptive corruptions in the UC framework, and they

    are private and robust against an

    optimal number of semi-honest or malicious parties. Our Gaussian

    sampling protocol is both noninteractive and efficient, assuming

    either a trusted setup phase (e.g., performed as part of key

    generation) or a sufficient amount of interactive but offline

    precomputation, which can be performed before the inputs to the

    sampling phase are known.



    21:17 [Pub][ePrint] The Holey Grail: A special score function for non-binary traitor tracing, by B. Skoric and J.-J. Oosterwijk and J. Doumen

      We study collusion-resistant traitor tracing in the simple decoder approach, i.e. assignment of scores for each user separately.

    We introduce a new score function for non-binary bias-based traitor tracing. It has three special properties that have long been sought after:

    (i) The expected score of an innocent user is zero in each content position.

    (ii) The variance of an innocent user\'s score is~1 in each content position.

    (iii) The expectation of the coalition\'s score does not depend on the

    collusion strategy.

    We also find a continuous bias distribution that optimizes the asymptotic (large coalition) performance.

    In the case of a binary alphabet our scheme reduces exactly to the

    symmetrized Tardos traitor tracing system.

    Unfortunately, the asymptotic fingerprinting rate

    of our new scheme decreases with growing alphabet size.

    We regret to inform you that this grail has holes.



    21:17 [Pub][ePrint] Light-weight primitive, feather-weight security? A cryptanalytic knock-out. (Preliminary results), by Valentina Banciu and Simon Hoerder and Dan Page

      In [12], the authors present a new light-weight cryptographic primitive which supports an associated RFID-based authentication protocol. The primitive has some structural similarities to AES, but is presented as a keyed one-way function using a 128-bit key. Although a security analysis is included, this is at a high-level only. To provide a more concrete idea as to the security of this primitive, we therefore make three contributions: first, a structural attack requiring $O(2^{5})$ plaintext/ciphertext pairs (and hence effort online) plus $O(2^{21})$ effort offline, second an algebraic attack on round reduced versions of the primitive which requires only a single plaintext/ciphertext pair, and, third debunk the claimed attack of [36] on the same primitive as wishful thinking. Our structural attack completely breaks the primitive and the algebraic attack highlights a crucial weakness of the primitive: we conclude that although one can consider countermeasures against these specific attacks, the design in general is questionable and should therefore be avoided.



    21:17 [Pub][ePrint] Private Database Queries Using Somewhat Homomorphic Encryption, by Dan Boneh and Craig Gentry and Shai Halevi and Frank Wang and David J. Wu

      In a private database query system, a client issues queries to a database and obtains the results without learning anything else about the database and without the server learning the query. While previous work has yielded systems that can efficiently support disjunction queries, performing conjunction queries privately remains an open problem. In this work, we show that using a polynomial encoding of the database enables efficient implementations of conjunction queries using somewhat homomorphic encryption. We describe a three-party protocol that supports efficient evaluation of conjunction queries. Then, we present two implementations of our protocol using Paillier\'s

    additively homomorphic system as well as Brakerski\'s somewhat homomorphic cryptosystem. Finally, we show that the additional homomorphic properties of the Brakerski cryptosystem allow us to handle queries involving several thousand elements over a million-record database in just a few minutes, far outperforming the implementation using the additively homomorphic system.



    21:17 [Pub][ePrint] Locally Computable UOWHF with Linear Shrinkage, by Benny Applebaum and Yoni Moses

      We study the problem of constructing locally computable Universal One-Way Hash Functions (UOWHFs) $\\mathcal{H}:\\{0,1\\}^n \\rightarrow \\{0,1\\}^m$. A construction with constant \\emph{output locality}, where every bit of the output depends only on a constant number of bits of the input, was established by [Applebaum, Ishai, and Kushilevitz, SICOMP 2006]. However, this construction suffers from two limitations: (1) It can only achieve a sub-linear shrinkage of $n-m=n^{1\\epsilon}$; and (2) It has a super-constant \\emph{input locality}, i.e., some inputs influence a large super-constant number of outputs. This leaves open the question of realizing UOWHFs with constant output locality and linear shrinkage of $n-m= \\epsilon n$, or UOWHFs with constant input locality and minimal shrinkage of $n-m=1$.

    We settle both questions simultaneously by providing the first construction of UOWHFs with linear shrinkage, constant input locality, and constant output locality. Our construction is based on the one-wayness of ``random\'\' local functions -- a variant of an assumption made by Goldreich (ECCC 2000). Using a transformation of [Ishai, Kushilevitz, Ostrovsky and Sahai, STOC 2008], our UOWHFs give rise to a digital signature scheme with a minimal \\emph{additive} complexity overhead: signing $n$-bit messages with security parameter $\\kappa$ takes only $O(n+\\kappa)$ time instead of $O(n\\kappa)$ as in typical constructions. Previously, such signatures were only known to exist under an \\emph{exponential} hardness assumption.

    As an additional contribution, we obtain new locally-computable hardness amplification procedures for UOWHFs that preserve linear shrinkage.



    21:17 [Pub][ePrint] Instantiating Random Oracles via UCEs, by Mihir Bellare and Viet Tung Hoang and Sriram Keelveedhi

      This paper provides a (standard-model) notion of security for (keyed) hash functions, called UCE, that we show enables instantiation of random oracles (ROs) in a fairly broad and systematic way. Goals and schemes we consider include deterministic PKE; message-locked encryption; hardcore functions; point-function obfuscation; OAEP; encryption secure for key-dependent messages; encryption secure under related-key attack; proofs of storage; and adaptively-secure garbled circuits with short tokens. We can take existing, natural and efficient ROM schemes and show that the instantiated scheme resulting from replacing the RO with a UCE function is secure in the standard model. In several cases this results in the first standard-model schemes for these goals. The definition of UCE-security itself is quite simple, asking that outputs of the function look random given some \'leakage\', even if the adversary knows the key, as long as the leakage does not permit the adversary to compute the inputs.