HADES StrategyとPOSEIDON Hash

HADES Strategy

P-SPN と SPN を組み合わせることで、Wide Trail Strategy が持つ攻撃への耐性に加えて、 その他の種類の攻撃にも耐性を持たせた、ブロック暗号を設計するための指針。

Wide Trail Strategy

Differential/Linear Cryptanalysis を耐性を持つラウンド関数を設計するためのストラテジー。
Algebraic attack のような Low-degree attack に対する耐性はない。

P-SPN (Partial-SPN) 構造

SPN の一部の S-Box を、全ラウンドで Identity 関数に置き換えるもの。Zorro などが採用している。
Wide Trail Strategy は、各ラウンドで全体的に S-Box を入力に適用することが前提なので、Wide Trail Strategy 向けに作られた、Differential/Linear Cryptanalysis に対する耐性を証明するツール群を P-SPN に対して使用することはできない。そのため、別途、試行錯誤的な形で、それらに対する耐性を証明していく必要がある。

P-SPN
+---------+--------+
| id　..　id | S .. S | Round 1
| id　..　id | S .. S | Round 2
| ....... | ...... | ...
| id　..　id | S .. S | Round r-1
| id　..　id | S .. S | Round r
+---------+--------+

HADES Strategy

Full round

SPNと同じように、全ての分割された入力データーに対して S-Box を適用する。
Wide Trail Strategy と同じ攻撃に対する耐性を持つ。

Partial round

１ラウンドに適用するS-Boxの数を１～３程度に減らして、かつ S-Box 内の関数の次数を上げる。 こうすることで、Algebraic attacks などの Low-degree attacks に対する耐性ができる。
残りの入力データーに対しては Identity 関数を適用する。Identity 関数は、入力と出力が同じになる関数。

###　構造
はじめと、終わりに、Full round を置いて、その間に Partial round を置く。
攻撃者の Partial rounds に対する攻撃を防ぐために、はじめと終わりに Full rounds を置き、Partial rounds をマスクする形になっている。

###　S-Box
$S-Box(x)=x^{\alpha}$
$\alpha \ge 3$ は、 $gcd(p-1,\alpha)=1$ となる最小の数。

HADES　Strategy
+--------------+
| S ........ S | Round 1　　　\
| ............ | ...      | Full rounds
| S ........ S | Round n 　/
+----------+---+
| id .. id | S | Round n+1　 \
| id .. id | S | Round n+2  |
| ........ | . | ...        |　Partial rounds
| id .. id | S | Round m-1  |
| id .. id | S | Round m　　　　　　　/
+----------+---+
| S ........ S | Round m+1 \
| ............ | ...       　| Full rounds
| S ........ S | Round r   /
+--------------+

ラウンド関数実行の詳細

１つのラウンド関数は、３つのステップに分けて実行される

1. $ARK(\cdot)$ (Add Round Key)
2. $S-Box(\cdot)$ (Sub Words)
3. $Mix(\cdot)$ (Mix Layer)

ARK,S-Box,Mix -> ... -> ARK,S-Box,Mix -> ARK(,Mix)
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 ^-- Optional

最後のラウンドを実行した後で、$ARK(\cdot)$ のみが実行される。その後に $Mix(\cdot)$ が実行される場合もある。

体, S-Box, Mix Layer の詳細

HADES では、使う 体、S-Box、線形変換レイヤー (Mix Layer) について、何を使うべきかについての制限を設けていない。

HADES MiMC

Wide Trail Strategy を基に作られた SHARK に HADES Strategy を適用したもの。

満たすべき条件

• $+$, $\times$　が定義されている、$p$　が素数の $F_p$ 上で実行
• $p \approx 2^n \ge 11$
• $t \ge 2$ words

ラウンド関数

• シークレットキー $k$は、 $k \in (F_p)^t$
• 行列 $M$　は、可逆行列で、$M \in (F_p)^{t \times t}$ を満たす。
• Sは、$S(\cdot): (F_p)^t \rightarrow (F_p)^t$ で以下の形。

ラウンドの種類	定義
Full	$S=[S(\cdot),...,S(\cdot)]$
Partial	$S=[S(\cdot),I(\cdot),...,I(\cdot)]$

$S(\cdot)$ は、S-Box。$I(\cdot)$ は Identity 関数。

その上で、

$R_k(\cdot): (F_p)^t \rightarrow (F_p)^t$
$R_k(\cdot) = k + M \times S(\cdot)$

ラウンド数

ラウンド数 $R$ は、$2 \cdot R_F + R_p$
S-Boxの内容や、$p$, $t$に依存して変わる

S-Box

$S-Box(x) = x^{\alpha}$
where $\alpha \ge 3$ s.t. $gcd(p-1, \alpha)=1$

非線形の変換レイヤーを提供するための部品になる。

Mix Layer

固定の $t \times t$ MDS マトリクス
$2t+1 \le t$ であれば、要素が$GF(p)$の、そのような行列が存在する。

線形の変換レイヤーを提供する。

鍵の作り方

$k^{(0)}=k$
$k^{(i)}=M \cdot k^{(i-1)} + RC^{(i)}$

$RC^{(i)}$は、ラウンド $i$ のラウンド定数。

POSEIDON Hash

Partial層の S-Box数が 1 の HADES の変種。

入力、パラメーター条件

$N$ は Permutation　(スポンジ) のサイズ
体 $F_p$ の位数は、$p \approx 2^n$　が成り立つ、素数の $p$。
入力サイズ $t$ は、$t \ge 2$ ワード

POSEIDON π Sponge

HADESMiMCの変種。
$s$ を Security level とした時、
Rate は、セルごとに $rate = N - 2s$、Capacity $c$ は $c = 2s$ となる。

ラウンド数

Permutation がランダムに数を決めていくものとして設計される場合に、
Capacity c のとき、$2^{\frac{1}{2}c}$回の、Squeeze までは、Random Oracle との区別がつかないので、
$M$ をセキュリティーレベルとすると、$s=\frac{1}{2}c$ なので、$2^M$ 回の Squeeze までは、
permutation は、Random Oracle ように振る舞う。

$2M$ のキャパシティを設定したとき、$POSEIDON-M$と書く。
$POSEIDON-M$ は、Collision/Preimage 攻撃について、$M$ ビットの耐性を持つ。

ラウンド関数

以下の ３ つのステップを、全てのラウンドにおいて実行する。

1. $ARC(\cdot)$ (Add Round Constants) (注: HADESでは、定数でなく鍵を足している）
2. $S-Box(\cdot)$ または $SB(\cdot)$ (Sub Words)
3. $Mix(\cdot)$ (Mix Layer)

S-Box 層

$gcd(\alpha, p-1)=1$ となる $\alpha$ を使って、$S-Box(\alpha)=x^{\alpha}$

この形の S-Box を使った Permutation を、$x^\alpha-POSEIDON^{\pi}$ と呼ぶ。$\alpha$ は実際の値で置き換える。
例えば、$\alpha=3$ のとき、$p \ne 1 \bmod 3$ ならば、$3-POSEIDON^{\pi}$ など。

また、$S-Box(0)=0$ の前提で、$S-Box(x)=x^{-1}$ という形もありとする。この場合は、$x^{-1}-POSEIDON^{\pi}$ と呼ぶ。

ZKアプリケーションで最も人気のある Prime fields である BLS12-381 and BN254 curve の Scalar field の Prime subfield については、$x^5$ が最も適していることが分かっている。

Linear 層

$2t + 1 \le p$ が成り立つ場合には、各要素が $F_p$ の、$t \times t$ MDS (Maximum Distance Separable) Matrix が存在する。$t$ はスポンジへの入力のサイズ。
Linear 層では、この Matrix を使って、入力を変換する。

MDSの作り方には、いくつかあるが、Cauchy Matrix はその一つで、作り方は：

For $x_i,y_i \in F_p$ where $i \in [1,t]$
$M_{i,j}=\frac{1}{x_i + y_i}$

条件は、$x_i + y_i \ne 0$　で、$x_i$　と $y_i$ をペアとしてみた場合にユニークであること。

参考資料

https://eprint.iacr.org/2019/1107.pdf
https://www.researchgate.net/publication/225704500_The_Wide_Trail_Design_Strategy
https://eprint.iacr.org/2019/458.pdf
https://eprint.iacr.org/2011/499.pdf (Capacityのサイズの話）