4.
紀要267
数論のソフトウェア情報学への応用について
高田 豊雄
1.
はじめにソフトウェア情報学の基盤となる数学は多岐の分 野に亘るが本稿ではそのうち整数論の応用について いくつか述べる．具体的には Paillier 暗号と高速 フーリエ変換に対する応用を紹介する．
2. Paillier 暗号
Paillier 暗号は Pascal Paillier によって 1999
年に発表された公開鍵暗号系であり，準同型性を有 することで知られている[1]．準同型性を有する暗号 とは，暗号化関数を𝐸𝐸
𝑘𝑘，平文メッセージを𝑚𝑚
1，𝑚𝑚
2， 何らかの演算を∘, ∗ で表すとすると，
𝐸𝐸
𝑘𝑘(𝑚𝑚
1) ∘ 𝐸𝐸
𝑘𝑘(𝑚𝑚
2) = 𝐸𝐸
𝑘𝑘(𝑚𝑚
1∗ 𝑚𝑚
2)
が成立することであり，秘密投票や電子現金の実現 が容易となるため実用上重要である．
𝑝𝑝
，𝑒𝑒
を大きな素数,𝑛𝑛 = 𝑝𝑝𝑒𝑒
とするとき，よく知ら れたRSA
公開鍵暗号系が𝑛𝑛
を法とする剰余を考える のに対し，Paillier 暗号では𝑛𝑛
2を法とする剰余を 考えるため，本稿ではまず𝑛𝑛
2を法とする剰余に関す る諸性質について述べる．2.1. 𝑛𝑛 2
を法とする剰余に関する諸性質 本節ではPaillier
暗号の理解に必要となる𝑛𝑛
2 を法とする剰余に関する諸性質について述べる．詳 細については参考文献欄の文献を参照してもらいた い．性質 1.
𝑝𝑝
，𝑒𝑒
をサイズが同じ*1大きな素数,𝜆𝜆 = lcm(𝑝𝑝 − 1, 𝑒𝑒 − 1)
，(但しlcm は最小公倍数を表す)
とする．このとき(𝑛𝑛, λ) = 1 , すなわち 𝑛𝑛
とλ
は互い に素である．(*1: ここでサイズが同じとは, 一般 性を失わず𝑝𝑝 > 𝑒𝑒 と仮定したとき, 𝑒𝑒 >
𝑝𝑝−12). □
性質 2. 任意の非負整数
𝑟𝑟
に対して(1 + 𝑛𝑛)
𝑘𝑘≡ 1 + 𝑟𝑟𝑛𝑛 (mod 𝑛𝑛
2),
特に,(1 + 𝑛𝑛)
𝑛𝑛≡ 1 (mod 𝑛𝑛
2) , す
なわち乗法群𝑍𝑍
𝑛𝑛∗2の元1 + 𝑛𝑛 の位数は 𝑛𝑛
である．□性質 3. 乗法群
𝑍𝑍
𝑛𝑛∗2は,𝑍𝑍
𝑛𝑛∗2= 𝑍𝑍
𝑛𝑛× 𝑍𝑍
𝑛𝑛∗であり，
その位数は
𝑛𝑛(𝑝𝑝 − 1)(𝑒𝑒 − 1) である． 𝑎𝑎 ∈ 𝑍𝑍
𝑛𝑛, 𝑏𝑏 ∈ 𝑍𝑍
𝑛𝑛∗ とするとき，次の𝑓𝑓 は， 𝑍𝑍
𝑛𝑛× 𝑍𝑍
𝑛𝑛∗と𝑍𝑍
𝑛𝑛∗2の間の同型
写像となる．
𝑓𝑓(𝑎𝑎, 𝑏𝑏) = (1 + 𝑛𝑛)
𝑎𝑎⋅ 𝑏𝑏
𝑛𝑛mod 𝑛𝑛
2□ 性質 2 および 3 から,
𝑚𝑚 ∈ 𝑍𝑍
𝑛𝑛∗2から 𝑎𝑎 ∈ 𝑍𝑍
𝑛𝑛を 抽出する写像を𝐿𝐿
とすると,𝐿𝐿 = (𝑚𝑚 − 1) ⁄ 𝑛𝑛
となる.ここで除算は(何らかの法の上の乗法逆元を乗ずる のではなく)整数上の除算を行う.
性 質
4. 𝑛𝑛
と 互 い に 素 な𝑎𝑎
に つ い て𝑎𝑎
𝜆𝜆𝑛𝑛≡ 1 (mod 𝑛𝑛
2) (カーマイケルの定理). □ 2.2. Paillier
暗号の具体的な方式Paillier
暗号の具体的な方式は個々の文献で細かな部分が異なる．本節では
Katz-Lindell
版[2]を 基に更に計算量を減らしたバージョンについて述べ る(計算量の削減については[3]も参照).[鍵生成]
大きく，サイズが同じ素数
𝑝𝑝
，𝑒𝑒
を選択し，その積 を𝑛𝑛 = 𝑝𝑝𝑒𝑒
とし，𝑔𝑔 = 𝑛𝑛 + 1
とする．𝜆𝜆 = lcm(𝑝𝑝 − 1, 𝑒𝑒 − 1)
とするとき，𝜇𝜇
をλ
の法𝑛𝑛
に関する乗法逆元とす る．(すなわち 𝜆𝜆 ⋅ 𝜇𝜇 ≡ 1 (mod 𝑛𝑛) ). 性質 1. より，
このような
𝜇𝜇
は必ず存在する.このとき，公開鍵は
𝑛𝑛
，秘密鍵は (𝜆𝜆 , 𝜇𝜇 )である．
[暗号化]
平文メッセージ
𝑚𝑚
を𝑚𝑚 ∈ 𝑍𝑍
𝑛𝑛とする．乱数𝑟𝑟 ∈ 𝑍𝑍
𝑛𝑛2 を生成する．その時，暗号文𝑐𝑐
を𝑐𝑐 = 𝐸𝐸(𝑀𝑀) = 𝑔𝑔
𝑚𝑚∙ 𝑟𝑟
𝑛𝑛mod 𝑛𝑛
2 とする．[復号]
暗号文
𝑐𝑐
より次式を計算する．𝑚𝑚 = 𝐿𝐿�𝑐𝑐
𝜆𝜆mod 𝑛𝑛
2� ∙ 𝜇𝜇 mod 𝑛𝑛 [数値例]
素数
𝑝𝑝 , 𝑒𝑒
を𝑝𝑝 = 13 , 𝑒𝑒 = 17 とする． 𝑛𝑛 = 𝑝𝑝𝑒𝑒 = 221 , 𝑛𝑛
2= 48841 である．
𝜆𝜆 = lcm(𝑝𝑝 − 1, 𝑒𝑒 − 1) = lcm(12,16) = 48
また，𝜇𝜇
は𝜆𝜆 = 48
の法221
に関する乗法逆元であり，𝜇𝜇 =
198 となる( 48 ⋅ 198 ≡ 1 (mod 221) )．
Journal of Faculty of Software and Information Sciences, Vol.15
268
いま仮に𝑚𝑚 = 21, 𝑟𝑟 = 30
とすると，暗号文𝑐𝑐
は𝑐𝑐 = 𝑔𝑔
𝑚𝑚∙ 𝑟𝑟
𝑛𝑛mod 𝑛𝑛
2= 222
21⋅ 30
221mod 48841
= 42377.
𝑐𝑐
の復号は𝐿𝐿�𝑐𝑐
𝜆𝜆mod 𝑛𝑛
2� ∙ 𝜇𝜇 mod 𝑛𝑛
= 𝐿𝐿(42377
48mod 48841) ⋅ 198 mod 221 = 𝐿𝐿(27405) ⋅ 198 mod 221
= 124 ⋅ 198 mod 221 = 21
となる．
[復号が正しく行われる理由]
性 質
4.
よ り, (𝑔𝑔
𝑚𝑚𝑟𝑟
𝑛𝑛)
𝜆𝜆≡ 𝑔𝑔
𝜆𝜆𝑚𝑚⋅ 𝑟𝑟
𝜆𝜆𝑛𝑛≡ 𝑔𝑔
𝜆𝜆𝑚𝑚(mod 𝑛𝑛
2) .
性質 2. より,
𝑔𝑔
𝜆𝜆𝑚𝑚≡ 1 + 𝜆𝜆𝑚𝑚𝑛𝑛 (mod 𝑛𝑛
2) . よって, 𝐿𝐿�𝑐𝑐
𝜆𝜆mod 𝑛𝑛
2� = 𝜆𝜆𝑚𝑚 . 最後に, 𝜇𝜇
の定義より,𝐿𝐿�𝑐𝑐
𝜆𝜆mod 𝑛𝑛
2� ∙ 𝜇𝜇 ≡ 𝜆𝜆𝑚𝑚𝜇𝜇 ≡ 𝑚𝑚 (mod 𝑛𝑛) . 2.3. Paillier
暗号の有用性Paillier
暗号は平文メッセージの加法に関して準同型性を有する．すなわち平文メッセージを
𝑚𝑚
1，𝑚𝑚
2とするとき，
𝐸𝐸(𝑚𝑚
1) ∙ 𝐸𝐸 (𝑚𝑚
2) = 𝑔𝑔
𝑚𝑚1∙ 𝑟𝑟
1𝑛𝑛⋅ 𝑔𝑔
𝑚𝑚2∙ 𝑟𝑟
2𝑛𝑛= 𝑔𝑔
𝑚𝑚1+𝑚𝑚2⋅ (𝑟𝑟
1⋅ 𝑟𝑟
2)
𝑛𝑛= 𝐸𝐸(𝑚𝑚
1+𝑚𝑚
2)
この性質は秘密投票に応用可能である．例えば
𝑚𝑚 = 0
を反対票，𝑚𝑚 = 1
を賛成票を表すものと決めておき，有権者が公開鍵で暗号化して投票を行えば，暗号化 されたまま投票内容の集計が可能となる．
また，前節から明らかな通り，暗号化と復号双方 とも計算時間に関して支配的な演算は
𝑛𝑛
2を法とす るベキ乗剰余演算1
回のみである．但し，法が𝑛𝑛
2で あることからRSA
公開鍵暗号系と比較して倍の桁数 の演算となる．本稿は計算量理論あるいは暗号理論に関するノー ト で は な く 整 数 論 に 関 す る ノ ー ト で あ る た め
Paillier
暗号系の安全性の詳細については触れないが，
Paillier 暗号の安全性は合成数剰余判定仮定
(Decisional Composite Residuosity Assumption (DCRA))
に基づく.𝑦𝑦 = 𝑥𝑥
𝑛𝑛mod 𝑛𝑛
2 となる𝑥𝑥 ∈ 𝑍𝑍
𝑛𝑛∗2 が存在するとき，𝑦𝑦 ∈ 𝑍𝑍
𝑛𝑛∗2は 𝑛𝑛
乗剰余と呼ばれる．DCRA
とは𝑛𝑛
乗剰余の集合が𝑍𝑍
𝑛𝑛∗2 のランダムな元の集合と多項式時間アルゴリズムで識別不能であるとい う仮定である．
3.
高速フーリエ変換への数論応用3.1.
離散フーリエ変換時間間隔
𝑇𝑇
でサンプリングされた長さ𝑁𝑁
の信号 系列を{𝑥𝑥(𝑛𝑛𝑇𝑇)}
𝑛𝑛=0𝑁𝑁−1とする．この系列の離散フーリエ 変換(Discrete Fourier Transform (DFT))は𝑋𝑋(𝑟𝑟) = ∑
𝑁𝑁−1𝑛𝑛=0𝑥𝑥(𝑛𝑛𝑇𝑇) ⋅ 𝑒𝑒
−𝑖𝑖2𝜋𝜋𝑛𝑛𝜋𝜋𝑁𝑁(3.1) 𝑟𝑟 = 0,1, … , 𝑁𝑁 − 1
で与えられる．情報科学全般における離散フーリエ変換の重要性 は改めて述べるまでもなく，上式を素直に計算する と
𝑁𝑁
2回の乗算を必要とすることから高速な計算ア ルゴリズムについて多くの研究がなされている．と り わ け 有 名 な の が 系 列 長 が2
の べ き 乗 の 場 合 のCooley-Tukey
アルゴリズム[4]であり(狭義の)高速 フーリエ変換(Fast Fourier Transform (FFT))と呼 ばれている．3.2.
系列長が素数の積の場合の高速フーリエ 変換Cooley-Tukey
アルゴリズムは一種の分割統治法 であり，ゆえに系列長が2
のべき乗の場合が最も計 算効率がよくなる．しかし，一般には系列長は2
のべ き乗であるとは限らない．その際0
詰めを行い，無理 矢理系列長を2
のべき乗とすることも行われるが，結果の取扱いに注意を要する場合が生じる．
1978
年, 文献[5]でWinograd
は系列長が素数の 積で表される場合の離散フーリエ変換の高速化を示 したのでここに紹介する.𝑊𝑊 = 𝑒𝑒
−𝑖𝑖2𝜋𝜋/𝑁𝑁とおく.
この𝑊𝑊
は(複素)1 の𝑁𝑁
乗根であり，フーリエカーネル等と呼ばれる. このとき 式(3.1)は以下のように表される．
𝑋𝑋(𝑟𝑟) = ∑
𝑁𝑁−1𝑛𝑛=0𝑥𝑥(𝑛𝑛𝑇𝑇) ⋅ 𝑊𝑊
𝑛𝑛𝑘𝑘(3.2)
いま系列長が𝑁𝑁 = 𝑁𝑁
1∙ 𝑁𝑁
2と2
つの素数の積の形で 書けるとする．任意の整数𝑏𝑏
1, 𝑏𝑏
2について，中国人 剰余定理より，次の𝑥𝑥
に関する連立合同式が同次解 をもつことはよく知られている．𝑥𝑥 ≡ 𝑏𝑏
1(mod 𝑁𝑁
1), 𝑥𝑥 ≡ 𝑏𝑏
2(mod 𝑁𝑁
2)
そこで，次の連立合同式を満たす
𝑝𝑝
1, 𝑝𝑝
2を考える．𝑝𝑝
1≡ 1 (mod 𝑁𝑁
1), 𝑝𝑝
1≡ 0 (mod 𝑁𝑁
2) (3.3)
𝑝𝑝
2≡ 0 (mod 𝑁𝑁
1), 𝑝𝑝
2≡ 1 (mod 𝑁𝑁
2) (3.4)
4.
紀要269
式(3.2)中に現れる任意の𝑛𝑛, 𝑟𝑟 についても,
次の 合 同 式 を 満 た す0 ≤ 𝑟𝑟
1, 𝑛𝑛
1≤ 𝑁𝑁
1− 1 , 0 ≤ 𝑟𝑟
2, 𝑛𝑛
2≤ 𝑁𝑁
2− 1 が一意に定まる．
𝑛𝑛 ≡ 𝑛𝑛
1(mod 𝑁𝑁
1), 𝑛𝑛 ≡ 𝑛𝑛
2(mod 𝑁𝑁
2) (3.5) 𝑟𝑟 ≡ 𝑟𝑟
1(mod 𝑁𝑁
1), 𝑟𝑟 ≡ 𝑟𝑟
2(mod 𝑁𝑁
2) (3.6)
このとき，式(3.2)中の各𝑛𝑛𝑟𝑟 について
𝑛𝑛𝑟𝑟 ≡ 𝑝𝑝
1𝑛𝑛
1𝑟𝑟
1+ 𝑝𝑝
2𝑛𝑛
2𝑟𝑟
2(mod 𝑁𝑁)
よって
𝑊𝑊
𝑛𝑛𝑘𝑘は以下のように表すことができる．𝑊𝑊
𝑛𝑛𝑘𝑘= 𝑊𝑊
1𝑞𝑞1𝑛𝑛1𝑘𝑘1∙ 𝑊𝑊
2𝑞𝑞2𝑛𝑛2𝑘𝑘2(3.7)
但し，各𝑗𝑗 = 1,2
について,𝑊𝑊
𝑗𝑗= 𝑒𝑒
−𝑖𝑖2𝜋𝜋/𝑁𝑁𝑗𝑗, 𝑒𝑒
𝑗𝑗= 𝑝𝑝
𝑗𝑗𝑁𝑁
𝑗𝑗/ 𝑁𝑁 ( 𝑝𝑝
𝑗𝑗の定義より𝑝𝑝
𝑗𝑗は𝑁𝑁/𝑁𝑁
𝑗𝑗の倍数であるため，𝑒𝑒
𝑗𝑗は 整数)である．よって，系列長𝑁𝑁
のDFT
は, 系列長𝑁𝑁
1, 𝑁𝑁
2のDFT
から計算することができる．ここまで系列 長が2
つの素数の積の場合をみてきたが，中国人剰 余定理の形から𝑁𝑁
が対毎に素な2
個以上の整数の積 の場合に拡張可能であることは自明である．3.3.
系列長が6
の場合の例𝑁𝑁 = 6 , 𝑁𝑁
1= 2 , 𝑁𝑁
2= 3 とする. 式(3.3), (3.4)
を満たす𝑝𝑝
1, 𝑝𝑝
2はそれぞれ𝑝𝑝
1= 3 , 𝑝𝑝
2= 4 となり，
𝑒𝑒
1= 1 , 𝑒𝑒
2= 2 である．
各
𝑛𝑛 , 0 ≤ 𝑛𝑛 ≤ 5 について，式(3.5)により対応す
る
(𝑛𝑛
1, 𝑛𝑛
2) の組は, それぞれ以下の通りとなる．
(0,0), (1,1), (0,2), (1,0), (0,1), (1,2)
𝑛𝑛
1, 𝑛𝑛
2の 辞 書 式 順 序 で𝑛𝑛
を 並 べ 替 え る と𝑛𝑛 = 0,4,2,3,1,5
の順となり,𝑊𝑊
1= 𝑒𝑒
−𝑖𝑖2𝜋𝜋/2, 𝑊𝑊
2= 𝑒𝑒
−𝑖𝑖2𝜋𝜋/3 とすると,𝑁𝑁 = 6 の DFT は式(3.2), (3.7)から
⎝
⎜ ⎜
⎛ 𝑋𝑋(0) 𝑋𝑋(4) 𝑋𝑋(2) 𝑋𝑋(3) 𝑋𝑋(1) 𝑋𝑋(5)⎠
⎟ ⎟
⎞
= �𝑊𝑊
10𝑊𝑊
10𝑊𝑊
10𝑊𝑊
11� ⊗ � 𝑊𝑊
20𝑊𝑊
20𝑊𝑊
20𝑊𝑊
20𝑊𝑊
22𝑊𝑊
24𝑊𝑊
20𝑊𝑊
24𝑊𝑊
22�
⎝
⎜ ⎜
⎛ 𝑥𝑥(0) 𝑥𝑥(4) 𝑥𝑥(2) 𝑥𝑥(3) 𝑥𝑥(1) 𝑥𝑥(5)⎠
⎟ ⎟
⎞
となる(但し
⊗ はクロネッカー積を表す)．
4.
おわりに本稿では，整数論のソフトウェア情報学への応用 例として Paillier 公開鍵暗号系と
Winograd
の高 速フーリエ変換アルゴリズムについて述べた．参考文献
