*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]
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.

*09:17* [Pub][ePrint]
A Note on the Impossibility of Obfuscation with Auxiliary Input, by Shafi Goldwasser and Yael Tauman Kalai
In this note we revisit the problem of obfuscation with auxiliary inputs. We show that the existence of indistinguishablity obfuscation (iO) implies that all functions with sufficient \"pseudo-entropy\" cannot be obfuscated with respect to a virtual box definition (VBB) in the presence of (dependent) auxiliary input.Namely, we show that for any candidate obfuscation O and for any function family F={f_s} with sufficient pseudo-entropy, there exists an (efficiently computable) auxiliary input aux, that demonstrates the insecurity of O. This is true in a strong sense: given O(f_s) and aux one can efficiently recover the seed s, whereas given aux and oracle access to f_s it is computationally hard to recover s.

A similar observation was pointed out in a recent work of Goldwasser et. al. (Crypto 2013), assuming *extractable* witness encryption. In this note we show that the extractability property of the witness encryption is not needed to get our negative result, and all that is needed is the existence of witness encryption, which in turn can be constructed from iO obfuscation.