MiMC
ブロック暗号
ハッシュ関数 (S{NT}ARK - friendly)
VDF (Even-Mansor modeのラウンドを多くする）
accumulator
plasma
秘匿コントラクトのrent solution
$ GF(2^m)、$ GF(p)上の演算。
体上の乗算の複雑性を最小化するためにS-boxesを避ける。
MiMC - n/n - Even-Mansour mode
https://gyazo.com/9412c6a9a802d6294082b546fe8e7e1c
round functionがr回繰り返される
毎ラウンドにkeyとround constantsが足される
非線形関数は$ f(x) = x^3
なので、round functionは、$ F_i(x) = F(x + K + c_i)
nは奇数
.$ r= n/{log_23}
inverseは、$ x^{{(2^{n+1}-1)}/3}
k{64]くらいで繰り返す
$ X+k_i+C_i=U ($ a=k_i+C_i)
$ U*U=Y
$ Y*U=Z
->
$ (X+a)(X+a+Y)=Y+Z
MiMC - 2n/n - Feistel mode
https://gyazo.com/f50f6e25cf3a809fd4d377d1b9bfd869
ファイステル構造なので、平文を2分割しラウンドごとに左入力をsubkeyでXORした値をラウンド関数であるf(x) = x^3に通し、右入力とXORをとり、次のラウンドで左右を入れ替える。
復号化は、使用するsubkeyの順番を逆にして同じ構造で通せばOK。（XORの性質と一方の入力はそのままだから）
Sponge mode
https://gyazo.com/0e04beb3a1ca6308d86ffc04dec381e2
最初にpadding
MiMCHash-tでは、MiMC-n/nでn=4t+1, s = 2t
例えば、MiMCHash-256: n= 1025
permutationになるようにnは奇数
掛け算に対して足し算は無視
over snarkではmultiplication1つ(=r1cs 1つ）
LowMCでは2つ
On the Indifferentiability of the Sponge Construction
実装
Security
block-level attackを防ぐために毎回違うround constantsで使う。
merkle rootをunique IVとして使う。
gcd(d, p-1) = 1となるようにexponent: dを定める。pはscalar field。
Interpolation Attack
secret keyを知ることなく暗号化関数に相当する多項式を生成し、ciphertextに対応するplainytextを生成する攻撃。
plaintext/ciphertextペアd+1個で秘密鍵を復元（あるいは新しいciphertextを生成）する次数dの多項式を作ることができる。
この攻撃を防ぐためにはRounds回数を増やすことが有効。
code:1.rs
p = 21888242871839275222246405745257275088548364400416034343698204186575808495617
e = 5 # exponent which is a permutation
b = log2(p) / 8 # bytes per field element
r = log2(p) / log2(e) # number of rounds
d = pow(e, r) # degree of the polynomial
l = d * log(d) # complexity of Lagrange form
m = 2**l * b # memory required to store coefficients
https://gyazo.com/d6d4b6828c447376b6d5f3e934a17ab2
GCD Attackはinterpolation attackよりも計算複雑性が高い。
longsightL
- compression function
https://gyazo.com/d3ac46dc01304a288e909e3a7ad77567
LP231 with MimC(F_p)-p/p
Mimcと比べて圧縮のためにpermutationを3回呼ばないといけないが、その分field sizeが1/3になるのでペイオフする。
固定鍵のブロック暗号から暗号学的ハッシュ関数を構築
Going back to MiMC: it seems as though Miyaguchi–Preneel is a better option than LPA231. Define LongsightMP-R/p/e as Miyaguchi–Preneel applied to MiMC-R/p/e. We need R = log7(p) ~= 91 rounds for the non-Feistel variant of MiMC-R/p/7. Raising to the power 7 requires 4 constraints. So, for the BLS12-381 p,
LongsightMP-91/p/7 requires 728 constraints.
LongsightL-91/p/7 requires 1092 constraints.
(For reference, the insecure LongsightF-322/p/3 required 644 constraints.)
However, it should be noted that MiMC's key schedule is trivial/non-existent (the same key is added in each round). This doesn't matter for LPA231 which doesn't use the key, but Miyaguchi–Preneel assumes an ideal cipher and so might be more attackable through key scheduling weaknesses. I'm not a symmetric cryptographer (yet) so I don't know how serious this is, but it makes me nervous.
LP231Ap
オリジナルは$ F_2^{128}の群で'+'はXOR。
$ F_pで'+'をmod p のadditionにしたvariantがLP231Ap
longsightF
510 -> 255 bit圧縮関数alternative
MiMCのFeistel modeを使う
510 bitのpermutationを作るために$ MiMC^P(F_p)-2p/pで行い、結果をsingle field elementにtruncateする。
2倍のroundのpermutation(322 rounds)が必要になるが、permutationのinstanceは１つだけ。
daira -> longsightFの安全性根拠
How many queries are needed to distinguish a truncated random permutation from a random function?
harry ->
code:longsightf322p3
function LongsightF322p3(xL ⦂ Fp, xR ⦂ Fp) {
for i from 0 up to 321 {
xL, xR := xR + (xL + Ci)3, xL
}
return xL
}
one layer of the merkle tree, including selection of the correct side of the authentication path.
(insecure) LongsightF-322/p/3 => 645 constraints
LongsightMp-91/p/7 => 728 constraints (Miyaguchi-Preneel)
LongsightL-91/p/7 => 1092 constraints
Pedersen hashing => 1779 constraints
BLAKE2s => 21136 constraints
daira ->
Despite these potential savings, I believe MiMC has had insufficient cryptanalysis and should be excluded from Sapling (even if the number of rounds were increased). We can always use it in some future circuit upgrade to further improve performance, if that seems justified.
My intuition is that the fixed key doesn't allow any round reduction.