Lattice-Based Quantum Advantage from Rotated Measurements

Yusuf Alnawakhtha; Atul Mantri; Carl A. Miller; Daochen Wang

Paper 2022/1497

Lattice-Based Quantum Advantage from Rotated Measurements

Yusuf Alnawakhtha, Joint Center for Quantum Information and Computer Science (QuICS), 3100 Atlantic Building, University of Maryland, College Park, MD 20742, USA

Atul Mantri, Joint Center for Quantum Information and Computer Science (QuICS), 3100 Atlantic Building, University of Maryland, College Park, MD 20742, USA

Carl A. Miller, Joint Center for Quantum Information and Computer Science (QuICS), 3100 Atlantic Building, University of Maryland, College Park, MD 20742, USA, Computer Security Division, National Institute of Standards and Technology (NIST), 100 Bureau Dr., Gaithersburg, MD 20899, USA

Daochen Wang, Joint Center for Quantum Information and Computer Science (QuICS), 3100 Atlantic Building, University of Maryland, College Park, MD 20742, USA

Abstract

Trapdoor claw-free functions (TCFs) are immensely valuable in cryptographic interactions between a classical client and a quantum server. Typically, a protocol has the quantum server prepare a superposition of two-bit strings of a claw and then measure it using Pauli- or measurements. In this paper, we demonstrate a new technique that uses the entire range of qubit measurements from the -plane. We show the advantage of this approach in two applications. First, building on (Brakerski et al. 2018, Kalai et al. 2022), we show an optimized two-round proof of quantumness whose security can be expressed directly in terms of the hardness of the LWE (learning with errors) problem. Second, we construct a one-round protocol for blind remote preparation of an arbitrary state on the -plane up to a Pauli- correction.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Contact author(s): nawaktha @ umd edu
amantri @ umd edu
camiller @ umd edu
daochen @ umd edu
History: 2022-11-01: approved; 2022-10-31: received; See all versions
Short URL: https://ia.cr/2022/1497
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1497,
      author = {Yusuf Alnawakhtha and Atul Mantri and Carl A. Miller and Daochen Wang},
      title = {Lattice-Based Quantum Advantage from Rotated Measurements},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1497},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1497}
}