| Quantum computing provides a new computational model that is only restricted by the laws of quantum physics. It has caused fundamental changes in many scientific fields. This thesis studies the strengths and limits of quantum computing from a cryptographic perspective. Our main focus is on investigating how secure computation, a central subject in classical cryptography, changes in a quantum world. In another endeavor, we also examine the potential of efficient quantum algorithms for solving some computational problems, which are regarded hard classically and are used in cryptographic constructions.;Secure computation allows a group of players to jointly perform a computational task on their private inputs without revealing more information about their inputs beyond what the output values imply. There are secure protocols that can realize any poly-time computation task under various conditions [Yao86, GMW87, CLOS02, Kil88]. However, these classical protocols may become insecure in presence of quantum attacks. First of all, quantum algorithms, e.g., Shor's quantum factoring algorithm [?], can solve some computational problems efficiently, which are otherwise assumed hard classically to construct cryptographic protocols. Even if we assume some problems are also hard for quantum computers, classically secure protocols based on them can still be broken by a quantum attacker without solving the hard problem necessarily. On the other hand, we can also exploit quantum computing capability in a positive way. For example, Bennett et al. [BBCS91] constructed a quantum protocol for oblivious transfer (OT) that is secure against unbounded attackers, assuming existence of an ideal commitment protocol. Remarkably, such a goal is unattainable using purely classical protocols.;In view of these challenges and opportunities, we make two major contributions in the realm of secure computation: first we prove that there are classical protocols for computing any poly-time function securely against poly-time quantum attackers and show that a large family of classical protocols can be made secure against quantum attackers. This means that the classical feasibility picture largely remains unchanged in the presence of quantum attacks. Second, we construct a quantum OT protocol assuming a task called 2-bit cut-and-choose is already realized, which gives another demonstration of separation between quantum and classical protocols in the flavor of [BBCS91]. Along the way we also develop new tools that are useful when analyzing quantum cryptographic protocols. As an application of our two-fold investigation into secure computation in a quantum world, we are able to give an almost thorough categorization of an important class of two-party secure computation tasks. Very roughly speaking, if we consider quantum poly-time attackers, there is a zero-one law, analogous to the classical setting [MPR10]: every task is either feasible or it can be used to realize any other task. Whereas in the presence of unbounded attackers, every task belongs into one of three mutually exclusive subclasses, in contrast with the more complicated classical picture [MPR09, KMQ11].;As we have seen, certain computational assumptions can be broken by efficient quantum algorithms. It is thus crucial to understand which problems are easy or hard for quantum computers. In this direction, we show evidence that an important number-theoretical problem can by solved by an efficient quantum algorithm. Specifically, we show that finding the group of units in a number field of arbitrary degree (Unit-Finding) can be reduced to an hidden subgroup problem (HSP). The best classical algorithm requires super-polynomial time to compute the units. Therefore it has also been used to as a candidate of hardness assumption for cryptographic constructions. However, our result indicates that finding units is potentially easy on a quantum computer, as the HSP instance to which we reduce is a natural generalization of the HSP instances for which there exist efficient quantum algorithms (e.g., HSP over finite Abelien groups and over constant-dimension real spaces). Thus we have made the first substantial step towards a complete quantum algorithm solving Unit-Finding. |
