On the {\sf P/poly} Validity of the Agr17 FE Scheme

Yupu Hu; Siyue Dong; Baocang Wang; Jun Liu; Yanbin Pan; Xingting Dong

Paper 2021/1442

On the {\sf P/poly} Validity of the Agr17 FE Scheme

Yupu Hu

Siyue Dong

Baocang Wang

Jun Liu

Yanbin Pan

Xingting Dong

Abstract

Functional encryption (FE) is a cutting-edge research topic in cryptography. The Agr17 FE scheme is a major scheme of FE area. This scheme had the novelty of “being applied for the group of general functions (that is, {\sf P/poly} functions) without IO”. It took the BGG+14 ABE scheme as a bottom structure, which was upgraded into a “partially hiding attribute” scheme, and combined with a fully homomorphic encryption (FHE) scheme. However, the Agr17 FE scheme had a strange operation. For noise cancellation of FHE decryption stage, it used bulky “searching noise” rather than elegant “filtering”. It searched total modulus interval, so that the FHE modulus should be polynomially large. In this paper we discuss the {\sf P/poly} validity of the Agr17 FE scheme. First, we obtain the result that the Agr17 FE scheme is {\sf P/poly} invalid. More detailedly, when the Agr17 FE scheme is applied for the group of randomly chosen {\sf P/poly} Boolean functions, FHE modulus at the “searching” stage cannot be polynomially large. Our analysis is based on three restrictions of the BGG+14 ABE scheme: (1) The modulus of the BGG+14 ABE should be adapted to being super-polynomially large, if it is applied for the group of randomly chosen {\sf P/poly} functions. (2) The modulus of the BGG+14 ABE cannot be switched. (3) If the BGG+14 ABE is upgraded into a “partially hiding attribute” scheme, permitted operations about hidden part of the attribute can only be affine operations. Then, to check whether the {\sf P/poly} validity can be obtained by modifying the scheme, we consider two modified versions. The first modified version is controlling the FHE noise by repeatedly applying bootstrapping, and replacing a modular inner product with an arithmetic inner product. The second modified version is replacing the search for the modulus interval with the search for a public noise interval, hoping such noise interval polynomially large and tolerating the modulus which may be super-polynomially large. The first modified version may be {\sf P/poly} valid, but it is weaker. There is no evidence to support the {\sf P/poly} validity of the second modified version. Finally, we present an additional conclusion that there is no evidence to support the {\sf P/poly} validity of the GVW15 PE scheme.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: learning with errors attribute-based encryption functional encryption
Contact author(s): yphu @ mail xidian edu cn
sydong @ stu xidian edu cn
bcwang @ xidian edu cn
jliu6 @ stu xidian edu cn
panyanbin @ amss ac cn
xtdong @ guet edu cn
History: 2024-04-22: last of 2 revisions; 2021-10-27: received; See all versions
Short URL: https://ia.cr/2021/1442
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1442,
      author = {Yupu Hu and Siyue Dong and Baocang Wang and Jun Liu and Yanbin Pan and Xingting Dong},
      title = {On the {\sf P/poly} Validity of the Agr17 FE Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1442},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1442}},
      url = {https://eprint.iacr.org/2021/1442}
}