最悪時の計算量的困難性の仮定の下で安全性が証明された最初の方式は、2005年にoded regevによって提案されている。