有界单向函数的通用求逆算法研究

• 作者: 刘吉强 薛锐
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 密码学 单向函数 有界单向函数 可忽略函数 求逆算法
• 年，卷（期）: 2006,（9）
• 所属期刊栏目: 密码学基础、密码算法和密钥管理
• 页码范围: 1603-1607
• 页数: 5页
• 分类号: TP3
• 字数: 564字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2006.09.013

摘要

有界单向函数是一个新的密码学概念.有界单向函数是为了研究设计更为灵活、更实用的密码系统的基础而提出的.该文的作者在以前的文章中,对有界单向函数与一般单向函数的关系进行了探讨,从而得到一般单向函数的一个刻画.由于单向函数的存在性与计算机科学中一系列重要未决的问题相联系,其本身的存在性是一个未决的问题.有界单向函数的研究对一般单向函数存在性的研究提供了一个新的途径.从它们之间的关系来看,如果对任意正整数c,存在c-单向函数,那么一定存在单向函数.鉴于现代密码学对单向函数的依赖性,对单向函数的存在性的研究具有重要的意义.该文进一步探讨有界单向函数的困难性.由于单向函数的存在性被规约到了有界单向函数的存在性,该文章着眼于固定的有界单向函数的研究.文中的主要结果是:对任意正整数c,存在一个被称为关于所有c-有界单向函数的通用c-有界算法,满足对于充分大的n,这个算法求逆的成功概率是所有c-有界算法求逆的成功概率的上界.从而给出了一个关于c-单向函数的刻画.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	薛锐	中国科学院软件研究所信息安全国家重点实验室	20	275	7.0	16.0
2	刘吉强	北京交通大学计算机与信息技术系	66	535	13.0	21.0