International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

13:17 [Pub][ePrint] Some security bounds for the DGHV scheme, by Franca Marinelli and Riccardo Aragona and Chiara Marcolla and Massimiliano Sala

  The correctness in decrypting a ciphertext after some operations in the DGVH scheme depends heavily on the dimension of the secret key. In this paper we compute two bounds on the size of the secret key for the DGHV scheme to decrypt correctly a ciphertext after a fixed number of additions and a fixed number of multiplication. Moreover we improve the original bound on the dimension of the secret key for a general circuit.

13:17 [Pub][ePrint] A Subexponential Construction of Graph Coloring for Multiparty Computation, by Hassan Jameel Asghar, Yvo Desmedt, Josef Pieprzyk, and Ron Steinfeld

  We show the first deterministic construction of an unconditionally secure multiparty computation (MPC) protocol in the passive adversarial model over black-box non-Abelian groups which is both optimal and has subexponential complexity of construction. More specifically, following the result of Desmedt et al. (2012) that the problem of MPC over non-Abelian groups can be reduced to finding a $t$-reliable $n$-coloring of planar graphs, we show the construction of such a graph which allows a path from the input nodes to the output nodes when any $t$-party subset is in the possession of the adversary. Unlike the (deterministic) constructions from Desmedt et al. (2012) our construction is subexponential and optimal at the same time, i.e., it is secure for any $t < \\frac{n}{2}$.

13:17 [Pub][ePrint] Efficient and Strongly Secure Dynamic Domain-Specific Pseudonymous Signatures for ID Documents, by Julien Bringer and Hervé Chabanne and Roch Lescuyer and Alain Patey

  The notion of domain-specific pseudonymous signatures (DSPS) has recently been introduced for private authentication of ID documents, like passports, that embed a chip with computational abilities. Thanks to this privacy-friendly primitive, the document authenticates to a service provider through a reader and the resulting signatures are anonymous, linkable inside the service and unlinkable across services. A subsequent work proposes to enhance security and privacy of DSPS through group signatures techniques. In this paper, we improve on these proposals in three ways. First, we spot several imprecisions in previous formalizations. We consequently provide a clean security model for \\emph{dynamic domain-specific pseudonymous signatures}, where we correctly address the dynamic and adaptive case. Second, we note that using group signatures is somehow an overkill for constructing DSPS, and we provide an optimized construction that achieves the same strong level of security while being more efficient. Finally, we study the implementation of our protocol in a chip and show that our solution is well-suited for these limited environments. In particular, we propose a secure protocol for delegating the most demanding operations from the chip to the reader.

16:17 [Pub][ePrint] Fine Tuning the Function Field Sieve Algorithm for the Medium Prime Case, by Palash Sarkar and Shashank Singh

  This work builds on the variant of the function field sieve (FFS) algorithm for the medium prime case introduced by Joux and

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.

19:17 [Pub][ePrint] Verifiable Computation in Multiparty Protocols with Honest Majority, by Peeter Laud and Alisa Pankova

  A lot of cryptographic protocols have been proposed for semi-honest model. In general, they are much more efficient than those proposed for the malicious model. In this paper, we propose a method that allows to detect the parties that have violated the protocol rules after the computation has ended, thus making the protocol secure against covert attacks. This approach can be useful in the settings where for any party it is fatal to be accused in violating protocol rules. In this way, up to the verification, all the computation can be performed in semi-honest model, which makes it very efficient in practice. The verification is statistical zero-knowledge, and it is based on linear probabilistically checkable proofs ($\\PCP$) for verifiable computation. Each malicious party is detected with probability $1 - \\varepsilon$ for a negligible $\\varepsilon$ that is defined by the failure of the corresponding linear $\\PCP$. The initial protocol has to be executed only once, and the verification requires in total $3$ additional rounds (if some parties act dishonestly, in the worst case they may force the protocol to substitute each round with $4$ rounds, due to the transmission functionality that prevents the protocol from stopping). The verification also ensures that all the parties have sampled all the randomness from an appropriate distribution. Its efficiency does not depend on whether the inputs of the parties have been shared, or each party uses its own private input.

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.

19:17 [Pub][ePrint] Bounded-Collusion Identity-Based Encryption from Semantically-Secure Public-Key Encryption: Generic Constructions with Short Ciphertexts, by Stefano Tessaro and David A. Wilson

  Identity-based encryption (IBE) is a special case of public-key encryption where user identities replace public keys. Every user is given a corresponding secret key for decryp- tion, and encryptions for his or her identity must remain confidential even to attackers who learn the secret keys associated with other identities. Several IBE constructions are known to date, but their security relies on specific assumptions, such as quadratic residuosity, as well as different pairing-based and lattice-based assumptions.

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.

19:17 [Pub][ePrint] A Comparison of the Homomorphic Encryption Schemes FV and YASHE, by Tancrède Lepoint and Michael Naehrig

  We conduct a theoretical and practical comparison of two Ring-LWE-based, scale-invariant, leveled homomorphic encryption schemes -- Fan and Vercauteren\'s adaptation of BGV and the YASHE scheme proposed by Bos, Lauter, Loftus and Naehrig. In particular, we explain how to choose parameters to ensure correctness and security against lattice attacks. Our parameter selection improves the approach of van de Pol and Smart to choose parameters for schemes based on the Ring-LWE problem by using the BKZ-2.0 simulation algorithm.

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.

19:17 [Pub][ePrint] Cryptanalysis on \"Secure untraceable off-line electronic cash system\", by Yalin Chen and Jue-Sam Chou*

  Recently, Baseri et al. proposed a secure untraceable off-line electronic cash system. They claimed that their scheme could achieve security requirements of an e-cash system such as, untraceability, anonymity, unlinkability, double spending checking, un-forgeability, date-attachability, and prevent forging coins. They further prove the un-forgeability security feature by using the hardness of discrete logarithm problems. However, after cryptanalysis, we found that the scheme cannot attain the security feature, untraceability. We, therefore, modify it to comprise this desired requirement, which is very important in an e-cash system.

19:17 [Pub][ePrint] A Polynomial Time Attack against Algebraic Geometry Code Based Public Key Cryptosystems, by Alain Couvreur and Irene Márquez-Corbella and Ruud Pellikaan

  We give a polynomial time attack on the McEliece public key cryptosystem based on algebraic geometry codes. Roughly speaking, this attacks runs in $O(n^4)$ operations in $\\mathbb F_q$, where $n$ denotes the code length. Compared to previous attacks, allows to recover a decoding algorithm for the public key even for codes from high genus curves.

13:17 [Pub][ePrint] Cuckoo Cycle; a memory-hard proof-of-work system, by John Tromp

  we propose an elegant memory-hard proof-of-work system based on cuckoo hashing

04:48 [PhD][New] Claude Carlet

  Name: Claude Carlet