{"type":"rich","height":"190","blog_url":"https://186.hatenablog.com/","author_url":"https://blog.hatena.ne.jp/smoking186/","version":"1.0","author_name":"smoking186","title":" Paillier\u306e\u8a71","description":"\u9069\u5f53\u306b\u8abf\u3079\u7269\u3092\u3057\u3066\u3044\u305f\u3089, Partial Discrete Logarithm Problem\u3063\u3066\u3082\u306e\u3092\u898b\u3064\u3051\u305f\u306e\u3067\u30e1\u30e2.N=pq\u3092safe prime\u306e\u7a4d\u3068\u3057\u307e\u3059 (p=2p'+1, q=2q'+1). G\u3092QR(N^2)\u3068\u3057\u307e\u3059. N^2\u3092\u6cd5\u3068\u3057\u305f\u5e73\u65b9\u5270\u4f59\u304c\u6210\u3059\u5de1\u56de\u7fa4. \u3059\u308b\u3068G\u306e\u4f4d\u6570\u306fpp'qq'. \u307e\u305f, \u4f4d\u6570N\u306e\u5143\u306f\u3061\u3087\u3046\u30691+kN\u306e\u5270\u4f59\u985e\u306b\u306a\u3063\u3066\u3044\u308b. \u3055\u3066, g\u3092g^{2p'q'} mod N^2 = 1+N mod N^2\u3068\u306a\u308b\u5143\u3060\u3068\u3059\u308b. \u3059\u308b\u3068, g\u3068h (=g^a mod N^2) \u3092\u4e0e\u3048\u3089\u308c\u305f\u3068\u304d\u306ba\u3092\u6c42\u3081\u308b\u306e\u306f\u96e3\u3057\u305d\u3046\u3067\u3042\u308b. \u3053\u308c\u304cPartial DL\u554f\u984c. \u3067,\u2026","published":"2009-04-13 21:20:38","width":"100%","provider_url":"https://hatena.blog","blog_title":"186 @ hatenablog","image_url":null,"categories":["crypt"],"html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2F186.hatenablog.com%2Fentry%2F20090413%2F1239625238\" title=\" Paillier\u306e\u8a71 - 186 @ hatenablog\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","url":"https://186.hatenablog.com/entry/20090413/1239625238","provider_name":"Hatena Blog"}