FIT2014（第 13 回情報科学技術フォーラム）L-013
Graphics Processing Unit を用いた拡大体上の QUAD ストリーム暗号の高速化
Accelerating QUAD Stream Cipher over Extend Field using Graphics Processing Unit

田中哲士 ∗†Satoshi Tanaka

安田貴徳 ∗
Takanori Yasuda

櫻井幸一 ∗†Kouichi Sakurai

概要

2.1

QUAD ストリーム暗号は鍵ストリームの生成に多変数公開鍵暗号の技術を利用しており，他のストリーム暗号と異なり公開鍵暗号レベルの証明可能安全性を持つ．一方で，QUAD は鍵の生成に多量の計算が必要であり，ストリーム暗号としては低速である．高速な実装手法の一つとして計算速度の高い
Graphics Processing Unit (GPU) を用いて実装する方法が知られており，暗号分野においても GPU を利用した AES の効率化等が報告されている [4]．我々は，これまで QUAD の高速化に対して挑戦しており，多項式の評価に必要な計算を並列化することにより効率化を図ってきた [6]．一方で，GF (232 )のような拡大体を用いることによる変数の削減を利用した高速化についても注目しており，効率的な拡大体上の乗算手法についても検討している [7]．本論文では GPU を用いた GF (232 )上の QUAD ストリーム暗号の実装を行い，その結果について述べる．

QUAD ストリーム暗号は式 2 の結果を鍵ストリームの生成に利用するストリーム暗号である [3]．Y = {y1 , . . . , ym } ∈GF (q)m を式 2 で与えられる多項式 S(X) の値とする．即ち，

1yi = fi (X) (1 ≤ i ≤ m),(5)である．ここで，m = kn（k ≤ 2）とする．QUAD では Y ={y1 , . . . , ym } を n 個の組 Sit = {x1 , . . . , xn } と (m − n) =(k − 1)n 個の組 Sout = {xn+1 , . . . , xm } の二つに分け，Soutを鍵ストリームとして出力する．一方で，Sit を次のステップにおける X として利用し，これを繰り返す．図 1 に QUAD
ストリーム暗号の鍵生成のイメージを示す．

多変数多項式

p を素数とし，q = pk （k ≥ 1）とする．このとき，GF (q)は標数 q の k 次拡大体とする．GF (q) 上の n 個組の変数をX = {x1 , . . . , xn } とすれば，GF (q) 上の n 変数の二次多項式は次のように表現できる．
∑f (X(= x1 , . . . , xn )) =1≤i≤j≤nαi,j xi xj +∑βi xi + γ1≤i≤n(αi,j , βi , γ ∈ GF (q), (1 ≤ i ≤ j ≤ n)). (1)更に，GF (q) 上の m 連立 n 変数二次多項式 S(X) を次のように表現する．

S(X) = {f1 (X), . . . , fm (X)}.

2

QUAD ストリーム暗号(2)

ストリーム暗号あるメッセージ M = {m1 , m2 , . . . , mL } に対して，鍵ストリーム列 K = {k1 , k2 , . . . , kL } を用いて，ci = mi⊕ki (1 ≤ i ≤ L),(3)となる暗号文 C = {c1 , c2 , . . . , cL } を生成する方式をストリーム暗号と呼ぶ．復号は同様に鍵 K を用いて，

mi = ci⊕ki (1 ≤ i ≤ L),(4)として入手することができる．メッセージ長以上の長さを持つ鍵を 1 回の暗号化にのみ使用する場合，情報理論的安全性を持つ暗号が構成されることが知られている．しかし実際には秘密裏にメッセージ長以上の暗号鍵を共有することは困難である．
その為実用上は，擬似乱数生成器と乱数のシードを共有することにより，同じ鍵ストリームを生成し暗号鍵を共有する手段などが行われている．
∗ 九州先端科学技術研究所，Institute of Systems, Information Tech-nologies and Nanotechnologies† 九州大学，Kyushu University, Fukuoka, Japan

Figure 1: QUAD の鍵生成
QUAD は安全性の根拠に MQ 問題と呼ばれる数学の問題を利用している．MQ 問題は有限体上の連立二次方程式の求解問
題，即ち，GF (q) 上の多項式 S(X) とその値 Y = S(X) が与えられたとき，元の変数 X の値を求める問題である．一般に，MQ 問題は NP 完全であることが知られており [1]，QUAD はMQ 問題が解決困難である限り安全な暗号であることが証明されている．

2.2

QUAD の計算コスト

QUAD の鍵ストリーム生成では一回の鍵生成ごとに Y の計算，式 2 で与えられる多項式 S(X) の評価が必要となる．
S(X)()
個の二次内の n 変数二次多項式 fi (X)（1 ≤ i ≤ m）は n+12の項と n 個の 1 次の項，(n+1)1 個の定数項を持っている．従って，
fi (X) の評価には 2 2 + n = n(n + 2) 回の GF (q) 上乗算()
及び n+1+ n = n(n + 3)/2 回の GF (q) 上加算が必要とな
2
り，S(X) の評価には mn(n + 2) 回の乗算と mn(n + 3)/2 回の加算が必要である．
Berbain らは QUAD の計算コストを減少させる以下の手法を提案している [2]．
単項式 xi xj の事前計算 二次の項 xi xj（1 ≤ i ≤ j ≤ n）は各方程式で共通である．従って，この計算を事前に行うことによって全体の乗算回数を mn(n + 5)/2 + n(n + 1)/2に減らすことができる．
ビットスライス 通常，一つの変数は一つのデータしか取り扱わないが，ビットスライスを利用し変数内に複数のデータを格納し，縦にデータを取り扱うことで変数単位でSIMD の計算が可能となり，全体の計算量を減らすことに繋がる．ビットスライス方式を適用するためには計算が並列化可能であることが重要だが，S(X) 内の fi (X)はそれぞれ独立であり，並列性が高くビットスライスによる計算削減の効果は高い．

149
第 4 分冊Copyright © 2014 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.

FIT2014（第 13 回情報科学技術フォーラム）GPU による QUAD の実装

33.1

GPGPU 技術

画面の出力や画像処理，3DCG の演算を行うことを目的とした計算装置を Graphics Processing Unit(GPU) と呼ぶ．GPUを画像処理以外の計算に利用し高い計算能力を達成する技術を
GPGPU と呼ぶ．現在は，GPU を提供する AMD や NVIDIAが提供する GPU 向けの開発キット [8, 9] や OpenCL 等のライブラリを用いることで，GPU 環境におけるプログラム開発が可能となってきている．

3.2

QUAD ストリーム暗号の並列化

現在の GPU は 1,000 個以上のコアを有しており，CPU よりも大きな計算能力を有しているといえる．一方で，GPU の各コアの計算能力は CPU のコアよりも低い．その為，GPU上で実装を行う場合，その並列性を利用し同時に多数の計算を行うことが望ましい．QUAD の場合，以下の 2 点の並列化が必要である．

1. 連立多項式 Q(X) = {f1 (X), . . . , fm (X)} の並列化
2. 二次多項式 yi = fi (X) の効率化
我々は以下の戦略で並列化を試みた．第 1 に連立多項式の並列化については berbain らのビットスライス [2] を採用した．
S(X) 内の多項式 fi (X) はそれぞれ独立であり並列化の効果が高いためである．第 2 に各多項式の計算は以下の 2 ステップで計算を行った．第 2 ステップの並列リダクションについて
は [6] のものを用いた．
(i)

(i)

1. 二次多項式 yi = fi (X) 内の全ての項 αj,k xj xk , βj xjを事前に計算する．
∑∑(i)
(i)
2. 総和 1≤j≤k≤n αi,j xj xk + 1≤j≤n βj xj + γ (i) を並列リダクションを用いて求める．

4

実装実験

実装実験として，GF (232 ) 上の 32, 48, 64 変数（k = 2) のQUAD を CPU 及び GPU 上で実装し，それぞれ，10MB のデータの暗号化時間を測定した．実装結果について，表 1 に示す．また，実装環境として，GPU に NVIDIA GeForce GTX
TITANCPU に Intel Core i7 875K を利用した．メモリ環境
は 8GB である．

Table 1: GPU を用いた GF (232 ) 上の QUAD 実装結果
変数
324864多項式
6496128
CPU
暗号化時間 (sec)205.105298.842392.277
スループット (kbps)
49.92634.26626.104
GPU
暗号化時間 (sec)
11.71810.06818.000
スループット (kbps)
873.869 1017.084 568.889
速度比×17.503 ×29.683 ×21.793

5乗算の計算量を m · n + m 回に落とすことに成功しており，高速な手法として期待できる．本発表では，Petzoldt の手法の適用結果について発表する．
また，実験結果では 48 変数から 64 変数の時点で速度比 29.7倍から 21.8 倍に下がっている．これは，総和等の一部計算で多数のスレッドが必要な計算であり，NVIDIA GeForce GTX
TITAN の 1 ブロックで取り扱えるスレッド数を超えていたと考えている．今後，QUAD の動作についてより詳しく分析し推測が正しいかを検証する．

謝辞
本研究は一部において，総務省戦略的情報通信研究開発推進事業（SCOPE）平成 25 年度 ICT イノベーション創出型研
究開発フェーズ I『多変数多項式システムを用いた安全な暗号技術の研究』（課題番号 0159-0172）の助成を受けている．

References[1] Bard, G.V.: NP-Completeness of MP, In Algebraic
Cryptanalysis, pp. 199-202, Springer, 2009[2] Berbain C., Billet, O., Gilbert, H.: Eﬃcient Implementations of Multivariate Quadratic Systems. In theProceedings of Selected Areas in Cryptography, LNCS,
vol. 4356, pp. 174-187, Springer, 2007.
[3] Berbain, B., Gilbert, H., Pataring, J.: QUAD: a Pratical Stream Cipher with Provable Security. In EUROCRYPTO’06, LNCS, vol.4004, pp.109-128, Springer,
2006.
[4] Manavski, S.A.: Cuda compatible gpu as an eﬃcient
hardware accelerator for aes cryptography. In International Conference on Signal Processing and Communications 2007 (ICSPC 2007), pp. 65-68. IEEE, 2007.
[5] Petzoldt, A.: Speeding up QUAD. In cryptography
ePrint archive, report, 2013.
[6] Tanaka, S., Nishide, T., Sakurai, K.: Eﬃcient Implementation for QUAD Stream Cipher with GPUs., In
the Journal of Computer Science an d Information Systems (ComSIS), vol. 10, num. 2, special issue, pp.897911, 2013.
[7] Tanaka, S., Yasuda, T. Sakurai, K.: Implementationof Eﬃcient Operations over GF (232 ) using Graphics
Processing Units. In Information and Communication
Technology, LNCS, vol. 8407, pp.602-611, Springer,
2014.
[8] Graphics Development
http://developer.amd.com/tools-and-sdks/graphics-development/[9] CUDA Zone
https://developer.nvidia.com/cuda-zone

まとめ

本論文では，QUAD ストリーム暗号の並列化手法について述べ，GPU 上で実装した結果を述べた．我々の実装手法ではGF (248 ) 上の 48 変数の QUAD ストリーム暗号を GPU 上で実装することによって，約 30 倍の高速化を実現することに成功した．
今後の課題として，Petzoldt の手法 [5] の適用を検討する．
Petzoldt は Linear Recurring Sequences を利用する事により，150
第 4 分冊Copyright © 2014 by
The Institute of Electronics, Information and Communication Engineers andInformation Processing Society of Japan All rights reserved.