密码学报（中英文）2025，Vol.12Issue(2)：247-264,18.DOI:10.13868/j.cnki.jcr.000760
基于NP语言的证据加密研究综述
An Overview of Witness Encryption Based on NP Language
摘要
Abstract
Witness encryption is a novel encryption scheme based on NP languages that eliminates the need for a key generation phase.The decryptor possesses witness corresponding to an instance of NP problem,rather than a key.In other words,the receiver does not need to be predetermined;only individuals with the decryption capability(witness)can decrypt the message.Since there is no need for key exchange phase to communication,witness encryption can be used for prize-based problem-solving,where the reward is given to those who successfully solve the problem.Furthermore,witness encryption is not only an independent encryption primitive but also a fundamental component for constructing other powerful cryptographic schemes.Currently,witness encryption has garnered sig-nificant attention from researchers and is primarily divided into two branches.One branch focuses on general witness encryption that supports all NP problems but often relies on strong assumptions.The other branch focuses on witness encryption specific to certain NP languages,emphasizing well-studied cryptographic assumptions and practical constructions.Given the significance of witness encryption in both theoretical research and practical applications,a comprehensive study and comparative analysis of the security models and scheme designs of witness encryption are provided.We describe and discuss classical witness encryption schemes,summarize witness encryption from different security framework perspectives,analyze and explore typical variants of witness encryption,and finally compare and analyze the applications of witness encryption in constructing other cryptographic primitives.Addi-tionally,we offer insights into future research directions,particularly in relation to similar primitives to witness encryption.关键词
证据加密/NP语言/NP完全语言/多线性映射/不可区分性混淆Key words
witness encryption/NP language/NP-complete language/multilinear maps/indistin-guishability obfuscation分类
计算机与自动化引用本文复制引用
王玉珠,张明武..基于NP语言的证据加密研究综述[J].密码学报（中英文）,2025,12(2):247-264,18.基金项目
湖北省重大研究计划(2023BAA027) （2023BAA027）
国家自然科学基金委员会-广东联合基金重点项目(U2001205) （U2001205）
国家自然科学基金(62072134) （62072134）
湖北省重点研发计划(2021BEA163) （2021BEA163）
广西自然科学基金重点项目(2019JJD170020)Major Research Plan of Hubei Province(2023BAA027) （2019JJD170020）
National Natural Science Foundation of China(62072134,U2001205) （62072134,U2001205）
Key Research and Development Program of Hubei Province(2021BEA163) （2021BEA163）
Key Project of Guangxi Natural Science Foundation(2019JJD170020) （2019JJD170020）
