1
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

posted at

updated at

Organization

Domingo-ferrer暗号入門(1)

Domingo-ferrer暗号とは

Domingo-ferrer暗号は、ドミンゴ先生が1996年と2002年に提案した暗号方式です。
今回説明するのは2002年に提案された方です。
なにをやっているか簡単に説明すると、平文の数値をごちゃごちゃして多項式の係数の形で暗号化しています。
特徴は以下の通り。

  • 足し算、掛け算が出来る完全準同型暗号
  • ノイズが無い
  • Known-plaintext Attackに対して、弱い(2006年に解読の論文が出ている[参考3])

アルゴリズム

鍵について

鍵は以下の通り。

説明
d 2より大きな整数
m $10^{200}$以上で約数を多く持つ整数
m' ランダムなmの約数
r mと互いに素の整数

暗号化(Encryption)

暗号化の手順は以下の通り。

 mod m'をとる
 ⑴の結果をd個に分ける
 分けた数それぞれmod mをとる
 ⑶の結果に$r^n$をかける (n:暗号文リストのindex)
 それぞれmod mをとる

例として2を暗号化してみます。
鍵は
m = 28
m' = 7
r = 3
d = 2
とします。

$16 ≡ 2 mod 7$

$16 = 3 + 13$

$3≡3 mod28$
$13≡13 mod28$

$[3*3, 13*3^2]$

$9 ≡ 9mod28$
$117≡5 mod28$

なので$2$の暗号文は$[9,5]$です。

正確には$5x^2+9x$です

復号化(Decryption)

復号化は手順以下の通り。

 それぞれに$r^{−n}$をかける (n:暗号文(リスト)のindex)
 それぞれmod mをとる
 要素全部足し合わせる
 mod m’をとる

例としてさっきの2の暗号である$[9,5]$を復号化してみます。

まずrのモジュラ逆数(mod mでの、rのインバース)をとっておきます。

$3*r^{-n}≡1mod28$
$r^{-r}=19$

$[9*r^{-1}, 5*(r^{-1})^2]$
$=[9*19, 5*19^2]$
$= [171, 1805]$

$171≡3 mod28$
$1805≡13 mod28$
$[3,13]$

$3 + 13 = 16$

$16≡2mod7$

ということで、めでたく2に復号化できました。

足し算

足し算は暗号文の同じインデックス同士を足し合わせるだけ。
上記の鍵で3も暗号化すると[18,15]になる。
そこで、2と3の足し算をしようとすると、

$2+3 = [9+18, 5+15] =[27,20]$

となる

掛け算

2と3の掛け算をしようとすると、

$2*3 = [9,5]*[18,15]$
$=[0, 9 * 18, 9 * 15 + 5 * 18, 5 * 15]$
$= [0, 162, 225, 75]$

参考

[1] J. Domingo-Ferrer, “A New Privacy Homomorphism and Applications,” in
Information Processing Letters, Vol. 60, no. 5, pp. 277–282, 1996.

[2] J. Domingo-Ferrer, “A Provably Secure Additive and Multiplicative Privacy
Homomorphism,” in ISC2002, LNCS. Vol. 2443, pp.471–483, 2002.

[3] Jung Hee Cheon, Woo-Hwan Kim, Hyun Soo Nam, “Known-Plaintext Cryptanalysis of the DomingoFerrer Algebraic Privacy Homomorphism Scheme,”, 2006

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
1
Help us understand the problem. What are the problem?