DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2018.5

Subset Sum Quantumly in 1.17^n

Authors: Alexander Helm and Alexander May

Published in: LIPIcs, Volume 111, 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)

Abstract

We study the quantum complexity of solving the subset sum problem, where the elements a_1, ..., a_n are randomly chosen from Z_{2^{l(n)}} and t = sum_i a_i in Z_{2^{l(n)}} is a sum of n/2 elements. In 2013, Bernstein, Jeffery, Lange and Meurer constructed a quantum subset sum algorithm with heuristic time complexity 2^{0.241n}, by enhancing the classical subset sum algorithm of Howgrave-Graham and Joux with a quantum random walk technique. We improve on this by defining a quantum random walk for the classical subset sum algorithm of Becker, Coron and Joux. The new algorithm only needs heuristic running time and memory 2^{0.226n}, for almost all random subset sum instances.

Cite as

Alexander Helm and Alexander May. Subset Sum Quantumly in 1.17^n. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 111, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{helm_et_al:LIPIcs.TQC.2018.5,
  author =	{Helm, Alexander and May, Alexander},
  title =	{{Subset Sum Quantumly in 1.17^n}},
  booktitle =	{13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-080-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{111},
  editor =	{Jeffery, Stacey},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2018.5},
  URN =		{urn:nbn:de:0030-drops-92527},
  doi =		{10.4230/LIPIcs.TQC.2018.5},
  annote =	{Keywords: Subset sum, Quantum walk, Representation technique}
}

Document

DOI: 10.4230/DagRep.6.9.46

Public-Key Cryptography (Dagstuhl Seminar 16371)

Authors: Marc Fischlin, Alexander May, David Pointcheval, and Tal Rabin

Published in: Dagstuhl Reports, Volume 6, Issue 9 (2017)

Abstract

This report documents the program and results of Dagstuhl seminar 16731 “Public-Key Cryptography” which took place September 11th -16th, 2016. The goal of the seminar was to bring together different sub areas from public-key cryptography and to promote research among these areas.

Cite as

Marc Fischlin, Alexander May, David Pointcheval, and Tal Rabin. Public-Key Cryptography (Dagstuhl Seminar 16371). In Dagstuhl Reports, Volume 6, Issue 9, pp. 46-58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{fischlin_et_al:DagRep.6.9.46,
  author =	{Fischlin, Marc and May, Alexander and Pointcheval, David and Rabin, Tal},
  title =	{{Public-Key Cryptography (Dagstuhl Seminar 16371)}},
  pages =	{46--58},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{9},
  editor =	{Fischlin, Marc and May, Alexander and Pointcheval, David and Rabin, Tal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.9.46},
  URN =		{urn:nbn:de:0030-drops-69147},
  doi =		{10.4230/DagRep.6.9.46},
  annote =	{Keywords: cryptanalysis, encryption, homomorphic encryption, key exchange, obfuscation, signatures}
}

Document

DOI: 10.4230/DagRep.1.9.76

Public-Key Cryptography (Dagstuhl Seminar 11391)

Authors: Marc Fischlin, Anna Lysyanskaya, Ueli Maurer, and Alexander May

Published in: Dagstuhl Reports, Volume 1, Issue 9 (2012)

Abstract

From September 25th till September 30th, 2011, the Dagstuhl Seminar 11391 about ``Public-Key Cryptography'' took place at Schloss Dagstuhl. The meeting hosted 33 international researchers and incited active discussions about recent developments in this area.

Cite as

Marc Fischlin, Anna Lysyanskaya, Ueli Maurer, and Alexander May. Public-Key Cryptography (Dagstuhl Seminar 11391). In Dagstuhl Reports, Volume 1, Issue 9, pp. 76-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{fischlin_et_al:DagRep.1.9.76,
  author =	{Fischlin, Marc and Lysyanskaya, Anna and Maurer, Ueli and May, Alexander},
  title =	{{Public-Key Cryptography (Dagstuhl Seminar 11391)}},
  pages =	{76--94},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{1},
  number =	{9},
  editor =	{Fischlin, Marc and Lysyanskaya, Anna and Maurer, Ueli and May, Alexander},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.9.76},
  URN =		{urn:nbn:de:0030-drops-33685},
  doi =		{10.4230/DagRep.1.9.76},
  annote =	{Keywords: Fully-Homomorphic Encryption, Leakage-Resilience, Constructive Cryptography}
}

Search Results

Documents authored by May, Alexander

Subset Sum Quantumly in 1.17^n

Abstract

Cite as

Public-Key Cryptography (Dagstuhl Seminar 16371)

Abstract

Cite as

Public-Key Cryptography (Dagstuhl Seminar 11391)

Abstract

Cite as

Thanks for your feedback!

Could not send message