高価な $F_q$ 上での掛け算の数を少なくすることによって高速化する。
具体的には、SPN構造で使われる、S-Box による Substitute 部分をなくし、round 関数を、体上での多項式を使った計算 $F(x) = x^3$ にする。
Knudsen-Nyberg cipher をベースにして作られている。
MiMC-b/k
$MiMC-b/k$ は、ブロックサイズが $b$ で、キーのサイズが $k$ の MiMC という意味。
計算
言葉での説明
各ラウンドでの処理
- 初回であれば入力の $x$、そうでなければ前回の計算結果に、キー $k$ を足す
- ラウンド定数 $c_i \in F_q$ を足す（はじめと終わりは $0$。それ以外は $F_q$ からランダムに選択する）
- 結果を $3$ 乗する。
最終処理
最後のラウンドの結果に、再度キー $k$ を足す。
数式での説明
$F_i(x) = F(x \oplus k \oplus c_i )$ where $c_0 = c_r = 0$
$MiMC-n/n(x) = (F_{r-1} \circ F_{r-2} \circ \; ... \; F_0)(x) \oplus k$
ラウンド定数
事前に決定したものを使いまわして問題ない。例えば、暗号化コードに埋め込んで全ての入力に対して同じ定数のセットを使っても構わない。
必要なラウンド数
$MiMC-n/n$ で、体が $F_2^n$ の場合
$n$ を奇数として、$\lceil \frac{n}{log_2 3} \rceil$$MiMC-n/n$ で、体が $F_p$（$p$ は素数）の場合
$\lceil \frac{log_p}{log_2 3} \rceil$
体が素数ベースの場合の注意点
ラウンド関数で、$x^3$ が permutation を作ることを確実にするために、$gcd(3, p-1)=1$ となるような $p$ を選ぶ。
参考サイト
https://eprint.iacr.org/2016/492.pdf
https://tidsskrift.dk/daimipb/article/view/6946/5908