On Efficient Pairings on Elliptic Curves over Extension Fields, by Xusheng Zhang and Kunpeng Wang and Dongdai Lin
In implementation of elliptic curve cryptography, three kinds of finite fields have been widely studied, i.e. prime field, binary field and optimal extension field. In pairing-based cryptography, however, pairing-friendly curves are usually chosen among ordinary curves over prime fields and supersingular curves over extension fields with small characteristics.
In this paper, we study pairings on elliptic curves over extension fields from the point of view of accelerating the Miller\'s algorithm to present further advantage of pairing-friendly curves over extension fields, not relying on the much faster field arithmetic. We propose new pairings on elliptic curves over extension fields can make better use of the multi-pairing technique for the efficient implementation. By using some implementation skills, our new pairings could be implemented much more efficiently than the optimal ate pairing and the optimal twisted ate pairing on elliptic curves over extension fields. At last, we use the similar method to give more efficient pairings on Estibals\'s supersingular curves over composite extension fields in parallel implementation.
Two Bitcoins at the Price of One? Double-Spending Attacks on Fast Payments in Bitcoin, by Ghassan O. Karame and Elli Androulaki and Srdjan Capkun
Bitcoin is a decentralized payment system that is based on Proof-of-Work. Bitcoin is currently gaining popularity as a digital currency; several businesses are starting to accept Bitcoin transactions. An example case of the growing use of Bitcoin was recently reported in the media; here, Bitcoins were used as a form of fast payment in a local fast-food restaurant.
In this paper, we analyze the security of using Bitcoin for fast payments, where the time between the exchange of currency and goods is short (i.e., in the order of few seconds). We focus on double-
spending attacks on fast payments and demonstrate that these attacks can be mounted at low cost on currently deployed versions of Bitcoin. We further show that the measures recommended by Bitcoin developers for the use of Bitcoin in fast transactions are not always effective in resisting double-spending; we show that if those recommendations are integrated in future Bitcoin implementations, double-spending
attacks on Bitcoin will still be possible. Finally, we leverage on our findings and propose a lightweight countermeasure that enables the detection of double-spending attacks in fast transactions.
Binary and q-ary Tardos codes, revisited, by Boris Skoric and Jan-Jaap Oosterwijk
The Tardos code is a much studied collusion-resistant fingerprinting code, with the special property that it has asymptotically optimal
length $m\\propto c_0^2$, where $c_0$ is the number of colluders.
In this paper we simplify the security proofs for this code,
making use of the Bernstein inequality and Bennett inequality instead of
the typically used Markov inequality. This simplified proof technique also slightly improves the tightness of the bound on the false negative error probability. We present new results on code length optimization, for both small and asymptotically large coalition sizes.
New Identity Based Encryption And Its Proxy Re-encryption, by Xu An Wang and Xiaoyuan Yang
Identity based encryption (IBE) has received great attention since Boneh and Franklin\'s breakthrough work on bilinear group based IBE . Till now, many IBE schemes relying on bilinear groups with dierent properties have been proposed [5, 25, 29, 14]. However, one part of the user\'s private key in all these IBE schemes is constructed as y = f(msk), where msk is the master key and y is an element in the underlying bilinear group G. In this paper, we propose a new IBE: one part of the private key is y = f(msk), where msk is the master key and y is an element in Zp . Here p is the underlying bilinear group\'s prime order. By using some novel techniques, we prove this new IBE is semantic secure under the selective identity chosen plaintext attacks (IND-sID-CPA) in the standard model. Based on this IBE scheme, we construct
an IND-ID-CCA secure identity based proxy re-encryption (IBPRE) scheme
which is master secret secure and ecient for the proxy compared with
other IND-ID-CCA (IBPRE) schemes.
A Generalization of the Rainbow Band Separation Attack and its Applications to Multivariate Schemes, by Enrico Thomae
The Rainbow Signature Scheme is a non-trivial generalization of the well known Unbalanced Oil and Vinegar (UOV) signature scheme (Eurocrypt \'99) minimizing the length of the signatures. By now the Rainbow Band Separation attack is the best key recovery attack known. For some sets of parameters it is even faster than a direct attack on the public key. Unfortunately the available description of the attack is very ad hoc and does not provide deep insights.
In this article we provide another view on the Rainbow Band Separation attack using the theory of equivalent keys and a new generalization called good keys. Thereby we generalize the attack into a framework that also includes Reconciliation attacks. We further formally prove the correctness of the attack and show that it does not only perform well on Rainbow, but on all multivariate quadratic (MQ) schemes that suffer from missing cross-terms. We apply our attack and break the Enhanced STS signature scheme and all its variants, as well as the MFE encryption scheme and its variant based on Diophantine equations. In the case of Rainbow and Enhanced TTS we show that parameters have to be chosen carefully and that the remaining efficiency gain over UOV is small. As there is still some room to improve the Band Separation attack, it is not clear whether layer-based MQ-schemes will eventually become superfluous or not.
Shorter IBE and Signatures via Asymmetric Pairings, by Jie Chen and Hoon Wei Lim and San Ling and Huaxiong Wang and Hoeteck Wee
We present efficient Identity-Based Encryption (IBE) and signature schemes
under the Symmetric External Diffie-Hellman (SXDH) assumption in bilinear
groups. In both the IBE and the signature schemes,
all parameters have constant numbers of group elements,
and are shorter than those of previous constructions
based on Decisional Linear (DLIN) assumption. Our constructions use both
dual system encryption (Waters, Crypto \'09) and dual pairing vector spaces
(Okamoto and Takashima, Pairing \'08, Asiacrypt \'09). Specifically, we show
how to adapt the recent DLIN-based instantiations of Lewko (Eurocrypt \'12)
to the SXDH assumption. To our knowledge, this is the first work to instantiate
either dual system encryption or dual pairing vector spaces under the SXDH assumption.
When Homomorphism Becomes a Liability, by Zvika Brakerski
We show that an encryption scheme cannot have a simple decryption circuit and be homomorphic at the same time. Specifically, if a scheme can homomorphically evaluate the majority function, then its decryption circuit cannot be a linear function of the secret key (or even a succinct polynomial), even if decryption error is allowed.
An immediate corollary is that known schemes that are based on the hardness of decoding in the presence of noise with low hamming weight cannot be fully homomorphic. This applies to known schemes such as LPN-based symmetric or public key encryption.
An additional corollary is that the recent candidate fully homomorphic encryption, suggested by Bogdanov and Lee (ePrint \'11, henceforth BL), is insecure. In fact, we show two attacks on the BL scheme: One by applying the aforementioned general statement, and another by directly attacking one of the components of the scheme.
ZKPDL: A Language-Based System for Efficient Zero-Knowledge Proofs and Electronic Cash, by Sarah Meiklejohn and C. Chris Erway and Alptekin Küpçü and Theodora Hinkle and Anna Lysyanskaya
In recent years, many advances have been made in cryptography, as well as in the performance of communication networks and processors. As a result, many advanced cryptographic protocols are now efficient enough to be considered practical, yet research in the area remains largely theoretical and little work has been done to use these protocols in practice, despite a wealth of potential applications.
This paper introduces a simple description language, ZKPDL, and an interpreter for this language. ZKPDL implements non-interactive zero-knowledge proofs of knowledge, a primitive which has received much attention in recent years. Using our language, a single program may specify the computation required by both the prover and verifier of a zero-knowledge protocol, while our interpreter performs a number of optimizations to lower both computational and space overhead.
Our motivating application for ZKPDL has been the efficient implementation of electronic cash. As such, we have used our language to develop a cryptographic library, Cashlib, that provides an interface for using ecash and fair exchange protocols without requiring expert knowledge from the programmer.