skip to main content
Language:
Search Limited to: Search Limited to: Resource type Show Results with: Show Results with: Search type Index

Breaking Symmetric Cryptosystems Using Quantum Period Finding

Advances in Cryptology – CRYPTO 2016, 2016, Vol.9815, p.207-237 [Peer Reviewed Journal]

International Association for Cryptologic Research 2016 ;Distributed under a Creative Commons Attribution 4.0 International License ;ISSN: 0302-9743 ;ISBN: 9783662530078 ;ISBN: 3662530074 ;EISSN: 1611-3349 ;EISBN: 9783662530085 ;EISBN: 3662530082 ;DOI: 10.1007/978-3-662-53008-5_8

Digital Resources/Online E-Resources

Citations Cited by
  • Title:
    Breaking Symmetric Cryptosystems Using Quantum Period Finding
  • Author: Kaplan, Marc ; Leurent, Gaëtan ; Leverrier, Anthony ;  Naya-Plasencia, María
  • Subjects: Block ciphers ; Computer Science ; Cryptography and Security ; Modes of operation ; Physics ; Post-quantum cryptography ; Quantum attacks ; Quantum Physics ; Slide attack ; Symmetric cryptography
  • Is Part Of: Advances in Cryptology – CRYPTO 2016, 2016, Vol.9815, p.207-237
  • Description: Due to Shor’s algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. In this paper, we consider attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in it. We study applications of a quantum procedure called Simon’s algorithm (the simplest quantum period finding algorithm) in order to attack symmetric cryptosystems in this model. Following previous works in this direction, we show that several classical attacks based on finding collisions can be dramatically sped up using Simon’s algorithm: finding a collision requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} varOmega (2^{n/2}) end{document} queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only O(n) queries in the quantum model. We obtain attacks with very strong implications. First, we show that the most widely used modes of operation for authentication and authenticated encryption (e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the situation with encryption modes: Anand et al. show that standard modes are secure with a quantum-secure PRF. Second, we show that Simon’s algorithm can also be applied to slide attacks, leading to an exponential speed-up of a classical symmetric cryptanalysis technique in the quantum model.
  • Publisher: Berlin, Heidelberg: Springer Berlin Heidelberg
  • Language: English
  • Identifier: ISSN: 0302-9743
    ISBN: 9783662530078
    ISBN: 3662530074
    EISSN: 1611-3349
    EISBN: 9783662530085
    EISBN: 3662530082
    DOI: 10.1007/978-3-662-53008-5_8
  • Source: Hyper Article en Ligne (HAL) (Open Access)
Back to results list
INSPIRE LIBRARY - TON DUC THANG UNIVERSITY (84-028) 37 755 057 Feedback
19 Nguyen Huu Tho St. Dist.7, HCM thuvien@tdtu.edu.vn

Copyright © 2017 INSPIRE LIBRARY - TON DUC THANG UNIVERSITY

Searching Remote Databases, Please Wait