公平的无连接可分电子现金方案.pdfVIP

第21卷 第3期 青 岛大 学学报 (自然科 学版 ) Vol_21No．3 2008年 9月 JOURNALOFQINGDAOUNIVERSITY (NaturalScienceEdition) Sep．2008 文章编号 ：1006—1037(2008)03—0070—05 公平的无连接可分电子现金方案 于永波，宋智玲 ，贾小珠 (青岛大学 信息X-．程学院，山东青岛266071) 摘要 ：基于二叉树 、比特承诺 、零知识证 明等技术提出了一种具有完全无连接性 ，无需可 信第三方参与的、公平的可分 电子现金方案 。方案的开户协议和取款协议复杂度均为 0(N+K)，用户花费任意一个节点的电子现金时间复杂度为 0(poly(K) ·polylog (N))，存款协议的时间复杂度与支付协议相同。方案的安全性基于强 RSA问题假设、计 算离散对数困难 问题假设和单 向哈希函数的存在性假设。 关键词：电子现金 ；可分性 ；无连接性 ；无可信第三方 中图分类号：TP309．5 文献标识码 ：A 自1991年 Okamoto和 Ohta第一次提出基于二叉树的可分 电子现金系统以来 ，可分电子现金一直是电 子现金领域的研究热点_】 ]。在电子现金的可分性基础上，人们试图进一步实现 电子现金的无连接性、 克服对可信第三方(TrustedThirdParty，TTP)的依赖 ，并寻求新的构造技术以提高电子现金协议的执行 效率。2000年 Nakanish和Sugiyama在文献E35中提出了一个效率很高 的可分电子现金方案 ，所有协议执 行 的时间复杂度不超过 0((1ogN)。)，并且该方案中电子现金是无连接 的，但该方案存在支付过程 中泄露节 点位置信息的缺陷。2005年，JanCamenisch，SusanHohenberger等人在文献E4-]中给出了一种基于紧凑型 电子钱包 的可分电子现金方案 ，一个 电子钱包 中可以存储面值为 2 的电子现金 ，每个 电子现金可以被无连 接 的花费，最重要的是该方案的取款协议和支付协议的时间复杂度都降到了O(n+忌)，电子钱包的存储空间 也只需O(+忌)bits(k是安全参数)，但是该方案在追踪违法用户时仍需 TTP的参与 ；Camenisch等人同时 又给出了一个改进 的方案 ，解决 了对 TTP的依赖问题 ，很好地保护了用户的隐私权 ，但代价是开户协议和支 付协议的时间复杂度分别增长到了O(n·忌+k。)和 O(n·忌)。本文在文献E33的基础上，提出了一种具有完 全无连接性、公平的、无需TTP参与的可分电子现金方案。通过运用高效的交互式零知识证明，使得方案的 取款协议和支付协议具有较高的执行效率；基于二叉树技术，实现了电子现金的可分性和完全无连接性(不 会泄露节点位置信息)且在追踪违法用户时无需TTP的参与 ；在匿名控制方面 ，对于用户、银行和商家来说 是公平的。 1 方案设计 1．1 预备知识 1．1．1 零知识证明 相关知识的证明：PK{(a，卢，…)：PredAPred。A…)表示一个关于整数a，，…知识 的零知识证明，他们 满足表达式 Pred ，Predz，…，并且 a，，…出现在指数位置。 方案使用以下形式的零知识证明： 收稿 日期 ：2008—05—09 作者简介 ：于永波(1982一)，男，硕士研究生，研究方向为信息安全。 第 3期 于永波 ，等 ：公平的无连接可分 电子现金方案 71 2)不同群中的两个 比特承诺值相等的知识证明：PK{(，)：—g zAy一一g雷z八O≤卢户 ； 3)一个 比特承诺值是另一个比特承诺值的离散对数的证明：PK{(a，』81，)：y=g 岛八 gg2“ }_8。 I．1．2 二叉树技术 在文献[3]描述的二叉树基础上，为了计算方便，引进一层辅助节点，构造一棵 z+1层的二叉树 。每个 节点n … 有一个F … 值与之关联，叶子节点不表示任何面值的电子现金，但是叶子结点同样具有 F值。 假设根节点的F值为F。，F … 一^ )Fi“，0，J一1，…，l，Fo