New Generation Computing, 21(2003)347-361
Ohmsha, Ltd. and Springer-Verlag

A Quantum Algorithm using NMR Computers to Break Secret-key Cryptosystems

Kazuo OHTA*, Tetsuo NISHINO*, Seiya OKUBO**, and Noboru KUNIHIRO*
* The University of Electro-Communications
** The Graduate School of Electro-Communications
1-15-1 Chofugaoka, Chofu, Tokyo 182-8585, Japan
{ota, nishino, s-okubo, kunihiro}@ice.uec.ac.jp

Received 31 August 2002
Revised manuscript received 30 April 2003

Abstract

In this paper, we discuss quantum algorithms that, for a given plaintext m_o and a given ciphertext c_o, will find a secret key, k_o, satisfying c_o = E(k_o, m_o), where an encryption algorithm, E, is publicly available. We propose a new algorithm suitable for an NMR (Nuclear Magnetic Resonance) computer based on the technique used to solve the counting problem. The complexity of our algorithm decreases as the measurement accuracy of the NMR computer increases. We discuss the possibility that the proposed algorithm is superior to Grover's algorithm based on initial experimental results.

Keywords: Grover's Algorithm, Secret-Key Cryptosystem, Secret-Key Search, NMR Computer, Bulk Quantum Turing Machine.

[Back]