保序加密

2019/11/07 密码学

保序加密(order preserving encryption, OPE)是一种密码保持明文顺序的加密方案。本文主要描述保序加密算法的流程,并简要分析OPE的代码实现。

保序加密算法

Boldyreva等人提出了一种利用随机保序函数和超几何分布设计的可证明安全的OPE算法,并给出了OPE的安全性证明,即攻击者得到全部密文情况下,除了密文的顺序之外再也得不到其他任何有用的信息。保序加密方案能达到的最优安全性是IND-OCPA,安全目标是保证除了明文顺序(密文顺序)外不泄露其他任何明文信息。

保序加密框架(OPES)的定义如下:


是一个保序加密函数,是两个明文值,并且有密文

则有


超几何分布

假设有个球,其中黑球个,白球个,每次不放回、随机地抽取一个球。那么在抽取总共个球的情况下有多少个黑球是一个随机变量。我们用来表示这个随机变量,用表示具体的黑球数量,那么满足的概率是

让我们来做一个简单的高中数学题。从分别标有1、2、3、4、5、6、7、8、9的9张卡片中任意抽取两张,则两张卡片上的数字之和是奇数的概率是多少?

解答:如果两个数字之和是奇数,也就是要满足这两个数分别是一个奇数、一个偶数。假设我们把偶数看作是黑球,奇数看作是白球,那么上面的题目就转变为从9个球(4黑5白)中抽2个球,其中有1个是黑球的概率是多少。那么有:

随机保序函数

假如有明文域和密文域,从密文域中随机抽取个不同的整数组成有序集合,构造了一个保序函数,把第个明文映射到第个密文,那么一个保序函数对应唯一的组合。下图是一个明文和密文映射关系的例子。

(该图片来源见参考资料条目2)

由此我们可以把构造随机保序函数看做是满足超几何分布的抽球实验,其中有个球,黑球数量是,白球数量是。下面给出保序函数的概率公式:

基于上面的公式我们可以构造出一个随机保序函数,将明文域映射到密文域。我们假设有个球(符号N表示密文域的大小),其中有个黑球(符号M表示明文域的大小)。随机从所有球中不放回地抽球。当我们完整地抽完所有球,形成一种抽球结果序列,按照黑球的出现顺序一一映射,以下图为例:

箱子中有4个黑球,6个白球。对应的是4个明文、10个密文。当我们每次不放回随机抽球的时候,出现了一种抽球结果,分别是白白黑黑白白黑黑白白。那么将密文按顺序对应球的位置,得到了一种映射关系。例如明文3经过映射之后到密文51。明文[1,2,3,4]对应的加密结果是[47,48,51,52]。

算法描述

在实现的过程中与上述的例子有点区别。计算机中是通过不断压缩明文、密文空间来实现抽球的。下面是加密解密的算法描述。

明文域的大小是,密文域的大小是。明文存在于明文域中。程序模拟在个球中抽一半数量的球(),其中有个黑球。判断明文域中位置是否是待加密的明文,如果是那么映射到密文域的位置。否则以位置将明文域切分为两段,以位置将密文域切分为两段。如果明文落在明文域左半段,那么选择明文域左半段、密文域左半段继续递归,类似的选择明文域右半段、密文域右半段。

每次一递归过程中,密文域总是被缩短一半。所以这个算法的时间复杂度最差情况下是,平均情况是。相关的时间复杂度证明请参见Boldyreva的论文。

代码实现

在github上有一份开源的基于Python的OPE代码实现,仓库地址是https://github.com/tonyo/pyope.git。下面截取部分代码来分析:

加密过程的主要递归是encrypt_recursive函数完成的。tape_gen是一个迭代器,在我的理解是,这个迭代器的作用是输出抽球结果的序列。tape_gen将输入的数据与密钥key结合生成新的密钥,并使用AES-CTR加密算法生成随机的字符串,以这个字符串的位来逐个逐个模拟黑球白球的结果。

密钥key是在OPE对象初始化的时候输入的,这样意味着每一个独立的密钥key对应着“随机”的抽球结果,因此在解密的时候,使用相同的密钥,tape_gen可以输出相同的抽球结果。如果抽球结果是完全随机的话,这样加密后的结果就无法解密了,这就是OPE算法的密钥key的作用。注意看上面的算法流程中忽略了这一点,因为这里的加密函数是可以自由选择的,以下面代码为例则是使用了AES-CTR

def encrypt_recursive(self, plaintext, in_range, out_range):
    in_size = in_range.size()       # M
    out_size = out_range.size()     # N
    in_edge = in_range.start - 1    # d
    out_edge = out_range.start - 1  # r
    mid = out_edge + int(math.ceil(out_size / 2.0))  # y
    assert in_size <= out_size
	# 递归结束
    if in_range.size() == 1:
        coins = self.tape_gen(plaintext)
        ciphertext = stat.sample_uniform(out_range, coins)
        return ciphertext
    coins = self.tape_gen(mid)
    x = stat.sample_hgd(in_range, out_range, mid, coins)
    # 更新明文域、输出域
    if plaintext <= x:
        in_range = ValueRange(in_edge + 1, x)
        out_range = ValueRange(out_edge + 1, mid)
    else:
        in_range = ValueRange(x + 1, in_edge + in_size)
        out_range = ValueRange(mid + 1, out_edge + out_size)
    return self.encrypt_recursive(plaintext, in_range, out_range)
def tape_gen(self, data):
	"""Return a bit string, generated from the given data string"""

	# FIXME
	data = str(data).encode()

	# Derive a key from data
	hmac_obj = hmac.HMAC(self.key, digestmod=hashlib.sha256)
	hmac_obj.update(data)
	assert hmac_obj.digest_size == 32
	digest = hmac_obj.digest()

	# Use AES in the CTR mode to generate a pseudo-random bit string
	aes_algo = algorithms.AES(digest)
	aes_cipher = Cipher(aes_algo, mode=CTR(b'\x00' * 16), backend=default_backend())
	encryptor = aes_cipher.encryptor()

	while True:
		encrypted_bytes = encryptor.update(b'\x00' * 16)
		# Convert the data to a list of bits
		bits = util.str_to_bitstring(encrypted_bytes)
		for bit in bits:
			yield bit

下面是模拟抽球过程的函数,具体细节就不展开了。

def sample_hgd(in_range, out_range, nsample, seed_coins):
    """Get a sample from the hypergeometric distribution, using the provided bit list as a source of randomness"""
    in_size = in_range.size()
    out_size = out_range.size()
    assert in_size > 0 and out_size > 0
    assert in_size <= out_size
    assert out_range.contains(nsample)

    # 1-based index of nsample in out_range
    nsample_index = nsample - out_range.start + 1
    if in_size == out_size:
        # Input and output domains have equal size
        return in_range.start + nsample_index - 1

    in_sample_num = HGD.rhyper(nsample_index, in_size, out_size - in_size, seed_coins)
    print("Get " + str(in_sample_num) + " black balls")
    if in_sample_num == 0:
        return in_range.start
    elif in_sample_num == in_size:
        return in_range.end
    else:
        in_sample = in_range.start + in_sample_num
        assert in_range.contains(in_sample)
        return in_sample

下面是测试OPE的代码,明文空间是[0,10],密文空间是[0,10000],密钥是“key”,明文是4和6,对应的加密结果是1525、5291。

def test_ope_encrypt_decrypt():
    """Encrypt and then decrypt"""
    values = [4, 6]
    key = b'key'
    in_range = ValueRange(0, 10)
    out_range = ValueRange(0, 10000)
    # Client encrypts values
    cipher = OPE(key, in_range, out_range)
    encrypted_values = [cipher.encrypt(value) for value in values]

    # Decryption at the peer side
    cipher_dec = OPE(key, in_range, out_range)
    for value, encrypted in zip(values, encrypted_values):
        print("\nRES: " + str(encrypted))
        decrypted = cipher_dec.decrypt(encrypted)
        assert value == decrypted, "Dec(Enc(P)) != P"

参考资料

  • Boldyreva A, Chenette N, Lee Y, O’Neill A. Order-Preserving symmetric encryption. In: Proc. of the 28th Annual Int’l Conf. on Advances in Cryptology. Berlin, 2009. 224−241. [doi: 10.1007/978-3-642-01001-9_13]
  • 项世军,何嘉勇.一种保序加密域数据库认证水印算法.软件学报,2018,29(12):3837−3852.
  • 郭晶晶, 苗美霞, 王剑锋. 保序加密技术研究与进展[J]. 密码学报, 2018, 5(2): 182–195.

Search

    Table of Contents