構成は理解した. 何をやっているかは理解したので, 次は安全性の証明. しかし複雑なことになっている. PIR + ECC + RS-ECC + PKEとか止めて欲しい.

q : 素数, n, m : 整数 のとき、 を示せ。0 < n < q^m とします。 逆にした方が分かり易いんじゃないでしょうか. 証明 Z/qZ上で, 恒等式が成立すれば題意が言える.まずZ/qZでを示す. これは割と簡単に言えて, の係数は. 0 < a < qについてとなるのでOK. (\bi…

ref:FOCS 2008 - Accepted Papers Tali Kaufman and Shachar Lovett. Worst Case to Average Case Reductions for Polynomials Stefan Dziembowski and Krzysztof Pietrzak. Leakage-Resilient Cryptography in the Standard Model Dan Boneh, Periklis Papa…

p:素数, p|nとする. を示せ. 某講義ノートに証明無しで書かれていて困った. p≠nは必要ない. イコールの場合は両辺ともに1なので問題なし Hさんの解答 である. もしpがnの最小の素因数であれば, 右側のn/p以外の項の分子からnを除いても良い (modulo nで考え…