Quantum key search with side channel advice

Daniel P. Martin; Ashley Montanaro; Elisabeth Oswald; Dan Shepherd

doi:10.1007/978-3-319-72565-9_21

Quantum key search with side channel advice

Daniel P. Martin, Ashley Montanaro, Elisabeth Oswald^*, Dan Shepherd

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Recently, a number of results have been published that show how to combine classical cryptanalysis with quantum algorithms, thereby (potentially) achieving considerable speed-ups. We follow this trend but add a novel twist by considering how to utilise side channel leakage in a quantum setting. This is non-trivial because Grover’s algorithm deals with unstructured data, however we are interested in searching through a key space which has structure due to the side channel information. We present a novel variation of a key enumeration algorithm that produces batches of keys that can be efficiently tested using Grover’s algorithm. This results in the first quantum key search that benefits from side channel information.

Original language	English
Title of host publication	Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers
Editors	Carlisle Adams, Jan Camenisch
Publisher	Springer Verlag
Pages	407-422
Number of pages	16
ISBN (Print)	9783319725642
DOIs	https://doi.org/10.1007/978-3-319-72565-9_21
Publication status	Published - 2018
Event	24th International Conference on Selected Areas in Cryptography, SAC 2017 - Ottawa, Canada Duration: 16 Aug 2017 → 18 Aug 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10719 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th International Conference on Selected Areas in Cryptography, SAC 2017
Country/Territory	Canada
City	Ottawa
Period	16/08/17 → 18/08/17

Bibliographical note

Funding Information:
EPSRC Early Career Fellowship EP/L021005/1. Elisabeth Oswald and Dan Martin were in part supported by EPSRC via grant EP/N011635/1 (LADA). No research data was created for this paper.

Publisher Copyright:
© Springer International Publishing AG 2018.

Keywords

Quantum computation
Side channel attacks

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-72565-9_21

Cite this

Martin, D. P., Montanaro, A., Oswald, E., & Shepherd, D. (2018). Quantum key search with side channel advice. In C. Adams, & J. Camenisch (Eds.), Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers (pp. 407-422). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10719 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-72565-9_21

Martin, Daniel P. ; Montanaro, Ashley ; Oswald, Elisabeth et al. / Quantum key search with side channel advice. Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers. editor / Carlisle Adams ; Jan Camenisch. Springer Verlag, 2018. pp. 407-422 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7cad67d10ac34c7dafe200febcbe21a0,

title = "Quantum key search with side channel advice",

abstract = "Recently, a number of results have been published that show how to combine classical cryptanalysis with quantum algorithms, thereby (potentially) achieving considerable speed-ups. We follow this trend but add a novel twist by considering how to utilise side channel leakage in a quantum setting. This is non-trivial because Grover{\textquoteright}s algorithm deals with unstructured data, however we are interested in searching through a key space which has structure due to the side channel information. We present a novel variation of a key enumeration algorithm that produces batches of keys that can be efficiently tested using Grover{\textquoteright}s algorithm. This results in the first quantum key search that benefits from side channel information.",

keywords = "Quantum computation, Side channel attacks",

author = "Martin, {Daniel P.} and Ashley Montanaro and Elisabeth Oswald and Dan Shepherd",

note = "Funding Information: EPSRC Early Career Fellowship EP/L021005/1. Elisabeth Oswald and Dan Martin were in part supported by EPSRC via grant EP/N011635/1 (LADA). No research data was created for this paper. Publisher Copyright: {\textcopyright} Springer International Publishing AG 2018.; 24th International Conference on Selected Areas in Cryptography, SAC 2017 ; Conference date: 16-08-2017 Through 18-08-2017",

year = "2018",

doi = "10.1007/978-3-319-72565-9_21",

language = "English",

isbn = "9783319725642",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "407--422",

editor = "Carlisle Adams and Jan Camenisch",

booktitle = "Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers",

}

Martin, DP, Montanaro, A, Oswald, E & Shepherd, D 2018, Quantum key search with side channel advice. in C Adams & J Camenisch (eds), Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10719 LNCS, Springer Verlag, pp. 407-422, 24th International Conference on Selected Areas in Cryptography, SAC 2017, Ottawa, Canada, 16/08/17. https://doi.org/10.1007/978-3-319-72565-9_21

Quantum key search with side channel advice. / Martin, Daniel P.; Montanaro, Ashley; Oswald, Elisabeth et al.
Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers. ed. / Carlisle Adams; Jan Camenisch. Springer Verlag, 2018. p. 407-422 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10719 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Quantum key search with side channel advice

AU - Martin, Daniel P.

AU - Montanaro, Ashley

AU - Oswald, Elisabeth

AU - Shepherd, Dan

N1 - Funding Information: EPSRC Early Career Fellowship EP/L021005/1. Elisabeth Oswald and Dan Martin were in part supported by EPSRC via grant EP/N011635/1 (LADA). No research data was created for this paper. Publisher Copyright: © Springer International Publishing AG 2018.

PY - 2018

Y1 - 2018

N2 - Recently, a number of results have been published that show how to combine classical cryptanalysis with quantum algorithms, thereby (potentially) achieving considerable speed-ups. We follow this trend but add a novel twist by considering how to utilise side channel leakage in a quantum setting. This is non-trivial because Grover’s algorithm deals with unstructured data, however we are interested in searching through a key space which has structure due to the side channel information. We present a novel variation of a key enumeration algorithm that produces batches of keys that can be efficiently tested using Grover’s algorithm. This results in the first quantum key search that benefits from side channel information.

AB - Recently, a number of results have been published that show how to combine classical cryptanalysis with quantum algorithms, thereby (potentially) achieving considerable speed-ups. We follow this trend but add a novel twist by considering how to utilise side channel leakage in a quantum setting. This is non-trivial because Grover’s algorithm deals with unstructured data, however we are interested in searching through a key space which has structure due to the side channel information. We present a novel variation of a key enumeration algorithm that produces batches of keys that can be efficiently tested using Grover’s algorithm. This results in the first quantum key search that benefits from side channel information.

KW - Quantum computation

KW - Side channel attacks

UR - http://www.scopus.com/inward/record.url?scp=85041843862&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-72565-9_21

DO - 10.1007/978-3-319-72565-9_21

M3 - Conference contribution

AN - SCOPUS:85041843862

SN - 9783319725642

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 407

EP - 422

BT - Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers

A2 - Adams, Carlisle

A2 - Camenisch, Jan

PB - Springer Verlag

T2 - 24th International Conference on Selected Areas in Cryptography, SAC 2017

Y2 - 16 August 2017 through 18 August 2017

ER -

Martin DP, Montanaro A, Oswald E, Shepherd D. Quantum key search with side channel advice. In Adams C, Camenisch J, editors, Selected Areas in Cryptography – SAC 2017 - 24th International Conference, Revised Selected Papers. Springer Verlag. 2018. p. 407-422. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-72565-9_21

Quantum key search with side channel advice

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this