Protection of Information in Quantum Databases
Y. Ozhigov
Electronic mail address: y@oz.msk.ru.
Department of Applied Mathematics,
Moscow State University of Technology Stankin,
Vadkovsky per. 3a, 101472, Moscow, Russia
Abstract
All modern cryptography is based on secret keys. But such methods of protecting information make no sense if the key can be quickly discovered by an unauthorized person. This way of penetrating protected systems was made possible by quantum computers due to results in [1,2]. This paper presents a method for protecting information in a database from a spy which knows all about its control system and has a quantum computer. Typically a database cannot distinguish between the operations of a spy and a legal user.
Such a database with quantum mechanical memory plays the role of a probabilistic oracle for some boolean function 
. It returns the value 
for query 
in time 
, afterwards its initial state is restored also in the same time, where 
is a cardinality of 
. Software of the database is independent of a function . A classical state of such a database must contain a list of pairs 
, taken in some order. Quantum mechanical principles allow mixing all these lists with different orders and equal amplitudes into one quantum state. We call such a state normal. All user operations extracting can be fulfilled only in states of such a sort. Now if somebody S tries to learn 
for 
the normal state is ruined such that a legal user with high probability will not obtain a pair of the form 
and hence the presence of S will be detected. It is proved that for a large the probability that a spy S learns does not exceed the probability of its exposure.
Here advantage is taken of relative diffusion transformations (RDT), which make it possible to fulfill all operations in normal states. Such transformations look like diffusion transforms used in [2] but RDT are defined in a different manner. A classical database with this property does not exist.
