Witness Encryption
#cryptography
An encryption scheme which uses Exact Cover Problem
NP-complete Problem
暗号化されたメッセージの意図された受信者を最も一般的な方法で指定することができます。WEでは、メッセージは、NP言語Lのインスタンスϕに対して暗号化され、ϕ ∈ Lである場合、メッセージはϕの証人wを入力として必要とする効率的な復号アルゴリズムを介して回復できます。例えば、Sudokuパズルにメッセージを暗号化することができ、そのパズルの有効な解のいずれかで復号可能なWE暗号文が得られます。驚くべきことに、このプリミティブには、「受信者の鍵を認証するための信頼できる第三者」は必要ありません。WEでは、秘密の復号鍵は(認証されていない)証人そのものです。最近の進展にもかかわらず、NPのすべてのための標準的な仮定からの実用的なWEはまだ難しいものです。