74 results on '"Espitau, Thomas"'
Search Results
2. Two-Round Threshold Signature from Algebraic One-More Learning with Errors
- Author
-
Espitau, Thomas, Katsumata, Shuichi, Takemure, Kaoru, Goos, Gerhard, Series Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Reyzin, Leonid, editor, and Stebila, Douglas, editor
- Published
- 2024
- Full Text
- View/download PDF
3. : Masking-Friendly Hash-and-Sign Lattice Signatures
- Author
-
Esgin, Muhammed F., Espitau, Thomas, Niot, Guilhem, Prest, Thomas, Sakzad, Amin, Steinfeld, Ron, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Joye, Marc, editor, and Leander, Gregor, editor
- Published
- 2024
- Full Text
- View/download PDF
4. Cryptanalysis of the Peregrine Lattice-Based Signature Scheme
- Author
-
Lin, Xiuhan, Suzuki, Moeto, Zhang, Shiduo, Espitau, Thomas, Yu, Yang, Tibouchi, Mehdi, Abe, Masayuki, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Tang, Qiang, editor, and Teague, Vanessa, editor
- Published
- 2024
- Full Text
- View/download PDF
5. Masking the GLP Lattice-Based Signature Scheme at Any Order
- Author
-
Barthe, Gilles, Belaïd, Sonia, Espitau, Thomas, Fouque, Pierre-Alain, Grégoire, Benjamin, Rossi, Mélissa, and Tibouchi, Mehdi
- Published
- 2024
- Full Text
- View/download PDF
6. On Gaussian Sampling, Smoothing Parameter and Application to Signatures
- Author
-
Espitau, Thomas, Wallet, Alexandre, Yu, Yang, Goos, Gerhard, Series Editor, Hartmanis, Juris, Founding Editor, van Leeuwen, Jan, Series Editor, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Kobsa, Alfred, Series Editor, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Nierstrasz, Oscar, Series Editor, Pandu Rangan, C., Editorial Board Member, Sudan, Madhu, Series Editor, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Weikum, Gerhard, Series Editor, Vardi, Moshe Y, Series Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Guo, Jian, editor, and Steinfeld, Ron, editor
- Published
- 2023
- Full Text
- View/download PDF
7. Antrag: Annular NTRU Trapdoor Generation : Making Mitaka as Secure as Falcon
- Author
-
Espitau, Thomas, Nguyen, Thi Thu Quyen, Sun, Chao, Tibouchi, Mehdi, Wallet, Alexandre, Goos, Gerhard, Series Editor, Hartmanis, Juris, Founding Editor, van Leeuwen, Jan, Series Editor, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Kobsa, Alfred, Series Editor, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Nierstrasz, Oscar, Series Editor, Pandu Rangan, C., Editorial Board Member, Sudan, Madhu, Series Editor, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Weikum, Gerhard, Series Editor, Vardi, Moshe Y, Series Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Guo, Jian, editor, and Steinfeld, Ron, editor
- Published
- 2023
- Full Text
- View/download PDF
8. Finding Short Integer Solutions When the Modulus Is Small
- Author
-
Ducas, Léo, Espitau, Thomas, Postlethwaite, Eamonn W., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Handschuh, Helena, editor, and Lysyanskaya, Anna, editor
- Published
- 2023
- Full Text
- View/download PDF
9. The nearest-colattice algorithm
- Author
-
Espitau, Thomas and Kirchner, Paul
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Geometry ,Computer Science - Cryptography and Security - Abstract
In this work, we exhibit a hierarchy of polynomial time algorithms solving approximate variants of the Closest Vector Problem (CVP). Our first contribution is a heuristic algorithm achieving the same distance tradeoff as HSVP algorithms, namely $\approx \beta^{\frac{n}{2\beta}}\textrm{covol}(\Lambda)^{\frac{1}{n}}$ for a random lattice $\Lambda$ of rank $n$. Compared to the so-called Kannan's embedding technique, our algorithm allows using precomputations and can be used for efficient batch CVP instances. This implies that some attacks on lattice-based signatures lead to very cheap forgeries, after a precomputation. Our second contribution is a proven reduction from approximating the closest vector with a factor $\approx n^{\frac32}\beta^{\frac{3n}{2\beta}}$ to the Shortest Vector Problem (SVP) in dimension $\beta$., Comment: 19 pages, presented at the Algorithmic Number Theory Symposium (ANTS 2020)
- Published
- 2020
10. Algebraic and Euclidean Lattices: Optimal Lattice Reduction and Beyond
- Author
-
Espitau, Thomas, Kirchner, Paul, and Fouque, Pierre-Alain
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Geometry ,Mathematics - Number Theory - Abstract
We introduce a framework generalizing lattice reduction algorithms to module lattices in order to practically and efficiently solve the $\gamma$-Hermite Module-SVP problem over arbitrary cyclotomic fields. The core idea is to exploit the structure of the subfields for designing a doubly-recursive strategy of reduction: both recursive in the rank of the module and in the field we are working in. Besides, we demonstrate how to leverage the inherent symplectic geometry existing in the tower of fields to provide a significant speed-up of the reduction for rank two modules. The recursive strategy over the rank can also be applied to the reduction of Euclidean lattices, and we can perform a reduction in asymptotically almost the same time as matrix multiplication. As a byproduct of the design of these fast reductions, we also generalize to all cyclotomic fields and provide speedups for many previous number theoretical algorithms. Quantitatively, we show that a module of rank 2 over a cyclotomic field of degree $n$ can be heuristically reduced within approximation factor $2^{\tilde{O}(n)}$ in time $\tilde{O}(n^2B)$, where $B$ is the bitlength of the entries. For $B$ large enough, this complexity shrinks to $\tilde{O}(n^{\log_2 3}B)$. This last result is particularly striking as it goes below the estimate of $n^2B$ swaps given by the classical analysis of the LLL algorithm using the so-called potential.
- Published
- 2019
11. Finding Short Integer Solutions When the Modulus Is Small
- Author
-
Ducas, Léo, primary, Espitau, Thomas, additional, and Postlethwaite, Eamonn W., additional
- Published
- 2023
- Full Text
- View/download PDF
12. Certified lattice reduction
- Author
-
Espitau, Thomas and Joux, Antoine
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Numerical Analysis ,Mathematics - Number Theory ,11H06, 11H55, 11R04 - Abstract
Quadratic form reduction and lattice reduction are fundamental tools in computational number theory and in computer science, especially in cryptography. The celebrated Lenstra-Lenstra-Lov\'asz reduction algorithm (so-called LLL) has been improved in many ways through the past decades and remains one of the central methods used for reducing integral lattice basis. In particular, its floating-point variants-where the rational arithmetic required by Gram-Schmidt orthogonalization is replaced by floating-point arithmetic-are now the fastest known. However, the systematic study of the reduction theory of real quadratic forms or, more generally, of real lattices is not widely represented in the literature. When the problem arises, the lattice is usually replaced by an integral approximation of (a multiple of) the original lattice, which is then reduced. While practically useful and proven in some special cases, this method doesn't offer any guarantee of success in general. In this work, we present an adaptive-precision version of a generalized LLL algorithm that covers this case in all generality. In particular, we replace floating-point arithmetic by Interval Arithmetic to certify the behavior of the algorithm. We conclude by giving a typical application of the result in algebraic number theory for the reduction of ideal lattices in number fields., Comment: 23 pages
- Published
- 2019
13. Shorter Hash-and-Sign Lattice-Based Signatures
- Author
-
Espitau, Thomas, Tibouchi, Mehdi, Wallet, Alexandre, Yu, Yang, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Dodis, Yevgeniy, editor, and Shrimpton, Thomas, editor
- Published
- 2022
- Full Text
- View/download PDF
14. Mitaka: A Simpler, Parallelizable, Maskable Variant of Falcon
- Author
-
Espitau, Thomas, Fouque, Pierre-Alain, Gérard, François, Rossi, Mélissa, Takahashi, Akira, Tibouchi, Mehdi, Wallet, Alexandre, Yu, Yang, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Dunkelman, Orr, editor, and Dziembowski, Stefan, editor
- Published
- 2022
- Full Text
- View/download PDF
15. An Assertion-Based Program Logic for Probabilistic Programs
- Author
-
Barthe, Gilles, Espitau, Thomas, Gaboardi, Marco, Grégoire, Benjamin, Hsu, Justin, and Strub, Pierre-Yves
- Subjects
Computer Science - Logic in Computer Science ,Computer Science - Programming Languages - Abstract
Research on deductive verification of probabilistic programs has considered expectation-based logics, where pre- and post-conditions are real-valued functions on states, and assertion-based logics, where pre- and post-conditions are boolean predicates on state distributions. Both approaches have developed over nearly four decades, but they have different standings today. Expectation-based systems have managed to formalize many sophisticated case studies, while assertion-based systems today have more limited expressivity and have targeted simpler examples. We present Ellora, a sound and relatively complete assertion-based program logic, and demonstrate its expressivity by verifying several classical examples of randomized algorithms using an implementation in the EasyCrypt proof assistant. Ellora features new proof rules for loops and adversarial code, and supports richer assertions than existing program logics. We also show that Ellora allows convenient reasoning about complex probabilistic concepts by developing a new program logic for probabilistic independence and distribution law, and then smoothly embedding it into Ellora. Our work demonstrates that the assertion-based approach is not fundamentally limited and suggests that some notions are potentially easier to reason about in assertion-based systems.
- Published
- 2018
16. Towards Faster Polynomial-Time Lattice Reduction
- Author
-
Kirchner, Paul, Espitau, Thomas, Fouque, Pierre-Alain, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Malkin, Tal, editor, and Peikert, Chris, editor
- Published
- 2021
- Full Text
- View/download PDF
17. Proving Expected Sensitivity of Probabilistic Programs
- Author
-
Barthe, Gilles, Espitau, Thomas, Grégoire, Benjamin, Hsu, Justin, and Strub, Pierre-Yves
- Subjects
Computer Science - Programming Languages ,Computer Science - Logic in Computer Science - Abstract
Program sensitivity, also known as Lipschitz continuity, describes how small changes in a program's input lead to bounded changes in the output. We propose an average notion of program sensitivity for probabilistic programs---expected sensitivity---that averages a distance function over a probabilistic coupling of two output distributions from two similar inputs. By varying the distance, expected sensitivity recovers useful notions of probabilistic function sensitivity, including stability of machine learning algorithms and convergence of Markov chains. Furthermore, expected sensitivity satisfies clean compositional properties and is amenable to formal verification. We develop a relational program logic called $\mathbb{E}$pRHL for proving expected sensitivity properties. Our logic features two key ideas. First, relational pre-conditions and post-conditions are expressed using distances, a real-valued generalization of typical boolean-valued (relational) assertions. Second, judgments are interpreted in terms of expectation coupling, a novel, quantitative generalization of probabilistic couplings which supports compositional reasoning. We demonstrate our logic on examples beyond the reach of prior relational logics. Our main example formalizes uniform stability of the stochastic gradient method. Furthermore, we prove rapid mixing for a probabilistic model of population dynamics. We also extend our logic with a transitivity principle for expectation couplings to capture the path coupling proof technique by Bubley and Dyer, and formalize rapid mixing of the Glauber dynamics from statistical physics.
- Published
- 2017
- Full Text
- View/download PDF
18. Relational $\star$-Liftings for Differential Privacy
- Author
-
Barthe, Gilles, Espitau, Thomas, Hsu, Justin, Sato, Tetsuya, and Strub, Pierre-Yves
- Subjects
Computer Science - Logic in Computer Science ,Computer Science - Programming Languages - Abstract
Recent developments in formal verification have identified approximate liftings (also known as approximate couplings) as a clean, compositional abstraction for proving differential privacy. This construction can be defined in two styles. Earlier definitions require the existence of one or more witness distributions, while a recent definition by Sato uses universal quantification over all sets of samples. These notions have each have their own strengths: the universal version is more general than the existential ones, while existential liftings are known to satisfy more precise composition principles. We propose a novel, existential version of approximate lifting, called $\star$-lifting, and show that it is equivalent to Sato's construction for discrete probability measures. Our work unifies all known notions of approximate lifting, yielding cleaner properties, more general constructions, and more precise composition theorems for both styles of lifting, enabling richer proofs of differential privacy. We also clarify the relation between existing definitions of approximate lifting, and consider more general approximate liftings based on $f$-divergences.
- Published
- 2017
- Full Text
- View/download PDF
19. Proving uniformity and independence by self-composition and coupling
- Author
-
Barthe, Gilles, Espitau, Thomas, Grégoire, Benjamin, Hsu, Justin, and Strub, Pierre-Yves
- Subjects
Computer Science - Programming Languages ,Computer Science - Logic in Computer Science - Abstract
Proof by coupling is a classical proof technique for establishing probabilistic properties of two probabilistic processes, like stochastic dominance and rapid mixing of Markov chains. More recently, couplings have been investigated as a useful abstraction for formal reasoning about relational properties of probabilistic programs, in particular for modeling reduction-based cryptographic proofs and for verifying differential privacy. In this paper, we demonstrate that probabilistic couplings can be used for verifying non-relational probabilistic properties. Specifically, we show that the program logic pRHL---whose proofs are formal versions of proofs by coupling---can be used for formalizing uniformity and probabilistic independence. We formally verify our main examples using the EasyCrypt proof assistant.
- Published
- 2017
20. Mitaka: A Simpler, Parallelizable, Maskable Variant of Falcon
- Author
-
Espitau, Thomas, primary, Fouque, Pierre-Alain, additional, Gérard, François, additional, Rossi, Mélissa, additional, Takahashi, Akira, additional, Tibouchi, Mehdi, additional, Wallet, Alexandre, additional, and Yu, Yang, additional
- Published
- 2022
- Full Text
- View/download PDF
21. Shorter Hash-and-Sign Lattice-Based Signatures
- Author
-
Espitau, Thomas, primary, Tibouchi, Mehdi, additional, Wallet, Alexandre, additional, and Yu, Yang, additional
- Published
- 2022
- Full Text
- View/download PDF
22. On a Dual/Hybrid Approach to Small Secret LWE : A Dual/Enumeration Technique for Learning with Errors and Application to Security Estimates of FHE Schemes
- Author
-
Espitau, Thomas, Joux, Antoine, Kharchenko, Natalia, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bhargavan, Karthikeyan, editor, Oswald, Elisabeth, editor, and Prabhakaran, Manoj, editor
- Published
- 2020
- Full Text
- View/download PDF
23. Fast Reduction of Algebraic Lattices over Cyclotomic Fields
- Author
-
Kirchner, Paul, Espitau, Thomas, Fouque, Pierre-Alain, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Micciancio, Daniele, editor, and Ristenpart, Thomas, editor
- Published
- 2020
- Full Text
- View/download PDF
24. Synthesizing Probabilistic Invariants via Doob's Decomposition
- Author
-
Barthe, Gilles, Espitau, Thomas, Fioriti, Luis María Ferrer, and Hsu, Justin
- Subjects
Computer Science - Programming Languages ,Computer Science - Symbolic Computation - Abstract
When analyzing probabilistic computations, a powerful approach is to first find a martingale---an expression on the program variables whose expectation remains invariant---and then apply the optional stopping theorem in order to infer properties at termination time. One of the main challenges, then, is to systematically find martingales. We propose a novel procedure to synthesize martingale expressions from an arbitrary initial expression. Contrary to state-of-the-art approaches, we do not rely on constraint solving. Instead, we use a symbolic construction based on Doob's decomposition. This procedure can produce very complex martingales, expressed in terms of conditional expectations. We show how to automatically generate and simplify these martingales, as well as how to apply the optional stopping theorem to infer properties at termination time. This last step typically involves some simplification steps, and is usually done manually in current approaches. We implement our techniques in a prototype tool and demonstrate our process on several classical examples. Some of them go beyond the capability of current semi-automatic approaches.
- Published
- 2016
- Full Text
- View/download PDF
25. Relational reasoning via probabilistic coupling
- Author
-
Barthe, Gilles, Espitau, Thomas, Grégoire, Benjamin, Hsu, Justin, Stefanesco, Léo, and Strub, Pierre-Yves
- Subjects
Computer Science - Logic in Computer Science ,Computer Science - Programming Languages - Abstract
Probabilistic coupling is a powerful tool for analyzing pairs of probabilistic processes. Roughly, coupling two processes requires finding an appropriate witness process that models both processes in the same probability space. Couplings are powerful tools proving properties about the relation between two processes, include reasoning about convergence of distributions and stochastic dominance---a probabilistic version of a monotonicity property. While the mathematical definition of coupling looks rather complex and cumbersome to manipulate, we show that the relational program logic pRHL---the logic underlying the EasyCrypt cryptographic proof assistant---already internalizes a generalization of probabilistic coupling. With this insight, constructing couplings is no harder than constructing logical proofs. We demonstrate how to express and verify classic examples of couplings in pRHL, and we mechanically verify several couplings in EasyCrypt.
- Published
- 2015
- Full Text
- View/download PDF
26. Masking the GLP Lattice-Based Signature Scheme at Any Order
- Author
-
Barthe, Gilles, primary, Belaïd, Sonia, additional, Espitau, Thomas, additional, Fouque, Pierre-Alain, additional, Grégoire, Benjamin, additional, Rossi, Mélissa, additional, and Tibouchi, Mehdi, additional
- Published
- 2023
- Full Text
- View/download PDF
27. Towards Faster Polynomial-Time Lattice Reduction
- Author
-
Kirchner, Paul, primary, Espitau, Thomas, additional, and Fouque, Pierre-Alain, additional
- Published
- 2021
- Full Text
- View/download PDF
28. Masking the GLP Lattice-Based Signature Scheme at Any Order
- Author
-
Barthe, Gilles, Belaïd, Sonia, Espitau, Thomas, Fouque, Pierre-Alain, Grégoire, Benjamin, Rossi, Mélissa, Tibouchi, Mehdi, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Nielsen, Jesper Buus, editor, and Rijmen, Vincent, editor
- Published
- 2018
- Full Text
- View/download PDF
29. LWE Without Modular Reduction and Improved Side-Channel Attacks Against BLISS
- Author
-
Bootle, Jonathan, Delaplace, Claire, Espitau, Thomas, Fouque, Pierre-Alain, Tibouchi, Mehdi, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Peyrin, Thomas, editor, and Galbraith, Steven, editor
- Published
- 2018
- Full Text
- View/download PDF
30. Fast Reduction of Algebraic Lattices over Cyclotomic Fields
- Author
-
Kirchner, Paul, primary, Espitau, Thomas, additional, and Fouque, Pierre-Alain, additional
- Published
- 2020
- Full Text
- View/download PDF
31. On a Dual/Hybrid Approach to Small Secret LWE
- Author
-
Espitau, Thomas, primary, Joux, Antoine, additional, and Kharchenko, Natalia, additional
- Published
- 2020
- Full Text
- View/download PDF
32. Loop-Abort Faults on Lattice-Based Fiat-Shamir and Hash-and-Sign Signatures
- Author
-
Espitau, Thomas, Fouque, Pierre-Alain, Gérard, Benoît, Tibouchi, Mehdi, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Avanzi, Roberto, editor, and Heys, Howard, editor
- Published
- 2017
- Full Text
- View/download PDF
33. Computing Generator in Cyclotomic Integer Rings : A Subfield Algorithm for the Principal Ideal Problem in and Application to the Cryptanalysis of a FHE Scheme
- Author
-
Biasse, Jean-François, Espitau, Thomas, Fouque, Pierre-Alain, Gélin, Alexandre, Kirchner, Paul, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Coron, Jean-Sébastien, editor, and Nielsen, Jesper Buus, editor
- Published
- 2017
- Full Text
- View/download PDF
34. Higher-Order Differential Meet-in-the-middle Preimage Attacks on SHA-1 and BLAKE
- Author
-
Espitau, Thomas, Fouque, Pierre-Alain, Karpman, Pierre, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gennaro, Rosario, editor, and Robshaw, Matthew, editor
- Published
- 2015
- Full Text
- View/download PDF
35. Masking the GLP Lattice-Based Signature Scheme at Any Order
- Author
-
Barthe, Gilles, primary, Belaïd, Sonia, additional, Espitau, Thomas, additional, Fouque, Pierre-Alain, additional, Grégoire, Benjamin, additional, Rossi, Mélissa, additional, and Tibouchi, Mehdi, additional
- Published
- 2018
- Full Text
- View/download PDF
36. An Assertion-Based Program Logic for Probabilistic Programs
- Author
-
Barthe, Gilles, primary, Espitau, Thomas, additional, Gaboardi, Marco, additional, Grégoire, Benjamin, additional, Hsu, Justin, additional, and Strub, Pierre-Yves, additional
- Published
- 2018
- Full Text
- View/download PDF
37. Synthesizing Probabilistic Invariants via Doob’s Decomposition
- Author
-
Barthe, Gilles, primary, Espitau, Thomas, additional, Ferrer Fioriti, Luis María, additional, and Hsu, Justin, additional
- Published
- 2016
- Full Text
- View/download PDF
38. Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage
- Author
-
Sun, Chao, primary, Espitau, Thomas, additional, Tibouchi, Mehdi, additional, and Abe, Masayuki, additional
- Published
- 2021
- Full Text
- View/download PDF
39. Mitaka: A simpler, parallelizable, maskable variant of Falcon
- Author
-
Espitau, Thomas, Takahashi, Akira, Tibouchi, Mehdi, and Wallet, Alexandre
- Published
- 2021
40. Relational Reasoning via Probabilistic Coupling
- Author
-
Barthe, Gilles, primary, Espitau, Thomas, additional, Grégoire, Benjamin, additional, Hsu, Justin, additional, Stefanesco, Léo, additional, and Strub, Pierre-Yves, additional
- Published
- 2015
- Full Text
- View/download PDF
41. Mitaka: Faster, Simpler, Parallelizable and Maskable Hash-and-Sign Signatures on NTRU Lattices
- Author
-
Espitau, Thomas, primary
- Published
- 2021
- Full Text
- View/download PDF
42. The nearest-colattice algorithm: Time-approximation tradeoff for approx-CVP
- Author
-
Espitau, Thomas, primary and Kirchner, Paul, additional
- Published
- 2020
- Full Text
- View/download PDF
43. Relational $\star$-Liftings for Differential Privacy
- Author
-
Barthe, Gilles, Espitau, Thomas, Hsu, Justin, Sato, Tetsuya, and Strub, Pierre-Yves
- Subjects
FOS: Computer and information sciences ,Computer Science - Logic in Computer Science ,Computer Science - Programming Languages ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,Logic in Computer Science (cs.LO) ,Programming Languages (cs.PL) - Abstract
Recent developments in formal verification have identified approximate liftings (also known as approximate couplings) as a clean, compositional abstraction for proving differential privacy. This construction can be defined in two styles. Earlier definitions require the existence of one or more witness distributions, while a recent definition by Sato uses universal quantification over all sets of samples. These notions have each have their own strengths: the universal version is more general than the existential ones, while existential liftings are known to satisfy more precise composition principles. We propose a novel, existential version of approximate lifting, called $\star$-lifting, and show that it is equivalent to Sato's construction for discrete probability measures. Our work unifies all known notions of approximate lifting, yielding cleaner properties, more general constructions, and more precise composition theorems for both styles of lifting, enabling richer proofs of differential privacy. We also clarify the relation between existing definitions of approximate lifting, and consider more general approximate liftings based on $f$-divergences.
- Published
- 2019
44. Relational ���-Liftings for Differential Privacy
- Author
-
Barthe, Gilles, Espitau, Thomas, Hsu, Justin, Sato, Tetsuya, and Strub, Pierre-Yves
- Subjects
Computer Science - Logic in Computer Science ,Computer Science - Programming Languages ,010201 computation theory & mathematics ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,0202 electrical engineering, electronic engineering, information engineering ,020207 software engineering ,0102 computer and information sciences ,02 engineering and technology ,16. Peace & justice ,01 natural sciences - Abstract
Recent developments in formal verification have identified approximate liftings (also known as approximate couplings) as a clean, compositional abstraction for proving differential privacy. This construction can be defined in two styles. Earlier definitions require the existence of one or more witness distributions, while a recent definition by Sato uses universal quantification over all sets of samples. These notions have each have their own strengths: the universal version is more general than the existential ones, while existential liftings are known to satisfy more precise composition principles. We propose a novel, existential version of approximate lifting, called ⋆-lifting, and show that it is equivalent to Sato's construction for discrete probability measures. Our work unifies all known notions of approximate lifting, yielding cleaner properties, more general constructions, and more precise composition theorems for both styles of lifting, enabling richer proofs of differential privacy. We also clarify the relation between existing definitions of approximate lifting, and consider more general approximate liftings based on f-divergences.
- Published
- 2019
- Full Text
- View/download PDF
45. GALACTICS
- Author
-
Barthe, Gilles, primary, Belaïd, Sonia, additional, Espitau, Thomas, additional, Fouque, Pierre-Alain, additional, Rossi, Mélissa, additional, and Tibouchi, Mehdi, additional
- Published
- 2019
- Full Text
- View/download PDF
46. Side-Channel Attacks on BLISS Lattice-Based Signatures
- Author
-
Espitau, Thomas, Fouque, Pierre-Alain, Gérard, Benoît, Tibouchi, Mehdi, ALgorithms for coMmunicAtion SecuriTY (ALMASTY), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), EMbedded SEcurity and Cryptography (EMSEC), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), DGA Maîtrise de l'information (DGA.MI), Direction générale de l'Armement (DGA), NTT Secure Platform Laboratories [Tokyo], Nippon Telegraph & Telephone Corporation - NTT, ANR-15-CE39-0002,ARRAND,Arithmétiques Randomisées(2015), European Project: 644209,H2020,H2020-ICT-2014-1,HEAT(2015), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)
- Subjects
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] ,number theory ,lattices ,EMA ,BLISS ,side-channel analysis ,digital signatures ,branch tracing ,postquantum cryptogra- phy - Abstract
International audience; In this paper, we investigate the security of the BLISS lattice-based signature scheme, one of the most promising candidates for post-quantum-secure signatures, against side-channel attacks. Several works have been devoted to its efficient implementation on various platforms, from desktop CPUs to microcontrollers and FPGAs, and more recent papers have also considered its security against certain types of physical attacks, notably fault injection and cache attacks. We turn to more traditional side-channel analysis, and describe several attacks that can yield a full key recovery. We first identify a serious source of leakage in the rejection sampling algorithm used during signature generation. Existing implementations of that rejection sampling step, which is essential for security, actually leak the " relative norm " of the secret key. We show how an extension of an algorithm due to Howgrave-Graham and Szydlo can be used to recover the key from that relative norm, at least when the absolute norm is easy to factor (which happens for a significant fraction of secret keys). We describe how this leakage can be exploited in practice both on an embedded device (an 8-bit AVR microcontroller) using electromagnetic analysis (EMA), and a desktop computer (recent Intel CPU running Linux) using branch tracing. The latter attack has been mounted against the open source VPN software strongSwan. We also show that other parts of the BLISS signing algorithm can leak secrets not just for a subset of secret keys, but for 100% of them. The BLISS Gaussian sampling algorithm in strongSwan is intrinsically variable time. This would be hard to exploit using a noisy source of leakage like EMA, but branch tracing allows to recover the entire randomness and hence the key: we show that a single execution of the strongSwan signature algorithm is actually sufficient for full key recovery. We also describe a more traditional side-channel attack on the sparse polynomial multiplications carried out in BLISS: classically, multiplications can be attacked using Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only. DPA; however, our target 8-bit AVR target implementation uses repeated shifted additions instead. Surprisingly, we manage to obtain a full key recovery in that setting using integer linear programming from a single EMA trace.
- Published
- 2017
47. Liftings for Differential Privacy
- Author
-
Barthe, Gilles, Espitau, Thomas, Hsu, Justin, Sato, Tetsuya, Strub, Pierre-Yves, Institute IMDEA Software [Madrid], ALgorithms for coMmunicAtion SecuriTY (ALMASTY), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), University of Pennsylvania, Research Institute for Mathematical Sciences, Kyoto University, Japan, and University of Pennsylvania [Philadelphia]
- Subjects
[INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL] ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] ,Differential Privacy ,Formal Verification ,Probabilistic Couplings - Abstract
International audience; Recent developments in formal verification have identified approximate liftings (also known as approximate couplings) as a clean, compositional abstraction for proving differential privacy. There are two styles of definitions for this construction. Earlier definitions require the existence of one or more witness distributions, while a recent definition by Sato uses universal quantification over all sets of samples. These notions have different strengths and weaknesses: the universal version is more general than the existential ones, but the existential versions enjoy more precise composition principles. We propose a novel, existential version of approximate lifting, called-lifting, and show that it is equivalent to Sato's construction for discrete probability measures. Our work unifies all known notions of approximate lifting, giving cleaner properties, more general constructions, and more precise composition theorems for both styles of lifting, enabling richer proofs of differential privacy. We also clarify the relation between existing definitions of approximate lifting, and generalize our constructions to approximate liftings based on f-divergences.
- Published
- 2017
48. A Subfield Algorithm for the Principal Ideal Problem in $$L_{|\varDelta _\mathbb {K}|}\left( \frac{1}{2}\right) $$ and Application to the Cryptanalysis of a FHE Scheme
- Author
-
Biasse, Jean-François, Espitau, Thomas, Fouque, Pierre-Alain, Gélin, Alexandre, Kirchner, Paul, University of South Florida [Tampa] (USF), ALgorithms for coMmunicAtion SecuriTY (ALMASTY), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), EMbedded SEcurity and Cryptography (EMSEC), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), and École normale supérieure - Paris (ENS-PSL)
- Subjects
[INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] - Abstract
International audience; The Principal Ideal Problem (resp. Short Principal Ideal Problem), shorten as PIP (resp. SPIP), consists in finding a generator (resp. short generator) of a principal ideal in the ring of integers of a number field. Several lattice-based cryptosystems rely on the presumed hardness of these two problems. In practice, most of them do not use an arbitrary number field but a power-of-two cyclotomic field. The Smart and Vercauteren fully homomorphic encryption scheme and the multilinear map of Garg, Gentry, and Halevi epitomize this common restriction. Recently, Cramer, Ducas, Peikert, and Regev showed that solving the SPIP in such cyclotomic rings boiled down to solving the PIP. In this paper, we present a heuristic algorithm that solves the PIP in prime-power cyclotomic fields in subexponential time L(1/2), where ∆ K denotes the discriminant of the number field. This is achieved by descending to its totally real subfield. The implementation of our algorithm allows to recover in practice the secret key of the Smart and Vercauteren scheme, for the smallest proposed parameters (in dimension 256).
- Published
- 2017
49. Certified lattice reduction.
- Author
-
Espitau, Thomas and Joux, Antoine
- Subjects
ALGEBRAIC number theory ,QUADRATIC forms ,FLOATING-point arithmetic ,INTERVAL analysis ,NUMBER theory ,ORTHOGONALIZATION - Abstract
Quadratic form reduction and lattice reduction are fundamental tools in computational number theory and in computer science, especially in cryptography. The celebrated Lenstra–Lenstra–Lovász reduction algorithm (so-called LLL) has been improved in many ways through the past decades and remains one of the central methods used for reducing integral lattice basis. In particular, its floating-point variants---where the rational arithmetic required by Gram–Schmidt orthogonalization is replaced by floating-point arithmetic---are now the fastest known. However, the systematic study of the reduction theory of real quadratic forms or, more generally, of real lattices is not widely represented in the literature. When the problem arises, the lattice is usually replaced by an integral approximation of (a multiple of) the original lattice, which is then reduced. While practically useful and proven in some special cases, this method doesn't offer any guarantee of success in general. In this work, we present an adaptive-precision version of a generalized LLL algorithm that covers this case in all generality. In particular, we replace floating-point arithmetic by Interval Arithmetic to certify the behavior of the algorithm. We conclude by giving a typical application of the result in algebraic number theory for the reduction of ideal lattices in number fields. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
50. Loop-Abort Faults on Lattice-Based Signatures and Key Exchange Protocols
- Author
-
Espitau, Thomas, primary, Fouque, Pierre-Alain, additional, Gerard, Benoit, additional, and Tibouchi, Mehdi, additional
- Published
- 2018
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.