基于新“0”测试参数的理想格上多线性映射

New Zero-Test Parameter Based Multilinear Maps from Ideal Lattices

密码学中的多线性映射具有广泛应用,包括多方密钥交换、广播加密、基于身份的加密、基于属性的加密、不可区分模糊器和函数加密等.虽然多线性映射存在无限应用的可能,但目前多线性映射构造方案仅有三个——GGH13、CLT13和GGH15,且它们都存在"0"化攻击、新的难度假设和可信安装的安全问题.针对第一个多线性映射候选构造方案GGH13,Hu和Jia最近基于"0"化攻击提出了攻击GGH13构造的多项式时间算法,完全破解了基于GGH13映射的两个重要应用——多方密钥交换协议(MPKE)和使用3-精确覆盖问题的证据加密方案(WE).本文主要改进理想格上的GGH13构造方案,以解决其存在的"0"化攻击和可信安装的安全问题.首先,为避免"0"化攻击问题,作者通过设计新的"0"测试参数提出基于新随机化方法的多线性映射构造,其安全性基于新的困难问题假设——ext-GDDH/ext-GCDH;其次,为去除可信安装问题,作者使用中国剩余定理提出无可信安装的理想格上多线性映射构造,其安全性基于新的困难问题假设——wots-ext-GCDH/wots-ext-GDDH;最后,作者给出基于改进多线性映射构造的多方密钥交换协议nr-MPKE和wots-MPKE.

Cryptographic multilinear maps have found many applications,including multipartite key exchange,broadcast encryption,identity-based encryption,attribute-based encryption,indistinguishability obfuscation and function encryption.Although the multilinear map has unlimited possibilities of applications,currently only the GGH13,CLT13 and GGH15 constructions are known,and all have zeroizing attacks,new hardness assumptions and trusted setup.For the first candidate construction GGH13 of multilinear maps,Hu and Jia recently extended the zeroizing attack in GGH13 introduced by Garg,Gentry and Halevi,and presented a polynomial time algorithm,which completely breaks two important GGH13-based applications,i.e.multipartite key exchange and witness encryption using 3-exact cover problem.This paper mainly improves the GGH13 construction from ideal lattices to solve its security issues of zeroizing attacks and trusted setup.First,in order to avoid the zeroizing attacks,we describe a new randomization construction of multilinear maps by designing new zero-test parameter.Different from the GGH13 construction,the public parameters in our construction do not contain encodings of zero,and only consists of some level-1 encodings of non-zero elements and their corresponding zero-test parameters.That is,essentially the new zero-test parameters are the product of the level-0 encoding of non-zero elements with the zero-test parameter in the origin GGH13 scheme.At present,the security of our construction only depends upon the new hardness assumptions ext-GDDH/ext-GCDH,and cannot reduce to other classical hardness problems.Furthermore,to analyze the security of our construction,we have proved that it can prevent the currently known attacks,i.e.the attacks of easily computable quantities,the attacks based on the low-level encodings of zeros or non-zeros.To further enhance the security and avoid potential attacks,we use the Kilian randomized matrix method and the NTRU prime field as the countermeasures,respectively.In addition,we theoretically prove that any noise-based construction of multilinear maps cannot completely avoid the zeroizing attacks.Second,in order to remove the trusted setup,we describe a construction without trusted setup of multilinear maps using ideal lattices by applying Chinese remainder theorem.In this construction,each participant first uses the new randomization construction as the basic building block to generate and publish her/his own public parameters.Then,each participant combines the public parameters of all parties by applying Chinese remainder theorem to generate the common public parameters shared by the parties.Finally,each participant adaptively generates all other algorithms of a graded encoding scheme under the common public parameters to obtain the construction without trusted setup.Similarly,the security of our construction without trusted setup only relies on the new hardness assumptions wots-ext-GCDH/wots-ext-GDDH,and cannot reduce to other classic hardness problems.Moreover,to analyze the security of the construction without trusted setup,we have proved that it can resist the currently known attacks,including the attacks against the new randomization construction and the extension of Cheon et al.’s zeroizing attacks.Third,we present the multipartite key exchange protocols nr-MPKE and wots-MPKE based on our improvement constructions of multilinear maps,respectively.The security of the nr-MPKE(resp.wots-MPKE)protocol relies on the hardness assumptions ext-GCDH/ext-GDDH(resp.wots-ext-GCDH/wots-ext-GDDH).