^Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" （页面存档备份，存于互联网档案馆）. Summer course on cryptography, MIT, 1996–2001
一月 04, 2023
單向函數, 此條目可参照英語維基百科相應條目来扩充, 2017年6月, 若您熟悉来源语言和主题, 请协助参考外语维基百科扩充条目, 请勿直接提交机械翻译, 也不要翻译不可靠, 低品质内容, 依版权协议, 译文需在编辑摘要注明来源, 或于讨论页顶部标记, href, template, translated, page, html, title, template, translated, page, translated, page, 标签, 未解決的計算機科學問題, 存在嗎, 单向函数, function, 是一. 此條目可参照英語維基百科相應條目来扩充 2017年6月 若您熟悉来源语言和主题 请协助参考外语维基百科扩充条目 请勿直接提交机械翻译 也不要翻译不可靠 低品质内容 依版权协议 译文需在编辑摘要注明来源 或于讨论页顶部标记 a href Template Translated page html title Template Translated page Translated page a 标签 未解決的計算機科學問題 單向函數存在嗎 单向函数 One way function 是一种具有下述特点的单射函数 对于每一个输入 函数值都容易计算 多项式时间 但是对于一个随机的函数值 算出其对应的输入却比较困难 无法在多项式时间内使用确定性图灵机计算 单向函数是否存在仍然是计算机科学中的一个开放性问题 事实上 如果单向函数存在 将证明复杂性类P NP问题中 P不等于NP 1 ex 2 2 page 70与之相对 P不等于NP的假设并不能直接推出单向函数的存在 2 实践中 常将 容易计算 和 不容易计算 定义为 对于合法用户容易计算 对于恶意用户不容易计算 从这个意义上 密码散列函数可以被当作单向函数 这是因为 虽然单向函数可能根本不存在 也无人能证明一个散列函数真的是单向函数 但也无人发现可以在合理时间内破解它们的实用算法 理论定义 编辑函数f 0 1 0 1 是一个单向函数当且仅当f可以用一个多项式时间的算法计算 但是对于任意一个以x为输入的随机化多项式算法A 任意一个多项式p n 和足够大n 使得 P r x 0 1 n f A f x f x lt 1 p n displaystyle Pr x in 0 1 n f A f x f x lt frac 1 p n 参见 编辑陷門函數 英语 Trapdoor function 參考資料 编辑 Oded Goldreich 英语 Oded Goldreich 2001 Foundations of Cryptography Volume 1 Basic Tools draft available 页面存档备份 存于互联网档案馆 from author s site Cambridge University Press ISBN 0 521 79172 3 see also http www wisdom weizmann ac il oded foc book html 页面存档备份 存于互联网档案馆 Goldwasser S and Bellare M Lecture Notes on Cryptography 页面存档备份 存于互联网档案馆 Summer course on cryptography MIT 1996 2001 取自 https zh wikipedia org w index php title 單向函數 amp oldid 73314495, 维基百科，wiki，书籍，书籍，图书馆，
