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
January 18, 2005 - Products of Small Primes in Cryptology, Error Codes and Theoretical Computer Science
by David Naccache
| Abstract: | In formal number theory a Godel numbering is a function which assigns to each symbol and
formula of some formal language a unique natural number called a Godel number (GN). The
concept was first used by Kurt Godel in the proof of his incompleteness theorem in 1930
(this theorem states that in any consistent formalization of mathematics that is
sufficiently strong to define the concept of natural numbers, one can construct a statement
that can be neither proved nor disproved within that system).
The GN of a string of integers a_0,...,a_k is simply obtained by computing the product
p_0^{a_0}*...*p_k^{a_k} where p_i is the i-th prime number (i.e. p_0=2, p_1=3, p_2=5,...).
Intriguingly, this very simple mathematical object has other applications than just
proving Godel's incompleteness theorem: GN-based public key cryptosystems and
error-correcting codes emerged during the last decade.
In this talk we will sketch the proof of Godel's incompleteness theorem and overview the
role of GN-encoding therein, we will then present two different public-key cryptosystems
(both by Naccache and Stern, 1997 and 1998) using GN message encoding as well as a
(somewhat unusual) error correcting code (unpublished, cf.
https://silentbob.gemplus.com/repository/h.pdf page 688). |
Publications
Julien Cathalo, David Naccache, and Jean-Jacques Quisquater. Comparing with RSA, Twelfth IMA International Conference on Cryptography and Coding, Lecture Notes in Computer Science, Springer-Verlag, December 2009 PDF BibTeX
Julien Cathalo, David Naccache, and Jean-Jacques Quisquater. Comparing With RSA, In Cryptology ePrint Archive, January 2009, Report 2009/021 BibTeX
Julien Cathalo, Jean-Sébastien Coron, and David Naccache. From Fixed-Length to Arbitrary-Length RSA Encoding Schemes Revisited, In S. Vaudenay, editor(s), 8th International Workshop on Practice and Theory in Public-Key Cryptography (PKC 2005), Volume 3386 of Lecture Notes in Computer Science, pages 234-243, January 2005 PDF BibTeX
Jean-Sébastien Coron, François Koeune, and David Naccache. From fixed-length to arbitrary-length RSA padding schemes, In T. Okamoto, editor(s), Advances in Cryptology - ASIACRYPT 2000, Volume 1976 of Lecture Notes in Computer Science, pages 90-97, Springer-Verlag, December 2000 PDF BibTeX
Jean-Sébastien Coron, David Naccache, and Julien P.. On the security of RSA padding, In M. Wiener, editor(s), Advances in Cryptology - CRYPTO '99, Volume 1666, pages 1-18, Springer-Verlag, January 1999 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.
