没有合适的资源?快使用搜索试试~ 我知道了~
模指数外包方案ExpSOS的格基密码分析.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 87 浏览量
2022-11-28
20:29:46
上传
评论
收藏 58KB DOCX 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/87192004/0001-51f8c59c7745cfe3360f81e33ed8c5c7_thumbnail-wide.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
15页
模指数外包方案ExpSOS的格基密码分析.docx
资源推荐
资源详情
资源评论
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/release/download_crawler_static/87192004/bg1.jpg)
模指数运算又称模幂运算,其作为一种基本运算广泛应用于 RSA 密码体制
[1]
和 DSA(digital sign-ature algorithm)的签名算法
[2]
中。通常地,指数长 n 比
特时大约需要执行 1.5n 次模乘操作,这对于计算资源有限的本地设备来说代价
十分昂贵。因此,研究模指数的安全外包具有重要的理论与现实意义。根据方
案所基于的安全模型,现有的外包方案可分为两类:基于双服务器的外包方案
和基于单服务器的外包方案。
基于双服务器的 方 案将输入的数据在本地端分成两部分并分别发 送给两
个互不串通的服务器,便于底数指数的逻辑拆分与加解密设计。Hohenberger
等
[3]
首次给出了外包计算的安全模型的形式化定义并提出了基于双服务器模型
的模指数外包协议。然而,在他们的协议中,服务器可以 12 概率欺骗用户。随
后,Chen 等
[4]
基于一种新的底数与指数逻辑拆分方法,设计了一种新的双服务器
模指数外包算法,改进了 Hohenberger 等的方案的效率,并将可验证概率提高到
23。Ye 等
[5]
进一步优化了之前的底数与指数拆分方法,分别针对单模指数与双
模指数运算提出了两种新的外包方案,在保持可验证性概率不变的情况下进一
步提高了外包算法的效率。最近,Fu 等
[6]
提出了一种新的高效、可验证的模指
数外包算法,该算法利用 EBPV 生成的随机整数提高了效率,并且可验证性概率
达到最优的 1。总的来说,双服务器方案一般可以节省比单服务器方案更多的计
算开销,但其安全性假设高,无法抵御服务器共谋攻击。
单服务器的外包方案只使用一个服务器,安全性假设低,不需要考虑共谋的
情况,但单服务器的方案节省计算开销不如双服务器有优势,当前单服务器外包
方案,本地端大多需要执行一个小秘密指数的模指数运算。一般地,该指数的大
小决定了方案的效率,其机密性决定着方案的安全性。Dijk 等
[7]
提出了第一个基
于单个不可信服务器来加速模幂的算法,但是他们的算法不能同时保证底数和
指数的安全。在 ESORICS 2014 中,Wang 等
[8]
提出了一个同时保护底数与指数
的安全外包模幂运算的通用算法。但是,它们算法的可验证概率仅为 12,且容易
遭受格算 法攻击
[9]
。随后,Ding 等
[10]
设计了一 种新的安 全外包算 法,用户能 以
119120 的概率检测出云服务器的欺诈行为。Li 等
[11]
与 Fu 等
[12]
相继考虑并设计
了模数为合数时的模幂运算的外包算法,并声称他们算法可验证概率可以达到
最优的 1。然而 Rangasamy 等
[13]
分析了他们的方案,并给出了相应的伪造攻击。
以上方案均未考虑模数的隐私性,Zhou 等
[14]
设计了第一个同时保护底数、指数
![](https://csdnimg.cn/release/download_crawler_static/87192004/bg2.jpg)
与模数的单服务器外包方案。最近,Chevalier 等
[9]
全面比较分析了当前单服务
器外包方案的优缺点,并给出了各种场景下的最优构建。
在 文 献 [14] 中 ,Zhou 等 提 出 了 一 种 基 于 单 个 服 务 器 的 模 指 数 外 包 方 案
ExpSOS,旨在安全高效地实现本地端模指数的计算。文中证明了其方案能保护
本地端底数 u、指数 a 和模数 N 的机密性,并能以高概率检测出服务器端的恶
意 行 为 。 最 近 , 在 文 献 [13]中 ,Rangasamy 等 模 仿 Chevalier 等
[9]
的 攻 击 , 对
ExpSOS 进行了简略的安全分析,他们的攻击假设用户调用了两次外包算法且
要求两次外包的模指数运算的指数相同,这样的攻击条件是十分严格的。本文
对 ExpSOS 进行了更全面的评估。具体来说,本文的贡献可以概括如下:
(1)对方案进行了唯密文分析,指出了方案潜在的弱密钥。通过将方案弱
密钥的求解转化为模线性多项式的小整数解问题,调用 Coppersmith 的格基构
造求解算法,仅利用密文就可以在多项式时间内恢复方案中的多个私有参数。
(2)为避免弱密钥攻击,详细估计了安全应用场景下底数和方案中安全参
数选取的规模。
(3)实验给出了数字签名标准推荐参数下 Exp- SOS 方案的弱密钥攻击
实例,验证了理论分析的正确性。
1 预备 知识
1.1 常用 符 号 及 其 含 义
一般地,本文用小写加粗字母表示列向量。表 1 列出了文中常用的专用符
号及数学函数。
表 1 符号说明
Table 1 Symbol description
符号
说明
Rm
m 维实数向量集
Z
整数集
Zn
n 维整数向量集
det(·)
行列式函数
![](https://csdnimg.cn/release/download_crawler_static/87192004/bg3.jpg)
符号
说明
||·||
欧氏范数
φ(·)
欧拉函数
e
欧拉常数
lb
以 2 为底的对数
新窗口打开| 下载 CSV
1.2 格与 相 关 不 变 量
作为一种经典的数学对象,格在解决计算机科学中的许多计算问题,特别是
在密码学领域发挥着重要的作用
[15⇓ ⇓ -18]
。
定义 1(格) 有 n 个线性无关的 m 维向量 b1b2⋯bn∈Rm,由{b1b2⋯bn}张
成的格 L 定义为:
L=L(B)=∑i=1nxibi|xi∈Z={Bx|x∈Zn},其中,B=[b1b2⋯ bn]是格 L 的一个 基 ,
称 m 为格的维数,n 为格的秩。若 m=n,则称之为满秩格。格 L 的行列式定义为。
det(L)=(det(BBT))12。如果 L 满秩,则有 det(L)=|det(B)|。在本文中,只使用满
秩格。格中最短向量的范数与格的行列式有如下关系:
定理 1(Minkowski 定理
[19]
) 设 L 为秩为 n 的格,存在非零向量 v 使得:
||v||≤ndet(L)1n
(1)
1982 年,著名的 LLL 算法
[20]
提出,它可以在多项式时间内找到格 L 的一个由
“短”向量组成的约化基,其具有以下性质:
定理 2
[21]
设 L 为秩为 n 的格,在多项式时间内,LLL 算法可以输出一系列约
化基向量 vi,1≤i≤n,满足:
||v1||≤||v2||≤⋯≤||vi||≤2n(n-1)4(2+1-i)det(L)1n+1-i
1.3 多项 式 范 数
定义 2(多 项 式 范 数 ) 对 于 任意 整 系 数 多 项 式 函 数 f:Zn→Z,记 f(x1,x2,
⋯,xn)=f1x1+f2x2+⋯+fnxn,其范数定义为。||f(x1,x2,⋯,xn)||=f12+f22+⋯+fn2。
剩余14页未读,继续阅读
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/3f07197aad004e4fa57ac5a008eb6aaf_weixin_57147647.jpg!1)
罗伯特之技术屋
- 粉丝: 3907
- 资源: 1万+
![benefits](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-1.c8e153b4.png)
下载权益
![privilege](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-2.ec46750a.png)
C知道特权
![article](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-3.fc5e5fb6.png)
VIP文章
![course-privilege](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-4.320a6894.png)
课程特权
![rights](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-icon.fe0226a8.png)
开通VIP
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)