■

• なんでROMでの証明を俺が書いてんだって話ですよ, 本当に. RO嫌いな方なのに理解が進む進む.
• Benny Applebaum, David Cash, Chris Peikert, Amit Sahai “Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems” (CRYPTO 2009)
  • AppelbaumがLPN仮定からKDM-CPA secureなSKE, 線形分伸ばす準線形時間擬似乱数生成器, weak PVRF (だっけか?) を作ったので, 3人位加わって拡張したらしい. (AppelebaumのサイトにいったらTech. Rep.扱いの論文があった.)
  • LWE仮定からKDM-CPA secureなPKEが出来る. ただし関数は秘密鍵のアフィン変換みたいなもの. s∈Z_p^nを秘密鍵として, <s,t>+w mod pという種類の関数のみを扱っている.
  • 証明は暗号と線形代数と多次元ガウス分布が分かっていればすぐ読めてしまう. 基本的にはRegev暗号なんだけど元のZ_qと鍵の作り方が変わっていてそこがミソになっている.