Agr17函数加密(FE)方案的P/poly无效性

P/poly Invalidity of Agr17 Functional Encryption Scheme

函数加密(functional encryption,FE)是密码研究领域的前沿课题,而Agr17函数加密(FE)方案是主流FE方案之一.该方案以BGG+14属性加密(ABE)为一个底层结构,并将其改造为一个“部分隐藏属性的谓词加密”(PHPE),再与一个全同态加密(FHE)组合而成.然而Agr17函数加密(FE)方案留下了一个问题,即方案中的换模运算如何实现.本文论述Agr17函数加密(FE)方案的P/poly无效性,Agr17函数加密(FE)方案在解密阶段的换模之后无法继续运行.指出Agr17函数加密(FE)方案的换模运算必须是双重换模,即对全同态密文的换模和对全同态密文所寄生的属性密文的换模.指出对全同态密文所寄生的属性密文的换模破坏了属性密文的结构,使得其后的属性解密无法运行.因为属性解密运算并不是普通的LWE解密,而是附带条件的LWE解密,换模则破坏了解密条件.给出了一种“自然的”修改方案,将小模内积换为算术内积,由属性密文的模内积来实现算术内积.修改方案可以正确解密,但并不安全,说明这种无效性并不容易通过修改方案而消失.

Functional encryption(FE)is an advanced topic in cryptography,and the Agr17 FE scheme is one of the well-known FE schemes.The Agr17 FE scheme takes a BGG+14 attribute-based encryption(ABE)scheme as a base structure,which is upgraded into a“partially hiding predicate encryption”(PHPE)scheme and combined with a fully homomorphic encryption(FHE)scheme.However,the implementation of the modulus reduction is an unsolved problem in the Agr17 FE scheme.This study demonstrates that the Agr17 FE scheme is P/poly invalid.More specifically,it is shown that,in processing the P/poly function,the Agr17 FE scheme cannot be implemented any further after its modulus reduction.It is shown that the modulus reduction of the Agr17 FE scheme should be a double modulus reduction,which includes two modulus reductions for the FHE ciphertext and ABE ciphertext,respectively.It is also shown that the modulus reduction for the ABE ciphertext will destroy the structure of ABE so that the subsequent decryption cannot be executed.The reason lies in that,the decryption of ABE is an LWE decryption with conditions rather than an ordinary LWE decryption,and the modulus reduction will destroy the conditions of decryption.Moreover,a“natural revision”of the Agr17 scheme is designed,in which the small modulus inner product is changed into an arithmetic inner product,which can be obtained by the modulus inner product of the ABE ciphertext.The revised scheme can decrypt correctly,but it is insecure,which demonstrates that such invalidity cannot be easily crossed by revising the scheme.