Witness Encryption 中可以使用一個 NP 語言 L
(對應一個關係 R
)的一個實例 x
加密一段訊息,對於知道某個 w
使 R(x, w)
成立的人可以解密,而若某 x
不存在於 L
中,則沒有多項式時間的攻擊者可以分辨任兩個具有相同長度原文的密文。值得注意的是,加密者不一定知道 x
是否存在於 L
中。[1] 以更白話的說法,我們可以找到一個 NP 問題,但不必要知道這個問題是否有解,而利用這個問題對某段訊息加密,接著交給可能知道的人解密。例如在 Goyal and Goyal[2] 中利用某筆紀錄對於某個 PoS 區塊鏈的存在條件中作為 NP 問題並對某電路進行加密,因此這個電路只有在區塊鏈將某筆紀錄上鏈後才可執行,也只能執行一次。