FOCS 2006の<a href="http://focs06.cs.princeton.edu/accepts.html">accepted papers</a>出ましたよ.

学習関係のは, Regev暗号やらAjtai-Dwork暗号やらを使って学習の不可能性を議論しているんだったかと (学習のことはよぉ知らんので受け売りで.) なのでこれは格子関係. Razborov and Yekhaninのは, 群を決めてrestricted modelで下限を示しているらしい. D. Boneh, E.-J. Goh, and K. Nissim. Evaluating 2-DNF Formulas on Ciphertexts (TCC 2005)って $O(n^{1/3})$ の計算量でPIRやってた気がするな. これがOptimalなの? あ, ECCC TR06-050を読んだらD. Boneh, E.-J. Goh, and K. Nissim. Evaluating 2-DNF Formulas on Ciphertexts (TCC 2005)を引いてない. 俺が間違ってんのかな.

A. A. Razborov and S. Yekhanin. An $\Omega(n^{1/3})$ Lower Bound for Bilinear Group Based Private Information Retrieval. (ECCC TR06-050)
Boaz Barak, Manoj Prabhakaran and Amit Sahai. Concurrent Non-Malleable Zero Knowledge.
Venkatesan Guruswami and Anindya Patthak. Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets.
Adam R. Klivans and Alexander A. Sherstov. Cryptographic Hardness Results for Learning Intersections of Halfspaces. (ECCC TR06-057)
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai. Cryptography from Anonymity. (Cryptology ePrint Archive - 2006/084)
Venkatesan Guruswami and Prasad Raghavendra. Hardness of Learning Halfspaces with Noise. (ECCC TR06-061)
Silvio Micali, Rafael Pass and Alon Rosen. Input-Indistinguishable Computation.
Russell Impagliazzo, Ragesh Jaiswal and Valentine Kabanets. List-decoding direct product codes and uniform hardness amplification.
Vitaly Feldman and Parikshit Gopalan and Subhash Khot and Ashok Kumar Ponnuswami. New Results for Learning Noisy Parities and Halfspaces. (ECCC TR06-059)
Danny Harnik and Moni Naor. On the Compressibility of NP Instances and Cryptographic Applications. (ECCC TR06-022 R01)
Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan. Statistical Zero-Knowledge Arguments for NP from Any One-Way Function. (ECCC TR06-075)
Eli Ben-Sasson, Swastik Kopparty and Jaikumar Radhakrishnan. Subspace Polynomials and List Decoding of Reed-Solomon Codes.