GVW15 谓词加密 (PE) 方案的 P/poly 有效性的一个注解

Abstract

谓词加密 (PE) 是密码研究领域的前沿课题之一, 也是身份基加密 (IBE)→属性基加密 (ABE)→谓词加密 (PE)→函数加密 (FE) 进阶过程的重要一环. GVW15谓词加密 (PE) 方案是一个主流的谓词加密 (PE) 方案, 以 BGG+14 属性加密 (ABE) 为底层结构, 再与全同态加密 (FHE) 组合而成. 该方案的一个重要运算是换模, 将全同态密文的模 Q 降为属性密文的模 q, 因此全同态密文中的噪声尺寸降为多项式大, 从而为后续的穷举噪声尺寸提供了可行性, 并进而正确解密. 本文指出, 没有证据表明 GVW15 谓词加密 (PE) 方案是 P/poly 有效的, 即在面对 P/poly 函数时, 没有证据表明GVW15谓词加密 (PE) 方案的换模运算能够将全同态密文中的噪声 (内噪声) 尺寸降为多项式大. 由于 GVW15 对 "换模" 这个关键操作没有给出详细论述, 本文只能去猜测所有可能的换模路径, 并按照最似然的理解, 指出每个可能的换模路径都面对特殊的、看来似乎很困难的可行性证明.

Alternate abstract:

Predicate encryption (PE) is a cutting-edge research topic in cryptography, and an essential component of a research route: identity-based encryption (IBE)→attribute-based encryption (ABE)→predicate encryption (PE)→functional encryption (FE). GVW15 predicate encryption scheme is a major predicate encryption scheme. The bottom structure is BGG+14 attribute-based encryption scheme, which is combined with a fully homomorphic encryption (FHE) scheme. A crucial operation of the scheme is modulus reduction, by which the modulus Q of the fully homomorphic encryption ciphertext (also referred to as the inner modulus) is scaled down to the modulus q of the attribute ciphertext (also referred to as the outer modulus). Therefore, the noise in the fully homomorphic encryption ciphertext (also referred to as the inner noise) is reduced to polynomial size, which enables the follow-up exhaustion of noise size and hence correct decryption. This paper shows that, there is no evidence to support the P/poly validity of GVW15 predicate encryption scheme, i.e., when addressing P/poly functions, there is no evidence to show that GVW15 scheme can be implemented. In specific, when addressing P/poly functions, there is no indication that the modulus reduction in GVW15 predicate encryption scheme can scale the noise in the fully homomorphic encryption ciphertext (the inner noise) down to polynomial size. It should be noted that, since GVW15 does not provide a detailed description about the modulus reduction, this paper guesses all possible routes of modulus reduction, and points out that, the feasibility proof of each possible modulus reduction route seems to be difficult.