6 Search Results for "Grilo, Alex B."


Document
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-dev.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}
}
Document
StoqMA Meets Distribution Testing

Authors: Yupan Liu

Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)


Abstract
StoqMA captures the computational hardness of approximating the ground energy of local Hamiltonians that do not suffer the so-called sign problem. We provide a novel connection between StoqMA and distribution testing via reversible circuits. First, we prove that easy-witness StoqMA (viz. eStoqMA, a sub-class of StoqMA) is contained in MA. Easy witness is a generalization of a subset state such that the associated set’s membership can be efficiently verifiable, and all non-zero coordinates are not necessarily uniform. This sub-class eStoqMA contains StoqMA with perfect completeness (StoqMA₁), which further signifies a simplified proof for StoqMA₁ ⊆ MA [Bravyi et al., 2006; Bravyi and Terhal, 2010]. Second, by showing distinguishing reversible circuits with ancillary random bits is StoqMA-complete (as a comparison, distinguishing quantum circuits is QMA-complete [Janzing et al., 2005]), we construct soundness error reduction of StoqMA. Additionally, we show that both variants of StoqMA that without any ancillary random bit and with perfect soundness are contained in NP. Our results make a step towards collapsing the hierarchy MA ⊆ StoqMA ⊆ SBP [Bravyi et al., 2006], in which all classes are contained in AM and collapse to NP under derandomization assumptions.

Cite as

Yupan Liu. StoqMA Meets Distribution Testing. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.TQC.2021.4,
  author =	{Liu, Yupan},
  title =	{{StoqMA Meets Distribution Testing}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.4},
  URN =		{urn:nbn:de:0030-drops-139995},
  doi =		{10.4230/LIPIcs.TQC.2021.4},
  annote =	{Keywords: StoqMA, distribution testing, error reduction, reversible circuits}
}
Document
Two Combinatorial MA-Complete Problems

Authors: Dorit Aharonov and Alex B. Grilo

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


Abstract
Despite the interest in the complexity class MA, the randomized analog of NP, there are just a few known natural (promise-)MA-complete problems. The first such problem was found by Bravyi and Terhal (SIAM Journal of Computing 2009); this result was then followed by Crosson, Bacon and Brown (PRE 2010) and then by Bravyi (Quantum Information and Computation 2015). Surprisingly, each of these problems is either from or inspired by quantum computation. This fact makes it hard for classical complexity theorists to study these problems, and prevents potential progress, e.g., on the important question of derandomizing MA. In this note we define two new natural combinatorial problems and we prove their MA-completeness. The first problem, that we call approximately-clean approximate-connected-component (ACAC), gets as input a succinctly described graph, some of whose vertices are marked. The problem is to decide whether there is a connected component whose vertices are all unmarked, or the graph is far from having this property. The second problem, called SetCSP, generalizes in a novel way the standard constraint satisfaction problem (CSP) into constraints involving sets of strings. Technically, our proof that SetCSP is MA-complete is a fleshing out of an observation made in (Aharonov and Grilo, FOCS 2019), where it was noted that a restricted case of Bravyi and Terhal’s MA complete problem (namely, the uniform case) is already MA complete; and, moreover, that this restricted case can be stated using classical, combinatorial language. The fact that the first, arguably more natural, problem of ACAC is MA-hard follows quite naturally from this proof as well; while containment of ACAC in MA is simple, based on the theory of random walks. We notice that this work, along with a translation of the main result of Aharonov and Grilo to the SetCSP problem, implies that finding a gap-amplification procedure for SetCSP (in the spirit of the gap-amplification procedure introduced in Dinur’s PCP proof) would imply MA=NP. In fact, the problem of finding gap-amplification for SetCSP is equivalent to the MA=NP problem. This provides an alternative new path towards the major problem of derandomizing MA. Deriving a similar statement regarding gap amplification of a natural restriction of $ACAC$ remains an open question.

Cite as

Dorit Aharonov and Alex B. Grilo. Two Combinatorial MA-Complete Problems. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{aharonov_et_al:LIPIcs.ITCS.2021.36,
  author =	{Aharonov, Dorit and Grilo, Alex B.},
  title =	{{Two Combinatorial MA-Complete Problems}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.36},
  URN =		{urn:nbn:de:0030-drops-135754},
  doi =		{10.4230/LIPIcs.ITCS.2021.36},
  annote =	{Keywords: Merlin-Arthur proof systems, Constraint sastifation problem, Random walks}
}
Document
Span Programs and Quantum Space Complexity

Authors: Stacey Jeffery

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)


Abstract
While quantum computers hold the promise of significant computational speedups, the limited size of early quantum machines motivates the study of space-bounded quantum computation. We relate the quantum space complexity of computing a function f with one-sided error to the logarithm of its span program size, a classical quantity that is well-studied in attempts to prove formula size lower bounds. In the more natural bounded error model, we show that the amount of space needed for a unitary quantum algorithm to compute f with bounded (two-sided) error is lower bounded by the logarithm of its approximate span program size. Approximate span programs were introduced in the field of quantum algorithms but not studied classically. However, the approximate span program size of a function is a natural generalization of its span program size. While no non-trivial lower bound is known on the span program size (or approximate span program size) of any concrete function, a number of lower bounds are known on the monotone span program size. We show that the approximate monotone span program size of f is a lower bound on the space needed by quantum algorithms of a particular form, called monotone phase estimation algorithms, to compute f. We then give the first non-trivial lower bound on the approximate span program size of an explicit function.

Cite as

Stacey Jeffery. Span Programs and Quantum Space Complexity. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 4:1-4:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{jeffery:LIPIcs.ITCS.2020.4,
  author =	{Jeffery, Stacey},
  title =	{{Span Programs and Quantum Space Complexity}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{4:1--4:37},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.4},
  URN =		{urn:nbn:de:0030-drops-116896},
  doi =		{10.4230/LIPIcs.ITCS.2020.4},
  annote =	{Keywords: Quantum space complexity, span programs}
}
Document
Track A: Algorithms, Complexity and Games
A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round

Authors: Alex B. Grilo

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


Abstract
The importance of being able to verify quantum computation delegated to remote servers increases with recent development of quantum technologies. In some of the proposed protocols for this task, a client delegates her quantum computation to non-communicating servers in multiple rounds of communication. In this work, we propose the first protocol where the client delegates her quantum computation to two servers in one-round of communication. Another advantage of our protocol is that it is conceptually simpler than previous protocols. The parameters of our protocol also make it possible to prove security even if the servers are allowed to communicate, but respecting the plausible assumption that information cannot be propagated faster than speed of light, making it the first relativistic protocol for quantum computation.

Cite as

Alex B. Grilo. A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{grilo:LIPIcs.ICALP.2019.28,
  author =	{Grilo, Alex B.},
  title =	{{A Simple Protocol for Verifiable Delegation of Quantum Computation in One Round}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{28:1--28:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.28},
  URN =		{urn:nbn:de:0030-drops-106044},
  doi =		{10.4230/LIPIcs.ICALP.2019.28},
  annote =	{Keywords: quantum computation, quantum cryptography, delegation of quantum computation}
}
Document
Pointer Quantum PCPs and Multi-Prover Games

Authors: Alex B. Grilo, Iordanis Kerenidis, and Attila Pereszlényi

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
The quantum PCP (QPCP) conjecture states that all problems in QMA, the quantum analogue of NP, admit quantum verifiers that only act on a constant number of qubits of a polynomial size quantum proof and have a constant gap between completeness and soundness. Despite an impressive body of work trying to prove or disprove the quantum PCP conjecture, it still remains widely open. The above-mentioned proof verification statement has also been shown equivalent to the QMA-completeness of the Local Hamiltonian problem with constant relative gap. Nevertheless, unlike in the classical case, no equivalent formulation in the language of multi-prover games is known. In this work, we propose a new type of quantum proof systems, the Pointer QPCP, where a verifier first accesses a classical proof that he can use as a pointer to which qubits from the quantum part of the proof to access. We define the Pointer QPCP conjecture, that states that all problems in QMA admit quantum verifiers that first access a logarithmic number of bits from the classical part of a polynomial size proof, then act on a constant number of qubits from the quantum part of the proof, and have a constant gap between completeness and soundness. We define a new QMA-complete problem, the Set Local Hamiltonian problem, and a new restricted class of quantum multi-prover games, called CRESP games. We use them to provide two other equivalent statements to the Pointer QPCP conjecture: the Set Local Hamiltonian problem with constant relative gap is QMA-complete; and the approximation of the maximum acceptance probability of CRESP games up to a constant additive factor is as hard as QMA. Our new conjecture is weaker than the original QPCP conjecture and hence provides a natural intermediate step towards proving the quantum PCP theorem. Furthermore, this is the first equivalence between a quantum PCP statement and the inapproximability of quantum multi-prover games.

Cite as

Alex B. Grilo, Iordanis Kerenidis, and Attila Pereszlényi. Pointer Quantum PCPs and Multi-Prover Games. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{grilo_et_al:LIPIcs.MFCS.2016.21,
  author =	{Grilo, Alex B. and Kerenidis, Iordanis and Pereszl\'{e}nyi, Attila},
  title =	{{Pointer Quantum PCPs and Multi-Prover Games}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.21},
  URN =		{urn:nbn:de:0030-drops-64364},
  doi =		{10.4230/LIPIcs.MFCS.2016.21},
  annote =	{Keywords: computational complexity, quantum computation, PCP theorem}
}
  • Refine by Author
  • 4 Grilo, Alex B.
  • 1 Aharonov, Dorit
  • 1 Bouaziz-Ermann, Samuel
  • 1 Jeffery, Stacey
  • 1 Kerenidis, Iordanis
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Quantum complexity theory
  • 1 Hardware → Quantum communication and cryptography
  • 1 Security and privacy → Cryptography
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Quantum computation theory

  • Refine by Keyword
  • 2 quantum computation
  • 1 Constraint sastifation problem
  • 1 Cryptography
  • 1 Merlin-Arthur proof systems
  • 1 PCP theorem
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2021
  • 1 2016
  • 1 2019
  • 1 2020
  • 1 2023

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