Asymmetric Quantum Cryptography and Multipartite Correlations

Abstract

The subject of this thesis is the analysis of secure asymmetric cryptographic schemes, and the study of the main resource for information processing protocols, the total, classical and quantum multipartite correlations.

Motivated by the usefulness of secure multiparty computation as a privacy-protecting data analysis tool, we proposed a practical quantum realization of randomized oblivious transfer. Our solution is aimed at targeting the limitations of security and efficiency faced by the classical schemes for oblivious transfer. A detailed security proof was written for the protocol. We also provide preliminary results of performance from an experimental setup based on an entangled photons source and polarization encoding.

The impossibility results for achieving unconditionally secure bit commitment have driven the research for secure solutions under several different assumptions. We propose a criteria for ranking the complexity of such assumptions, together with new functionality, called the asymmetric quantum beamer, which is minimal under the listed criteria. Using this new assumption we develop a universally composable bit commitment protocol with linear com­ plexity in its security parameter.

Based on previous work for a correlation hierarchy for probability distributions, we for­ malize a framework of correlation structures for quantum systems. We explore some of its mathematical properties, computational complexity, use for information compression of quantum states, and some aspects of categorization of correlations by the way they are dis­ tributed as well as by their nature (classical/quantum). Additionally, we present a practical application for the correlation structures framework for early classification of time series data sets. The proposed method is based on selectively cutting correlations that are not directly connected to the class variable until a criterion of optimality is satisfied. The algorithm was able to successfully guess the class of test data from real world sources using only a few initial time steps. Its versatility for application for other problems is highlighted.

Finally, we lay the foundations of a quantum algorithmic complexity theory based on the dc-QTM model. We conclude that, although the algorithmic complexity of a physical state and its classical description are equivalent, they can be differentiated while taking the role of a resource to compute another state. Additionally, we prove that the chain rule does not hold for this version of algorithmic complexity and argue how that result can be used to define the complexity of correlations in quantum systems.