紛失通信プロトコル

暗号理論において、紛失通信（ふんしつつうしん、Oblivious Transfer、以下OTと記す）とは、暗号プロトコルの一種で、送信者が送信したデータのうち、受信者がどれを受信したのか、送信者が知ることができないようなプロトコルである。忘却送信ということもある。1981年にマイケル・ラビンが提案したRabin-OTが最初のOTである。

落とし戸置換(厳密には、enhanced trapdoor permutation)が存在すれば、OTが存在することが示されている。

Rabin-OT

チューリング賞を受賞したマイケル・ラビンが考えた暗号技術であり、一方向性関数と並んで最も重要なものとなっている。彼のプロトコルは、紛失通信路をラビン暗号を使いシミュレートするというものであった。すなわち、この方式を使うと、1/2の確率で相手にメッセージが届き、残りの1/2の確率でメッセージが一切届かない。さらに送信者は、受信者にメッセージが届いたかどうかが一切分からないという一見役に立たなさそうなものであった。しかしながら、この風変わりな暗号技術は、後にYaoのGarbled Circuit等の暗号プロトコルを設計していく上で、重要な役割を担うことになる。

1-out of-2 OT

送信者は2個のメッセージを送信し、受信者はその片方のみを受信することができ、送信者は、受信者がどちらのメッセージを受信したのかは知ることができないタイプのOTである。

1-out of-2 OTを拡張することで、n個のメッセージのうちk個を受信する k-out of-n OT が構成できることが知られている。

参考文献

• M.O.Rabin, "How to exchange secrets by oblivious transfer", Technical Report TR-81, Harvard University, 1981.