不经意传输协议两种构造方法帽子怎么织
朱健东;张玉灵;黄根勋
【摘 要】不经意传输协议作为密码学的基础协议在实际生活中有很多应用,其构造方法分直接和间接构造两种.利用整数的t进制表示和DDH假设等概念,在Naor-Pinkas方案的基础上,给出了一个计算上更简单的协议间接构造方法,再借助现有公钥体制的同态性给出了不经意传输协议的直接构造方法.
【期刊名称】左耳英文《现代电子技术》
【年(卷),期】2007(030)021
【总页数】3页(P76-78)
有关劳动的古诗【关键词】不经意传输;同态加密;同态性;DDH假设
【作 者】朱健东;张玉灵;黄根勋
【作者单位】解放军63898部队,河南,济源,454650;郑州大学,升达经贸管理学院,河南,郑州,451191;解放军信息工程大学,河南,郑州,450001
【正文语种】中 文
胖子的幽默句子【中图分类】TN918.1
1 引 言
不经意传输协议作为一个密码学的基础协议，他的基本思想首先由Rabin[1]提出。在Rabin的不经意传输中，Alice想以某种方式发送某个比特给Bob，要求满足两条：一方面，Bob能以0.5的概率得到这条消息；另一方面，Alice不知道Bob是否获得了这条消息。不经意传输可以看成是抛硬币协议的特殊形式，虽然Rabin协议本身看上去似乎只是一个游戏，并没有什么实际意义，但研究者们敏锐地感觉他可能很有用。后来，Even[2]和Brassard[3]等人进一步给出了和的概念。随着研究的深入，不经意传输协议广泛地应用于其他的密码学协议中，例如比特承诺、零知识证明、保密信息检索、公平电子合同的签订等，而这些协议在电子商务和电子政务等领域对信息安全的保护发挥着越来越重要的作用[4,5]。
2 预备知识
2.1 基本概念
定义有n个秘密，想将其中之一交给Alice，Alice得到一个秘密，但Bob不知道Alice得到的是哪一个。
的方法有两种：第一种是首先构造然后执行多轮来实现第二种是直接利用密码学基础技术构造一般看来，的直接构造方法往往计算复杂度较大，达到O(n)。Moni Noar和Beny Pinkas在文献[6]中把转化成log2n个使得他的计算复杂度降低到O(log2n)，而本文将把他进一步转化成q个其中tq=n。由于q是可变的，我们可以选择最佳的q使得计算复杂度最小。
但是，的间接构造最终还是要转到直接构造上来，我们发现很多现有公钥加密时都具有同态性，因此将利用这种性质直接构造
的安全性和计算复杂度
是一个双方协议，分为输入和输出两部分。
输入：
发送者：X1，X2，…，Xn；
接收者：选择i，1≤i≤n。
输出：
接收者：Xi；
发送者：无。
协议分两个阶段：初始化和传输阶段。考虑到发送者可能在传输的过程中改变消息的内容，要求Bob在消息传输前进行预处理，即在初始化阶段他用n个密钥对n个消息处理(承诺)，然后把处理的结果全部发给Alice，这里的承诺可以采用文献[7]的方案。传输阶段Alice首先选择i：1≤i≤n，然后与Bob执行协议，获得密钥，进而获得Xi。
(1) 安全性
协议的安全性从发方和收方两个角度考虑：
发方的安全性 在执行完协议之后，接收者不能获得除选择之外的其他消息的任何信息。
收方的安全性 发送者执行完协议之后，不知道接受者获得了哪个消息。
(2) 计算复杂度
陷入僵局考虑到公钥运算和指数模运算的相对困难性，复杂度只计算发方和收方分别作公钥运算和指数模运算的次数。
3 不经意传输协议的间接构造
我们的协议基于下面的Decisional Diffie-Hellman假设。
定义2 (DDH假设)g是循环群Gg的生成元，a，b，c是Gg随机选取的三个数，则区分三元组(ga,gb,gab)和(ga,gb,gc)是困难的。
方案1 n条消息编号为0,1,…,n-1,并将他们写成t进制，其中n=tq，则每条消息可以由q位数表示他。∀i∈{0,1,…,n-1}，i=i1i2…iq，0≤i1,i2,…,iq≤t-1。g是有限域上的本原元。
(1) 初始化
① Bob随机的选择q个数组：
(a(0,0),a(1,0),…,a(t-1,0)),(a(0,1),a(1,1),
僰人…,a(t-1,1)),…,(a(0,q-1),a(1,q-1),…,
a(t-1,q-1))
生成密钥得到Yi=CommitKi(Xi)；
羞辱意思
② Bob把Y0，Y1，…，Yn-1全部交给Alice。
(2) 传输阶段
① Bob随机的选择q个数r0，r1，…，rq-1，分别用来随机化上述的q个数组，得到：
(a(0,0)r0,a(1,0)r0,…,a(t-1,0)r0),(a(0,1)r1,
a(1,1)r1,…,a(t-1,1)r1),…,(a(0,q-1)rq-1,
a(1,q-1)rq-1,…,a(t-1,q-1)rq-1)
② 如果Alice想得到第i条消息，i=i0,…,iq-1执行q次协议，Alice得到a(ij,j)rj，j=0,1,…,q-1；
③ Bob把g1/(r0r1…rq-1)发给Alice；
④ Alice恢复密钥：
Ki=(g1/(r0r1…rq-1))(a(i0,0)r0)(a(i1,1)r1)…(a(iq-1,q-1)rq-1)
得到Ki，Xi=CommitKi(Yi)。
定理1 在承诺方案安全和DDH假设下，执行k轮上述的协议，Alice至多获得k条消息，Bob不知道Alice的选择。
该方案的计算复杂度在很大程度上取决于具体的的计算复杂度。Wen-Guey Tzeng在文献[8]中的一个需发方做2n次指数模运算，收方做2次指数模运算。如果先用上述方案把转化成q个再采用文献[8]的方案执行这样发方需做n+2qt+1次指数模运算，收方需做2q+1次指数模运算，我们发现t=3是最佳的。当然，如果想进一步减少计算复杂度，可采用和一致生成器[6]生成承诺密钥，而不用指数模运算，这样上述协议的计算复杂度只取决于q个的复杂度，当n很大，这种下降的幅度是很大的。
4 不经意传输协议的直接构造
4.1 公钥密码体制的同态性
4.1.1 同态公钥密码体制
令Π=(GΠ,E,D)是一个公钥密码体制，其中G是密钥生成算法，GΠ:1k|→(x,Κ)，E是加密算法，EΚ:(m;r)|→EΚ(m;r)，D是解密算法，DΚ:|→DΚ(c)。假设对任意私钥x，相应的明文空间MΠ(x)和密文空间CΠ(x)分别是定义了“+”运算和“·”的Abel群，随机数空间记为RΠ(x)。
对二元运算∘，RΠ(x)2|→RΠ(x)，若EΚ(m1;r1)·婚姻登记机关
EΚ(m2;r2)=Ek(m1+m2;r1∘r2)，我们说Π是同态的。
最早的同态语义安全的公钥加密算法是1984年提出的ElGamal体制[8]。
4.1.2 RSA和Rabin公钥加密体制的同态性
通过研究发现，我们所熟知的RSA和Rabin公钥体制也具有同态性，这里只阐述RSA的同
态性。设n=pq，p，q是两个保密的大素数。选择一个整数e，满足1<e<φ(n)，且gcd(φ(n),e)=1，其中φ(n)是n的欧拉常数。计算d，满足de≡1 mod φ(n)。{e,n}为公钥，{d,n}为私钥。设m1，m2是明文空间中的两个元素，则：
4.2 基于同态加密的不经意传输协议
协议1 一般化的同态不经意传输协议
初始化:S用不同的密钥ki承诺每个消息，承诺值Yi=Commitki(mi)，并生成自己的同态公钥加密算法(EΚ,DΚ),将EΚ公开,选择随机数ri∈RΠ(x),并将EΚ(ki;ri)和Yi交给收方R，i=1,2,…,n。
传输阶段:
① R选择随机数tσ,rσ′，把cσ=EΚ(kσ;rσ)·EΚ(tσ;rσ′)发送给S；
② S解密cσ得到kσ+tσ并发送给R；
③ R由kσ+tσ得到kσ，进而由承诺Yσ恢复一个消息。
协议的正确性：如果S和R都是诚实的，那么cσ=EΚ(kσ+tσ;rσ∘rσ′)，kσ=DΚ(cσ)-tσ，因此可以恢复S的一个消息。
定理2 在同态公钥加密体制的语义安全和承诺方案的安全的假设下，执行完上述的不经意传输协议后， R只能得到S的一个消息，S不知道R的选择。
证明：发方安全性：如果R想从承诺值中获得消息，只能从EΚ(ki;ri)中获得ki，这与同态公钥加密体制的语义安全性矛盾；
收方安全性:S只能从kσ+tσ获得关于R的选择的信息。由于tσ相对S的不可知性，对某一个mσ和tσ及任意mσ′，总存在tσ′使得kσ+tσ=kσ′+tσ′，即S不知道R获得的是哪个消息，R的选择是无条件安全的。
