论文笔记——频率隐藏保序加密

论文标题:Frequency-Hiding Order-Preserving Encryption

原文作者:Florian Kerschbaum, Authors Info & Claims

原文链接:https://dl.acm.org/doi/abs/10.1145/2810103.2813629

发表会议:CCS '15: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security

目录

· 简介

· 术语介绍

· 基于问题

· 安全性定义

· 方案构造

· 安全性证明


· 简介

保序加密技术可以被用于对加密的数据进行有效的范围查询,这也使得保序加密更加适合用于数据外包的云计算场景,但目前的保序加密技术的安全性仍然存在着一些争议。本文主要是提出了一种保序加密方案,通过随机化密文来隐藏明文的频率,比以往的方案安全性更高并且存储规模仍然很小。该方案中的密文近似均匀分布,从而提高了对频率分析攻击的抵抗能力。因此可以更安全地外包大型数据库,其安全性也会随着数据集的增大而增加。

· 术语介绍

1. 保序加密 (order-preserving encryption)

密文保持了明文顺序特征的一种加密方案,即如果明文ab满足a<b,那么经过加密后的密文E(a)E(b)也满足E(a)<E(b)

2. 有状态的保序加密方案 (stateful order-preserving encryption)

一个有状态的保序加密方案\Pi _{FHOPE}通常由以下三个算法组成:

  • S\leftarrow KeyGen(\lambda):通过一个安全参数\lambda生成一个密钥状态S;

  • y \leftarrow Encrypt(S, x):计算明文x对应的密文y,并将状态更新到S';

  • x\leftarrow Decrypt(S, y):基于状态S和密文y,解密出明文x

有状态的保序加密方案和无状态的保序加密方案的区别:

有状态的保序加密方案需要在加密和解密操作之间保持某种状态,以便进行正确的解密操作。这个状态可能是一个密钥,或者是一个随机数或计数器等。在加密操作时,这个状态被用来生成密文;在解密操作时,这个状态被用来还原明文。由于状态的存在,这种方案可能需要更多的存储空间,并且可能需要更多的计算来管理状态。相比之下,无状态的保序加密方案不需要在加密和解密操作之间保持任何状态。它们使用一些固定的参数来生成密文,并使用相同的参数来解密密文。由于无需维护状态,这种方案通常需要更少的存储空间,并且可以更快速地进行加密和解密操作。需要注意的是,虽然无状态的保序加密方案具有一些优势,但它们可能更容易受到一些攻击,例如频谱分析和差分攻击。因此,在选择加密方案时,需要考虑到具体的应用场景和安全需求。

3. IND-OCPA security

ND代表不可区分性(indistinguishability),OCPA代表选择明文攻击(chosen plaintext attack)下的安全性。

在IND-OCPA安全模型下,攻击者可以选择一些明文并获得相应的密文,然后尝试通过分析这些密文来破解密钥。在这个过程中,攻击者不能直接访问密钥,但可以进行大量的"明文-密文"查询。如果方案在这种攻击下是安全的,那么攻击者无法获得有用的信息,IND-OCPA安全是公钥加密方案中最基本的安全性要求之一,也是目前保序加密方案最强的安全性,也就是除了顺序以外不泄露任何有关明文的信息。

IND-OCPA安全被定义为challenger和adversary之间的一个game:adversary准备两个明文序列,其中两个序列具有相同的顺序,并且序列中的每个明文是不同的。他把这两个序列发送给challenger。challenger对其中一个序列进行加密,并将密文发送给adversary,adversary猜测它是两个序列中的哪一个。

· 基于问题

在外包的数据库(结构化数据)中,数据库表的每一列都被进行加密,例如,在一个关于用户的典型数据库表中,会有诸如名字和姓氏、出生日期、性别等字段,每个字段都用各自对应的密钥进行加密。然而,在大多数这些字段中,输入并不是均匀分布的。史密斯的姓氏在美国肯定比赫克斯特布尔更常见。事实上,研究表明,即使是部分频率信息,就像可搜索加密的情况一样,也可以有很的高概率被解密条目。对于一个典型的数据库中的许多字段,关于频率分布的信息是很容易获得的,例如,许多网站列出了每个地区最常见的名字和姓氏。于是本文提出了一种保序加密方案,重复的明文可以映射为不同的密文但仍然保持其顺序信息。

· 安全性定义

将上述介绍过的IND-OCPA安全扩展到随机化密文的保序加密方案中。那么 IND-FAOCPA安全定义的目标是:密文只泄露明文的随机顺序,即两个具有相同随机顺序的序列(但不同的明文频率)应该是无法区分的。本文定义了以下的 security game Game_{FAOCPA} (\lambda )

有了以上game,我们现在可以定义针对频率分析有序选择明文攻击的安全性:

如果敌手A在 Game_{FAOCPA} (\lambda )中输出c的概率可以忽略不计,即:

Pr[A(Game_{FAOCPA} (\lambda ))=c]<\frac{1}{2} +\frac{1}{Poly(\lambda )},那么一个有状态的保序加密方案\Pi _{FHOPE}在频率分析顺序选择明文攻击下是满足 IND-FAOCPA安全的。

· 方案构造

同mOPE一样,本文数据的存储方式也是以二叉树的数据结构,但是增加了两个参数,如下图所示:

参数介绍:n为要插入的所有的明文的数量,N为不同明文的个数。因此,上述算法1中的位长度为k=\left \lceil log_{2} N \right \rceil\lambda为密文的安全参数,因此,在算法1中的l=\lambda k,安全参数也可以用于确定伪随机性的种子的长度。

接下来,现在我们执行下述算法2中的加密。我们将二叉搜索树(状态)表示为节点\left \{ t \right \} 的集合T,此外,为当前节点添加输入t,为下限和上限添加最小值和最大值,以实现递归。(注:最大值和最小值表示了当前的明文加密以后可能的密文的上限和下限)

 其中,第5步中的REBALANCE()算法表示重新平衡这棵二叉树(这里我的理解是:如果新插入的这个明文和max之差小于2的话,这个明文对应的密文就别无选择了,也很容易被频率攻击猜到这个明文是可能和上一个结点中存储的明文相等的):

 了解了以上过程后,我们可以举个例子:假如我们有一个明文序列X=1,2,1,3 ,具有min=-1max=128。然后前两个明文1,2对应的密文是确定的y_{1} =64y_{2} =96。那么对于第三个明文x_{3} =1,由于它和x_{1} =1是两个重复的明文,所以这里要对它进行随机化以隐藏明文的频率。那么现在树的结构有如下两种情况:

  • 情况1:

此时,加密算法执行到第1步,此时t.plain=2,跳转到第7步,由于t的左子树不为空,所以递归到t.plain=1,此时若随机取的coin=0,且此时t的左子树为空,所以明文x_{3} =1加密后的密文应该是min+\left \lceil \frac{t.cipher-min}{2} \right \rceil =-1+\left \lceil \frac{64-(-1)}{2} \right \rceil =-1+33=32;若随机取的

coin=1,并且此时t的右子树为空,加密后的密文应该是t.cipher+\left \lceil \frac{max-t.cipher}{2} \right \rceil =64+\left \lceil \frac{128-(64)}{2} \right \rceil =64+64=112y_{3} =48

  • 情况2:

同理,加密算法执行到第1步,此时t.plain=1,如果随机取的coin=0,此时t的左子树为空,所以明文x_{3} =1加密后的密文应该是min+\left \lceil \frac{t.cipher-min}{2} \right \rceil =-1+\left \lceil \frac{64-(-1)}{2} \right \rceil =-1+33=32;若随机取的

coin=1,并且此时t的右子不树为空,所以递归到t.plain=2,加密后的密文应该是min+\left \lceil \frac{t.cipher-min}{2} \right \rceil =-1+\left \lceil \frac{96-(-1)}{2} \right \rceil =-1+49=48

综上所述,明文x_{3} =1随机化后的密文值可能是y_{1} =32,y_{1} =32,和y_{3} =48

那么再假设我们有一个明文序列X=0,1,0,1 ,那么最终的树可能如下图所示:

每一次插入新的节点的时候,不难看出,重复的明文可以作为具有相同明文结点的子节点,也可以作为具有不同明文结点的子节点,这取决与我们算法2中coin的随机取值情况。

由于相比于正式的算法\Pi _{FHOPE},我们在算法2中添加了递归输入t,所以相应的解密算法调用Decrypt (x)最终会递归到Decrypt(x, root(T ))

· 安全性证明

通过构造一个加密模拟器,为两个挑战序列中的每一个产生相同的输出来证明。因此,计算的不可区分性源于将随机源实现为伪随机函数而不是任何其他硬度假设。模拟器的算法如下:

 而对于算法5中的coin的随机取法,这里也定义了一个随机算法:

 算法7的输出是确定性的,而\gamma _{i}\gamma _{v}的选择则由算法6决定。算法6在所有可能的随机顺序中均匀地选择一个随机顺序。由于每个随机顺序的结果是不同的二叉搜索树,而随机coin函数的每个输出也产生不同的二叉搜索树,因此算法7的输出与统一的随机coin算法是难以区分的。所以在算法中敌手赢得 Game_{FAOCPA} (\lambda )的概率减去\frac{1}{2} 是可忽略级别的。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/53215.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

论文阅读:Video Object Segmentation and Tracking A Survey

论文名字 Video Object Segmentation and Tracking A Survey 来源 arXiv 论文地址&#xff1a;http://arxiv.org/abs/1904.09172?contextcs.CV 年份 2019.4.26 作者 RUI YAO, GUOSHENG LIN, SHIXIONG XIA, JIAQI ZHAO, YONG ZHOU 核心点 对现有的VOST算法进行分…

「都是url惹的祸」(问题:小数点参数被截取|刷新页面找不到资源)

问题背景&#xff1a; 在开发的时候有个页面跳转的需求点并且需要带着五个参数飞过去&#xff0c;其中包含版本号&#xff08;就是有小数点的数字&#xff0c;这也是遇到的一个问题一会聊一哈&#xff09;&#xff0c;本来触发完事件横跳过去没有问题&#xff0c;寻思着看一下N…

mysql用户名不存在_dedecms系统后台登陆提示用户名密码不存在

dedecms最近被曝有非常多的安全漏洞&#xff0c;最近有些用户反应后台管理员账号密码没有修改但无法正常登陆&#xff0c;提示用户名不存在&#xff0c;经研究发现是程序漏洞管理员被直接篡改&#xff0c;解决方案如下。 一、请先使用phpmyadmin登陆mysql管理&#xff0c;虚拟主…

桂林三金,吃不到中药股红利

如果说&#xff0c;国货品牌崛起的大潮本质上是国家的崛起&#xff0c;而非货的崛起。那么&#xff0c;中药的一时火热&#xff0c;靠的也不是疗效&#xff0c;是文化自信。 文化自信改变不了中药的疗效&#xff0c;但可以提升消费者对中药的信心。片仔癀靠着独家秘方&#xf…

如何实现沉浸式旅游与非物质文化遗产的共同发展

中国非物质文化遗产资源丰富&#xff0c;是世界上非物质文化遗产数量最多的国家。丰富多样的资源为非物质文化遗产旅游业的建设提供了良好的基础。非物质文化遗产旅游是基于非物质文化遗产资源开发的文化旅游消费形式。文化资源包括各民族代代相传的传统文化表现形式。非物质文…

@河南省文旅厅 携手让非遗“活”起来!

太极拳申遗成功两周年之际 河南省文化和旅游厅联合百度智能云 打造的“太极拳一张图” 正式上线啦&#xff01; 河南省是我国非物质文化遗产资源大省&#xff0c;此次推出的“太极拳一张图”正是河南省贯彻落实二十大精神&#xff0c;深入推进非遗数字化保护体系建设和传播推广…

小红书百万博主如何炼成?美妆博主专访

“在小红书上如何快速涨粉&#xff1f;”是大家长期以来的疑惑&#xff0c;为此我们找到了小红书美妆博主小颠儿kini&#xff0c;让我们看看他在成为百万博主的道路上都总结了哪些心得吧&#xff01; 采访手记&#xff1a;截止到发稿&#xff0c;美妆博主小颠儿kini在小红书上的…

基于Java Web技术的动车购票系统

毕 业 设 计 中文题目基于Java Web技术的动车购票系统英文题目Train ticket system based on Web JavaTechnology 毕业设计诚信声明书 本人郑重声明&#xff1a;在毕业设计工作中严格遵守学校有关规定&#xff0c;恪守学术规范&#xff1b;我所提交的毕业设计是本人在 指导教师…

什么是注意力机制?

Attention机制在近几年来在图像&#xff0c;自然语言处理等领域中都取得了重要的突破&#xff0c;被证明有益于提高模型的性能。 Attention机制本身也是符合人脑和人眼的感知机制&#xff0c;这次我们主要以计算机视觉领域为例&#xff0c;讲述Attention机制的原理&#xff0c…

深入理解注意力机制(Attention Mechanism)和Seq2Seq

学习本部分默认大家对RNN神经网络已经深入理解了&#xff0c;这是基础&#xff0c;同时理解什么是时间序列&#xff0c;尤其RNN的常用展开形式进行画图&#xff0c;这个必须理解了。 这篇文章整理有关注意力机制&#xff08;Attention Mechanism &#xff09;的知识&#xff0…

Attention注意力机制学习(一)------->SENet

目录 前言 论文 注意力机制 Squeeze-and-Excitation (SE) 模块 第一步Squeeze(Fsq) 第二步excitation(Fex) SE注意力机制应用于inception和ResNet 前言 在深度学习领域&#xff0c;CNN分类网络的发展对其它计算机视觉任务如目标检测和语义分割都起到至关重要的作用&…

Attention,Multi-head Attention--注意力,多头注意力详解

Attention 首先谈一谈attention。 注意力函数其实就是把一个query&#xff0c;一个key-value的集合映射成一个输出。其中query&#xff0c;key&#xff0c;value&#xff0c;output&#xff08;Attention Value&#xff09;都是向量。输出是values的加权求和&#xff0c;是qu…

1.注意力机制

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 参考&#xff1a;注意力机制 文章目录 前言一、注意力机制1.非参注意力池化层K(x-x~i~)的选择 2.参数化的注意力机制3.小结 二、注意力分数一维注意力分数拓展到高纬度1.加性…

注意力机制(Attention)

注意力机制分类 包括软注意力机制&#xff08;Soft Attention&#xff09;和硬注意力机制&#xff08;Hard Attention&#xff09;。 硬注意力机制指随机选择某个信息作为需要注意的目标&#xff0c;是一个随机过程&#xff0c;不方便用梯度反向传播计算。软注意力机制指在选…

Attention机制理解笔记(空间注意力+通道注意力+CBAM+BAM)

Attention机制理解笔记 声明Attention分类(主要SA和CA)spitial attentionchannel attentionSA CA(spitial attentionchannel attention)加强SACA理解 空间注意力机制和通道注意力机制解释attention机制Attention模型架构1.空间注意力模型(spatial attention)2.通道注意力机制3…

【Attention】注意力机制在图像上的应用

【Attention】注意力机制在图像上的应用 [SeNet] Squeeze-and-Excitation Networks &#xff08;CVPR2018&#xff09;[Non-local] Non-local neural Networks &#xff08;CVPR2018&#xff09;[GCNet] Non-local Networks Meet Squeeze-Excitation Networks and Beyond 2019-…

注意力机制(Attention Mechanism)-SENet

引言 神经网络中的注意力机制&#xff08;Attention Mechanism&#xff09;是在计算能力有限的情况下&#xff0c;将计算资源分配给更重要的任务&#xff0c;同时解决信息超载问题的一种资源分配方案。在神经网络学习中&#xff0c;一般而言模型的参数越多则模型的表达能力越强…

BahdanauAttention与LuongAttention注意力机制简介

在使用tensorflow时发现其提供了两种Attention Mechanisms&#xff08;注意力机制&#xff09;&#xff0c;如下 The two basic attention mechanisms are: tf.contrib.seq2seq.BahdanauAttention (additive attention, ref.)tf.contrib.seq2seq.LuongAttention (multiplicat…

注意力机制详解系列(一):注意力机制概述

👨‍💻作者简介: 大数据专业硕士在读,CSDN人工智能领域博客专家,阿里云专家博主,专注大数据与人工智能知识分享。公众号: GoAI的学习小屋,免费分享书籍、简历、导图等资料,更有交流群分享AI和大数据,加群方式公众号回复“加群”或➡️点击链接。 🎉专栏推荐: 目…

深入理解图注意力机制(Graph Attention Network)

©PaperWeekly 原创 作者&#xff5c;纪厚业 学校&#xff5c;北京邮电大学博士生 研究方向&#xff5c;异质图神经网络及其应用 介绍 图神经网络已经成为深度学习领域最炽手可热的方向之一。作为一种代表性的图卷积网络&#xff0c;Graph Attention Network (GAT) 引入了…