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-08-30
15:17 [Pub][ePrint] Lattice-Based FHE as Secure as PKE, by Zvika Brakerski and Vinod Vaikuntanathan

  We show that (leveled) fully homomorphic encryption (FHE) can be based on the hardness of $\\otild(n^{1.5+\\epsilon})$-approximation for lattice problems (such as GapSVP) under quantum reductions for any $\\epsilon>0$ (or $\\otild(n^{2+\\epsilon})$-approximation under classical reductions). This matches the best known hardness for ``regular\'\' (non-homomorphic) lattice based public-key encryption up to the $\\epsilon$ factor. A number of previous methods had hit a roadblock at quasipolynomial approximation. (As usual, a circular security assumption can be used to achieve a non-leveled FHE scheme.)

Our approach consists of three main ideas: Noise-bounded sequential evaluation of

high fan-in operations; Circuit sequentialization using Barrington\'s Theorem; and finally,

successive dimension-modulus reduction.



15:17 [Pub][ePrint] Searching for Nonlinear Feedback Shift Registers with Parallel Computing, by Przemysław Dąbrowski and Grzegorz Łabuzek and Tomasz Rachwalik and Janusz Szmidt

  Nonlinear feedback shift registers (NLFSRs) are used to construct pseudorandom generators for stream ciphers. Their theory is not so complete as that of linear feedback shift registers (LFSRs). In general, it is not known how to construct all NLFSRs with maximum period. The direct method is to search for such registers with suitable properties. Advanced technology of parallel computing has been applied both in software and hardware to search for maximum period NLFSRs having a fairly simple algebraic normal form.



15:17 [Pub][ePrint] Cryptanalysis of the SIMON Family of Block Ciphers, by Hoda A. Alkhzaimi and Martin M. Lauridsen

  Recently, the U.S National Security Agency has published the specifications of two families of lightweight block ciphers, SIMON and SPECK, in ePrint report 2013/404. The ciphers are developed with optimization towards both hardware and software in mind. While the specification paper discusses design requirements and performance of the presented lightweight ciphers thoroughly, no security assessment is given. This paper is a move towards filling that cryptanalysis gap for the SIMON family of ciphers. We present a series of observations on the presented construction that, in some cases, yield attacks, while in other cases may provide basis of further analysis by the cryptographic community. Specifically, we obtain attacks using classical- as well as truncated differentials. In the former case, we show how the smallest version of SIMON, Simon32/64, exhibits a strong differential effect.



15:17 [Pub][ePrint] Warrant-Hiding Delegation-by-Certificate Proxy Signature Schemes, by Christian Hanser and Daniel Slamanig

  Proxy signatures allow an entity (the delegator) to delegate his signing capabilities to other entities (called proxies), who can then produce signatures on behalf of the delegator. Typically, a delegator may not want to give a proxy the power to sign any message on his behalf, but only messages from a well defined message space. Therefore, the so called delegation by warrant approach has been introduced. Here, a warrant is included into the delegator\'s signature (the so called certificate) to describe the message space from which a proxy is allowed to choose messages to produce valid signatures for. Interestingly, in all previously known constructions of proxy signatures following this approach, the warrant is made explicit and, thus, is an input to the verification algorithm of a proxy signature. This means, that a verifier learns the entire message space for which the proxy has been given the signing power. However, it may be desirable to hide the remaining messages in the allowed message space from a verifier. This scenario has never been investigated in context of proxy signatures, but seems to be interesting for practical applications. In this paper, we resolve this issue by introducing so called warrant-hiding proxy signatures. We provide a formal security definition of such schemes by augmenting the well established security model for proxy signatures by Boldyreva et al. Furthermore, we discuss strategies how to realize this warrant-hiding property and we also provide two concrete instantiations of such a scheme. They enjoy different advantages, but are both entirely practical. Moreover, we prove them secure with respect to the augmented security model.



15:17 [Pub][ePrint] Private Over-threshold Aggregation Protocols over Distributed Databases, by Myungsun Kim and Abedelaziz Mohaisen and Jung Hee Cheon and Yongdae Kim

  In this paper, we revisit the private over-threshold data aggregation problem, and formally define the problem\'s security requirements as both data and user privacy goals. To achieve both goals, and to strike a balance between efficiency and functionality, we devise a novel cryptographic construction that comes in two schemes; a fully decentralized construction and its practical but semi-decentralized variant. Both schemes are provably secure in the semi-honest model.

We analyze the computational and communication complexities of our construction, and show that it is much more efficient than the existing protocols in the literature.

Finally, we show that our basic protocol is efficiently transformed into a stronger protocol secure in the presence of malicious adversaries, together with performance and security analysis.



12:17 [Pub][ePrint] The Parallel-Cut Meet-In-The-Middle Attack, by Ivica Nikolic, Lei Wang and Shuang Wu

  We propose a new type of meet-in-the-middle attack that splits the

cryptographic primitive in parallel to the execution of the operations. The result of the division are two primitives that have smaller input sizes and thus require lower attack complexities.

However, the division is not completely independent and the sub-primitives depend (output of one is the input for the other) mutually on a certain number of bits. When the number of such bits is relatively small, we show a technique based on three classical meet-in-the-middle attacks that can recover the secret key of the cipher faster than an exhaustive search. We apply our findings to the lightweight block cipher KLEIN and show attacks on 10/11/13 rounds of KLEIN-64/-80/-96.

Our approach requires only one or two pairs of known plaintexts and always recovers the secret key.



12:17 [Pub][ePrint] On the Limits of Provable Anonymity, by Nethanel Gelernter and Amir Herzberg

  We study provably secure anonymity, focusing on ultimate

anonymity - strongest-possible anonymity requirements and

adversaries. We begin with rigorous definition of anonymity

against wide range of computationally-bounded attackers,

including eavesdroppers, malicious peers, malicious destina-tions, and their combinations. Following the work of Hevia and Micciancio [15], our definition is generic, and captures dierent notions of anonymity (e.g., unobservability and sender anonymity).

We then study the feasibility of ultimate anonymity. We

show there is a protocol satisfying this requirement, but with

absurd (although polynomial) inefficiency and overhead. We

show that such inefficiency and overhead is unavoidable for

`ultimate anonymity\'. We then present a slightly-relaxed

requirement and present feasible protocols for it.



12:17 [Pub][ePrint] On a Relation between the Ate Pairing and the Weil Pairing for Supersingular Elliptic Curves, by Takakazu Satoh

  The hyperelliptic curve Ate pairing provides an efficient way to compute a

bilinear pairing on the Jacobian variety of a hyperelliptic curve.

We prove that, for supersingular elliptic curves with embedding degree

two, square of the Ate pairing is nothing but the Weil pairing.

Using the formula, we develop an X-coordinate only pairing inversion method.

However, the algorithm is still infeasible for cryptographic size problems.



12:17 [Pub][ePrint] Gossip Latin Square and The Meet-All Gossipers Problem, by Nethanel Gelernter and Amir Herzberg

  Given a network of n = 2^k

gossipers, we want to schedule a cyclic calendar

of meetings between all of them, such that: (1) each gossiper communicates

(gossips) only once a day, with one other gossiper, (2) in every (n 1) consecutive

days, each gossiper meets all other gossipers, and (3) every gossip, initiated by

any gossiper, will reach all gossipers within k = log(n) days.

In this paper we study the above stated meet-all gossipers problem, by den-ing and constructing the Gossip Latin Square (GLS), a combinatorial structure

which solves the problem.



12:17 [Pub][ePrint] Efficient Unobservable Anonymous Reporting against Strong Adversaries, by Nethanel Gelernter and Amir Herzberg

  We present DURP, a decentralized protocol for

unobservable, anonymous reporting to an untrusted destination,

with low latency and overhead. DURP provably ensures strong

anonymity properties, as required for some applications (and not

provided by existing systems and practical designs, e.g., Tor),

specifically:

Provable unobservability against global eavesdropper and

malicious participants.

Provable source anonymity against a malicious destination.

Probable-innocence against a malicious destination which is

also a global eavesdropper.

DURP design is a modular combination of two modules: a

queuing module, ensuring fixed rates for certain events, together

with an anonymization module, which can use either Onion-Routing (DURP^OR) or Crowds (DURP^Crowds). We present anal-ysis, backed by simulation results, of the network properties and

performance of DURP, and show it has reasonable overhead. We

also use the analysis results to create an optimized version of

DURP.



12:17 [Pub][ePrint] Accelerating Scalar Conversion for Koblitz Curve Cryptoprocessors on Hardware Platforms, by Sujoy Sinha Roy and Junfeng Fan and Ingrid Verbauwhede

  Koblitz curves are a class of computationally efficient elliptic curves where scalar multiplications can be accelerated using $\\tau$NAF representations of scalars. However conversion from an integer scalar to a short $\\tau$NAF is costly and thus restricts speed. In this paper we present acceleration techniques for the recently proposed scalar conversion hardware based on division by $\\tau^2$. Acceleration is achieved in two steps. First we perform computational optimizations to reduce the number of long subtraction operations during the conversion of scalar. This helps in reducing the number of integer adder/subtracter circuits from the critical paths of the conversion architecture. In the second step, we perform pipelining in the conversion architecture in such a way that the pipeline stages are always utilized. Due to bubble free nature of the pipelining, clock cycle requirement of the conversion architecture remains same, while operating frequency increases drastically.

We present detailed experimental results to support our claims made in this paper.