*18:17* [Pub][ePrint]
Differing-Inputs Obfuscation and Applications, by Prabhanjan Ananth and Dan Boneh and Sanjam Garg and Amit Sahai and Mark Zhandry
In this paper we study of the notion of differing-input obfuscation, introduced by Barak et al. (CRYPTO 2001, JACM 2012). For any two circuit C0 and C1, differing-input obfuscator diO guarantees that non-existence of a adversary that can find an input on which C0 and C1 differ implies that diO(C0) and diO(C1) are computationally indistinguishable. We show many applications of this notion:- We define the notion of differing-input obfuscator for Turing machines and give a construction for the same (without converting it to a circuit) with input-specific running times. More specifically, for each input our obfuscated Turning machine takes times proportional to the running time of the Turing machine on that specific input rather than the machines worst-cast running time.

- We give a functional encryption scheme that is fully-secure even when the adversary can obtain an unbounded number of secret keys. Furthermore our scheme allows for secret-keys to be associated with Turing machines and thereby achieves input-specific running times and can be equipped with delegation properties. We stress that no previous scheme in the literature had any of these properties.

- We construct the first broadcast encryption system where the ciphertext and secret-key size is constant (i.e. independent of the number of users), and the public key is logarithmic in the number of users. It is the first such scheme where all three parameters are this short. Both our constructions make inherent use of the power provided by differing-input obfuscation. It is not currently known how to construct systems with these properties from the weaker notion of indistinguishability obfuscation.

*18:17* [Pub][ePrint]
Obfuscation ==> (IND-CPA Security =/=> Circular Security), by Antonio Marcedone and Claudio Orlandi
Circular security is an important notion for public-key encryption schemes and is needed by several cryptographic protocols. In circular security the adversary is given an extra ``hint\'\' consisting of a cycle of encryption of secret keys i.e., (E_{pk_1}(sk_2),..., E_{pk_n}(sk_1)). A natural question is whether every IND-CPA encryption scheme is also circular secure. It is trivial to see that this is not the case when n=1. In 2010 a separation for n=2 was shown by [ABBC10,GH10] under standard assumptions in bilinear groups. In this paper we finally settle the question showing that for every $n$ there exist an IND-CPA secure scheme which is not n-circular secure. Our result relies on the recent progress in program obfuscation.

*12:17* [Pub][ePrint]
Bounded Tamper Resilience: How to go beyond the Algebraic Barrier, by Ivan Damgaard and Sebastian Faust and Pratyay Mukherjee and Daniele Venturi
Related key attacks (RKAs) are powerful cryptanalytic attacks where an adversary can change the secret key and observe the effect of such changes at the output. The state of the art in RKA security protects against an a-priori unbounded number of certain algebraic induced key relations, e.g., affine functions or polynomials of bounded degree. In this work, we show that it is possible to go beyond the algebraic barrier and achieve security against arbitrary key relations, by restricting the number of tampering queries the adversary is allowed to ask for. The latter restriction is necessary in case of arbitrary key relations, as otherwise a generic attack of Gennaro et al. (TCC 2004) shows how to recover the key of almost any cryptographic primitive. We describe our contributions in more detail below.1) We show that standard ID and signature schemes constructed from a large class of $\\Sigma$-protocols (including the Okamoto scheme, for instance) are secure even if the adversary can arbitrarily tamper with the prover\'s state a bounded number of times and obtain some bounded amount of leakage. Interestingly, for the Okamoto scheme we can allow also independent tampering with the public parameters.

2) We show a bounded tamper and leakage resilient CCA secure public key cryptosystem based on the DDH assumption. We first define a weaker CPA-like security notion that we can instantiate based on DDH, and then we give a general compiler that yields CCA-security with tamper and leakage resilience. This requires a public tamper-proof common reference string.

3) Finally, we explain how to boost bounded tampering and leakage resilience (as in 1. and 2. above) to continuous tampering and leakage resilience, in the so-called floppy model where each user has a personal hardware token (containing leak- and tamper-free information) which can be used to refresh the secret key.

We believe that bounded tampering is a meaningful and interesting alternative to avoid known impossibility results and can provide important insights into the security of existing standard cryptographic schemes.

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