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

12:17 [Pub][ePrint] Universally composable privacy preserving finite automata execution with low online and offline complexity, by Peeter Laud and Jan Willemson

  In this paper, we propose efficient protocols to obliviously execute non-deterministic and deterministic finite automata (NFA and DFA) in the arithmetic black box (ABB) model. In contrast to previous approaches, our protocols do not use expensive public-key operations, relying instead only on computation with secret-shared values. Additionally, the complexity of our protocols is largely offline. In particular, if the DFA is available during the precomputation phase, then the online complexity of evaluating it on an input string requires a small constant number of operations per character. This makes our protocols highly suitable for certain outsourcing applications.

12:17 [Pub][ePrint] Formal verification of a software countermeasure against instruction skip attacks, by Karine Heydemann and Nicolas Moro and Emmanuelle Encrenaz and Bruno Robisson

  Fault attacks against embedded circuits enabled to define many new attack paths against secure circuits. Every attack path relies on a specific fault model which defines the type of faults that the attacker can perform. On embedded processors, a fault model in which an attacker is able to skip an assembly instruction is practical and has been obtained by using several fault injection means. To handle this issue, some countermeasure schemes which rely on temporal redundancy have been proposed. Nevertheless, double fault injection in a long enough time interval is practical and can bypass those countermeasure schemes. Some fine-grained other countermeasure schemes have been proposed for specific instructions. However, to the best of our knowledge, no approach that enables to secure a generic assembly program in order to make it fault-tolerant to instruction skip attacks has been formally proven yet. In this paper, we provide a fault-tolerant replacement sequence for every instruction of the whole Thumb2 instruction set and provide a formal proof of this fault tolerance. This simple transformation enables to add a reasonably good security level to an embedded program and makes practical fault injection attacks much harder to achieve.

12:17 [Pub][ePrint] A Black-Box Construction of a CCA2 Encryption Scheme from a Plaintext Aware Encryption Scheme, by Dana Dachman-Soled

  We present a construction of a CCA2-secure encryption scheme from a plaintext aware, weakly simulatable public key encryption scheme. The notion of plaintext aware, weakly simulatable public key encryption has been considered previously by Myers, Sergi and shelat (SCN, 2012) and natural encryption schemes such as the Damgard Elgamal Scheme (Damgard, Crypto, 1991) and the Cramer-Shoup Lite Scheme (Cramer and Shoup, SIAM J. Comput., 2003) were shown to satisfy these properties.

Recently, Myers, Sergi and shelat (SCN, 2012) defined an extension of non-malleable CCA1 security, called cNM-CCA1, and showed how to construct a cNM-CCA1-secure encryption scheme from a plaintext aware and weakly simulatable public key encryption scheme. Our work extends and improves on this result by showing that a full CCA2-secure encryption scheme can be constructed from the same assumptions.

12:17 [Pub][ePrint] Public-Key Encryption with Weak Randomness: Security against Strong Chosen Distribution Attacks, by Damien Vergnaud and David Xiao

  Chosen Distribution Attacks (CDA) were introduced by Bellare et al. (Asiacrypt \'09) to model attacks where an adversary can control the distribution of both messages and random coins used in an encryption scheme. One important restriction in their definition is that the distributions chosen by the adversary cannot depend on the public key being attacked, and they show that some restriction of this form is necessary (for the same reasons that secure deterministic encryption is impossible if we allow arbitrary dependence between the plaintext distributions and the public key).

Subsequently Raghunathan et al. (Eurocrypt \'13) showed how to relax this restriction by allowing the message/randomness distributions to depend on the public key as long as the distributions belong to a family of bounded size fixed before the public key is known.

We extend the definition further to what we call Strong Chosen Distribution Attacks where the message/randomness distributions may depend on the public key as long as certain entropy conditions are satisfied. Our security model comes from a natural model of attack where an adversary infiltrates the encryption system and installs a trojan program prior to knowing the public key, and subsequently is allowed limited communication with the trojan program.

We present secure constructions in the standard and random oracle models both with and without decryption oracles (corresponding to CPA or CCA security). We also prove that our definition simultaneously generalizes previous definitions in this line of work.

12:17 [Pub][ePrint] Secret Key Cryptosystem based on Non-Systematic Polar Codes, by Reza Hooshmand

  Polar codes are provably capacity achieving linear block codes. The generator matrix of these codes is specified by knowing the parameters of transmission channel, length and dimension of the used code. On the other hand, for the cryptosystems based on general decoding problem (i.e. code based cryptosystems), the generator matrix of the applied code should be properly hidden from the attacker. Moreover, in the computational security, it is assumed that an attacker with restricted processing power has unlimited access to transmission media. Thus, an attacker can construct the generator matrix of polar codes, especially for Binary Erasure Channel on which this matrix can be efficiently specified.

In this paper, we introduce a novel method to hide the generator matrix of polar codes in such a way that an attacker cannot construct it in polynomial time even by knowledge of the channel parameters, dimension and length of the used code. By the help of this method, a secret key cryptosystem based on non-systematic polar codes over Binary Erasure Channel is proposed which provides both data security and reliability in one process simultaneously. In fact, the main goal of this research is to achieve the acceptable level of security and reliability by taking advantage of the interesting properties of polar codes. The proposed scheme resists against the typical attacks on the cryptosystems based on error correcting codes. Also, by employing some efficient methods, the key length of our scheme is decreased compared to Rao-Nam secret key cryptosystem. Moreover, our scheme benefits from high code rate, proper error performance, faster processing and efficient implementation.

12:17 [Pub][ePrint] Separations in Circular Security for Arbitrary Length Key Cycles, by Venkata Koppula and Kim Ramchen and Brent Waters

  While standard notions of security suffice to protect any message supplied by an adversary, in some situations stronger notions of security are required. One such notion is n-circular security, where ciphertexts Enc(pk1, sk2), Enc(pk2, sk3), ..., Enc(pkn, sk1) should be indistinguishable from encryptions of zero.

In this work we prove the following results for n-circular security:

- For any n there exists an encryption scheme that is IND-CPA secure but not n-circular secure.

- There exists a bit encryption scheme that is IND-CPA secure, but not 1-circular secure.

- If there exists an encryption system where an attacker can distinguish a key encryption cycle from an encryption of zeroes, then in a transformed cryptosystem there exists an attacker which recovers secret keys from the encryption cycles.

Our first two results apply a novel utilization of indistinguishability obfuscation. The last result is generic and applies to any such cryptosystem.

09:17 [Pub][ePrint] Discrete Logarithms and Mordell-Weil Groups , by Mohammad Sadek

  Let $E_p$ be an elliptic curve over a prime finite field $\\Fp$, $p\\ge5$, and $P_p,Q_p\\in E_p(\\Fp)$. The elliptic curve discrete logarithm problem, ECDLP, on $E_p$ is to find $m_p\\in\\mathbb{F}_p^{\\times}$ such that $Q_p=m_p P_p$ if $Q_p\\in\\langle P_p\\rangle$. We propose an algorithm to attack the ECDLP relying on a Hasse principle detecting linear dependence in Mordell-Weil groups of elliptic curves via a finite number of reductions.

09:17 [Pub][ePrint] Anonymous aggregation for lightweight multiparty computations, by Constantinos Patsakis

  While multiparty computations are becoming more and more efficient, their performance has not reached the needed level to be widely deployed for many applications. Nevertheless, the heterogeneous environment of modern computing needs this functionality to provide users their right to privacy. For a wide range of applications there is no need for complex computations, operations such as multiplication or addition might be sufficient. In this work we introduce the concepts of Anonymous Aggregation and Anonymous Aggregators, two lightweight cryptographic primitives that can perform specific private computations efficiently in restricted environments.

09:17 [Pub][ePrint] Fine-Tuning Groth-Sahai Proofs, by Alex Escala and Jens Groth

  Groth-Sahai proofs are efficient non-interactive zero-knowledge proofs that have found widespread use in pairing-based cryptography. We propose efficiency improvements of Groth-Sahai proofs in the SXDH setting, which is the one that yields the most efficient non-interactive zero-knowledge proofs.

- We replace some of the commitments with ElGamal encryptions, which reduces the prover\'s computation and for some types of equations reduces the proof size.

- Groth-Sahai proofs are zero-knowledge when no public elements are paired to each other. We observe that they are also zero-knowledge when base elements for the groups are paired to public constants.

- The prover\'s computation can be reduced by letting her pick her own common reference string. By giving a proof she has picked a valid common reference string this does not compromise soundness.

- We define a type-based commit-and-prove scheme, which allows commitments to be reused in many different proofs.

09:17 [Pub][ePrint] Linear Cryptanalysis of Round Reduced Variants of SIMON, by Javad Alizadeh, Nasour Bagheri, Praveen Gauravaram, Abhishek Kumar, and Somitra Kumar Sanadhya

  SIMON [3] is a family of lightweight block ciphers which has been recently proposed by U.S National Security Agency (NSA). Although the original proposal does not include any detailed security analysis but several detailed analysis has been published on this recently [1,2].

In this paper we investigate the security of this family of block ciphers against linear cryptanalysis. We present several linear characteristics for all variants of SIMON. Our best linear

characteristic covers SIMON 32/64 reduced to 13 rounds out of 32 rounds with the bias $2^{-16}. In addition we present attacks for the round reduced variants of SIMON48/96, SIMON64/128, SIMON96/144 and SIMON128/256. Our results are the best known results on linear cryptanalysis for any variant of SIMON.

09:17 [Pub][ePrint] TUC: Time-sensitive and Modular Analysis of Anonymous Communication, by Michael Backes and Praveen Manoharan and Esfandiar Mohammadi

  The anonymous communication (AC) protocol Tor constitutes the most widely deployed technology for providing anonymity for user communication over the Internet. Tor has been subject to several analyses which have shown strong anonymity guarantees for Tor. However, all previous analyses ignore time-sensitive leakage: timing patterns in web traffic allow for attacks such as website fingerprinting and traffic correlation, which completely break the anonymity provided by Tor. For conducting a thorough and comprehensive analysis of Tor that in particular includes all of these time-sensitive attacks, one of the main obstacles is the lack of a rigorous framework that allows for a time-sensitive analysis of complex AC protocols.

In this work, we present TUC (for Time-sensitive Universal Composability): the first universal composability framework that includes a comprehensive notion of time, which is suitable for and tailored to the demands of analyzing AC protocols. As a case study, we extend previous work and show that the onion routing (OR) protocol, which underlies Tor, can be securely abstracted in TUC, i.e., all time-sensitive attacks are reflected in the abstraction. We finally leverage our framework and this abstraction of the OR protocol to formulate a countermeasure against website fingerprinting attacks and to prove this countermeasure secure.