Domingo-ferrer暗号とは
Domingo-ferrer暗号は、ドミンゴ先生が1996年と2002年に提案した暗号方式です。
今回説明するのは2002年に提案された方です。
なにをやっているか簡単に説明すると、平文の数値をごちゃごちゃして多項式の係数の形で暗号化しています。
特徴は以下の通り。
- 足し算、掛け算が出来る完全準同型暗号
- ノイズが無い
- Known-plaintext Attackに対して、弱い（2006年に解読の論文が出ている[参考3]）
アルゴリズム
鍵について
鍵は以下の通り。
| 鍵 | 説明 |
|---|---|
| d | ２より大きな整数 |
| m | $10^{200}$以上で約数を多く持つ整数 |
| m' | ランダムなmの約数 |
| r | mと互いに素の整数 |
暗号化(Encryption)
暗号化の手順は以下の通り。
⑴ mod m'をとる
⑵ ⑴の結果をd個に分ける
⑶ 分けた数それぞれmod mをとる
⑷ ⑶の結果に$r^n$をかける (n:暗号文リストのindex)
⑸ それぞれmod mをとる
例として２を暗号化してみます。
鍵は
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$
なので$２$の暗号文は$[9,5]$です。
正確には$5x^2+9x$です
復号化(Decryption)
復号化は手順以下の通り。
⑴ それぞれに$r^{−n}$をかける (n:暗号文(リスト)のindex)
⑵ それぞれmod mをとる
⑶ 要素全部足し合わせる
⑷ mod m’をとる
例としてさっきの２の暗号である$[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$
ということで、めでたく２に復号化できました。
足し算
足し算は暗号文の同じインデックス同士を足し合わせるだけ。
上記の鍵で３も暗号化すると[18,15]になる。
そこで、２と３の足し算をしようとすると、
$2+3 = [9+18, 5+15] =[27,20]$
となる
掛け算
２と３の掛け算をしようとすると、
$2*3 = [9,5]*[18,15]$
$=[0, 9 * 18, 9 * 15 + 5 * 18, 5 * 15]$
$= [0, 162, 225, 75]$