Disclaimer: This page refers to an external person. It only lists all the interactions between this person and the Crypto Group. Validity or accuracy of the following information is thus not guaranteed in any way.
Seminars given
November 17, 2005 - Discrete-Log-Based Signatures May Not Be Equivalent to Discrete Log
by Damien Vergnaud
| Abstract: | We provide evidence that the unforgeability of several
discrete-log based signatures like Schnorr signatures cannot
be equivalent to the discrete log problem in the standard model.
This contradicts in nature well-known proofs standing in weakened proof methodologies, in particular proofs employing various formulations of the Forking Lemma in the random oracle Model. Our impossibility proofs apply to many discrete-log-based signatures like ElGamal signatures and their extensions, DSA, ECDSA and KCDSA as well as standard generalizations of these, and even RSA-based signatures like GQ.
All known reductions attesting the unforgeability of Fiat-Shamir
transformed signatures in the random oracle model lead to a loss factor close to q_h in terms of execution time or success probability (q_h denotes the number of oracle queries). There
exists no proof that this loss factor is necessary. We prove, however, that any random-oracle-based reduction from computing the discrete logarithm to forging Schnorr signatures must lose at least a factor close to the square root of q_h. We further
conjecture that the 1/q_h loss is optimal. In any case, our results show that a proof of equivalence in the ROM (if algebraic) will *never be tight*. We believe our work sheds a new perspective as to why no efficient proof of equivalence to the discrete log problem has ever been found for Schnorr signatures despite considerable research efforts.
We stress that our work sheds more light on the provable (in)security of popular signature schemes but does
not explicitly lead to actual attacks on these.
(Joint work with Pascal Paillier from Advanced Cryptographic Services, Gemplus Card International. A paper summarizing this work will appear in the proceedings of the Asiacrypt'05 conference.)
|
Publications
Malika Izabachène, Benoit Libert, and Damien Vergnaud. Block-wise P-signatures and Non-Interactive Anonymous Credentials with Efficient Attributes, In L. Chen, editor(s), 13th IMA International Conference on Cryptography and Coding (IMACC 2011), Volume 7089 of Lecture Notes on Computer Science, pages 431-450, Springer, December 2011, BibTeX
Brett Hemenway, Benoit Libert, Rafail Ostrovsky, and Damien Vergnaud. Lossy Encryption: Constructions from General Assumptions and Efficient Selective Opening Chosen Ciphertext Security, In D.-H. Lee & X. Wang, editor(s), Asiacrypt 2011, Volume 7073 of Lecture Notes in Computer Science, pages 70-88, Spinger, December 2011, BibTeX
Benoit Libert, and Damien Vergnaud. Unidirectional Chosen-Ciphertext Secure Proxy Re- Encryption, In IEEE Transactions on Information Theory, Volume 57-3, pages 1786-1802, March 2011 BibTeX
Benoit Libert, and Damien Vergnaud. Group Signatures with Verifier-Local Revocation and Backward Unlinkability in the Standard Model, In A. Miyaji and J. Garay, editor(s), 8th International Conference on Cryptology and Network Security (CANS 2009), Volume 5888 of Lecture Notes in Computer Science, pages 498-517, Springer, December 2009 BibTeX
Benoit Libert, and Damien Vergnaud. Adaptive-ID Secure Revocable Identity-Based Encryption, In M. Fischlin, editor(s), Topics in Cryptology - CT-RSA 2009, Volume 5473 of Lecture Notes in Computer Science, pages 1-15, Springer, April 2009 BibTeX
Benoit Libert, and Damien Vergnaud. Towards Black-Box Accountable Authority IBE with Short Ciphertexts and Private Keys, In G. Tsudik and S. Jarecki, editor(s), Public Key Cryptography 2009 (PKC 2009), Volume 5443 of Lecture Notes in Computer Science, pages 235-255, Springer, March 2009 BibTeX
Benoit Libert, and Damien Vergnaud. Multi-Use Unidirectional Proxy Re-Signatures, In P. Syverson and S. Jha, editor(s), 15th ACM Conference on Computer and Communications Security (ACM-CCS 2008), pages 511-520, ACM Press, October 2008, BibTeX
Benoit Libert, and Damien Vergnaud. Tracing Malicious Proxies in Proxy Re-Encryption, In S. Galbraith and K. Paterson, editor(s), 2nd International Conference on Pairing-Based Cryptography (Pairing 2008), Volume 5209 of Lecture Notes in Computer Science, pages 332-353, Springer, September 2008, To Appear BibTeX
Benoit Libert, and Damien Vergnaud. Unidirectional Chosen-Ciphertext Secure Proxy Re-Encryption, In R. Cramer , editor(s), 11th International Workshop on Practice and Theory in Public Key Cryptography (PKC 2008), Volume 4939 of Lecture Notes in Computer Science, pages 360-379, Springer, March 2008 BibTeX
Copyright Notice
(
click here to expand/retract)
Some material that is available from this page is copyrighted.
IACR Copyright Notice: Permission is granted for a user to display all
material at this site, to copy the material onto a single computer, and to make
print copies of the material for personal use only. All other rights are
retained by the International Association for Cryptologic Research. In
particular, any other copying, other redistribution, or any commercial use of
the material requires the permission of the publisher, which may be requested
by contacting the International Association for Cryptologic Research.
IEEE Copyright Notice: This material is presented to ensure timely
dissemination of scholarly and technical work. Copyright and all rights therein
are retained by authors or by other copyright holders. All persons copying this
information are expected to adhere to the terms and constraints invoked by each
author's copyright. In most cases, these works may not be reposted without the
explicit permission of the copyright holder.
ACM Copyright Notice: Copyright © 1999 by the Association for
Computing Machinery, Inc. Permission to make digital or hard copies of part of
this work for personal or classroom use is granted without fee provided that
copies are not made or distributed for profit or commercial advantage and that
copies bear this notice and the full citation on the first page or intial
screen of the document. Copyrights for components of this work owned by others
than ACM must be honored. Abstracting with credit is permitted. To copy
otherwise, to republish, to post on servers, or to redistribute to lists,
requires prior specific permission and/or a fee. Request permissions from
Publications Dept., ACM Inc., fax +1 (212) 869-0481, or
permissions@acm.org.
Springer-Verlag LNCS Copyright Notice: The copyright of these
contributions has been transferred to Springer-Verlag Berlin Heidelberg New
York. The copyright transfer covers the exclusive right to reproduce and
distribute the contribution, including reprints, translations, photographic
reproductions, microform, electronic form (offline, online), or any other
reproductions of similar nature. Online available from Springer-Verlag LNCS
series.
