6 Search Results for "Stehlé, Damien"

Document
DOI: 10.4230/LIPIcs.ITCS.2025.8
Single-Round Proofs of Quantumness from Knowledge Assumptions

Authors: Petia Arabadjieva, Alexandru Gheorghiu, Victor Gitton, and Tony Metger

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
A proof of quantumness is an efficiently verifiable interactive test that an efficient quantum computer can pass, but all efficient classical computers cannot (under some cryptographic assumption). Such protocols play a crucial role in the certification of quantum devices. Existing single-round protocols based solely on a cryptographic hardness assumption (like asking the quantum computer to factor a large number) require large quantum circuits, whereas multi-round ones use smaller circuits but require experimentally challenging mid-circuit measurements. In this work, we construct efficient single-round proofs of quantumness based on existing knowledge assumptions. While knowledge assumptions have not been previously considered in this context, we show that they provide a natural basis for separating classical and quantum computation. Our work also helps in understanding the interplay between black-box/white-box reductions and cryptographic assumptions in the design of proofs of quantumness. Specifically, we show that multi-round protocols based on Decisional Diffie-Hellman (DDH) or Learning With Errors (LWE) can be "compiled" into single-round protocols using a knowledge-of-exponent assumption [Bitansky et al., 2012] or knowledge-of-lattice-point assumption [Loftus et al., 2012], respectively. We also prove an adaptive hardcore-bit statement for a family of claw-free functions based on DDH, which might be of independent interest.
Cite as

Petia Arabadjieva, Alexandru Gheorghiu, Victor Gitton, and Tony Metger. Single-Round Proofs of Quantumness from Knowledge Assumptions. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{arabadjieva_et_al:LIPIcs.ITCS.2025.8,
  author =	{Arabadjieva, Petia and Gheorghiu, Alexandru and Gitton, Victor and Metger, Tony},
  title =	{{Single-Round Proofs of Quantumness from Knowledge Assumptions}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.8},
  URN =		{urn:nbn:de:0030-drops-226364},
  doi =		{10.4230/LIPIcs.ITCS.2025.8},
  annote =	{Keywords: Proofs of quantumness, Knowledge assumptions, Learning with errors, Decisional Diffie-Hellman}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.73
On White-Box Learning and Public-Key Encryption

Authors: Yanyi Liu, Noam Mazor, and Rafael Pass

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We consider a generalization of the Learning With Error problem, referred to as the white-box learning problem: You are given the code of a sampler that with high probability produces samples of the form y,f(y) + ε where ε is small, and f is computable in polynomial-size, and the computational task consist of outputting a polynomial-size circuit C that with probability, say, 1/3 over a new sample y' according to the same distributions, approximates f(y') (i.e., |C(y')-f(y')| is small). This problem can be thought of as a generalizing of the Learning with Error Problem (LWE) from linear functions f to polynomial-size computable functions. We demonstrate that worst-case hardness of the white-box learning problem, conditioned on the instances satisfying a notion of computational shallowness (a concept from the study of Kolmogorov complexity) not only suffices to get public-key encryption, but is also necessary; as such, this yields the first problem whose worst-case hardness characterizes the existence of public-key encryption. Additionally, our results highlights to what extent LWE "overshoots" the task of public-key encryption. We complement these results by noting that worst-case hardness of the same problem, but restricting the learner to only get black-box access to the sampler, characterizes one-way functions.
Cite as

Yanyi Liu, Noam Mazor, and Rafael Pass. On White-Box Learning and Public-Key Encryption. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 73:1-73:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ITCS.2025.73,
  author =	{Liu, Yanyi and Mazor, Noam and Pass, Rafael},
  title =	{{On White-Box Learning and Public-Key Encryption}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{73:1--73:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.73},
  URN =		{urn:nbn:de:0030-drops-227012},
  doi =		{10.4230/LIPIcs.ITCS.2025.73},
  annote =	{Keywords: Public-Key Encryption, White-Box Learning}
}
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.CCC.2019.11
A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW Heuristic

Authors: Noah Stephens-Davidowitz

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

Abstract
For 0 <= alpha <= 1/2, we show an algorithm that does the following. Given appropriate preprocessing P(L) consisting of N_alpha := 2^{O(n^{1-2 alpha} + log n)} vectors in some lattice L subset {R}^n and a target vector t in R^n, the algorithm finds y in L such that ||y-t|| <= n^{1/2 + alpha} eta(L) in time poly(n) * N_alpha, where eta(L) is the smoothing parameter of the lattice. The algorithm itself is very simple and was originally studied by Doulgerakis, Laarhoven, and de Weger (to appear in PQCrypto, 2019), who proved its correctness under certain reasonable heuristic assumptions on the preprocessing P(L) and target t. Our primary contribution is a choice of preprocessing that allows us to prove correctness without any heuristic assumptions. Our main motivation for studying this is the recent breakthrough algorithm for IdealSVP due to Hanrot, Pellet - Mary, and Stehlé (to appear in Eurocrypt, 2019), which uses the DLW algorithm as a key subprocedure. In particular, our result implies that the HPS IdealSVP algorithm can be made to work with fewer heuristic assumptions. Our only technical tool is the discrete Gaussian distribution over L, and in particular, a lemma showing that the one-dimensional projections of this distribution behave very similarly to the continuous Gaussian. This lemma might be of independent interest.
Cite as

Noah Stephens-Davidowitz. A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW Heuristic. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 11:1-11:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{stephensdavidowitz:LIPIcs.CCC.2019.11,
  author =	{Stephens-Davidowitz, Noah},
  title =	{{A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW Heuristic}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{11:1--11:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.11},
  URN =		{urn:nbn:de:0030-drops-108331},
  doi =		{10.4230/LIPIcs.CCC.2019.11},
  annote =	{Keywords: Lattices, guaranteed distance decoding, GDD, GDDP}
}
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}
}
  • Refine by Type
  • 6 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2022
  • 1 2019
  • 1 2016
  • 1 2006

  • Refine by Author
  • 3 Stehlé, Damien
  • 1 Agrawal, Shweta
  • 1 Arabadjieva, Petia
  • 1 Bai, Shi
  • 1 Gheorghiu, Alexandru
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 1 DagSemProc

  • Refine by Classification
  • 1 Security and privacy → Cryptography
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Cryptographic protocols
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 3 Lattices
  • 1 Bounded Distance Decoding Problem
  • 1 Decisional Diffie-Hellman
  • 1 Floating-point arithmetic
  • 1 GDD
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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