entropoid - crypto-writeup-public

よく分かってないけどそのうちCTFに出るでしょ

Abstract

entropoidと呼ばれるDLPベースの耐量子暗号が提案されていた。これは分配多元環（non associative algebraic structure）上の冪乗演算である

この論文ではentropoid上のDLPを有限体上のDLPに帰着することで多項式時間に落とす

元論文では128bitのセキュリティパラメータを提案していたが、それはラップトップで10分以内に解けるようになる

ちなみに元論文というのはこれ

Introduction

元論文では分配多元環上の二項演算を定義していたが、十分に強い(alternative?)結合法則を用いて指数を減らすようなmapを定義できる。

entropoidは $(G, *)$ というquasigroupであり、 $x, y, z, w \in G$ について次の疑似結合法則(? pseudo-associativity law)を満たす（これが成立するときentropicという）

$(x * y) * (z * w) = (x * z) * (y * w)$

quasi groupというのは集合

$G$

と

$*: G\times G \to G$

という演算によって定義される構造で、

$\forall x, y \in G$

について、

$lx = y, xr = y$

をみたす

$l, r \in G$

が一意に定まる

このとき

$l$

は

left quotien

と言って

$l = y / x$

と表すし、

$r$

は

right quotient

といって

$r = x \backslash y$

と表す

ここで $\mathbf{A}$ という射を用意する。 $\mathbf{A}: x \to x^{\mathbf{A}} = (x*(x*(x*(\dots(x*x)))))$ という感じで $a$ 回繰り返す冪演算（ここで結合則が成り立つことを仮定していないので、left-to-rightな演算とright-to-leftな $(((((x*x)*x)\dots *x)$ は区別される）

このとき次が成り立つ（というか後者は定義される）

$x^{\mathbf{A}+\mathbf{B}} = x^{\mathbf{A}} * x^{\mathbf{B}}$
$x^{\mathbf{AB}} = (x^{\mathbf{A}})^{\mathbf{B}}$
ここから $(x^{\mathbf{A}})^{\mathbf{B}} = (x^{\mathbf{B}})^{\mathbf{A}}$ が成り立つらしい。これは entropic なquasi groupで成り立つとか

この性質からDiffie-Hellman schemeを構築できそう。

さて、entropicなgroupoid（亜群）を構成していく。というか天下り的に与える

$G = (\mathbb{F_p})^{L}$ とする。つまり $x \in G$ は $x = (x_1, x_2, \dots, x_L)$ という感じ

このとき、演算 $(*)$ を次の要件を満たすように定義する

$(*)$ は entropic
$(*)$ は non linear
$(*)$ は非交換的( non-commutative ）
$(*)$ は非結合的 non-associative

$L=2$ のとき、適切に $a_1, \dots, a_{15}, b_1, \dots, b_{15}$ を選んで、次のような演算がこれを満たしうる

$x * y = (x_1, x_2) * (y_1, y_2) = (P_1(x_1, x_2, y_1, y_2), P_2(x_1, x_2, y_1, y_2)$
$P_1(x_1, x_2, y_1, y_2) = a_1 + a_2x_1 + a_3x_2 + a_4y_1 + a_5y_2 + a_6x_1y_1 + \dots + a_{10}x_1^2 + \dots + a_{15}y^2$
$P_2(x_1, x_2, y_1, y_2) = b_1 + b_2x_1 + b_3x_2 + b_4y_1 + b_5y_2 + b_6x_1y_1 + \dots + b_{10}x_1^2 + \dots + b_{15}y^2$

実際に満たす演算として、次のようなものがある

$(x_1, x_2) * (y_1, y_2) = \left( \frac{a_3(a_8b_2 - b_7)}{a_8b_7} + a_3 x_2 + \frac{a_8b_2y_1}{b_7} * a_8x_2y_1, - \frac{b_2(a_8 - a_3b_7)}{a_8b_7} + \frac{a_3b_7y_2}{a_8} + b_2x_1 + b_7x_1y_2 \right)$