單向函數
未解決的計算機科學問題:單向函數存在嗎?
单向函数(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,使得
参见编辑
參考資料编辑
- ^ 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
🔥 Top keywords: Baike: 首页Special:搜索胖猫跳江事件背着善宰跑九龍城寨之圍城逆天奇案2璩静淚之女王歌手2024Energy (組合)新生 (网络剧)习近平匈牙利邊佑錫劉俊謙 (香港)金智媛神耆小子塞尔维亚金秀賢 (男演員)母亲节猩球崛起:王國誕生九龍寨城馴鹿寶貝家族榮耀之繼承者Seventeen (組合)六四事件不夠善良的我們张维为楊佩潔TripleS支配物种庆余年郭葦昀洪若潭命案金惠奫2024年英雄联盟季中邀请赛春色寄情人BABYMONSTER笑看風雲乘風2024排球少年!!角色列表破墓徐巧芯中华人民共和国中華民國打天下2WIND BREAKER—防風少年—习明泽排球少年!!彭丽媛磁暴ILLIT贾斯汀·比伯逆天奇案BOYNEXTDOOR猿人爭霸戰:猩凶革命張書偉我的婆婆怎麼那麼可愛我獨自升級怪獸8號謝坤達IVE (組合)與鳳行關於我轉生變成史萊姆這檔事角色列表黃道十二宮福建號航空母艦虽然不是英雄葉乃文五月天張員瑛草榴社区張文傑2024年花蓮地震极光香緹·摩爾迷宮飯呂家愷搜查班長1958日本劉德華海莉·鮑德溫蕭景鴻越位 (足球)葬送的芙莉蓮周處除三害 (電影)毛泽东願榮光歸香港林峯周雨彤伍允龍羅毓儀香港Baike: 分類索引沒有秘密猩球崛起:終極決戰角質層唐振剛柯佳嬿文化大革命