Cryptographic Applications Of Iterative Quantum Algorithms

Two of the most remarkable results —BB84 protocol(Bennett-Brassard protocol proposed in 1984)and Shor's factoring algorithm—of quantum computation and quantum information have had a profound influence on the current cryptographic regime.However,the Grover's iterated search algorithm,which is more widely applicable,has not found sufficient cryptographic applications apart from exhaustive key search.In addition,the cryptographic value of the non-Markovian case of another typical iterated computing process—quantum random walk,or quantum walk with memory,has not yet been explored.In order to enrich the cryptographic applications of these two kinds of quantum iterated algorithms,this work presents three quantum schemes concerning cryptanalysis,search on encrypted data and one-way functions based on Grover's search or quantum walks with memory.First,a quantum differential cryptanalytic scheme combining quantum minimum finding and quantum counting is proposed.Quantum differential attack takes advantage of quantum parallelism,speeds up the right-pair counting process for each candidate subkey and picks out the subkey with most number of right pairs more quickly by making use of Grover's search repeatedly.As a result,quantum differential cryptanalysis achieves a quadratic speedup over the best classical differential cryptanalysis and has desirable storage complexity as well.Second,a quantum homomorphic search protocol on encrypted superposition states is developed,whose correctness has been verified by a small-scale numerical simulation.This protocol combines Grover's algorithm with quantum homomorphic computing based on quantum one-time pad and encrypts the search field within the data items twice,so that a quantum server that knows neither the plain data nor the original search condition can search out the encrypted index of the target item from the superposed cipher state without decryption.Due to the large number of T gates in Grover's circuit,the homomorphic quantum search proceeds interactively.In order to ease the interactive burden of the client,the protocol introduce a trusted third party equipped with few quantum abilities and let this party interact with the server and update the keys.Furthermore,a non-interactive homomorphic protocol for an arbitrary Clifford circuit(containing no T gate)is also proposed,where the encrypted key for the input state is updated by the server using quantum homomorphic computing,and the simplified classical key-update process corresponding to the quantum homomorphic key-update procedure is performed by the client.Since the input state of the Clifford circuit and the encryption key are both perfectly protected under quantum one-time pad,the client does not need to interact with the server during the homomorphic evaluation,and the computational complexity of the simplified key-update process is polynomial in the input size.This protocol is both perfectly secure and compact,which is rarely achieved among the existing quantum homomorphic computing schemes based on quantum one-time pad.Finally,a model of one-dimensional quantum walks with two-step memory(QW2M)is concretely defined and analytically examined,whose general amplitude expression is deduced using path integral analysis and combinatorial approaches.Although this new kind of walk is an extension of one-dimensional quantum walks with one-step memory(QW1M),its probability distribution does not possess the localization property of QW1 M.Moreover,a quantum hash function based on QW2 M and QW1 M is constructed and tested.The test result shows that a one-bit change within the input of this function causes a fifty percent output deviation on average;thus,the new quantum hash function is very sensitive to the input message.