Paper 2019/1023

Randomly Rotate Qubits Compute and Reverse --- IT-Secure Non-Interactive Fully-Compact Homomorphic Quantum Computations over Classical Data Using Random Bases

Dor Bitan and Shlomi Dolev

Abstract

Homomorphic encryption (HE) schemes enable processing of encrypted data and may be used by a user to outsource storage and computations to an untrusted server. A plethora of HE schemes has been suggested in the past four decades, based on various assumptions, and which achieve different attributes. In this work, we assume that the user and server are quantum computers, and look for HE schemes of classical data. We set a high bar of requirements and ask what can be achieved under these requirements. Namely, we look for HE schemes which are efficient, information-theoretically (IT) secure, perfectly correct, and which support homomorphic operations in a fully-compact and non-interactive way. Fully-compact means that decryption costs O(1) time and space. To the best of our knowledge, there is no known scheme which fulfills all the above requirements. We suggest an encryption scheme based on random bases and discuss the homomorphic properties of that scheme. We demonstrate the usefulness of random bases in an efficient and secure QKD protocol and other applications. In particular, our QKD scheme has safer security in the face of weak measurements.