数理解析研究所講究録
第 820 巻 1993 年 54-58

54

暗号における組合わせ構造について
岡本栄司
北陸先端科学技術大学院大学
情報科学研究科
e-mail: okamoto@jaist-east.ac.jp

1

はじめに

暗号は情報発信者が受信者のみに意味がわかるように情報を伝える技術であり、認証は当事者情報の正当性を保証する技術である。 これらの暗号/認証においてベースとなる数学的な理論には、
情報理論、初等整数論、計算量理論、組合わせ理論などがある。それらは次のような役割を担っ.ている。

情報理論
-

-

安全性保証 (計算機パワー無限)

情報帯域の下限

・初等整数論-.
.

-

公開鍵暗号系、ディジタル署名系構成 (剰余演算)
解読 (素因数分解、離散対数)

川算量理論
-

安全性保証 (計算複雑度、 計算機パワー有限)組合わせ理論

組合わせ理論は暗号/認証において多く用いられているが、中でも、暗号アルゴリズム、認証、鍵配送/管理の各部門で効果的に用いられている。 ここでは、 トピック的にそれらの例を示し、 その有効性を探る。

2暗号アルゴリズム

2.1

誤り伝搬

通信暗号では、暗号化情報の伝送中に誤りが生じると、 たとえ 1 ビットエラーでも受信側復号中にそのエラーが広がる (エラー伝搬) これは、衛星通信などへの適用を考えると好ましくない。
そこで、 まず、エラー伝搬を起こさない暗号アルゴリズムはどういうものかを探る。
。

定理 1 エラー伝搬を起こさないための全単射暗号の条件は、暗号変換が(1)$y=P\tau\cdot\oplus c\iota$で与えられることである。 ただし、$r$は平文ベクトル、 は暗号文ベクトル、定数ベクトル、市はビット毎の排他的論理和である。

$y$

$P$

は転麗行列、$a$は55(証明) 復号時に誤り伝搬を起こさない陪号変換を ] とし、平文ベクトルと暗号文ベクトルをそれぞれ 次元ベクトル.2, とおく:
$7l$

$y$

(2)

$y=f(?\cdot)$

を成分 のみが 1 で他は全て の単位ベクトルとおく。 は 0(零ベクトル) からハミン
グ距離 1 だけ離れているので、 $j^{-1}(0)$ と $f^{-1}(e_{i})$ もハミング距離 1 だけ離れているはずである。
従って、
ここで、

$0$

$i$

$r_{i}$$\epsilon_{i}$(3)$f^{-1}(e_{i})=f^{-1}(0)\oplus e_{\sigma(i)}$となる。
次に、 これを用いて、 一般に$y= \sum_{i’=1}^{\tau}y;r_{i}$のとき(4)$f^{-1}(|/)=a \not\in’\sum_{i=1}^{\prime\iota}y_{i}\epsilon_{\sigma\langle i)}^{I}$の重みに関する数学的帰納法にて示す。 ここで、 $a=f^{-1}(0)$ とおいた。重み 1 のときは既に示してある。重みが 以下のときは正しいとして、 の重みが $k+1$ とする。 の最初の 2 つの非零成分を抜き出してを$y$

$k$

$y$

$y$

(5)

,

$y=e_{i_{l}}\oplus e_{j_{2}\oplus_{\sim}^{\sim}}$とする。数学的帰納法の仮定から、(6)$f^{-1}( \approx)=a\oplus\sum_{i\neq i_{1},i_{2}}y;r_{\sigma\langle i)}$$\int^{-1}(\epsilon_{j_{1}}\oplus\approx)=a$

市(7)$\sum_{i\neq i_{1}}y_{i}e_{\sigma\{i)}$(8)$f^{-1}( \not\in\cdot;_{2}tpz)=a\oplus\sum_{i\neq i,)}.y_{i}e_{\sigma\langle i)}$との問は共にハミング距離 1 なので、 に対する平文ベクトルはのいつれかしかない。 しかし、前者は に対応する平文ベクトルなので、後者が に対する平文ベクトルである。
ここで、式 (3) の右辺を ? とおくとが成り立つ。 と$y$$\epsilon_{i_{1}}\oplus 2$

、

あるいは

$a \oplus\sum_{i\neq i_{1},i_{2}}y_{i’\sigma\langle i)}$か$P_{i_{2^{\oplus z}}}$

$y$

$z$

$a d\dashv\sum_{i=I}^{rt}y_{i}r_{\sigma\langle i)}$

$y$

(9)

$\sum_{1=1}^{n}y;e_{\sigma(i)}=a\oplus x=\sum_{i=1}^{n}(a;\oplus x_{i})$

から、
(10)

$y_{i}=a_{\sigma\langle i)}\oplus:t\cdot\sigma(i)$となる。従って、$\int(?\cdot)=y=\sum_{=j1}^{r\iota}y_{i^{\xi}i}=\sum_{=j1}^{n}(a_{\sigma\langle i\}}\oplus?_{\sigma(i)})e_{i}=2^{J}\#\sum_{=j.1}^{n}x_{\sigma\langle i)^{\xi_{j}}}$

.

(11)

が得られ、 定理が証明できた。 (証明終り)

誤り伝搬が少し起きる場合の議論も行なわれているが、完全な構造解明には至っていない$[MO91]_{\text{。}}$

56
22

秘密情報分散法 [Ok92]

閾値法は,, 人中ん人集まれば元の重要な秘密情報を保管するのに、分散化する方法がある。
人以下では元の情報の 1 ビットすら得られないという方法である。
情報を復元でき、このi-X 値法は、実用を目指して拡張されている。 最も一般的な拡張は、次の単調性で$(A\cdot, \cdot\prime\prime)$$l_{\tau}\cdot--1$$(k, ’\iota)$ある。

定理 2 秘密情報分散可能となる条件は、単調性 :(12)$X’\subseteq Y.$ $-\lambda’\in\prime l\Rightarrow Y\in\Lambda$である。 ここで、 } は元秘密情報復元可能な人の集まり、 $X$$L$$\}’$、は人の集まりである。

(証明) 秘密晴報分散法があれば、単調であるのは明らかである。十分条件を示す。’5\ellにおける秘密情報とする。 /1 が単調ならば、 の任意の極小グループに対して、 そこに属すメン$(’\Gamma(\}/)$$\mathcal{A}$バー$i_{1},$ $i_{2},$$\cdots$に(13)$6=a_{i_{1}}+a_{i_{2}}+\cdots(mod p)$, (Li2’.. . をランダムに生成して、渡す。これを各極小グループ毎に行なう。これは、秘密情報分散法になっている。 (証明終り)となる$a_{i_{1}}$この一般化秘密情報分散法の欠点は、各人が持つべき分割情報が 7? の指数関数的に比例することである。そこで、式 (12) の条件を多少変えて、各人が持つ分割情報が元の情報と同じ大きさとなる理想分散法の研究されている。 しかし、上記定理 2 を見ればわかるように、秘密情報 5 は、極小グループ毎に亙いに独立な情報とすることができる。 このようにしたときには、秘密情報量/分散情報量は、 1 まで上げられる。 なお、 1 以上にすることは実用上余り意味がない。

3認証

認証においては、ディジタル署名、 メッセージ認証、ユーザ認証のいずれをとっても、ハッシュ関数を必要とする。暗号分野でいうハッシュ関数はいわゆる一方向性ハッシュ関数 で、$h$(14)$1_{l}(x)=h(y)$を満たす (衝突する),?\dashv を容易に見い出せないことをいう。
個の元をもってくると、 その中に: $X$ }’ が全射とする。 $N=|Y|$ ならば、 $X$ から衝突する入カペアの存在する可能性は高い。実際には $X$ から $1.18\sqrt{JN}$ の元をもってくると、衝突する確率は 1/2 以上になる。
定理 3$\sqrt{tV}$$h$(証明) }’ から重複を許してん個のを選んだとき、 これらが全て異なる場合は、と異なり、 かつ がと異なり、、かつ が ,, $a_{k-1}$ と異なる場合である。
したがって、求める確率 $P$ は、$c\iota_{1},$$a_{2}$が$a_{1}$$a_{3}$$a_{2},$$\cdots,$$a_{k}$$a_{1},$ $a_{2}$$P=1-\underline{7t-1}\uparrow?.-$2$a_{k}$$a_{1}$$a_{2},$$\cdots$$\frac{\prime l-l_{i}+- 1}{\uparrow?}=1-(1-\frac{1}{n})(1-\frac{2}{1}7)\cdots(1-\underline{k-]}71)$$7?.7l$で与えられる。 これを自然対数を用いて近似すると、$: r=\frac{k-1}{n}$(15)として、$? \underline{1}.\log(1-P)=\frac{1}{n}\sum_{=0}^{A.-1}\log l_{l}^{1-\frac{j}{r})}$$\simeq\int_{1-\tau}^{1}\log l\mathfrak{c}l\dagger=-.l\cdot-(l-r)\log(1-x)=-\frac{:r^{2}}{2}-\frac{i13}{3}-\cdots$(16)57を得る。

$1^{J}=\frac{1}{2}$となるんを求めるには、上式から、解$\frac{x^{2}}{2}\simeq 71\underline{1}$.

$J^{\cdot}$が小さいことを利用して解けばよく、(17)$\log 2$(18)$A\cdot\simeq\sqrt{2\log 2_{7l}}=1.18\sqrt{n}$が得られる。 $k=$ [777[のときは、確率は $P=0.4$ になる。 (証明終り).I^記定理 3 はいわゆるバースディパラドックスである。これによれば、認証の標準として定められている DES を用いた認証法は N $N=2^{32}$ を採用しているので、弱い。実際、$\sqrt{\backslash }=2^{1)}\backslash =6_{J}^{r},$$536$

個の入力について衝突を検査するのは容易である。
なお、バースディパラドックスの定式化にはもう一つある。 クラスの中で、誕生日の一致する男女のペアが存在する確率 ，魃曚垢燭瓩砲蓮 クラスの大きさはどのくらい必要かというもので、実際にはこのタイプが解読に用いられる。スケールが大きくなると、 どちらの定式化でも同じ結果となる [Ni90]。

4

暗号鍵

暗号鍵は暗号変換のパラメータと考えられる。 暗号強度が高いためには、 暗号鍵数は多い必要がある。 しかし、暗号鍵の個数だけをいくら多くても、 暗号文を正しい鍵以外の鍵で復号して元の平文に近い文が出てくるようではまずい。 この場合、似た効果しかもたらさない鍵は 「同じ」 鍵として扱うべきである。 このとき、「異なる」鍵の個数を実質鍵数 [Ok88] といい、 この実質鍵数が多い必要がある。
定理 4 鍵空間において\mbox{\boldmath $\tau$}--‘目蚤 (の球に属す鍵の個数を$Q_{\epsilon}$とする。 このとき、実質鍵数は(19)$)3NK=N_{\backslash }\cdot/Q_{\epsilon}$で与えられる。ここで、 は「同一」とみなすか否かの境界を示す閾値であり、$f$$N_{J\backslash ^{-}}$は全鍵数である。

(証明) 鍵空間における全鍵数を瓠とすると、任意に選んだ鍵 $K$ がある鍵を中心として半径\epsilon の球に属する確率は、篶で与えられる。 一方、 一般的に、 互いに異なる碁石が,S’A’h=個存在$l\backslash ’0$

したとき、任意に選んだ碁石がある特定の碁石に一致する確率は–“;Nl/‘- である。そこで、 これらの確率を等号で結べば、式 (19) を得る。 (証明終り)

ここで、 ビット反転率 [Na80] に基づいて、乱数加算型の簡単な暗号 y=.?叫 $K$ の実質鍵数を具体的に求めてみよう。長さ の二つのビット系列のビット反転率 $d(X_{1}, .t_{2})$ を$:1_{1},$$\prime l$$d\{x_{1},$$\tau_{2}$)$L_{2}$$= \frac{\}1alYlIni_{11}g(ir_{1},i\ddagger_{2})}{n}$(20)で定義する。 ここで、 Ha $1ll|11i_{t1}g(.l_{1}.x_{2})$ は? の間のハミング距離である。 ただし、反転率は0.5 のときが最も離れており、 1 のときは実は距離 と同じとみなすべきである。そこで、修正したビット反転率 $r(?_{1}, z_{2})$ :$x_{1}.$$0$$r(a_{1}.:1_{2})= \frac{1}{2}-|\frac{1}{2}-\frac{Ha\iota nI11ing(x_{1},?_{2})}{n}|$(21)$y=x\oplus K$(22)を用いる。
さて、 暗号変換を

58とする。 ここで、 は任意の,, 次元バイナリベクトルをとり得るものとする。 このとき、 ある鍵\kappa から半径\epsilon の球に属する鍵の個数は、$l\backslash$$Q_{t}$$Q_{\epsilon}=|\{.\}$: Hamrning(K, )$;v$$\leq,,\subset$$=|\{z‘ :\backslash v\in\iota igl_{1}t(:l\cdot)\leq t\}\epsilon$で与えられる (すなわち、$wC^{\backslash ig1_{1}t(r\cdot)}$

または垣 $aIttIni_{I1}g(K,:I^{\cdot})\geq 7’(]-c)$ }または weight $(a\cdot)\geq 71(]-c)$ }$|$$|$(23)

は、.r の中の 1 の個数を示す)。 これは、誤差関数を用いて近似できる。
(24)$\sum_{i=0}^{k}(\begin{array}{l}7li\end{array})\simeq 1-\in\backslash rf(\frac{A\cdot-1\iota p}{\sqrt{7\iota pq}}I$$p+q=1$ .
ここで、$erf(x)=$$\infty\frac{1}{\sqrt{2_{7i}}}e^{-\frac{t^{2}}{2}dt\simeq\frac{1}{\wedge 2\pi x}e^{-\frac{x^{2}}{2}}}$.

(25)

この誤差関数を用いると、実質鍵数は$SNI \backslash ^{r}=\frac{2^{n}}{Q_{\epsilon}}=\frac{1}{2erf(1-2\epsilon)\sqrt{|;}}=\sqrt{\frac{n\pi}{2}}(1-2\epsilon)r_{-}^{\frac{(1-2\epsilon)^{2}??}{2}}$(26)となる。
オーダーを見るために、 2 を底とする対数をとると、主要項は$\frac{(1-2\epsilon)^{2_{71}}}{2}]og_{2}e$(27)

であり、見かけ上の鍵ビット長 7? が減っていることがわかる。

References[M091] 宮野, 岡本: 暗号における誤り波及に関するグラフ理論的一考察, 電子情報通信学会晴報
セキュリティ研究技術報告, pp.47-53, 1991
$IbF_{\lrcorner}(--\{90- 51$[Na80] 中村: 自己同期型簡易陪号方式に関する一考察, 第 3 回情報理論とその応用研究会予稿集,$pp.37^{-}1- 377$

[Ni90] Nishim,1980) $ilitv$$11^{\cdot}\dot{e}\{:P_{1}\cdot obat$

to meet in the middle. Journal of Cryptography, Vol.2, pp.13-22,

1990[Ok88] $OkaI1l()((y$ ; Substan(ial number of cryptographic keys and its application to encryption
design. , Proc. of Eurocrv[)( $88$ . pp.361-373, 1988
[Ok92] 岡本, 秘密情報分散管理方式の構造について, SCIS92, 1902