BLS12-381について
BLS署名だけに使われている楕円曲線ではなく、一般的にペアリングの計算を行う場合の現状ベストプラクティスな楕円曲線として活用されている。
具体的には、
DfinityのBLS署名
sharding notariesの署名集約
zk-SNARKs
VDFs
どういう仕組みなのか
なぜpairing-friendllyなのか
なぜpairingの計算がしやすくなるほど秘密鍵の漏洩リスクが上がるのか
BN curves と BLS curves
Barreto-naehring(BN254)
.$ q = 2^{254}
110-bit security
Barreto-Lynn-Scott(BLS)
. $ q = 2^{384}
128-bit security
https://gyazo.com/239c271dbdcf08a4187dd42fa0a622f2
従来の公開鍵プロトコルの文脈ではグループの位数を増やせばセキュリティは増加する（その分、データサイズも増加する）が、ペアリングベースの暗号文脈では、埋め込み次数を増やすことがセキュリティ増加に繋がる。
BLS12曲線
BLS12曲線はq,rに関して、位数qの基礎体$ F_q、埋め込み次数12の位数rのサブグループとし、
$ q = \frac{x^4 - x^2 + 1}{3}(x - 1)^2 + x
$ r = (x^4 - x^2 + 1)
ここに、いい感じのxを代入して安全性的にいい感じのq, rが得られるようにパラメタを設定したのがBLS12-381。
埋め込み次数をkとして、$ G_1と$ C(F_{p^k})(=$ F_{p^k}を座標にした楕円曲線)は位数rのサブグループ$ G_2を持つ。（実際、位数rのサブグループはr-1個存在する）
有限体座標変換はk＝2であり、ペアリング計算はk＝12。
楕円曲線の埋め込み次数 (embdding degree of elliptic curve)
pを有限体の位数、rを楕円曲線の位数とした場合、rがp^k-1を割れるような最小の整数kを埋め込み次数と呼ぶ。$ \frac{p^k-1}r, $ p^k = 1 (mod r)となる最小のk
拡大体$ F_{q^2}から拡大体を作る操作を繰り返すことで、位数rのサブグループの元と位数rの$ F_q^{12}のサブグループの元との間で安全性の高いペアリング計算を行うことが可能になる。why。
拡大体を構築していく具体的なプロセスは以下の通り。
A=-1として、$ F_{q^2}は、$ \frac{F_q(u)}{u^2-A}
既約多項式u^2+1を法とした多項式の集合。
B=u+1として、$ F_{q^6}は、$ \frac{F_{q^2}(v)}{u^3-B}
C=vとして、$ F_{q^{12}}は、$ \frac{F_{q^6}(w)}{w^2-C}
BLS12-381
上記の必要条件を満たした最も大きな$ qと最も小さな$ xのハミング重みを生成するために、x = -0xd201000000010000でBLS12-381をインスタンス化。
ハミング重みとは、ビット列中の1の個数。つまり、0だけからなるシンボルとのハミング距離。
q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
(381 bits)
r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
(255 bits)
もしBLS12曲線で128-bit securityを目指すのであれば$ qは約384bits、$ rは約256bits。
計算効率性のため、zkcryptoでは以下のプロパティを加えている。
qは$ 2^383より小さく、rは$ 2^255より小さくする。
ペアリングの計算効率性を上げるためxのハミング重みを小さくする。
x mod 72 = {16, 64}
$ E(Fq) : y^2 = x^3 + 4
$ E'(F_{q^2}) : y^2 = x^3 + 4(u + 1)
cofactorとは、楕円曲線の群の位数をbasepointにおけるサブグループの位数で割った値。
code:G1
x = 3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507
y = 1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569
code:G2
x = 3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758*u + 352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160
y = 927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582*u + 1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905
.$ F_qの元はビッグエンディアンで48bytes
.$ F_{q^2}の元はビッグエンディアンで96bytes
G1はFqの元が座標、G2はFq^2の元が座標
G1の非圧縮形は96bytes, 点圧縮は48bytes
G2の非圧縮形は192bytes, 点圧縮は96bytes
座標に変換される前にG1, G2エンコーディングの最上位ビットsはマスクされる。
最上位ビットがセットされたら圧縮形であり、されなければ非圧縮形
セカンド最上位ビットがセットされたらその点は無限遠点で他のbitsは全てzeroに。
サード最上位ビットは、その点が圧縮形かつ無限遠点ではなく、そのx座標においてより大きなy座標である場合にセットされる。
MOV リダクション
ECDLP(楕円曲線)からより簡単なDLP(有限体)に帰着する攻撃手法。
埋め込み次数が12以上だと安全
もし埋め込み次数が1だと、ECDLPが有限体上での演算の難易度になってしまう。
ただし、埋め込み次数が高すぎるとペアリングの計算が大変になってしまう。
.$ Q=rPのECDLPにおいて$ rPを計算する代わりに、任意のQに対して$ u = e(P, Q)と$ v = e(rP, Q)を計算する。
.$ v = e(P, Q)^r = u^rを計算することで、ECDLPを解くために有限体のDLPに帰着させることができている。
DLP: 位数1024bits VS ECDLP: 位数160bitsなのでDLPが解きやすくなる
巡回群の離散対数問題に対して（特にECDLPに対して、DLPに対してはもっと効率的な方法が提案されている）最も効率的な攻撃方法はPolardのρ法。
ECDLPに対する総当たり攻撃の計算量がO(位数）であるのに対し、ρ法ではp＝位数として、$ O(\sqrt{p})となる。
一方で、DLPはindex calculus algorithmなどを使ってsubexponential時間で解くことができる。
埋め込み次数が十分に大きいとv=u^rとなるrを見つけることが困難になる。
128 bits of securityは$ 2^{128}ステップの攻撃が必要であるということ。
MOVアタックに必要なのはECDLP(楕円曲線)からDLP(有限体)に帰着すること。全てのEC群を移すのではなく、点Pから生成した巡回群subgroup<P>を移す。
実装まとめ
rust, C++の実装が多い。