さて - 186 @ hatenablog

R.Impagliazzo and M.Naor "Efficient Cryptographic Schemes Provably as Secure as Subset Sum"の方は3まで大筋理解。やっとleftover hash lemma + Markov's Boundの所を理解した。よくよく考えれば素直な証明なのに(論文だとあっさり文章で3行で終わってるし)嵌まってしまった。あぁー、もぅ。
で、D.Aharonov and O.Regev "Lattice Problems in NP \cap coNP"の方はとりあえずという感じ。6.1と6.2がどうも怪しい……気がする。
GapCVP_{\beta}を

YES instance: $d(v,L) > \beta$
NO instance: $d(v,L) \leq 1$

って定義しておいて、GapCVP_{\sqrt{n}}の話をしている時に、なぜか

6.2 YES instance: $d(v,L) \geq \sqrt{n}$
6.1 NO instance: $d(v,L) \leq \frac{1}{100}$

なんで1/100なんだろね。