Search Results

Documents authored by Vergnaud, Damien

Document
DOI: 10.4230/LIPIcs.ITC.2024.11
Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations

Authors: Pascal Giorgi, Fabien Laguillaumie, Lucas Ottow, and Damien Vergnaud

Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)

Abstract
Secure multi-party computation aims to allow a set of players to compute a given function on their secret inputs without revealing any other information than the result of the computation. In this work, we focus on the design of secure multi-party protocols for shared polynomial operations. We consider the classical model where the adversary is honest-but-curious, and where the coefficients (or any secret values) are either encrypted using an additively homomorphic encryption scheme or shared using a threshold linear secret-sharing scheme. Our protocols terminate after a constant number of rounds and minimize the number of secure multiplications. In their seminal article at PKC 2006, Mohassel and Franklin proposed constant-rounds protocols for the main operations on (shared) polynomials. In this work, we improve the fan-in multiplication of nonzero polynomials, the multi-point polynomial evaluation and the polynomial interpolation (on secret points) to reach a quasi-linear complexity (instead of quadratic in Mohassel and Franklin’s work) in the degree of shared input/output polynomials. Computing with shared polynomials is a core component of several multi-party protocols for privacy-preserving operations on private sets, like the private disjointness test or the private set intersection. Using our new protocols, we are able to improve the complexity of such protocols and to design the first variants which always return a correct result.
Cite as

Pascal Giorgi, Fabien Laguillaumie, Lucas Ottow, and Damien Vergnaud. Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 11:1-11:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{giorgi_et_al:LIPIcs.ITC.2024.11,
  author =	{Giorgi, Pascal and Laguillaumie, Fabien and Ottow, Lucas and Vergnaud, Damien},
  title =	{{Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{11:1--11:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-333-1},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{304},
  editor =	{Aggarwal, Divesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.11},
  URN =		{urn:nbn:de:0030-drops-205194},
  doi =		{10.4230/LIPIcs.ITC.2024.11},
  annote =	{Keywords: Multi-party computation, polynomial operations, privacy-preserving set operations}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.23
Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator

Authors: Charles Bouillaguet, Florette Martinez, and Damien Vergnaud

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We present attacks on a generalized subset-sum pseudorandom generator, which was proposed by von zur Gathen and Shparlinski in 2004. Our attacks rely on a sub-quadratic algorithm for solving a vectorial variant of the 3SUM problem, which is of independent interest. The attacks presented have complexities well below the brute-force attack, making the generators vulnerable. We provide a thorough analysis of the attacks and their complexities and demonstrate their practicality through implementations and experiments.
Cite as

Charles Bouillaguet, Florette Martinez, and Damien Vergnaud. Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bouillaguet_et_al:LIPIcs.MFCS.2023.23,
  author =	{Bouillaguet, Charles and Martinez, Florette and Vergnaud, Damien},
  title =	{{Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.23},
  URN =		{urn:nbn:de:0030-drops-185579},
  doi =		{10.4230/LIPIcs.MFCS.2023.23},
  annote =	{Keywords: Cryptography, pseudo-random generator, subset-sum problem, 3SUM problem, cryptanalysis}
}
Document
DOI: 10.4230/LIPIcs.ITC.2023.9
Quantum Security of Subset Cover Problems

Authors: Samuel Bouaziz-Ermann, Alex B. Grilo, and Damien Vergnaud

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)

Abstract
The subset cover problem for k ≥ 1 hash functions, which can be seen as an extension of the collision problem, was introduced in 2002 by Reyzin and Reyzin to analyse the security of their hash-function based signature scheme HORS. The security of many hash-based signature schemes relies on this problem or a variant of this problem (e.g. HORS, SPHINCS, SPHINCS+, ...). Recently, Yuan, Tibouchi and Abe (2022) introduced a variant to the subset cover problem, called restricted subset cover, and proposed a quantum algorithm for this problem. In this work, we prove that any quantum algorithm needs to make Ω((k+1)^{-(2^k)/(2^{k+1}-1})⋅ N^{(2^{k}-1})/(2^{k+1}-1)}) queries to the underlying hash functions with codomain size N to solve the restricted subset cover problem, which essentially matches the query complexity of the algorithm proposed by Yuan, Tibouchi and Abe. We also analyze the security of the general (r,k)-subset cover problem, which is the underlying problem that implies the unforgeability of HORS under a r-chosen message attack (for r ≥ 1). We prove that a generic quantum algorithm needs to make Ω(N^{k/5}) queries to the underlying hash functions to find a (1,k)-subset cover. We also propose a quantum algorithm that finds a (r,k)-subset cover making O (N^{k/(2+2r)}) queries to the k hash functions.
Cite as

Samuel Bouaziz-Ermann, Alex B. Grilo, and Damien Vergnaud. Quantum Security of Subset Cover Problems. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bouazizermann_et_al:LIPIcs.ITC.2023.9,
  author =	{Bouaziz-Ermann, Samuel and Grilo, Alex B. and Vergnaud, Damien},
  title =	{{Quantum Security of Subset Cover Problems}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.9},
  URN =		{urn:nbn:de:0030-drops-183378},
  doi =		{10.4230/LIPIcs.ITC.2023.9},
  annote =	{Keywords: Cryptography, Random oracle model, Quantum information}
}
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 About DROPS Imprint Privacy Contact