Volume

Dagstuhl Seminar Proceedings, Volume 9221

Publication Details

  • published at: 2009-08-20
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.09221.1
09221 Abstracts Collection – Algorithms and NumberTheory

Authors: Johannes A. Buchmann, John Cremona, and Michael Pohst

Abstract
From 24.05. to 29.05.2009, the Dagstuhl Seminar 09221 ``Algorithms and Number Theory '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Johannes A. Buchmann, John Cremona, and Michael Pohst. 09221 Abstracts Collection – Algorithms and NumberTheory. In Algorithms and Number Theory. Dagstuhl Seminar Proceedings, Volume 9221, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{buchmann_et_al:DagSemProc.09221.1,
  author =	{Buchmann, Johannes A. and Cremona, John and Pohst, Michael},
  title =	{{09221 Abstracts Collection – Algorithms and NumberTheory}},
  booktitle =	{Algorithms and Number Theory},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9221},
  editor =	{Johannes A. Buchmann and John Cremona and Michael E. Pohst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09221.1},
  URN =		{urn:nbn:de:0030-drops-21282},
  doi =		{10.4230/DagSemProc.09221.1},
  annote =	{Keywords: Algorithms, Number Theory, Cryptography}
}
Document
DOI: 10.4230/DagSemProc.09221.2
Density of Ideal Lattices

Authors: Johannes A. Buchmann and Richard Lindner

Abstract
The security of many emph{efficient} cryptographic constructions, e.g.~collision-resistant hash functions, digital signatures, and identification schemes, has been proven assuming the hardness of emph{worst-case} computational problems in ideal lattices. These lattices correspond to ideals in the ring of integers of some fixed number field $K$. In this paper we show that the density of $n$-dimensional ideal lattices with determinant $le b$ among all lattices under the same bound is in $O(b^{1-n})$. So for lattices of dimension $> 1$ with bounded determinant, the subclass of ideal lattices is always vanishingly small.
Cite as

Johannes A. Buchmann and Richard Lindner. Density of Ideal Lattices. In Algorithms and Number Theory. Dagstuhl Seminar Proceedings, Volume 9221, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{buchmann_et_al:DagSemProc.09221.2,
  author =	{Buchmann, Johannes A. and Lindner, Richard},
  title =	{{Density of Ideal Lattices}},
  booktitle =	{Algorithms and Number Theory},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9221},
  editor =	{Johannes A. Buchmann and John Cremona and Michael E. Pohst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09221.2},
  URN =		{urn:nbn:de:0030-drops-21256},
  doi =		{10.4230/DagSemProc.09221.2},
  annote =	{Keywords: Post-quantum cryptography, provable security, ideal lattices}
}
Document
DOI: 10.4230/DagSemProc.09221.3
Lattice-based Blind Signatures

Authors: Markus Rückert

Abstract
Motivated by the need to have secure blind signatures even in the presence of quantum computers, we present two efficient blind signature schemes based on hard worst-case lattice problems. Both schemes are provably secure in the random oracle model and unconditionally blind. The first scheme is based on preimage samplable functions that were introduced at STOC 2008 by Gentry, Peikert, and Vaikuntanathan. The scheme is stateful and runs in 3 moves. The second scheme builds upon the PKC 2008 identification scheme of Lyubashevsky. It is stateless, has 4 moves, and its security is based on the hardness of worst-case problems in ideal lattices.
Cite as

Markus Rückert. Lattice-based Blind Signatures. In Algorithms and Number Theory. Dagstuhl Seminar Proceedings, Volume 9221, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ruckert:DagSemProc.09221.3,
  author =	{R\"{u}ckert, Markus},
  title =	{{Lattice-based Blind Signatures}},
  booktitle =	{Algorithms and Number Theory},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9221},
  editor =	{Johannes A. Buchmann and John Cremona and Michael E. Pohst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09221.3},
  URN =		{urn:nbn:de:0030-drops-21278},
  doi =		{10.4230/DagSemProc.09221.3},
  annote =	{Keywords: Blind signatures, post-quantum, lattices, privacy}
}
Document
DOI: 10.4230/DagSemProc.09221.4
Probabilistic Analysis of LLL Reduced Bases

Authors: Michael Schneider

Abstract
LLL reduction, originally founded in 1982 to factor certain polynomials, is a useful tool in public key cryptanalysis. The search for short lattice vectors helps determining the practical hardness of lattice problems, which are supposed to be secure against quantum computer attacks. It is a fact that in practice, the LLL algorithm finds much shorter vectors than its theoretic analysis guarantees. Therefore one can see that the guaranteed worst case bounds are not helpful for practical purposes. We use a probabilistic approach to give an estimate for the length of the shortest vector in an LLL-reduced bases that is tighter than the worst case bounds.
Cite as

Michael Schneider. Probabilistic Analysis of LLL Reduced Bases. In Algorithms and Number Theory. Dagstuhl Seminar Proceedings, Volume 9221, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{schneider:DagSemProc.09221.4,
  author =	{Schneider, Michael},
  title =	{{Probabilistic Analysis of LLL Reduced Bases}},
  booktitle =	{Algorithms and Number Theory},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9221},
  editor =	{Johannes A. Buchmann and John Cremona and Michael E. Pohst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09221.4},
  URN =		{urn:nbn:de:0030-drops-21267},
  doi =		{10.4230/DagSemProc.09221.4},
  annote =	{Keywords: Lattice reduction, LLL algorithm}
}
Document
DOI: 10.4230/DagSemProc.09221.5
Rational Points on Curves of Genus 2: Experiments and Speculations

Authors: Michael Stoll

Abstract
I will present results of computations providing statistics on rational points on (small) curves of genus 2 and use them to present several conjectures. Some of them are based on heuristic considerations, others are not.
Cite as

Michael Stoll. Rational Points on Curves of Genus 2: Experiments and Speculations. In Algorithms and Number Theory. Dagstuhl Seminar Proceedings, Volume 9221, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{stoll:DagSemProc.09221.5,
  author =	{Stoll, Michael},
  title =	{{Rational Points on Curves of Genus 2: Experiments and Speculations}},
  booktitle =	{Algorithms and Number Theory},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9221},
  editor =	{Johannes A. Buchmann and John Cremona and Michael E. Pohst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09221.5},
  URN =		{urn:nbn:de:0030-drops-21246},
  doi =		{10.4230/DagSemProc.09221.5},
  annote =	{Keywords: Rational points, genus 2}
}

Filters

  • Authors
  • B
  • Buchmann, Johannes A.
  • C
  • Cremona, John
  • L
  • Lindner, Richard
  • P
  • Pohst, Michael
  • R
  • Rückert, Markus
  • S
  • Schneider, Michael
  • Stoll, Michael

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact