5 Search Results for "Dinur, Itai"

Document
DOI: 10.4230/LIPIcs.TQC.2024.8
(Quantum) Complexity of Testing Signed Graph Clusterability

Authors: Kuo-Chin Chen, Simon Apers, and Min-Hsiu Hsieh

Published in: LIPIcs, Volume 310, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)

Abstract
This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity Õ(N^{1/3}) for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [Adriaens and Apers, 2023]. Second, we prove an Ω̃(√N) classical query lower bound for testing clusterability, which nearly matches the upper bound from [Adriaens and Apers, 2023]. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.
Cite as

Kuo-Chin Chen, Simon Apers, and Min-Hsiu Hsieh. (Quantum) Complexity of Testing Signed Graph Clusterability. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 310, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.TQC.2024.8,
  author =	{Chen, Kuo-Chin and Apers, Simon and Hsieh, Min-Hsiu},
  title =	{{(Quantum) Complexity of Testing Signed Graph Clusterability}},
  booktitle =	{19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-328-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{310},
  editor =	{Magniez, Fr\'{e}d\'{e}ric and Grilo, Alex Bredariol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2024.8},
  URN =		{urn:nbn:de:0030-drops-206786},
  doi =		{10.4230/LIPIcs.TQC.2024.8},
  annote =	{Keywords: Quantum Algorithm, classical Query lower Bound, Graph Property testing}
}
Document
DOI: 10.4230/LIPIcs.TQC.2024.10
Guidable Local Hamiltonian Problems with Implications to Heuristic Ansatz State Preparation and the Quantum PCP Conjecture

Authors: Jordi Weggemans, Marten Folkertsma, and Chris Cade

Published in: LIPIcs, Volume 310, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)

Abstract
We study "Merlinized" versions of the recently defined Guided Local Hamiltonian problem, which we call "Guidable Local Hamiltonian" problems. Unlike their guided counterparts, these problems do not have a guiding state provided as a part of the input, but merely come with the promise that one exists. We consider in particular two classes of guiding states: those that can be prepared efficiently by a quantum circuit; and those belonging to a class of quantum states we call classically evaluatable, for which it is possible to efficiently compute expectation values of local observables classically. We show that guidable local Hamiltonian problems for both classes of guiding states are QCMA-complete in the inverse-polynomial precision setting, but lie within NP (or NqP) in the constant precision regime when the guiding state is classically evaluatable. Our completeness results show that, from a complexity-theoretic perspective, classical Ansätze selected by classical heuristics are just as powerful as quantum Ansätze prepared by quantum heuristics, as long as one has access to quantum phase estimation. In relation to the quantum PCP conjecture, we (i) define a complexity class capturing quantum-classical probabilistically checkable proof systems and show that it is contained in BQP^NP[1] for constant proof queries; (ii) give a no-go result on "dequantizing" the known quantum reduction which maps a QPCP-verification circuit to a local Hamiltonian with constant promise gap; (iii) give several no-go results for the existence of quantum gap amplification procedures that preserve certain ground state properties; and (iv) propose two conjectures that can be viewed as stronger versions of the NLTS theorem. Finally, we show that many of our results can be directly modified to obtain similar results for the class MA.
Cite as

Jordi Weggemans, Marten Folkertsma, and Chris Cade. Guidable Local Hamiltonian Problems with Implications to Heuristic Ansatz State Preparation and the Quantum PCP Conjecture. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 310, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{weggemans_et_al:LIPIcs.TQC.2024.10,
  author =	{Weggemans, Jordi and Folkertsma, Marten and Cade, Chris},
  title =	{{Guidable Local Hamiltonian Problems with Implications to Heuristic Ansatz State Preparation and the Quantum PCP Conjecture}},
  booktitle =	{19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)},
  pages =	{10:1--10:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-328-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{310},
  editor =	{Magniez, Fr\'{e}d\'{e}ric and Grilo, Alex Bredariol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2024.10},
  URN =		{urn:nbn:de:0030-drops-206804},
  doi =		{10.4230/LIPIcs.TQC.2024.10},
  annote =	{Keywords: Quantum complexity theory, local Hamiltonian problem, quantum state ansatzes, QCMA, quantum PCP conjecture}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.27
Locality-Preserving Hashing for Shifts with Connections to Cryptography

Authors: Elette Boyle, Itai Dinur, Niv Gilboa, Yuval Ishai, Nathan Keller, and Ohad Klein

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Can we sense our location in an unfamiliar environment by taking a sublinear-size sample of our surroundings? Can we efficiently encrypt a message that only someone physically close to us can decrypt? To solve this kind of problems, we introduce and study a new type of hash functions for finding shifts in sublinear time. A function h:{0,1}ⁿ → ℤ_n is a (d,δ) locality-preserving hash function for shifts (LPHS) if: (1) h can be computed by (adaptively) querying d bits of its input, and (2) Pr[h(x) ≠ h(x ≪ 1) + 1] ≤ δ, where x is random and ≪ 1 denotes a cyclic shift by one bit to the left. We make the following contributions. - Near-optimal LPHS via Distributed Discrete Log. We establish a general two-way connection between LPHS and algorithms for distributed discrete logarithm in the generic group model. Using such an algorithm of Dinur et al. (Crypto 2018), we get LPHS with near-optimal error of δ = Õ(1/d²). This gives an unusual example for the usefulness of group-based cryptography in a post-quantum world. We extend the positive result to non-cyclic and worst-case variants of LPHS. - Multidimensional LPHS. We obtain positive and negative results for a multidimensional extension of LPHS, making progress towards an optimal 2-dimensional LPHS. - Applications. We demonstrate the usefulness of LPHS by presenting cryptographic and algorithmic applications. In particular, we apply multidimensional LPHS to obtain an efficient "packed" implementation of homomorphic secret sharing and a sublinear-time implementation of location-sensitive encryption whose decryption requires a significantly overlapping view.
Cite as

Elette Boyle, Itai Dinur, Niv Gilboa, Yuval Ishai, Nathan Keller, and Ohad Klein. Locality-Preserving Hashing for Shifts with Connections to Cryptography. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 27:1-27:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{boyle_et_al:LIPIcs.ITCS.2022.27,
  author =	{Boyle, Elette and Dinur, Itai and Gilboa, Niv and Ishai, Yuval and Keller, Nathan and Klein, Ohad},
  title =	{{Locality-Preserving Hashing for Shifts with Connections to Cryptography}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{27:1--27:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.27},
  URN =		{urn:nbn:de:0030-drops-156231},
  doi =		{10.4230/LIPIcs.ITCS.2022.27},
  annote =	{Keywords: Sublinear algorithms, metric embeddings, shift finding, discrete logarithm, homomorphic secret sharing}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.13
Tight Bounds on Online Checkpointing Algorithms

Authors: Achiya Bar-On, Itai Dinur, Orr Dunkelman, Rani Hod, Nathan Keller, Eyal Ronen, and Adi Shamir

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
The problem of online checkpointing is a classical problem with numerous applications which had been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times. At ICALP'13 Bringmann et al. studied this problem as a special case of an online/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than 1.59-o(1) for all k, and smaller than ln4-o(1)~~1.39 for the sparse subset of k's which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of k. In this paper we solve the main problems left open in the ICALP'13 paper by proving that ln4 is a tight upper and lower bound on the asymptotic discrepancy for all large k, and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et al.) for all the small values of k <= 10.
Cite as

Achiya Bar-On, Itai Dinur, Orr Dunkelman, Rani Hod, Nathan Keller, Eyal Ronen, and Adi Shamir. Tight Bounds on Online Checkpointing Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{baron_et_al:LIPIcs.ICALP.2018.13,
  author =	{Bar-On, Achiya and Dinur, Itai and Dunkelman, Orr and Hod, Rani and Keller, Nathan and Ronen, Eyal and Shamir, Adi},
  title =	{{Tight Bounds on Online Checkpointing Algorithms}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.13},
  URN =		{urn:nbn:de:0030-drops-90179},
  doi =		{10.4230/LIPIcs.ICALP.2018.13},
  annote =	{Keywords: checkpoint, checkpointing algorithm, online algorithm, uniform distribution, discrepancy}
}
Document
DOI: 10.4230/DagSemProc.09031.6
Cube Testers and Key Recovery Attacks On Reduced-Round MD6 and Trivium

Authors: Jean-Philippe Aumasson, Itai Dinur, Willi Meier, and Adi Shamir

Published in: Dagstuhl Seminar Proceedings, Volume 9031, Symmetric Cryptography (2009)

Abstract
CRYPTO 2008 saw the introduction of the hash function MD6 and of cube attacks, a type of algebraic attack applicable to cryptographic functions having a low-degree algebraic normal form over GF(2). This paper applies cube attacks to reduced round MD6, finding the full 128-bit key of a 14-round MD6 with complexity 2\^22 (which takes less than a minute on a single PC). This is the best key recovery attack announced so far for MD6. We then introduce a new class of attacks called cube testers, based on efficient property-testing algorithms, and apply them to MD6 and to the stream cipher Trivium. Unlike the standard cube attacks, cube testers detect nonrandom behavior rather than performing key extraction, but they can also attack cryptographic schemes described by nonrandom polynomials of relatively high degree. Applied to MD6, cube testers detect nonrandomness over 18 rounds in 2\^17 complexity; applied to a slightly modified version of the MD6 compression function, they can distinguish 66 rounds from random in 2\^24 complexity. Cube testers give distinguishers on Trivium reduced to 790 rounds from random with 2^30 complexity and detect nonrandomness over 885 rounds in 2\^27, improving on the original 767-round cube attack.
Cite as

Jean-Philippe Aumasson, Itai Dinur, Willi Meier, and Adi Shamir. Cube Testers and Key Recovery Attacks On Reduced-Round MD6 and Trivium. In Symmetric Cryptography. Dagstuhl Seminar Proceedings, Volume 9031, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{aumasson_et_al:DagSemProc.09031.6,
  author =	{Aumasson, Jean-Philippe and Dinur, Itai and Meier, Willi and Shamir, Adi},
  title =	{{Cube Testers and Key Recovery Attacks On Reduced-Round MD6 and Trivium}},
  booktitle =	{Symmetric Cryptography},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9031},
  editor =	{Helena Handschuh and Stefan Lucks and Bart Preneel and Phillip Rogaway},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09031.6},
  URN =		{urn:nbn:de:0030-drops-19443},
  doi =		{10.4230/DagSemProc.09031.6},
  annote =	{Keywords: Cube attacks, property testing, MD6, Trivium}
}
  • Refine by Author
  • 3 Dinur, Itai
  • 2 Keller, Nathan
  • 2 Shamir, Adi
  • 1 Apers, Simon
  • 1 Aumasson, Jean-Philippe
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Cryptographic primitives
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Nearest neighbor algorithms
  • 1 Theory of computation → Online algorithms
  • 1 Theory of computation → Proof complexity
  • Show More...

  • Refine by Keyword
  • 1 Cube attacks
  • 1 Graph Property testing
  • 1 MD6
  • 1 QCMA
  • 1 Quantum Algorithm
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2024
  • 1 2009
  • 1 2018
  • 1 2022

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 Imprint Privacy Contact