高寺 俊喜(JP3BGY)

無線家で電子工作好きなエンジニア。暗号に興味あり。
現在はTSG平部員（2018年総長賞にいた人）

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi (っ`･ω･´)っﾌﾚｰﾌﾚｰ!!!

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi レビューできる状態にするには最低限の編集をしないといけなくて～みたいな話ですかね。まあ、概要説明であればAIでも大きな間違いはないとは思います。もちろん、動画全体でも要所の説明でも見返して気になったところがあればご相談ください。

[高寺 俊喜(JP3BGY) @JP3BGY]

いや、今までのベストはp^{1/2}O(log p)^O(1)か、abst見落としてたわ。

[高寺 俊喜(JP3BGY) @JP3BGY]

https://t.co/Ko4HsnBw1g
supersinglar isogeny problemの進展
p^{1/2}からp^{1/3+o(1)}に改善とのこと。

[levent @__alpoge__]

hello there the jacobian conjecture is false thanx to my close friend akhil for asking about it and my other close friend fable for working during the world cup final

((1+xy)^3 z + y^2 (1+xy) (4+3xy), y + 3 x (1+xy)^2 z + 3 x y^2 (4+3xy), 2 x - 3 x^2 y - x^3 z): \C^3\to \C^3, has jacobian determinant -2, and sends (0, 0, -1/4), (1, -3/2, 13/2), and (-1, 3/2, 13/2) to (-1/4, 0, 0)

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi 同型の話はむしろ簡単な説明があって、実は同型って一対一対応する（逆変換が存在する）ような（一次）変数変換なんですよ。なので、そのような変換ができることとj-invが一致することが示せる、みたいな説明をすればよいと思います。

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi そういえば言いそびれてましたが、SIDHで最終的に得られるj-invariantは一致しますが、実は(ψ_*φ)∘φと(φ_*ψ)∘ψは写像として一致するとは限りません。この可換図式は”同型による違いを除いて”一致します。そのため、SIDHだとE_ABとE_BAは式が違うかもしれないし、向き(符号)が違うかもしれません。

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi もう少しだけ踏み込んだ説明をするなら、添付したスライドページのように、pushforwardの具体的構成と可換図式の部分のみを説明して、詳細は次回って感じにしてもいいと思います。ただ、これだけの説明でも胃もたれする人はいるとは思うので、この辺はお好みでってところかと。

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi その点が、以前言ったseparable isogenyと部分群の対応の話になりますが、正直最初の動画ではその説明はなくてもいいような気はします。説明するのであれば、SIDHとは別にpushforwardの説明を行うのがよいと思います。

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi 最後の表現は計算問題として多項式同値（多項式時間でもう一方の問題に帰着される）であることを念頭に置いて、準同型性をなくした形になってるので、問題を文字通りにとれば準同型性があるが、ないものと計算問題として同値であるというのがいいと思います。

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi ただ、最後のは注意が必要で、有理関数を多項式時間で計算できるとは限りません。d次の同種写像はd次の有理関数で表されるので、dが多項式オーダーじゃないものは、当然多項式時間で有理関数表示が得られません。
なので、正確には「有理関数と対応することが保証されている写像」になるとは思います。

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi 数学的な見方をするなら、「有理関数で表され(=射である)準同型写像」で、弱い条件付けなら「射であり、零点を保存する」で、同種写像問題から見るのであれば、「曲線E,E'を固定したとき、奇跡的にEの点をすべてE'に移す(定数ではない)有理関数」あたりが、暗号好き向けの説明になると思います。

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi さらに、楕円曲線(E,O_E) (O_EはEの零点)とその上の任意の点P∈Eに対して、φ:E->Eでφ(Q)=P+Qは常に射(morphism)となることが知られていて、これらの定理から、同種写像を求める問題と射を求める問題は計算仮定として等価であることが言えます。

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi ただし、同種写像問題を念頭に置く場合、群準同型性は問題の複雑度に寄与しないことには注意が必要です。
というのも、射影平面上の楕円曲線は任意点に対して、それを零点とする群が一意に構成され、さらに射はその零点を保存していれば常に群準同型写像になることが知られています。

[高寺 俊喜(JP3BGY) @JP3BGY]

@meowricator プロトコルに限定したら超楕円曲線の出る幕は皆無ですね…SIDH関連で近い順に探して最初に出るのがCD-MM-R攻撃の実装だと思います。

[高寺 俊喜(JP3BGY) @JP3BGY]

@meowricator @fwarashi SIDH関連といえばKaniの補題で使う、2次元アーベル多様体としての種数2の超楕円曲線のヤコビアンではないですか？

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi こうしてほかの人と同種写像暗号の話ができるのは自分としてもうれしいので、いつでも声をかけてください。単に進捗報告と雑談だけでも僕はとっても喜びます。

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi 実装まで立ち入らないのであれば、SIDHとCSIDHはまとめて紹介しやすくて、最終的には似た形の同種写像の可換図式を作るが、その方法がVeluと群作用で違うってだけなので、かなり説明を簡素化できると思います。

[高寺 俊喜(JP3BGY) @JP3BGY]

@fwarashi いいと思います。最後に、SIDHとCSIDHのやりたいこと(Velu, 群作用を用いた可換図式の構成)の紹介をすると完璧ですかね。
それと、CGLは残念ながらcryptohackにはありませんが、2-同種とバックトラック検知さえわかればいいので取り組みやすく、実装演習を行うならCGLがおすすめです。