Public-Key Encryption from Average Hard NP Language

Hongda Li; Peifang Ni; Yao Zan

Paper 2023/1260

Public-Key Encryption from Average Hard NP Language

Hongda Li, State Key Laboratory of Information Security, Institute of Information Engineering, CAS

Peifang Ni

, Institute of Software, Chinese Academy of Sciences

Yao Zan, State Key Laboratory of Information Security, Institute of Information Engineering, CAS

Abstract

The question of whether public-key encryption (PKE) can be constructed from the assumption that one-way functions (OWF) exist remains a central open problem. In this paper we give two constructions of bit PKE scheme derived from any NP language L, along with a polynomial-time instance-witness sampling algorithm. Furthermore, we prove that if L is average hard NP language, the the presented schemes is CPA secure. Our results give a positive answer to this longstanding problem, as the existence of OWF implies the existence of average hard NP language with a polynomial-time instance-witness sampling algorithm. Additionally, we obtain a witness encryption (WE) scheme for NP language based on the presented PKE scheme. This result highlights that WE scheme can also be established based on the existence of OWF.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: public-key encryption one-way function average hard NP language witness encryption
Contact author(s): lihongda @ iie ac cn
peifang2020 @ iscas ac cn
zanyao @ iie ac cn
History: 2023-08-21: approved; 2023-08-21: received; See all versions
Short URL: https://ia.cr/2023/1260
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1260,
      author = {Hongda Li and Peifang Ni and Yao Zan},
      title = {Public-Key Encryption from Average Hard {NP} Language},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1260},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1260}
}