CN106571905A - 一种数值型数据同态保序加密方法 - Google Patents

Abstract

本发明涉及一种数值型数据同态保序加密方法，采用加密保序融合技术，在单个密文模型中，能够支持在密文上的同态加、乘计算，保持与明文一致的顺序，其中，使用本发明所设计方法对明文进行加密，并在密文分片上构建保序索引，随后将密文发送到不可信的服务器中存储，服务器可以对加密数据进行排序、查询、数据的加和乘的操作，如此，加密结果不仅能够进行加和乘运算，还支持范围查询；随后将加密结果返回给可信端，系统使用解密函数和密钥将密文结果恢复成明文，最终返回给用户，大大提高了数据加密后应用与解密的效率。

Description

一种数值型数据同态保序加密方法

技术领域

本发明涉及一种数值型数据同态保序加密方法，涉及数据库加密、隐私保护和密码学技术领域。

背景技术

随着云计算的发展，为了追求更好的便捷性和更大的经济效益，越来越多的用户将数据存储在云中。然而数据的安全性成为一个挑战，用户将数据存储在云中，敏感数据暴露在云环境下，存在数据泄漏的风险。传统的解决方法是将数据加密后再存储，这种方法虽然能够保护敏感数据，但是也带来一些问题，其中最主要的是数据经过加密后失去了原有数据的特性，对于明文数据的操作无法在密文上执行。同态算法的产生正是为了解决上述问题，其特征是明文经过同态算法加密后具有和明文相同的属性，并且对明文的操作同样应用于密文数据。用户将需要存储或者处理的数据以密文的形式发送到云服务器中，云服务器在这些密文上进行处理，将处理后的结果以密文的形式返回给用户，再由用户对密文结果进行解密。自1978年由Revest等人提出同态加密算法以来，同态算法得到充分的研究，其中2013年刘东喜提出了一种用于数据库查询的同态加密方案，使用密钥和随机数来加密数值，支持整数和浮点数的加密和乘法同态操作，该方案将一个明文数据加密后形成多个密文分片，每个密文分片均带有随机噪声，这些密文分片必须通过特殊的解密函数及密钥才能够恢复明文。该方案的优点在于：加密过程基于线性函数，相比于以往的同态加密算法，其执行效率更高；并能保持明文数据类型，数值型数据经过加密后仍然是数值型，可以直接在密文上完成计算。然而已有的同态加密算法不能保持明文的顺序性，2011年MIT研究项目提出了洋葱加密模型，使用多种加密技术的结合解决此类问题，将明文数据分别使用保序加密和同态加密处理后存储，但由此带来了数据更新的问题，当数据进行同态加时，需要对运算后的数据使用保序加密算法重新加密，降低了数据处理的效率。如此，对于加密和明文顺序的保持分别提出了解决方案，但是现有技术尚不能将两者结合在一起，若能将此两种技术融合在一起共同作用于待加密数据的话，将能够大大提高数据的处理效率。

发明内容

本发明所要解决的技术问题是提供一种采用加密保序融合技术，使得数值型数据加密结果，不仅能够进行加和乘运算，还支持面向范围查询的数值型数据的加密保序。

本发明为了解决上述技术问题采用以下技术方案：本发明设计了一种数值型数据同态保序加密方法，包括加密存储方法，包括如下步骤：

步骤001.针对待处理数值型数据，采用同态加密算法进行加密，获得N个子密文分片c₁、…、c_n、…、c_N，其中，子密文分片c_n＝Enc_n(key(N),v_n)+Noise_n(key(N),R)，n∈{1、…、N}，N表示子密文分片的数量，v_n表示子密文分片c_n所对应的明文，key(N)表示密钥，R表示随机值，Enc_n(key(N),v_n)表示用密钥key(N)对明文v进行线性映射，Noise_n(key(N),R)表示随机噪声，它是关于随机值R和密钥key(N)的线性函数，然后进入步骤002；

步骤002.针对N个子密文分片，随机选择(m·N)个子密文分片，针对所选各个子密文分片中的随机噪声，分别按如下进行限制：

0＜Noise_n(key(N),R)＜Enc_n(key(N),v_n+dif)-Enc_n(key(N),v)

其中，dif表示所有子密文分片对应各个明文中、任意两明文值之间的最小差值，m表示预设百分比，然后进入步骤003；

步骤003.针对所有子密文分片，分别添加随机因子ζ，更新各个子密文分片c_n，并针对各个子密文分片c_n进行存储，同时，针对各个子密文分片c_n分别与对应随机因子ζ之间的对应关系进行存储。

作为本发明的一种优选技术方案：还包括子密文分片添加存储方法，包括如下步骤：

步骤a01.针对待添加存储子密文分片，定义随机因子ζ_new，并进入步骤a02；

步骤a02.判断所述已存储的子密文分片中，是否存在与待添加存储子密文分片具有相同属性的子密文分片，是则进入步骤a03；否则进入步骤a04；

步骤a03.采用待添加存储子密文分片的随机因子ζ_new，针对已存储与待添加存储子密文分片具有相同属性的子密文分片中的随机因子ζ进行替换，该待添加存储子密文分片的添加存储方法结束；

步骤a04.针对该待添加存储子密文分片进行存储，同时，针对该待添加存储子密文分片与对应随机因子ζ_new之间的对应关系进行存储。

作为本发明的一种优选技术方案：还包括查询结果解密方法，其中，针对查询所获得的各个子密文分片c_n，根据如下公式进行解密：

获得查询所获得各个子密文分片c_n对应的明文V，其中，f_n(key(N))表示解密函数。

作为本发明的一种优选技术方案：所述m·N＝1。

作为本发明的一种优选技术方案：所述m＝100％。

本发明所述一种数值型数据同态保序加密方法采用以上技术方案与现有技术相比，具有以下技术效果：本发明设计的数值型数据同态保序加密方法，采用加密保序融合技术，在单个密文模型中，能够支持在密文上的同态加、乘计算，保持与明文一致的顺序，其中，使用本发明所设计方法对明文进行加密，并在密文分片上构建保序索引，随后将密文发送到不可信的服务器中存储，服务器可以对加密数据进行排序、查询、数据的加和乘的操作，如此，加密结果不仅能够进行加和乘运算，还支持范围查询；随后将加密结果返回给可信端，系统使用解密函数和密钥将密文结果恢复成明文，最终返回给用户，大大提高了数据加密后应用与解密的效率。

附图说明

图1是本发明所设计数值型数据同态保序加密方法的流程示意图；

图2是实施例一中密钥与随机因子示意图；

图3是实施例一中加密后的子密文分片；

图4是实施例一中添加随机因子后的子密文分片；

图5a是实施例一中待添加存储子密文分片；

图5b是实施例一中待添加存储子密文分片后所对应的密文数据；

图6a是实施例二中加密后的子密文分片；

图6b是实施例二中添加随机因子后的子密文分片。

具体实施方式

下面结合说明书附图对本发明的具体实施方式作进一步详细的说明。

如图1所示，本发明设计了一种数值型数据同态保序加密方法，包括加密存储方法，具体包括如下步骤：

步骤001.针对待处理数值型数据，采用同态加密算法OHE(V,key(N))＝(c₁、…、c_n、…、c_N)进行加密，获得N个子密文分片c₁、…、c_n、…、c_N，其中，子密文分片c_n＝Enc_n(key(N),v_n)+Noise_n(key(N),R)，n∈{1、…、N}，N表示子密文分片的数量，v_n表示子密文分片c_n所对应的明文，key(N)表示密钥，R表示随机值，Enc_n(key(N),v_n)表示用密钥key(N)对明文v进行线性映射，Noise_n(key(N),R)表示随机噪声，它是关于随机值R和密钥key(N)的线性函数，然后进入步骤002。

其中，k₁,…,k_N和s₁,…,s_N均为实数，Noise_n(key(N),R)＝[(r₁,p₁),…,(r_n,p_n),…,(r_N,p_N)]，每个密文分片的随机噪声由两个随机数r_n,p_n构成。

根据c_n＝Value_n(v_n,k_n,s_n)+Noise_n(k_n,r_n,p_n)，Value_n(v_n,k_n,s_n)＝k_n×s_n×v_n；

步骤002.针对N个子密文分片，随机选择(m·N)个子密文分片，针对所选各个子密文分片中的随机噪声，分别按如下进行限制，对于其余各个子密文分片中的随机噪声，在取值范围为(-∞，+∞)；

0＜Noise_n(key(N),R)＜Enc_n(key(N),v_n+dif)-Enc_n(key(N),v)

其中，dif表示所有子密文分片对应各个明文中、任意两明文值之间的最小差值，m表示预设百分比，然后进入步骤003；实际应用中，具体可以设计选择m·N＝1，或者设计选择m＝100％。

随机噪声经过限制之后，数据安全性降低，为了不降低数据安全性，在所有各个密文分片上，分别设计添加随机因子，因此执行如下步骤003。

步骤003.针对所有子密文分片，分别添加随机因子ζ，更新各个子密文分片c_n，并针对各个子密文分片c_n进行存储，同时，针对各个子密文分片c_n分别与对应随机因子ζ之间的对应关系进行存储。

与上述加密存储方法相对应的，本发明设计了子密文分片添加存储方法，包括如下步骤：

步骤a01.针对待添加存储子密文分片，定义随机因子ζ_new，并进入步骤a02；

步骤a02.判断所述已存储的子密文分片中，是否存在与待添加存储子密文分片具有相同属性的子密文分片，是则进入步骤a03；否则进入步骤a04；

步骤a03.采用待添加存储子密文分片的随机因子ζ_new，针对已存储与待添加存储子密文分片具有相同属性的子密文分片中的随机因子ζ进行替换，该待添加存储子密文分片的添加存储方法结束；

步骤a04.针对该待添加存储子密文分片进行存储，同时，针对该待添加存储子密文分片与对应随机因子ζ_new之间的对应关系进行存储。

不仅如此，本发明还进一步设计了查询结果解密方法，其中，针对查询所获得的各个子密文分片c_n，根据如下公式进行解密：

获得查询所获得各个子密文分片c_n对应的明文V，其中，f_n(key(N))表示解密函数。因此，

通过获得明文V。

本发明由于加入随机因子，攻击者无法确定密文值的范围，使得同态保序加密的方法能够抵御选择明文攻击，提高了该方法的安全性。

上述技术方案所设计的数值型数据同态保序加密方法，采用加密保序融合技术，在单个密文模型中，能够支持在密文上的同态加、乘计算，保持与明文一致的顺序，其中，使用本发明所设计方法对明文进行加密，并在密文分片上构建保序索引，随后将密文发送到不可信的服务器中存储，服务器可以对加密数据进行排序、查询、数据的加和乘的操作，如此，加密结果不仅能够进行加和乘运算，还支持范围查询；随后将加密结果返回给可信端，系统使用解密函数和密钥将密文结果恢复成明文，最终返回给用户，大大提高了数据加密后应用与解密的效率。

将上述所设计数值型数据同态保序加密方法技术方案应用到实际当中，具体包括步骤：

步骤一：产生密钥并初始化

如图2所示，产生的密钥和初始的随机因子。

步骤二：同态加密及保序索引

输入明文数据为，并将子密文分片的个数设置为5个，如图3所示，是加密后的子密文分片，在算法实例中，令第一个子密文分片具有保序特性，如图2所示。

步骤三：向子密文分片中添加随机因子

在该实例中，使用加法对随机因子的运算，假设当前首次对子密文分片进行加密，因此使用初始的随机因子，对第一个子密文分片进行更新，密文值如图4所示。

步骤四：随机因子变换

假设现在需要加入一个新的数据，使用同态保序加密算法对新数据进行加密，得到的待添加存储子密文分片如图5a所示，生成新的随机因子，4.781033349635872E9，使已有子密文分片的随机因子变为新的随机因子，得到对应的密文数据如图5b所示。

步骤五：解密

根据公式：

，

最后，基于从图5b所示密文数据中回复明文。

顺序比较的具体实施方法：

步骤一：假设比较条件是，即从已有的数据中筛选出大于25的值，首先将关键字25使用上述加密算法进行加密，并使用图1中的密钥，加密结果如图6a所示；

步骤二：读取存储在本地的随机因子，当前的随机因子值为ζ＝4.71033×10⁹，对步骤一中加密后的关键字密文添加随机因子，得到的结果如图6b所示；

步骤三：使用图6b中的首个密文分片与数据库中的相应密文分片直接进行比较，得出数据库中满足比较条件的密文值，将相应的密文分组返回到可信端，进行解密。

上面结合附图对本发明的实施方式作了详细说明，但是本发明并不限于上述实施方式，在本领域普通技术人员所具备的知识范围内，还可以在不脱离本发明宗旨的前提下做出各种变化。

Claims (5)

1.一种数值型数据同态保序加密方法，其特征在于，包括加密存储方法，包括如下步骤：

步骤001.针对待处理数值型数据，采用同态加密算法进行加密，获得N个子密文分片c₁、…、c_n、…、c_N，其中，子密文分片c_n＝Enc_n(key(N),v_n)+Noise_n(key(N),R)，n∈{1、…、N}，N表示子密文分片的数量，v_n表示子密文分片c_n所对应的明文，key(N)表示密钥，R表示随机值，Enc_n(key(N),v_n)表示用密钥key(N)对明文v进行线性映射，Noise_n(key(N),R)表示随机噪声，它是关于随机值R和密钥key(N)的线性函数，然后进入步骤002；

步骤002.针对N个子密文分片，随机选择(m·N)个子密文分片，针对所选各个子密文分片中的随机噪声，分别按如下进行限制：

0＜Noise_n(key(N),R)＜Enc_n(key(N),v_n+dif)-Enc_n(key(N),v)

其中，dif表示所有子密文分片对应各个明文中、任意两明文值之间的最小差值，m表示预设百分比，然后进入步骤003；

步骤003.针对所有子密文分片，分别添加随机因子ζ，更新各个子密文分片c_n，并针对各个子密文分片c_n进行存储，同时，针对各个子密文分片c_n分别与对应随机因子ζ之间的对应关系进行存储。

2.根据权利要求1所述一种数值型数据同态保序加密方法，其特征在于，还包括子密文分片添加存储方法，包括如下步骤：

步骤a01.针对待添加存储子密文分片，定义随机因子ζ_new，并进入步骤a02；

步骤a02.判断所述已存储的子密文分片中，是否存在与待添加存储子密文分片具有相同属性的子密文分片，是则进入步骤a03；否则进入步骤a04；

步骤a03.采用待添加存储子密文分片的随机因子ζ_new，针对已存储与待添加存储子密文分片具有相同属性的子密文分片中的随机因子ζ进行替换，该待添加存储子密文分片的添加存储方法结束；

步骤a04.针对该待添加存储子密文分片进行存储，同时，针对该待添加存储子密文分片与对应随机因子ζ_new之间的对应关系进行存储。

3.根据权利要求1所述一种数值型数据同态保序加密方法，其特征在于，还包括查询结果解密方法，其中，针对查询所获得的各个子密文分片c_n，根据如下公式进行解密：

$V=\underset{n=1}{\overset{N}{\Σ}}\left(f_n\right(key\left(N\right))\×c_n)$

获得查询所获得各个子密文分片c_n对应的明文V，其中，f_n(key(N))表示解密函数。

4.根据权利要求1至3中任意一项所述一种数值型数据同态保序加密方法，其特征在于：所述m·N＝1。

5.根据权利要求1至3中任意一项所述一种数值型数据同态保序加密方法，其特征在于：所述m＝100％。