單向函數

維基百科,自由的百科全書
跳至導覽 跳至搜尋
未解決的計算機科學問題單向函數存在嗎? Question mark2.svg

單向函數 (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,使得

參見[編輯]

  1. ^ 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)
  2. ^ Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography". Summer course on cryptography, MIT, 1996–2001