1.一种安全近似模式匹配方法,其特征是,包括如下步骤:密钥生成方生成公开秘钥和解密秘钥,并将公开秘钥传输至文本持有方和模式持有方;
文本持有方基于公开秘钥和持有的文本,得到加密文本;
模式持有方基于公开秘钥和持有的模式,得到加密模式;
两个第三方对加密文本和加密模式进行同态操作,对加密模式中的每个子模式与加密文本进行匹配,并将匹配结果发送至密钥生成方;
密钥生成方使用所述解密秘钥对匹配结果进行解密并乘以随机数后,发送至模式持有方。
2.如权利要求1所述的一种安全近似模式匹配方法,其特征是,所述得到加密文本的具体步骤为:
使用多项式打包方法将持有的文本打包为多项式;
将所述多项式的系数使用公开秘钥加密成加密文本。
3.如权利要求1所述的一种安全近似模式匹配方法,其特征是,所述得到加密模式的具体步骤为:
以重复通配符为拆分点对持有的模式进行拆分,得到子模式;
使用多项式打包方法将所有子模式打包为多项式;
将所述多项式的系数使用公开秘钥加密成加密模式。
4.如权利要求1所述的一种安全近似模式匹配方法,其特征是,所述子模式为不含通配符的子模式或只含复合通配符的子模式。
5.如权利要求4所述的一种安全近似模式匹配方法,其特征是,所述进行匹配的具体步骤为:
如果子模式为所述不含通配符的子模式,直接采用平方欧式距离对每个子模式与加密文本进行匹配;
如果子模式为所述只含复合通配符的子模式,使用双查询方法对每个子模式与加密文本进行匹配。
6.如权利要求5所述的一种安全近似模式匹配方法,其特征是,所述双查询方法具体为:
将只含复合通配符的子模式构造为两个子模式串,得到第一子模式串和第二子模式串;
计算第一子模式串与加密文本的匹配结果,并将匹配结果中系数为设定值的位置存储到第一集合;
计算第二子模式串与加密文本的匹配结果,并将匹配结果中系数为设定值的位置存储到第二集合;
取第一集合与第二集合之间的差值,若差值为空,则只含复合通配符的子模式与加密文本匹配成功,否则,匹配失败。
7.如权利要求1所述的一种安全近似模式匹配方法,其特征是,所述两个第三方均具有计算能力,且为半诚实可信的。
8.一种安全近似模式匹配系统,其特征是,包括文本持有方、模式持有方、密钥生成方和两个第三方;
所述密钥生成方,其被配置为:生成公开秘钥和解密秘钥,并将公开秘钥传输至文本持有方和模式持有方;
所述文本持有方,其被配置为:基于公开秘钥和持有的文本,得到加密文本;
所述模式持有方,其被配置为:基于公开秘钥和持有的模式,得到加密模式;
所述两个第三方,均被配置为:对加密文本和加密模式进行同态操作,对加密模式中的每个子模式与加密文本进行匹配,并将匹配结果发送至密钥生成方;
所述密钥生成方,还被配置为:使用所述解密秘钥对匹配结果进行解密并乘以随机数后,发送至模式持有方。
9.如权利要求8所述的一种安全近似模式匹配系统,其特征是,所述子模式为不含通配符的子模式或只含复合通配符的子模式。
10.如权利要求8所述的一种安全近似模式匹配系统,其特征是,所述两个第三方均具有计算能力,且为半诚实可信的。