基于隐藏数问题对广义SRA智力扑克协议的安全性研究.pdfVIP

基于隐藏数问题对广义SRA智力扑克协议的安全性研究 基于隐藏数问题对广义SRA智力 扑克协议的安全性研究’ 苏东 吕克伟 中国科学院研究生院信息安全国家重点实验室 的。该协议可以做到在没有可信第三方的情形下，互不信任的两方可以相互给对 方发牌而又不能欺骗对方。但是由于该协议中的加密函数会泄露明文的部分信息， 使得协议恶意参与方可以在一定程度上影响协议的必威体育官网网址性与公平性。本文针对此 题给出了z：上的广义SRA智力扑克协议，有效地弥补了SRA智力扑克协议的这 个缺陷；并利用隐藏数问题的研究结果对广义SRA智力扑克协议的安全性进行了 分析，证明广义SRA智力扑克协议中洗牌方的置换和密钥的安全性分析可以通过 非一致多项时间算法归约为踢文的前[(109logp)／2+1]个最高有效位和洗牌方密 钥前[2109logp]个最高有效位的计算困难性上。 关键词：智力扑克隐藏数问题比特安全 1 引言 现代密码学主要是建立在一些数学问题的计算困难性上。一个问题是困难的 意味着很难找到它的精确解，但这并不意味着找到部分解或近似解也很难。比如， 当P为大素数时，有限域F。上的离散对数问题是困难的，但离散对数的最低有效 位(LSB：LeastSignificantBit)是很容易计算出来的。因此，有必要弄清楚找到 _个困难问题的近似解或部分解的难度与找到它精确解的难度之间的关系。换句 话说，要确定出能以不可忽略的优势在多项式时间内找到精确解所需要的最少信 息，以及确定出和精确解一样难于计算的部分信息，这就是隐藏数问题。所谓隐 家重大研究计划“973”(No．2007CB311202)的支持。 ·137· 第十八届全国信息必威体育官网网址学术会议(IS2008)论文集 Number 藏数问题(HiddenProblem，简记为HNP)是指已知若干个随机数石E F。 年提出的，近年来已经被广泛应用于分析单向函数、密码系统及相关困难问题的 的密钥安全性可以归约到该密钥eggP+loglogP个最高有效位(MSB)的计算困 难性上，即计算出密钥的√log P+loglogP个最高有效位与计算出整个密钥一样困 难，在文献[4]中他们又证明了在非一致模型下最有效比特的个数可以减少到 2109logP。在密码系统的比特安全性方面，还证明了EIGamal密码体制、Shamir消 息传递机制、XTR和LUC协议等密码系统的比特安全性。在对密码系统的攻击方 面，已完成对数字签名算法(DSA)、基于椭圆曲线的数字签名算法(ECDSA)和 Nybcrg-Rueppel签名机制的攻击。在伪随机数生成器的构造方面，已利用模逆的隐 藏数问题构造出了高效的伪随机生成器。目前，隐藏数问题到已经有很多种扩展 形式，也得到了广泛的应用¨1|，其主要研究方法均是利用指数和的界和格 约减m】。 在网络环境下进行的扑克游戏称为智力扑克，同真实世界中的扑克游戏一样， 智力扑克协议也要满足可用性、安全性、公平性和可审计性。智力扑克协议可分 为两种类型：有可信第三方的协议和无可信第三方的协议。第一个无可信第三方 力扑克协议。该协议可以做到在没有可信第三方的情形下，互不信任的两方可以 相互给对方发牌而又不能欺骗对方。但是由于该协议中的加密函数会泄露明文的 部分信息，使得协议恶意参与方可以在一定程度上影响协议的必威体育官网网址性与公平性。 议，从而得到不泄露任何部分信息的智力扑克协议。 在本文中，我们给出了zf上的广义SRA协议，该协议以确定方式弥补了 SRA协议的缺陷，并利用隐藏数问题的结果对协议的安全性进行了分析，把整个 协议的安全性非一致多项时间归约到明文前[(109logp)／2+1]个最高有效位和第 二个参与方秘密密钥前[2109logP]个最高有效位的计算困难性上。 符号与约定： [／gsp’]。 (2)髯l．一，确∈Rzi表示从zi中均匀独立选取d个数。 ·138· 基于隐藏数问题对广义SRA智力