*12:17* [Pub][ePrint]
Statistical weaknesses in 20 RC4-like algorithms and (probably) the simplest algorithm free from these weaknesses - VMPC-R, by Bartosz Zoltak
We find statistical weaknesses in 20 RC4-like algorithms including the original RC4, RC4A, PC-RC4 and others.This is achieved using a simple statistical test.

We found only one algorithm which was able to pass the test - VMPC-R.

This algorithm, being approximately three times more complex then RC4,

is probably the simplest RC4-like cipher capable of producing pseudo-random output.

*18:17* [Pub][ePrint]
Statistical weaknesses in 20 RC-4 like algorithms and (probably) the simplest algorithm free from these weaknesses - VMPC-R, by Bartosz Zoltak
We find statistical weaknesses in 20 RC-4 like algorithms including the original RC4, RC4A, PC-RC4 and others.This is achieved using a simple statistical test.

We found only one algorithm which was able to pass the test - VMPC-R.

This algorithm, being approximately three times more complex then RC4,

is probably the simplest RC4-like cipher capable of producing pseudo-random output.

*18:17* [Pub][ePrint]
Structure-Preserving Signatures from Type II Pairings, by Masayuki Abe and Jens Groth and Miyako Ohkubo and Mehdi Tibouchi
We investigate structure-preserving signatures in asymmetric bilinear groups with an efficiently computable homomorphism from one source group to the other, i.e., the Type II setting. It has been shown that in the Type I and Type III settings (with maximal symmetry and maximal asymmetry respectively), structure-preserving signatures need at least 2 verification equations and 3 group elements. It is therefore natural to conjecture that this would also be required in the intermediate Type II setting, but surprisingly this turns out not to be the case. We construct structure-preserving signatures in the Type II setting that only require a single verification equation and consist of only 2 group elements. This shows that the Type II setting with partial asymmetry is different from the other two settings in a way that permits the construction of cryptographic schemes with unique properties.We also investigate lower bounds on the size of the public verification key in the Type II setting. Previous work in structure-preserving signatures has explored lower bounds on the number of verification equations and the number of group elements in a signature but the size of the verification key has not been investigated before. We show that in the Type II setting it is necessary to have at least 2 group elements in the public verification key in a signature scheme with a single verification equation.

Our constructions match the lower bounds so they are optimal with respect to verification complexity, signature sizes and verification key sizes. In fact, in terms of verification complexity, they are the most efficient structure preserving signature schemes to date. Depending on the context in which a scheme is deployed it is sometimes desirable to have strong existential unforgeability, and in other cases full randomizability. We give two structure-preserving signature schemes with a single verification equation where both the signatures and the public verification keys consist of two group elements each. One signature scheme is strongly existentially unforgeable, the other is fully randomizable. Having such simple and elegant structure-preserving signatures may make the Type II setting the easiest to use when designing new structure-preserving cryptographic schemes, and lead to schemes with the greatest conceptual simplicity.

*03:17* [Pub][ePrint]
Sakai-Ohgishi-Kasahara Non-Interactive Identity-Based Key Exchange Scheme, Revisited, by Yu Chen and Qiong Huang and Zongyang Zhang
Identity-based non-interactive key exchange (IB-NIKE) is a powerful but a bit overlooked primitive in identity-based cryptography. While identity-based encryption and signature have been extensively investigated over the past three decades, IB-NIKE has remained largely unstudied. Currently, there are only few IB-NIKE schemes in the literature. Among them, Sakai-Ohgishi-Kasahara (SOK) scheme is the first efficient and secure IB-NIKE scheme, which has great influence on follow-up works. However, the SOK scheme required its identity mapping function to be modeled as a random oracle to prove security. Moreover, the existing security proof heavily relies on the ability of programming the random oracle. It is unknown whether such reliance is inherent. In this work, we intensively revisit the SOK IB-NIKE scheme, and present a series of possible and impossible results in the random oracle model and the standard model. In the random oracle model, we first improve previous security analysis for the SOK IB-NIKE scheme by giving a tighter reduction. We then use meta-reduction technique to show that the SOK scheme is unlikely proven to be secure based on the computational bilinear Diffie-Hellman (CBDH) assumption without programming the random oracle. In the standard model, we show how to instantiate the random oracle in the SOK scheme with a concrete hash function from admissible hash functions (AHFs) and indistinguishability obfuscation.

The resulting scheme is fully adaptive-secure based on the decisional bilinear Diffie-Hellman inversion (DBDHI) assumption. To the best of our knowledge, this is first fully adaptive-secure IB-NIKE scheme in the standard model that does not explicitly require multilinear maps. Previous schemes in the standard model either have merely selective security or use multilinear maps as a key ingredient. Of particular interest, we generalize the definition of AHFs, and propose a generic construction which enables AHFs with previously unachieved parameters.

*03:17* [Pub][ePrint]
Exponent-inversion Signatures and IBE under Static Assumptions, by Tsz Hon Yuen and Sherman S.M. Chow and Cong Zhang and Siu Ming Yiu
Boneh-Boyen signatures are widely used in many advanced cryptosystems. It has a structure of ``inversion in the exponent\", and its unforgeability against $q$ chosen-messages attack is proven under the non-static $q$-Strong Diffie-Hellman assumption. It has been an open problem whether the exponent-inversion signature, and its various applications, can be proved based on a weaker static assumption. We propose a dual-form Boneh-Boyen signature and demonstrate how to prove the security for the exponent-inversion signature structure in the standard model under static assumptions. We apply our proof technique to a number of related cryptosystems employing similar structure, including anonymous credentials, identity-based encryption (IBE) and accountable authority IBE. Our results give the first exponent-inversion IBE in the standard model under static assumption. Our anonymous credentials and accountable authority IBE are also better than existing schemes in terms of both security and efficiency.

*00:17* [Pub][ePrint]
Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption, by Craig Gentry and Allison Lewko and Amit Sahai and Brent Waters
We revisit the question of constructing secure general-purpose indistinguishability obfusca- tion (iO), with a security reduction based on explicit computational assumptions. Previous to our work, such reductions were only known to exist based on instance-dependent assumptions and/or ad-hoc assumptions: In the original constructive work of Garg et al. (FOCS 2013), the underlying explicit computational assumption encapsulated an exponential family of assump- tions for each pair of circuits to be obfuscated. In the more recent work of Pass et al. (ePrint 2013), the underlying assumption is a meta-assumption that also encapsulates an exponential family of assumptions, and this meta-assumption is invoked in a manner that captures the spe- cific pair of circuits to be obfuscated. The assumptions underlying both these works substantially capture (either explicitly or implicitly) the actual structure of the obfuscation mechanism itself.In our work, we provide the first construction of general-purpose indistinguishability obfus- cation proven secure via a reduction to an instance-independent computational assumption over multilinear maps, namely, the Multilinear Subgroup Elimination Assumption. Our assumption does not depend on the circuits to be obfuscated (except for its size), and does not correspond to the underlying structure of our obfuscator. The technical heart of our paper is our reduction, which gives a new way to argue about the security of indistinguishability obfuscation.