Search Results

Documents authored by Stehlé, Damien

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.8
Round-Optimal Lattice-Based Threshold Signatures, Revisited

Authors: Shweta Agrawal, Damien Stehlé, and Anshu Yadav

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Threshold signature schemes enable distribution of the signature issuing capability to multiple users, to mitigate the threat of signing key compromise. Though a classic primitive, these signatures have witnessed a surge of interest in recent times due to relevance to modern applications like blockchains and cryptocurrencies. In this work, we study round-optimal threshold signatures in the post-quantum regime and improve the only known lattice-based construction by Boneh et al. [CRYPTO'18] as follows: - Efficiency. We reduce the amount of noise flooding used in the construction from 2^Ω(λ) down to √Q, where Q is the bound on the number of generated signatures and λ is the security parameter. By using lattice hardness assumptions over polynomial rings, this allows to decrease the signature bit-lengths from Õ(λ³) to Õ(λ), bringing them significantly closer to practice. Our improvement relies on a careful analysis using Rényi divergence rather than statistical distance in the security proof. - Instantiation. The construction of Boneh et al. requires a standard signature scheme to be evaluated homomorphically. To instantiate this, we provide a homomorphism-friendly variant of Lyubashevsky’s signature [EUROCRYPT '12] which achieves low circuit depth by being "rejection-free" and uses an optimal, moderate noise flooding of √Q, matching the above. - Towards Adaptive Security. The construction of Boneh et al. satisfies only selective security, where all the corrupted parties must be announced before any signing query is made. We improve this in two ways: in the Random Oracle Model, we obtain partial adaptivity where signing queries can be made before the corrupted parties are announced but the set of corrupted parties must be announced all at once. In the standard model, we obtain full adaptivity, where parties can be corrupted at any time but this construction is in a weaker pre-processing model where signers must be provided correlated randomness of length proportional to the number of signatures, in an offline preprocessing phase.
Cite as

Shweta Agrawal, Damien Stehlé, and Anshu Yadav. Round-Optimal Lattice-Based Threshold Signatures, Revisited. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ICALP.2022.8,
  author =	{Agrawal, Shweta and Stehl\'{e}, Damien and Yadav, Anshu},
  title =	{{Round-Optimal Lattice-Based Threshold Signatures, Revisited}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.8},
  URN =		{urn:nbn:de:0030-drops-163491},
  doi =		{10.4230/LIPIcs.ICALP.2022.8},
  annote =	{Keywords: Post-Quantum Cryptography, Lattices, Threshold Signatures}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.76
Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices

Authors: Shi Bai, Damien Stehlé, and Weiqiang Wen

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We present a probabilistic polynomial-time reduction from the lattice Bounded Distance Decoding (BDD) problem with parameter 1/( sqrt(2) * gamma) to the unique Shortest Vector Problem (uSVP) with parameter gamma for any gamma > 1 that is polynomial in the lattice dimension n. It improves the BDD to uSVP reductions of [Lyubashevsky and Micciancio, CRYPTO, 2009] and [Liu, Wang, Xu and Zheng, Inf. Process. Lett., 2014], which rely on Kannan's embedding technique. The main ingredient to the improvement is the use of Khot's lattice sparsification [Khot, FOCS, 2003] before resorting to Kannan's embedding, in order to boost the uSVP parameter.
Cite as

Shi Bai, Damien Stehlé, and Weiqiang Wen. Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 76:1-76:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bai_et_al:LIPIcs.ICALP.2016.76,
  author =	{Bai, Shi and Stehl\'{e}, Damien and Wen, Weiqiang},
  title =	{{Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{76:1--76:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.76},
  URN =		{urn:nbn:de:0030-drops-62085},
  doi =		{10.4230/LIPIcs.ICALP.2016.76},
  annote =	{Keywords: Lattices, Bounded Distance Decoding Problem, Unique Shortest Vector Problem, Sparsification}
}
Document
DOI: 10.4230/DagSemProc.06021.11
Worst Cases for the Exponential Function in the IEEE 754r decimal64 Format

Authors: Vincent Lefèvre, Damien Stehlé, and Paul Zimmermann

Published in: Dagstuhl Seminar Proceedings, Volume 6021, Reliable Implementation of Real Number Algorithms: Theory and Practice (2006)

Abstract
We searched for the worst cases for correct rounding of the exponential function in the IEEE 754r decimal64 format, and computed all the bad cases whose distance from a breakpoint (for all rounding modes) is less than $10^{-15}$,ulp, and we give the worst ones. In particular, the worst case for $|x| geq 3 imes 10^{-11}$ is $exp(9.407822313572878 imes 10^{-2}) = 1.098645682066338,5,0000000000000000,278ldots$. This work can be extended to other elementary functions in the decimal64 format and allows the design of reasonably fast routines that will evaluate these functions with correct rounding, at least in some domains.
Cite as

Vincent Lefèvre, Damien Stehlé, and Paul Zimmermann. Worst Cases for the Exponential Function in the IEEE 754r decimal64 Format. In Reliable Implementation of Real Number Algorithms: Theory and Practice. Dagstuhl Seminar Proceedings, Volume 6021, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{lefevre_et_al:DagSemProc.06021.11,
  author =	{Lef\`{e}vre, Vincent and Stehl\'{e}, Damien and Zimmermann, Paul},
  title =	{{Worst Cases for the Exponential Function in the IEEE 754r decimal64 Format}},
  booktitle =	{Reliable Implementation of Real Number Algorithms: Theory and Practice},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6021},
  editor =	{Peter Hertling and Christoph M. Hoffmann and Wolfram Luther and Nathalie Revol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06021.11},
  URN =		{urn:nbn:de:0030-drops-7483},
  doi =		{10.4230/DagSemProc.06021.11},
  annote =	{Keywords: Floating-point arithmetic, decimal arithmetic, table maker's dilemma, correct rounding, elementary functions}
}
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