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

New Zero-Test Parameter Based Multilinear Maps from Ideal Lattices

作　　者：古春生 景征骏 史培中 于志敏 GU Chun-Sheng;JING Zheng-Jun;SHI Pei-Zhong;YU Zhi-Min(School of Computer Engineering,Jiangsu University of Technology,Changzhou,Jiangsu 213001;State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093)

机构地区：[1]江苏理工学院计算机工程学院,江苏常州213001 [2]国科学院信息工程研究所信息安全国家重点实验室,北京100093

出　　处：《计算机学报》2018年第5期1068-1108,共41页Chinese Journal of Computers

基　　金：本课题得到国家自然科学基金(61672270,61602216)、教育部人文社会科学研究项目(14YJAZH023,15YJCZH129)、中国科学院信息安全国家重点实验室开放课题面上项目(2015-MSB-10)、江苏省“青蓝工程”中青年学术带头人项目(KYQ14004)、江苏省高校优秀中青年教师和校长境外研修计划资助、常州市应用基础研究指导性项目(2016365)资助.

摘　　要：密码学中的多线性映射具有广泛应用,包括多方密钥交换、广播加密、基于身份的加密、基于属性的加密、不可区分模糊器和函数加密等.虽然多线性映射存在无限应用的可能,但目前多线性映射构造方案仅有三个——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 theoreticall

关 键 词：多线性映射 “0”化攻击 可信安装 多方密钥交换 证据加密 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]