| 摘要: |
| 伪随机函数（Pseudorandom Function, PRF）是现代密码学的基本原语之一，由私钥空间、定义域空间及值域空间所表达。一方从私钥空间随机选取一个私钥，对定义域空间内的任一点，可计算一个PRF输出。为了满足日益丰富的安全或应用需求，学者们开启了对PRF的扩展性研究，即在PRF的基础上增加一些额外的特性，本文着重于PRF受限性研究（Constrained PRF，CPRF）。拥有PRF私钥的一方，可对定义域空间的某些子集生成受限密钥，该受限密钥可被授权给第三方以计算子集内的所有点处的PRF输出！
具体来讲，本文的研究分为两个方面。首先从受限集合的类别、正确性、安全性和额外的属性等四个方面对CPRF的定义进行讨论，着重回答目前存在的一些争议点的问题，比如能否用CPRF取代函数伪随机函数，单挑战安全性是否等价于多挑战安全性等。其次研究CPRF的可验证性(Constrained Verifiable Random Function, CVRF)，提出一个半动态安全的CVRF构造。值得注意的是，已知的CVRF构造，要么满足弱安全性，如选择挑战安全性；要么满足稍强安全性，如半动态安全性或者动态安全性，遗憾的是，满足稍强安全性的方案皆为非紧致的安全性归约证明，而且支持相对有限的受限集合类。本文的构造在满足稍强安全性，即半动态安全性的同时，不仅具有紧致的安全性归约证明，还支持任意有效可表达的受限集合。 |
| 关键词: 伪随机函数 受限伪随机函数 可验证受限伪随机函数 安全性归约证明 |
| DOI： |
| 投稿时间：2023-07-22修订日期：2023-11-09 |
| 基金项目: |
|
| Constrained Pseudorandom Functions: Discussion of Definitions and A Verifiability Construction |
|
Zan Yao1,2, Li Hongda1,2, Liang Bei3, Meng Xianning1,2
|
| (1.Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100085, China;2.School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China;3.Yanqi Lake Beijing Institute of Mathematical Sciences and Applications, Beijing 101408, China) |
| Abstract: |
| Pseudorandom Function (PRF) is one of the basic primitives in modern cryptography, is represented by a key space, a domain space and a range space. One party selects a secret key randomly from the key space, and calculates a PRF output for any point in the domain. In order to meet the increasingly rich security or application requirements, scholars have started to study the extensibility of PRF, that is, adding some additional features on the basis of PRF. In this paper, we focus on the study of Constrained PRF (CPRF), that is, a party in possession of a PRF secret key can generate a constrained key for some subset of the domain, which can be authorized to a third party to compute the PRF output at all points in the subset!
Specifically, our research is divided into two aspects. Firstly, the definition of CPRF is discussed from four aspects: the constraint category, correctness, security and additional properties, and some controversial issues are emphatically answered, such as whether the Functional PRF can be replaced by CPRF, and whether the security of one challenge is equivalent to the security of multiple challenges. Secondly, the Constrained Verifiable Random Function (CVRF) is studied, and a semi-adaptively secure construction of CVRF is proposed. It is worth noting that the known CVRF constructions, either satisfy weak security such as the selective-challenge security; Either it satisfies stronger security, such as semi-adaptive security or adaptive security. Unfortunately, the proofs satisfying the stronger security are all non-compact reductions and support relatively limited classes of constrained sets. While the construction in this paper not only satisfies the stronger security, that is, semi-adaptive security, but also has compact security reduction proofs and supports any effectively represented constrained sets. |
| Key words: Pseudorandom Function Constrained Pseudorandom Function Constrained Verifiable Random Function Security reduction proof |
