Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service via
To receive your credentials via mail again, please click here.
You can also access the full news archive.
Lercier in 2006. We make two contributions. The first contribution introduces a divisility and smoothness technique which
is similar to that of the special-q technique used in integer factorisation algorithms. Such a technique, though, has not
been earlier used in the context of discrete log computations and provides concrete speed-ups in the practical run-time of
the relation collection and the descent phases of the FFS algorithm. The second contribution is to improve the
descent phase of the algorithm. The improvements are based on increasing the degree of freedom and the use of a walk
technique. As a consequence, we show that it is feasible to carry out discrete log computations for certain fields which are
excluded by the analysis of Joux and Lercier. In concrete terms, we present record computations of discrete logs for fields
with 16 and 18-bit prime characteristic. Further, we provide concrete analysis of the effectiveness of the FFS algorithm for
certain fields with medium sized prime characteristic.
The major drawback of the proposed scheme is that the number of values sent before and after the protocol is exponential in the number of parties. Nevertheless, the settings make the verification very efficient for a small number of parties.
To circumvent the lack of generic constructions, Dodis et al. (EUROCRYPT \'02) introduced the notion of bounded-collusion IBE (BC-IBE), where attackers only learn secret keys of an a-priori bounded number t of identities. They provided a generic BC-IBE construction from any semantically-secure encryption scheme which, however, suffers from a ω(t) blow-up in ciphertext size. Goldwasser et al. (TCC 2012) recently presented a generic construction with no ciphertext-length blow-up. Their construction requires an underlying public-key scheme with a key homomorphism, as well as a hash-proof-style security definition that is strictly stronger than semantic security. This latter requirement in particular reduces the applicability of their construction to existing schemes.
In this paper, we present the first generic constructions of BC-IBE from semantically-secure encryption schemes with no ciphertext-length blow-up. Our constructions require different degrees of key-homomorphism and malleability properties that are usually easy to verify. We provide concrete instantiations based on the DDH, QR, NTRU, and LWE assumptions. For all of these assumptions, our schemes present the smallest BC-IBE ciphertext size known to date. Our NTRU-based construction is particularly interesting, due to the lack of NTRU- based IBE constructions as well as the fact that it supports fully-homomorphic evaluation. Our results also yield new constructions of bounded CCA-secure cryptosystems.
We implemented both schemes in C++, using the arithmetic library FLINT, and compared them in practice to assess their respective strengths and weaknesses. In particular, we performed a homomorphic evaluation of the lightweight block cipher SIMON. Combining block ciphers with homomorphic encryption allows to solve the gargantuan ciphertext expansion in cloud applications.