The LLL Algorithm_ Survey and Applications [Nguyen & Valée 2009-12-02].pdf

(7033 KB) Pobierz
Information Security and Cryptography
Texts and Monographs
Series Editors
David Basin
Ueli Maurer
Advisory Board
Martín Abadi
Ross Anderson
Michael Backes
Ronald Cramer
Virgil D. Gligor
Oded Goldreich
Joshua D. Guttman
Arjen K. Lenstra
John C. Mitchell
Tatsuaki Okamoto
Kenny Paterson
Bart Preneel
Phong Q. Nguyen • Brigitte Vallée
Editors
The LLL Algorithm
Survey and Applications
123
Editors
Dr. Phong Q. Nguyen
INRIA Research Director
École Normale Supérieure
Département d'Informatique
Paris, France
phong.nguyen@ens.fr
Dr. Brigitte Vallée
CNRS Research Director
and Research Director
Ø
Département d'Informatique
Université de Caen, France
brigitte.vallee@info.unicaen.fr
ISSN 1619-7100
ISBN 978-3-642-02294-4
DOI 10.1007/978-3-642-02295-1
e-ISBN 978-3-642-02295-1
Springer Heidelberg Dordrecht London New York
Library of Congress Control Number:
2009934498
ACM Computing Classification (1998): F.2, F.1, E.3, G.1
© Springer-Verlag Berlin Heidelberg 2010
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
concerned, specif ically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting,
reproduction on microf ilm or in any other way, and storage in data banks. Duplication of this publication or
parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in
its current version, and permission for use must always be obtained from Springer. Violations are liable to
prosecution under the German Copyright Law.
The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply,
even in the absence of a specif ic statement, that such names are exempt from the relevant protective laws and
regulations and therefore free for general use.
Cover design:
KuenkelLopka GmbH
Printed on acid-free paper
Springer is a part of Springer Science+Business Media (www.springer.com)
Preface
Computational aspects of geometry of numbers have been revolutionized by the
Lenstra–Lenstra–Lov´ sz lattice reduction algorithm (LLL), which has led to break-
a
throughs in fields as diverse as computer algebra, cryptology, and algorithmic
number theory. After its publication in 1982, LLL was immediately recognized
as one of the most important algorithmic achievements of the twentieth century,
because of its broad applicability and apparent simplicity. Its popularity has kept
growing since, as testified by the hundreds of citations of the original article, and
the ever more frequent use of LLL as a synonym to lattice reduction.
As an unfortunate consequence of the pervasiveness of the LLL algorithm,
researchers studying and applying it belong to diverse scientific communities, and
seldom meet. While discussing that particular issue with Damien Stehl´ at the 7th
e
Algorithmic Number Theory Symposium (ANTS VII) held in Berlin in July 2006,
John Cremona accurately remarked that 2007 would be the 25th anniversary of LLL
and this deserved a meeting to celebrate that event. The year 2007 was also involved
in another arithmetical story. In 2003 and 2005, Ali Akhavi, Fabien Laguillaumie,
and Brigitte Vall´ e with other colleagues organized two workshops on cryptology
e
and algorithms with a strong emphasis on lattice reduction: CAEN ’03 and CAEN
’05, CAEN denoting both the location and the content (Cryptologie
et Algorith-
mique En Normandie).
Very quickly after the ANTS conference, Ali Akhavi, Fabien
Laguillaumie, and Brigitte Vall´ e were thus readily contacted and reacted very
e
enthusiastically about organizing the LLL birthday conference. The organization
committee was formed.
Within a couple of months, the three L’s, Arjen and Hendrik Lenstra, and L´ szl´
a o
Lov´ sz, kindly accepted to participate, which provided confidence to the organizing
a
team. At the same time, a program committee was created. Its members – Karen
Aardal, Shafi Goldwasser, Phong Nguyen, Claus Schnorr, Denis Simon, and Brigitte
Vall´ e – come from diverse fields, so as to represent as many LLL-practitioners as
e
possible. They invited speakers to give overview talks at the conference.
The anniversary conference eventually took place between 29th June and 1st
July 2007, at the University of Caen. During these three days, 14 invited talks were
given on topics closely related to the LLL algorithm. A poster session gathered 12
presentations on ongoing research projects. Overall, 120 researchers from 16 coun-
tries and very diverse scientific backgrounds attended the event. And naturally,
v

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin