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

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