Search

Your search keyword '"Vergnaud, Damien"' showing total 344 results
Start Over Author "Vergnaud, Damien"

Refine your results

more »

more »

more »

more »
344 results on '"Vergnaud, Damien"'

1. Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions

Author

Bouaziz--Ermann, Samuel, Grilo, Alex B., Vergnaud, Damien, and Vu, Quoc-Huy

Subjects
Quantum Physics, Computer Science - Cryptography and Security
Abstract

There has been a recent interest in proposing quantum protocols whose security relies on weaker computational assumptions than their classical counterparts. Importantly to our work, it has been recently shown that public-key encryption (PKE) from one-way functions (OWF) is possible if we consider quantum public keys. Notice that we do not expect classical PKE from OWF given the impossibility results of Impagliazzo and Rudich (STOC'89). However, the distribution of quantum public keys is a challenging task. Therefore, the main question that motivates our work is if quantum PKE from OWF is possible if we have classical public keys. Such protocols are impossible if ciphertexts are also classical, given the impossibility result of Austrin et al. (CRYPTO'22) of quantum enhanced key-agreement (KA) with classical communication. In this paper, we focus on black-box separation for PKE with classical public key and quantum ciphertext from OWF under the polynomial compatibility conjecture, first introduced in Austrin et al.. More precisely, we show the separation when the decryption algorithm of the PKE does not query the OWF. We prove our result by extending the techniques of Austrin et al. and we show an attack for KA in an extended classical communication model where the last message in the protocol can be a quantum state.

Published
2023

2. Quantum security of subset cover problems

Author

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

Subjects
Quantum Physics, Computer Science - Cryptography and Security
Abstract

The subset cover problem for $k \geq 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+, $\dots$). 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 $\Omega\left((k+1)^{-\frac{2^{k}}{2^{k+1}-1}}\cdot N^{\frac{2^{k}-1}{2^{k+1}-1}}\right)$ 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 \geq 1$). We prove that a generic quantum algorithm needs to make $\Omega\left(N^{k/5}\right)$ 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\left(N^{k/(2+2r)}\right)$ queries to the $k$ hash functions.

Published
2022

4. Commitments with Efficient Zero-Knowledge Arguments from Subset Sum Problems

Author

Maire, Jules, Vergnaud, Damien, 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, Tsudik, Gene, editor, Conti, Mauro, editor, Liang, Kaitai, editor, and Smaragdakis, Georgios, editor

Published
2024
Full Text
View/download PDF

7. Dynamic Random Probing Expansion with Quasi Linear Asymptotic Complexity

Author

Belaïd, Sonia, Rivain, Matthieu, Taleb, Abdul Rahman, Vergnaud, Damien, 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, Tibouchi, Mehdi, editor, and Wang, Huaxiong, editor

Published
2021
Full Text
View/download PDF

8. The Key-Dependent Message Security of Key-Alternating Feistel Ciphers

Author

Farshim, Pooya, Khati, Louiza, Seurin, Yannick, Vergnaud, Damien, 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, and Paterson, Kenneth G., editor

Published
2021
Full Text
View/download PDF

12. Succinct Diophantine-Satisfiability Arguments

Author

Towa, Patrick, Vergnaud, Damien, 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, Moriai, Shiho, editor, and Wang, Huaxiong, editor

Published
2020
Full Text
View/download PDF

13. Public-Key Generation with Verifiable Randomness

Author

Blazy, Olivier, Towa, Patrick, Vergnaud, Damien, 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, Moriai, Shiho, editor, and Wang, Huaxiong, editor

Published
2020
Full Text
View/download PDF

18. Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND

Author

Kushilevitz, Eyal, Ostrovsky, Rafail, Prouff, Emmanuel, Rosén, Adi, Thillard, Adrian, Vergnaud, Damien, 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, Hofheinz, Dennis, editor, and Rosen, Alon, editor

Published
2019
Full Text
View/download PDF

19. Secure Outsourcing in Discrete-Logarithm-Based and Pairing-Based Cryptography (Invited Talk)

Author

Vergnaud, Damien, Hutchison, David, Editorial Board Member, Kanade, Takeo, Editorial Board Member, Kittler, Josef, Editorial Board Member, Kleinberg, Jon M., Editorial Board Member, Mattern, Friedemann, Editorial Board Member, Mitchell, John C., Editorial Board Member, Naor, Moni, Editorial Board Member, Pandu Rangan, C., Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Terzopoulos, Demetri, Editorial Board Member, Tygar, Doug, Editorial Board Member, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Blazy, Olivier, editor, and Yeun, Chan Yeob, editor

Published
2019
Full Text
View/download PDF

20. Analysis and Improvement of an Authentication Scheme in Incremental Cryptography

Author

Khati, Louiza, Vergnaud, Damien, 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, Cid, Carlos, editor, and Jacobson Jr., Michael J., editor

Published
2019
Full Text
View/download PDF

22. Towards Black-Box Accountable Authority IBE with Short Ciphertexts and Private Keys

Author

Libert, Benoît and Vergnaud, Damien

Subjects
Computer Science - Cryptography and Security
Abstract

At Crypto'07, Goyal introduced the concept of Accountable Authority Identity-Based Encryption as a convenient tool to reduce the amount of trust in authorities in Identity-Based Encryption. In this model, if the Private Key Generator (PKG) maliciously re-distributes users' decryption keys, it runs the risk of being caught and prosecuted. Goyal proposed two constructions: the first one is efficient but can only trace well-formed decryption keys to their source; the second one allows tracing obfuscated decryption boxes in a model (called weak black-box model) where cheating authorities have no decryption oracle. The latter scheme is unfortunately far less efficient in terms of decryption cost and ciphertext size. In this work, we propose a new construction that combines the efficiency of Goyal's first proposal with a very simple weak black-box tracing mechanism. Our scheme is described in the selective-ID model but readily extends to meet all security properties in the adaptive-ID sense, which is not known to be true for prior black-box schemes., Comment: 32 pages

Published
2008

23. Multi-Use Unidirectional Proxy Re-Signatures

Author

Libert, Benoît and Vergnaud, Damien

Subjects
Computer Science - Cryptography and Security, D.4.6
Abstract

In 1998, Blaze, Bleumer, and Strauss suggested a cryptographic primitive named proxy re-signatures where a proxy turns a signature computed under Alice's secret key into one from Bob on the same message. The semi-trusted proxy does not learn either party's signing key and cannot sign arbitrary messages on behalf of Alice or Bob. At CCS 2005, Ateniese and Hohenberger revisited the primitive by providing appropriate security definitions and efficient constructions in the random oracle model. Nonetheless, they left open the problem of designing a multi-use unidirectional scheme where the proxy is able to translate in only one direction and signatures can be re-translated several times. This paper solves this problem, suggested for the first time 10 years ago, and shows the first multi-hop unidirectional proxy re-signature schemes. We describe a random-oracle-using system that is secure in the Ateniese-Hohenberger model. The same technique also yields a similar construction in the standard model (i.e. without relying on random oracles). Both schemes are efficient and require newly defined -- but falsifiable -- Diffie-Hellman-like assumptions in bilinear groups., Comment: 16 pages

Published
2008

24. New Extensions of Pairing-based Signatures into Universal (Multi) Designated Verifier Signatures

Author

Vergnaud, Damien

Subjects
Computer Science - Cryptography and Security, D.4.6
Abstract

The concept of universal designated verifier signatures was introduced by Steinfeld, Bull, Wang and Pieprzyk at Asiacrypt 2003. These signatures can be used as standard publicly verifiable digital signatures but have an additional functionality which allows any holder of a signature to designate the signature to any desired verifier. This designated verifier can check that the message was indeed signed, but is unable to convince anyone else of this fact. We propose new efficient constructions for pairing-based short signatures. Our first scheme is based on Boneh-Boyen signatures and its security can be analyzed in the standard security model. We prove its resistance to forgery assuming the hardness of the so-called strong Diffie-Hellman problem, under the knowledge-of-exponent assumption. The second scheme is compatible with the Boneh-Lynn-Shacham signatures and is proven unforgeable, in the random oracle model, under the assumption that the computational bilinear Diffie-Hellman problem is untractable. Both schemes are designed for devices with constrained computation capabilities since the signing and the designation procedure are pairing-free. Finally, we present extensions of these schemes in the multi-user setting proposed by Desmedt in 2003., Comment: 23 pages

Published
2008

25. Lattice Attacks on Pairing-Based Signatures

Author

Mefenza, Thierry, Vergnaud, Damien, 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, and O'Neill, Máire, editor

Published
2017
Full Text
View/download PDF

26. Lattice Attacks Against Elliptic-Curve Signatures with Blinded Scalar Multiplication

Author

Goudarzi, Dahmun, Rivain, Matthieu, Vergnaud, Damien, 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

27. Security of Pseudo-Random Number Generators with Input : (Invited Talk)

Author

Vergnaud, Damien, 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, Farshim, Pooya, editor, and Simion, Emil, editor

Published
2017
Full Text
View/download PDF

28. Generalized Polynomial Decomposition for S-boxes with Application to Side-Channel Countermeasures

Author

Goudarzi, Dahmun, Rivain, Matthieu, Vergnaud, Damien, Vivek, Srinivas, 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, Fischer, Wieland, editor, and Homma, Naofumi, editor

Published
2017
Full Text
View/download PDF

29. Reusing Nonces in Schnorr Signatures : (and Keeping It Secure...)

Author

Beunardeau, Marc, Connolly, Aisling, Ferradi, Houda, Géraud, Rémi, Naccache, David, Vergnaud, Damien, 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, Foley, Simon N., editor, Gollmann, Dieter, editor, and Snekkenes, Einar, editor

Published
2017
Full Text
View/download PDF

30. Private Multiplication over Finite Fields

Author

Belaïd, Sonia, Benhamouda, Fabrice, Passelègue, Alain, Prouff, Emmanuel, Thillard, Adrian, Vergnaud, Damien, 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, Katz, Jonathan, editor, and Shacham, Hovav, editor

Published
2017
Full Text
View/download PDF

31. Full Disk Encryption: Bridging Theory and Practice

Author

Khati, Louiza, Mouha, Nicky, Vergnaud, Damien, 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, and Handschuh, Helena, editor

Published
2017
Full Text
View/download PDF

36. Lattice attacks on pairing-based signatures.

Author

Mefenza, Thierry and Vergnaud, Damien

Subjects
*EXPONENTIATION, *ELLIPTIC curves, *PUBLIC key cryptography, *CRYPTOSYSTEMS, *HEURISTIC algorithms, *CRYPTOGRAPHY, *MULTIPLICATION
Abstract

Practical implementations of cryptosystems often suffer from critical information leakage through side-channels (such as their power consumption or their electromagnetic emanations). For public-key cryptography on embedded systems, the core operation is usually group exponentiation – or scalar multiplication on elliptic curves – which is a sequence of group operations derived from the private-key that may reveal secret bits to an attacker (on an unprotected implementation). We present lattice-based polynomial-time (heuristic) algorithms that recover the signer's secret in popular pairing-based signatures when used to sign several messages under the assumption that blocks of consecutive bits of the corresponding exponents are known by the attacker. Our techniques rely upon Coppersmith's method and apply to many signatures in the so-called exponent-inversion framework in the standard security model (i.e. Boneh-Boyen, Gentry and Pontcheval-Sanders signatures) as well as in the random oracle model (i.e. Sakai-Kasahara signatures). [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

37. Randomness Complexity of Private Circuits for Multiplication

Author

Belaïd, Sonia, Benhamouda, Fabrice, Passelègue, Alain, Prouff, Emmanuel, Thillard, Adrian, Vergnaud, Damien, 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, Fischlin, Marc, editor, and Coron, Jean-Sébastien, editor

Published
2016
Full Text
View/download PDF

38. Easing Coppersmith Methods Using Analytic Combinatorics: Applications to Public-Key Cryptography with Weak Pseudorandomness

Author

Benhamouda, Fabrice, Chevalier, Céline, Thillard, Adrian, Vergnaud, Damien, 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, Cheng, Chen-Mou, editor, Chung, Kai-Min, editor, Persiano, Giuseppe, editor, and Yang, Bo-Yin, editor

Published
2016
Full Text
View/download PDF

39. Privately Outsourcing Exponentiation to a Single Server: Cryptanalysis and Optimal Constructions

Author

Chevalier, Céline, Laguillaumie, Fabien, Vergnaud, Damien, 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, Askoxylakis, Ioannis, editor, Ioannidis, Sotiris, editor, Katsikas, Sokratis, editor, and Meadows, Catherine, editor

Published
2016
Full Text
View/download PDF

40. Mitigating Server Breaches in Password-Based Authentication: Secure and Efficient Solutions

Author

Blazy, Olivier, Chevalier, Céline, Vergnaud, Damien, 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, and Sako, Kazue, editor

Published
2016
Full Text
View/download PDF

41. Distribution and Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function

Author

Mefenza, Thierry, Vergnaud, Damien, 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, Duquesne, Sylvain, editor, and Petkova-Nikova, Svetla, editor

Published
2016
Full Text
View/download PDF

43. Practical Key Recovery for Discrete-Logarithm Based Authentication Schemes from Random Nonce Bits

Author

Bauer, Aurélie, Vergnaud, Damien, 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, Güneysu, Tim, editor, and Handschuh, Helena, editor

Published
2015
Full Text
View/download PDF

44. Robust Pseudo-Random Number Generators with Input Secure Against Side-Channel Attacks

Author

Abdalla, Michel, Belaïd, Sonia, Pointcheval, David, Ruhault, Sylvain, Vergnaud, Damien, 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, Malkin, Tal, editor, Kolesnikov, Vladimir, editor, Lewko, Allison Bishop, editor, and Polychronakis, Michalis, editor

Published
2015
Full Text
View/download PDF

45. Algorithms for Outsourcing Pairing Computation

Author

Guillevic, Aurore, Vergnaud, Damien, 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, Joye, Marc, editor, and Moradi, Amir, editor

Published
2015
Full Text
View/download PDF

46. Non-Interactive Zero-Knowledge Proofs of Non-Membership

Author

Blazy, Olivier, Chevalier, Céline, Vergnaud, Damien, 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, and Nyberg, Kaisa, editor

Published
2015
Full Text
View/download PDF

50. Quantum Security of Subset Cover Problems

Author

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

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.

Published
2023
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results