记录黑客技术中优秀的内容,传播黑客文化,分享黑客技术精华

一种云计算环境下基于可变搜索树的保序加密研究方案

2022-09-28 20:38

摘要

云环境下存在传统密码技术保护隐私数据困难的问题,保序加密因具有加密不改变明文原有顺序的特性在云环境下被广泛使用,但效率普遍不高。针对云环境下保序加密效率问题提出了一种基于搜索树可变的保序加密方案。介绍了云环境下保序加密方案的应用场景、系统模型和形式化定义,设计了一种云环境下保序加密的通用方案并实现。实验结果表明,所提出的保序加密方案的加密速率为 114.44 Mbit/s,具有较高的效率。

内容目录:
1 保序加密概述
1.1 系统模型
1.2 形式化定义
1.3 方案分类
1.4 方案选择
2 基于搜索树的保序加密方案
2.1 基本思想
2.2 基本原理
2.3 方案描述
2.4 方案安全性分析
2.5 实验结果及分析
3 结 语

云计算是以互联网为中心的一种技术,采用分布式计算、并行计算、网络存储和虚拟化等技术,将软件、硬件计算和存储等资源通过网络连接,形成一种云状的计算网络,为用户提供快速、便捷、自由的计算与存储服务。

其与传统的网络应用模式相比,具有应用 / 资源虚拟化、动态可扩展、按需部署、灵活性高、可靠性高和性价比高等优势。云计算包括了很多服务,其中最为广泛的为基础设施即服务(Infrastructure as a Service,IaaS)、 平 台 即 服务(Platform as a Service,PaaS)和软件即服务(Software as a Service,SaaS)3 种模式。云服务产生大量的个人隐私数据和商业信息等数据资源,由云服务器汇聚存储。

由于云端服务器和用户终端都在开放的网络环境下运行,使得云端数据不可避免地面临着安全风险和威胁。因此,如何在保证云端数据安全性和隐私性的前提下,在云计算环境下为用户提供安全可靠的数据存储和应用服务,成为亟待解决的问题。

目前,在云计算环境下出于对隐私数据的保护,用户终端一般先采用常规密码算法对数据进行加密,再将密态数据存储于云服务器,保证用户的隐私数据的机密性,但同时也杜绝了在云端服务器操作用户数据的可能性,当用户需要对存储在云端服务器或数据库中的密文数据进行操作时,必须先下载至本地终端进行解密,然后才能执行相应的操作。这种方式不仅增加了用户操作成本,还加重了网络和本地的负担,极大地限制了云计算的处理能力。

近些年,结合云计算环境下对密文数据进行操作的使用需求,密码学家研究并提出了保序加密、密文检索、同态加密等密码体制及方案,从而实现密文状态下的密文排序、密文检索、密文计算等功能,通过综合运用这些密码算法,构建密文数据库系统,为用户提供安全的密文保障。其中,密文排序作为云计算安全的主要应用之一,通过保序加密密码技术来实现。本文重点研究云计算环境的保序加密技术,通过对保序加密方案的特点进行分析,得到频率隐藏保序加密方案的构造思路,设计了一种保序加密方案,实现云计算环境下的数据保序加密。此方案在为用户隐私数据提供保护的同时,也能让云服务器进行密文排序等操作。

目前,常见的 Popa 方案 将二叉树维持在一个 B 树的形态,具有较强的安全性,但是只要发生了数据的更新、插入或者删除等操作,就需要对整个树做平衡操作,时间消耗很大。文献 [6] 提出可以使用非线性的加密算法实现索引加密,在数据库中构造了索引结构,简化数据库检索过程,提出了基于噪声的非线性表达式,但是如果输入的明文重复率很高,则很容易被推算出安全参数,影响算法的安全性。


01

保序加密概述



在云计算环境下,用户终端一般将复杂的计算和存储外包给云服务器。然而,不完全可信的云服务器可能会泄露用户隐私。为保护用户隐私数据,用户采用传统密码算法对数据加密后,再外包存储于云服务器,这些密文数据失去了原有的一些性质,无法对其进行范围查询。因此,在云计算环境下对密文数据实施范围查询提出需求,保序加密是满足密文空间范围查询需求的有效方法。

1.1 系统模型

2004 年,Agrawal 等 人 首次提出保序加密的概念,给出一种对数值型数据进行保序 加 密 的 方 案(Order-Preserving Encryption Scheme,OPES)。保序加密系统模型主体一般包括数据拥有者、云服务器、数据使用者,如图 1 所示。

图 1 保序加密系统模型

(1)数据拥有者。受限于存储和计算能力,数据拥有者一般将外包数据进行加密后,上传至云服务器存储。为了保护数据可用性,数据拥有者将采用可保留明文原有特殊性质的加密方案来加密数据。(2)数据使用者。对云服务器存储的数据进行查询时,数据使用者需要向数据拥有者索取密钥,再将查询请求发送给云服务器,收到查询结果后,数据使用者对查询结果进行解密。(3)云服务器。根据数据使用者的查询请求,云服务器在密文数据库中进行检索,将存储结果发送给数据使用者。

1.2 形式化定义

定义 1:保序加密方案可描述为多元组,为

其中,包含了密钥生成算法 Genk 产生的密钥 K ;加密算法 Enc 输入密钥 K 和明文 M ,输出密文 C ;解密算法 Dec 输入密钥 K 和密文C ,输出明文 M 。对于每个明文 M 和密钥 K ,需保证

对于两个随机明文 及密钥 K ,当时,,则 称这个方案为保序加密方案。

定义 2:(有状态)保序加密方案。

其中,为根据安全性参数λ 生成秘密状态 S ;为明文 x 计算密文 y 并将状态从 S 更新到 S' ;为基于状态 S 通过密文 y 计算明文 x 。

如果对于任何有效状态 S 和 x ,都满足,则加密方案是“正确”的。如果保留了顺序(即对于任何i 和j 有),则加密方案是“保序”的。

定义 3:序列随机化。

令 n 为序列中明文的个数。序列 X 满足随机化顺序,则成立。

1.3 方案分类

保序加密方案对明文加密后,密文保留原有明文顺序,用户可直接对密文数据进行排序、比较大小等操作,既可以确保用户数据安全,又可以增加密文数据的可操作性,目前主要应用于云服务器对密文数据库进行范围查询、近似邻检索等。

保序加密方案分类主要有检索结构分类和密文变化情况分类。

(1)检索结构分类。根据保序加密方案中是否含有明文检索结构,将现有的保序加密方案分为无索引结构和基于索引结构的保序加密方案。无索引结构的保序加密方案是指加密密文直接保留原有明文顺序。基于索引结构的保序加密方案是指明文数据采用常规分组体制加密方案进行加密,同时建立保序索引结构来比较明文顺序(2)密文变化情况分类。根据密文是否变化,可将现有的保序加密方案大致分为密文不变和密文可变的保序加密方案。密文不变的保序加密方案是指相同的明文数据经保序加密算法加密后,产生的密文相同。密文可变的保序加密方案是指相同的明文数据加密后,产生的密文不相同。

1.4 方案选择

保序加密方案直接对密文进行比较操作,若提高比较操作的效率,就会适当降低其安全性,密文的顺序会向攻击者泄露一些信息。在云计算环境中,攻击者的常用手段是唯密文攻击,其中统计性攻击是最有效的攻击方法。攻击者主要通过分析数据分布规律和数据频率对密文实施统计攻击。

(1)数据分布规律。利用保序加密方案所具有的明文空间映射密文空间的性质,攻击者可通过统计分析密文数据分布规律,推测明文数据分布规律。

(2)数据频率。攻击者通过统计分析高频率出现的密文数据来推导出对应的明文,使得密文数据出现的频率与明文数据一致,从而攻击加密方案成功。

经过安全性及其他性能等综合评估,本文选择了 Kerschbaum 等人 于 2015 年提出的以频率隐藏保序加密方案的思想来构建一种新的方案,该方案通过动态的二叉平衡树结构来随机化密文隐藏明文的频率,每个节点都有个状态t 来表示节点最大和最小范围,利用压缩树来节省客户端存储空间。


02

基于搜索树的保序加密方案



2.1 基本思想

频率隐藏保序加密方案的基本思想 是随机化密文分布,从而达到隐藏明文频率的目的。该方案需要在客户端(加解密侧)维护一个搜索树(二叉树)状态,以实现对数据的加密和解密,可以将搜索树状态看作私钥。加密时,先检查明文数据是否被存储于客户端的搜索树中,若明文数据未被存储于搜索树中,则对明文数据进行确定性加密产生密文数据;若明文数据被存储于搜索树中,则对明文数据进行随机化加密产生密文数据,并且更新搜索树增加新的节点,该节点含有对应的明文数据和密文数据。总之,频率隐藏保序加密方案对搜索树中首次出现的明文数据进行确定性保序加密,对搜索树中后续出现的明文数据进行随机化保序加密。随机化密文比确定性密文具有更高的熵,与普通保序加密方案相比,频率隐藏保序加密方案需要在客户端存储更多的状态信息,为了节省存储空间,本方案还具备数据压缩技术,既提供了实用性,又增强了密文的安全性。

2.2 基本原理

频率隐藏保序加密方案采用了具有排序性质的二叉树,在每个节点的值为明密文对,其性质如下文所述。

若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值;它的左、右子树也分别为二叉排序树。

2.3 方案描述

本文提出的一种基于搜索树的保序加密方案是将明文数据按其被加密的顺序插入到排序二叉树中,具有动态分配的叶子和二叉搜索树。其中,搜索树是动态变化的,存在一定的阈值深度,超过该阈值深度后,搜索树将被重新平衡。因此,本方案包括预处理步骤、加密算法ENCRYPT、解密算法 DECRYPT 和重平衡化搜索树算法 REBALANCE。

预处理步骤如下文所述。明文数据集合 X中的明文数据若非数值形式(如字符串),需要转换成数值,最终以数值形式存在,这些数值与其他数值进行大小比较,其结果有大于、小于和等于 3 种情况。当搜索树算法开始执行时,若搜索树为空,则需要创建根节点 t0,对明文x 加密,并且将明文 x 和其对应的密文 y 存储在根节点中,创建搜索树根节点过程如图 2 所示。

图 2 创建搜索树根节点

搜索树步骤开始执行时,若已有根节点的搜索树,也就是说,明文集合 X 中至少有一个明文 x 已被加密,并且至少有一个节点(如根节点)被包括在该搜索树中。接收输入集合包括明文 x、当前考虑的节点t 、 min 值和 max 值,判断明文x 是否等于当前考虑的节点t 中的明文,若明文 x 等于,则基于 RANDOMCOIN 确定判断条件硬币值 coin 为真;若明文 x 不等于,则 coin 被设置为假,表明明文 x 是唯一的,对其进行确定性加密。

当判断完成明文 x 是否大于或 coin是否等于 1 时,若条件满足其中之一,则向右遍历搜索树,判断在当前考虑的节点t 的右侧是否已经存在子节点,若右子节点不为空(右侧已经存在子节点),则更新该输入集合包括明文 x 、下一节点作为当前考虑节点 t 、节点作为 min 值和 max 值后,返回至起始输入;若为空(右侧没有已经存在的子节点),则判断是否满足搜索树的阈值深度,即当前考虑的节点 t 的与 max值的差值是否小于 2。若满足阈值深度,则重平衡搜索树,生成更新的搜索树,将明文 x 及其密文右子节点密文作为插入到更新的搜索树中;若没有满足阈值深度,则直接将明文 x 及其密文作为新节点插入到搜索树中。

当判断明文 x 是否大于或 coin 是否等于 1 时,若明文 x 不大于,则向左遍历搜索树,判断在当前考虑的节点t 的左侧是否已经存在子节点,若左子节点不为空(左侧已经存在子节点),则更新该输入集合包括明文 x 、下一节点作为当前考虑节点t 、 min和节点作为 max 值,返回至起始输入;若为空(左侧没有已经存在的子节点),则判断是否满足搜索树的阈值深度,即当前考虑的节点 t 的与 min 值的差值是否小于 2。若满足阈值深度,则重平衡搜索树,生成更新的搜索树,将明文 x 及其左子节点密文作为新节点插入到更新的搜索树中;若没有满足阈值深度,则直接将明文 x 及其密文作为新节点插入到搜索树中。整个预处理过程如图 3 所示。

图 3 预处理过程

λ 为方案的安全性参数;N 为不同明文数据的个数;为明文数据的比特长度;为密文数据的比特长度。

算法 1:加密算法

输入:明文 x ,节点 t ,最小值 min ,最大值 max

输出:密文 y

状态:节点的排序二叉树T

初始化:在初始建立二叉树状态时,可以将T 初始化为空

1 若,则随机在 {0,1} 选择一个

2 若,则令

3 若,则执行如下操作:

3.1 若,则继续递归调用

3.2 若,则执行以下操作:

3.2a 若,那么调用

3.2b 若,则创建新节点,即有如下变换,

4 若,则执行如下操作:

4.1 若,则继续递归调用

4.2 若,则执行以下操作:

4.2a 若,那么调用

4.2b 若,则创建新节点,即

加密时,可调用

算法 2:解密算法

输入:密文 y ,节点t

输出:明文 x

状态:节点的排序二叉树T

1 若,则递归调用

2 若,则递归调用

3 若,则返回

解密时,可以将 T 的根节点作为输入来求解密文,即

算法 3:重平衡化搜索树算法

输入:明文x,最小值 min ,最大值 max

输出:密文y

状态:节点的排序二叉树T

1 令

2 将 X 按照升序排列

3 创建一个新节点

4 令

5 令

6 令

7 调用

8 调用

9 用 y' 和 y'' 替换 y ,用 X' 和 X'' 替换 X ,进行递归调用

10 在T 中找到 x,并返回

2.4 方案安全性分析

对于保序加密的主流研究,可以用不可区分性或香农熵等指标来刻画其安全性,实际上考虑的是从密文中恢复出正确明文的成功率。在使用保序加密的部分场景中,攻击者不需要恢复出精确的明文,只需要恢复出一个足够接近的近似值。为此,可以采用恢复出的明文与实际明文之间的距离,即平均绝对误差来衡量安全性。

假设攻击者知道一定的明密文对,相当于攻击者已知了解密函数在一些定点的取值,此时攻击者可以用插值给出解密函数的估计。不同的插值方法可以给出解密函数的不同估计。当攻击者对于本方案有一定的了解时,可以根据加密函数的特性针对性地选择插值方案。对于本文方案,假设攻击者采用线性插值方法来恢复明文,对于密文 y ,若已知的明密文对中小于 y 的最大密文为,大于 y 的最小密文为,且对应的明文为,则解密函数在 y 的取值为:

对于最小与最大的明文,若已知的明密文对中不包含这两个明文,则认为它们分别被映射到最小密文和最大密文,并以这两对来对其他密文进行插值。则解密函数解密出的密文平均绝对误差为:

如果攻击者解密出的密文平均绝对误差为定值,则可以估计这两个序列之间的准确映射关系,认为其成功攻击了本文提出的保序加密方案。本文方案在预处理过程中提前判断阈值深度,重平衡搜索树,使得攻击者获得的密文平均绝对误差会一直变化,除非其获得了全部的明密文对才可能得到定值。所以本文方案是安全的。

2.5 实验结果及分析

对本文提出的方案进行实验,设置明文数据比特长度 k 为 12,安全性参数 λ 为 5,则密文数据比特长度。实验操作系统为 Windows 10,处理器为 Intel Core i5-6200U2.3 GHz,内存为 8 G,编程语言为 C 语言。实验结果表明,虽然随着明文大小的变化,加密时间也随之变化,但是整体的加密速率是一致的,为 114.441 Mbit/s,实验结果如图 4所示。

图 4 加密时间和加密速率

本文方案与采用类似构造的 Popa 方案在相同实验环境下进行对比,在输入相同明文的情况下,Popa 方案加密速率只有 73.934 Mbit/s。相较于 Popa 方案,本文的方案在加密速率方面提高了 54.7%。


03

结 语



云计算环境下,用户对于安全的进一步需求促使密码技术有了很大的发展。但是传统的密码技术在用户将自身隐私数据传至云端保存的场景下存在困难,如用户端的计算能力有限,传统的加密技术会破坏明文数据的特性,不利于后续的范围检索等。

本文提出的保序加密方案对搜索树中首次出现的明文数据进行确定性保序加密,对搜索树中后续出现的明文数据进行随机化保序加密,可以有效地应用于云环境下的加密数据检索等场景中,同时本方案的加密速率在 100 Mbit/s 之上,在一些交互强、延迟低的应用场景下也具有良好的效果。
引用格式:王小骥 , 杨竞 , 汤殿华 , 等 . 一种云计算环境下基于可变搜索树的保序加密研究方案 [J].信息安全与通信保密 ,2022(7):90-99.
作者简介 >>>
王小骥,男,学士,高级工程师,主要研究方向为信息安全与通信保密;
杨 竞,男,博士,工程师,主要研究方向为网络空间安全、密码学;
汤殿华,男,硕士,高级工程师,主要研究方向为密码学;
王 辉,女,硕士,高级工程师,主要研究方向为保密通信;
刘 瑶, 女, 硕 士, 工 程 师,主要研究方向为保密通信。

选自《信息安全与通信保密》2022年第7期


商务合作 | 开白转载 | 媒体交流 | 理事服务 

请联系:15710013727(微信同号)

《信息安全与通信保密》杂志投稿

联系电话:13391516229(微信同号)

邮箱:xxaqtgxt@163.com   

《通信技术》杂志投稿

联系电话:15198220331(微信同号)

邮箱:txjstgyx@163.com


知识来源: mp.weixin.qq.com%2Fs%2FM2_9Y-FsJTYwDSVEgAmyyQ&id=a1c556357fb38fc12339dd3da36f075d

阅读:136858 | 评论:0 | 标签:加密

想收藏或者和大家分享这篇好文章→复制链接地址

“一种云计算环境下基于可变搜索树的保序加密研究方案”共有0条留言

发表评论

姓名:

邮箱:

网址:

验证码:

黑帝公告 📢

十年经营持续更新精选优质黑客技术文章Hackdig,帮你成为掌握黑客技术的英雄

🙇🧎营运续持们我助帮↓

标签云 ☁