International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Adaptive Hardcore Bit and Quantum Key Leasing over Classical Channel from LWE with Polynomial Modulus

Authors:
Duong Hieu Phan , LTCI, Telecom Paris, Institut Polytechnique de Paris, Paris, France
Weiqiang Wen , LTCI, Telecom Paris, Institut Polytechnique de Paris, Paris, France
Xingyu Yan , State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, 100876, China.
Jinwei Zheng , LTCI, Telecom Paris, Institut Polytechnique de Paris, Paris, France
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2024
Abstract: Quantum key leasing, also known as public key encryption with secure key leasing (PKE-SKL), allows a user to lease a (quantum) secret key to a server for decryption purpose, with the capability of revoking the key afterwards. In the pioneering work by Chardouvelis et al (arXiv:2310.14328), a PKE-SKL scheme utilizing classical channels was successfully built upon the noisy trapdoor claw-free (NTCF) family. This approach, however, relies on the superpolynomial hardness of learning with errors (LWE) problem, which could affect both efficiency and security of the scheme. In our work, we demonstrate that the reliance on superpolynomial hardness is unnecessary, and that LWE with polynomial-size modulus is sufficient to achieve the same goal. Our approach enhances both efficiency and security, thereby improving the practical feasibility of the scheme on near-term quantum devices. To accomplish this, we first construct a noticeable NTCF (NNTCF) family with the adaptive hardcore bit property, based on LWE with polynomial-size modulus. To the best of our knowledge, this is the first demonstration of the adaptive hardcore bit property based on LWE with polynomial-size modulus, which may be of independent interest. Building on this foundation, we address additional challenges in prior work to construct the first PKE-SKL scheme satisfying the following properties: (i) the entire protocol utilizes only classical communication, and can also be lifted to support homomorphism. (ii) the security is solely based on LWE assumption with polynomial-size modulus. As a demonstration of the versatility of our noticeable NTCF, we show that an efficient proof of quantumness protocol can be built upon it. Specifically, our protocol enables a classical verifier to test the quantumness while relying exclusively on the LWE assumption with polynomial-size modulus.
BibTeX
@inproceedings{asiacrypt-2024-34554,
  title={Adaptive Hardcore Bit and Quantum Key Leasing over Classical Channel from LWE with Polynomial Modulus},
  publisher={Springer-Verlag},
  author={Duong Hieu Phan and Weiqiang Wen and Xingyu Yan and Jinwei Zheng},
  year=2024
}