【研究】Lossy Trapdoor Functions and Their Applications (Peikert, Waters) [STOC'08]

今更．
Lossy TDFsというプリミティブを提案し，それのblack-box-useでアプリケーションを提案．
DDH，LWH　→　lossy TDFs　→　CPA, CCA, OT, TCRHF…

Lossy TDFsは，practicalに使われる関数はinjectiveだが，証明で使うことができる関数は写像先が小さい（lossy．statisticallyに入力がhidden），しかしその2つの関数はindというもの．

leftover hash lemmaはよく知らんが，どれくらいランダムっぽいbitをextractできるのかだと思っている．
そこらへんを評価すると結局，lossy TDFsに対してfamily of pairwise independent HFがハードコア関数となる．
CPAはそれをgoldreich,levin（だっけ）の方法，つまりメッセージをハードコアとex-orすることでマスク．

CCAについては，strong unforgeable one-time signatureを使って，DECできないcをクエリさせないあの方法．
メッセージはハードコア関数でマスク．
NIZKは使っていなくて，乱数を2つの関数でencryptすることによりcheckする．
このとき，lossy TDFsだけだとDECクエリに答えることが出来ないので（statisticallyにDECできない），ABO TDFs（overwhelmingにinjective，ただしある値でlossy）を使って，lossy TDFsがinjective→lossyとなっても答えられるようにしている．

DDHでのconstructionは，加法準同型なElgamalを使って，
要するにinjective→恒等写像，lossy→0行列をメッセージにかけてしまおうというもの．
しかし，lossyである（出力先空間を小さくする）ためにはもうちょっと工夫が必要で，数あるencryptの乱数部分を共通にしてやってencryptすることで，出力先を2^n→pにしている．