Oded Regev, "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography," STOC 2005.主結果はGapSVPからランダム線型符号の復号問題への帰着であるが，これを基にGapSVPベースの公開鍵暗号系の構成を与えている． つまり，ある近似パラメ…

V. Guruswami, C. Umans and S. Vadhan "Extractors and condensers from univariate polynomials." CCC 2007に採録された論文．最適なパラメータを達成するrandomness extractorとloss-less condenserを以前の多変数多項式符号(Reed-Muller)に基づく構成と…