International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) 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).

05:22 [Pub][ePrint] Speeding up QUAD, by Albrecht Petzoldt

  QUAD is a provable secure stream cipher based on multivariate polynomials which was proposed in 2006 by Berbain, Gilbert and Patarin \\cite{BG06}. In this paper we show how to speed up QUAD over GF(256) by a factor of up to 5.8. We get this by using structured systems of polynomials, in particular partially circulant polynomials and polynomials generated by a linear recurring sequence (LRS), instead of random ones. By using this strategy, we can also reduce the system parameter of QUAD by about 99 \\verb!%!. We furthermore present experiments, which seem to show that using structured polynomials of this special choice does not influence the security of QUAD.

05:22 [Pub][ePrint] Encrypted Secret Sharing and Analysis by Plaintext Randomization, by Stephen R. Tate and Roopa Vishwanathan and Scott Weeks

  In this paper we consider the problem of secret sharing where shares

are encrypted using a public-key encryption (PKE) scheme and

ciphertexts are publicly available. While intuition tells us that the

secret should be protected if the PKE is secure against

chosen-ciphertext attacks (i.e., CCA-secure), formally proving this

reveals some subtle and non-trivial challenges. We isolate the

problems that this raises, and devise a new analysis technique called

``plaintext randomization\'\' that can successfully overcome these

challenges, resulting in the desired proof. The encryption of

different shares can use one key or multiple keys, with natural

applications in both scenarios.

05:22 [Pub][ePrint] Attribute-Based Encryption with Fast Decryption, by Susan Hohenberger and Brent Waters

  Attribute-based encryption (ABE) is a vision of public key encryption that allows users to encrypt and decrypt messages based on user attributes. This functionality comes at a cost. In a typical implementation, the size of the ciphertext is proportional to the number of attributes associated with it and the decryption time is proportional to the number of attributes used during decryption. Specifically, many practical ABE implementations require one pairing operation per attribute used during decryption.

This work focuses on designing ABE schemes with fast decryption algorithms. We restrict our attention to expressive systems without system-wide bounds or limitations, such as placing a limit on the number of attributes used in a ciphertext or a private key. In this setting, we present the first key-policy ABE system where ciphertexts can be decrypted with a constant number of pairings. We show that GPSW ciphertexts can be decrypted with only 2 pairings by increasing the private key size by a factor of X, where X is the set of distinct attributes that appear in the private key. We then present a generalized construction that allows each system user to independently tune various efficiency tradeoffs to their liking on a spectrum where the extremes are GPSW on one end and our very fast scheme on the other. This tuning requires no changes to the public parameters or the encryption algorithm. Strategies for choosing an individualized user optimization plan are discussed. Finally, we discuss how these ideas can be translated into the ciphertext-policy ABE setting at a higher cost.

05:22 [Pub][ePrint] L-P States of RC4 Stream Cipher , by Jing Lv and Dongdai Lin

  The stream cipher RC4 was designed by R.Rivest in $1987$, and it is a widely deployed cipher. Many predictive states of RC4 for some special indices $i$ were presented in the last $20$ years. In this paper, we present several long term predictive states. These states increase the probability to guess part of the internal state in a known plaintext attack and present a cryptanalytic weakness of RC4. This paper also analyzes possible long term bias in the keystream and further propose a search method for the long term predictive states.

05:22 [Pub][ePrint] Multi-Party Computation of Polynomials and Branching Programs without Simultaneous Interaction, by S. Dov Gordon and Tal Malkin and Mike Rosulek and Hoeteck Wee

  Halevi, Lindell, and Pinkas (CRYPTO 2011) recently proposed a model for secure computation that captures communication patterns that arise

in many practical settings, such as secure computation on the web. In their model, each party interacts only once, with a single centralized server. Parties do not interact with each other; in fact, the parties need not even be online simultaneously.

In this work we present a suite of new, simple and efficient protocols for secure computation in this \"one-pass\" model. We give protocols that obtain optimal privacy for the following general tasks:

-- Evaluating any multivariate polynomial $F(x_1, \\ldots ,x_n)$ (modulo a large RSA modulus N), where the parties each hold an input $x_i$.

-- Evaluating any read once branching program over the parties\' inputs.

As a special case, these function classes include all previous functions for which an optimally private, one-pass computation was known, as well as many new functions, including variance and other statistical functions, string matching, second-price auctions, classification algorithms and some classes of finite automata

and decision trees.

05:22 [Pub][ePrint] Dynamic Cube Attack on Grain-v1, by Majid Rahimi, Mostafa Barmshory, Mohammad Hadi Mansouri, Mohammad Reza Aref

  This article aims to present dynamic cube attack on Grain-v1. Dynamic cube attack finds the secret key by using distinguishers gained from structural weakness. The main idea of dynamic cube attack lies in simplifying the output function. After making it simpler, dynamic cube attack will be able to exploit distinguishing attack for recovering the secret key. In this paper, we investigate Grain-v1 to which key recovery attack has never been applied because its feedback function is so sophisticated. we apply dynamic cube attack on it by utilizing both intelligent choices of Initial Value variables and appropriate simplifications. Our attack is done in feasible time complexity, and it recovers all bits of the key while the number of initialization rounds in Grain-v1 is decreased to 100. This attack is faster than exhaustive search by a factor $2^{32}$.

05:22 [Pub][ePrint] Chosen Ciphertext Secure (CCS): Stateful Symmetric Key CCA Encryption with Minimal Ciphertext Expansion, by Jonathan Trostle

  In some wireless environments, minimizing the size of messages is paramount due to the resulting significant energy savings. We

present a new stateful symmetric encryption scheme: CCS or Chosen

Ciphertext Secure scheme. CCS has the property that modifications to

the ciphertext randomizes the resulting plaintext. Using this property,

we prove the scheme is CCA2 secure. Thus we obtain CCA2 encryption

schemes with minimal ciphertext expansion which are applicable to resource constrained wireless environments. For protocols that send short messages, our scheme is similar to Counter with CBC-MAC (CCM) for

computation but has much shorter messages (since we can use much

smaller or no MAC tags) for a similar level of security. A key idea is

that various protocol fields in the underlying plaintext act as an authentication tag given changes to the message ciphertext. To the best of our knowledge, CCS is the first scheme that achieves CCA2 security with only 2-3 bytes of ciphertext expansion.

05:22 [Pub][ePrint] Pseudorandom Generators from Regular One-way Functions: New Constructions with Improved Parameters, by Yu Yu

  We revisit the problem of basing pseudorandom generators on regular one-way functions, and present the following constructions:

(1) For any known-regular one-way function (on $n$-bit inputs) that is known to be $\\eps$-hard to invert, we give a neat (and tighter) proof for the folklore construction of pseudorandom generator of seed length $\\Theta(n)$ by making a single call to the underlying one-way function.

(2) For any unknown-regular one-way function with known $\\eps$-hardness, we give a new construction with seed length $\\Theta(n)$ and $O(n/\\log{(1/\\eps)})$ calls. Here the number of calls is also optimal by matching the lower bounds of Holenstein and Sinha [FOCS 2012].

Both constructions require the knowledge about $\\eps$, but the dependency can be removed while keeping nearly the same parameters. In the latter case, we get a construction of pseudo-random generator from any unknown-regular one-way function using seed length $\\tilde{O}(n)$ and $\\tilde{O}(n/\\log{n})$ calls, where $\\tilde{O}$ omits a factor that can be made arbitrarily close to constant (e.g. $\\log\\log\\log{n}$ or even less). This improves the \\emph{randomized iterate} approach by Haitner, Harnik and Reingold [CRYPTO 2006] which requires seed length $O(n{\\log}{n})$ and $O(n/\\log{n})$ calls.

05:22 [Pub][ePrint] The Legal Classification of Identity-Based Signatures, by Christoph Sorge

  Identity-based cryptography has attracted attention in the cryptographic research community in recent years. Despite the importance of cryptographic schemes for applications in business and law, the legal implications of identity-based cryptography have not yet been discussed. We investigate how identity-based signatures fit into the legal framework. We focus on the European Signature Directive, but also take the UNCITRAL Model Law on Electronic Signatures into account. In contrast to previous assumptions, identity-based signature schemes can, in principle, be used even for qualified electronic signatures, which can replace handwritten signatures in the member states of the European Union. We derive requirements to be taken into account in the development of future identity-based signature schemes.

05:22 [Pub][ePrint] Cryptography Challenges for Computational Privacy in Public Clouds, by Sashank Dara

  Computational privacy is a property of cryptographic

system that ensures the privacy of data (and/or operations)

while being processed at an untrusted server. Cryptography

has been an indispensable tool for computer security but its

readiness for this new generational shift of computing platform

i.e. Cloud Computing is still questionable.

Theoretical constructions like Fully Homomorphic Encryption,

Functional encryption, Server aided Multiparty Computation,

Verifiable Computation, Instance Hiding etc. are few

directions being pursued. These cryptographic techniques solve

Cloud privacy problems at different levels but most of them dont

fit well in overall scheme of things.

We state the privacy requirements for Cloud offerings in

various delivery methods. We discuss the challenges with current

cryptographic techniques being pursued by researchers and show

that they dont cater to blanket cover these privacy requirements.

We urge the need to find generalizations and connections

among these isolated techniques. As this might give more insights

into the underpinnings of Computational Privacy and lead to

better solutions.

05:22 [Pub][ePrint] Computing the Rank of Incidence Matrix and Algebraic Immunity of Boolean Functions, by Deepak Kumar Dalai

  The incidence matrix between a set of monomials and a set of vectors in $\\F_2$ has a great importance in the study of coding theory, cryptography, linear algebra, combinatorics. The rank of these matrices are very useful while computing algebraic immunity($\\ai$) of Boolean functions in cryptography literature~\\cite{MPC04,DGM04}.

Moreover, these matrices are very sparse and well structured. Thus, for aesthetic reason finding rank of these matrices is also very interesting in mathematics.

In this paper, we have reviewed the existing algorithms with added techniques to speed up the algorithms and have proposed some new efficient algorithms for the computation of the rank of incidence matrix and solving the system of equations where the co-efficient matrix is an incidence matrix.Permuting the rows and columns of the incidence matrix with respect to an ordering, the incidence matrix can be converted to a lower block triangular matrix, which makes the computation in quadratic time complexity and linear space complexity. Same technique is used to check and computing low degree annihilators of an $n$-variable Boolean functions in faster time complexity than the usual algorithms. Moreover, same technique is also exploited on the Dalai-Maitra algorithm in~\\cite{DM06} for faster computation. On the basis of experiments, we conjecture that the $\\ai$ of $n$-variable inverse S-box is $\\lfloor\\sqrt{n}\\rfloor + \\lceil\\frac{n}{\\lfloor\\sqrt{n}\\rfloor}\\rceil-2$.

We have also shown the skepticism on the existing fastest algorithm

in~\\cite{ACGKMR06} to find $\\ai$ and lowest degree annihilators of a Boolean function.