“世界最速”のペアリング暗号化技術をどう実現するか？　ペアリングを使うのに固定多倍長演算が必要な理由

ふだんはペアリングを使った暗号化技術の研究や実装を担当

光成滋生氏：「WebAssembly向け多倍長演算の実装」について光成が発表します。

簡単に背景を紹介したあと、実装についてIntelのx64における多倍長演算の歴史を紹介して、WebAssemblyでの戦略を紹介します。

自己紹介です。SNSやGitHubでは@herumiで活動しています。Intelや富岳でのJITやAI関係の最適化をしていて、今日はそちらではなくて暗号とセキュリティに関するR＆Dの中の、ごく一部を紹介します。

私は主に、ペアリングを使った暗号化技術の研究や実装をやっています。ペアリングは暗号文の内積や署名の集約などができる機能をもっています。実装を公開していますが、一応世界最速なはずです。WindowsやLinux、MacやM1 mac、AndroidやiPhoneなどで動いて、GoやC#、JavaやRustなどのbindingを提供しています。

一例として、暗号文のままの積和演算ができます。例えば、クラウドでカメラを買った人が漫画を買っているか。あるいは喫煙歴のある人がどれぐらい肺がんになりやすいかなどを調べる時に、クロス集計をよくしますが、それぞれの人が自分の買った・買わない、吸った・吸わないなどを暗号化してサーバーに送ります。

クラウドサーバーでは暗号化されたままクロス集計をして、解析をする人がデータを復号して研究します。この状態になった時は、それぞれのデータが何かがわからないのでプライバシーの向上が望まれます。

これはすごく簡単なWebAssemblyで作ったデモですが、これは漫画を買った・買わないという列だと思ってください。これはカメラを買った・買わないで、例えばこの人が、買ってない・買った、買っていない・買ってない、買った・買っていないと各自で暗号化します。

隣に暗号文が載っていて、同じ0や1を暗号化してもでも異なる数字の暗号文になっているので、暗号文を見ただけでは0か1かわかりません。この状態のまま、クラウドにある計算サーバーにデータを送ります。データは暗号文のまま集計計算をします。研究したい復号クライアントに集計結果を渡して、それを復号するとクロス集計結果が得られるというかたちです。

ほかには、署名の秘密分散や集約などの機能を実践できます。BLS署名と呼ばれています。wasm（WebAssembly）の最後のほうに出てきたEthereumでは、EthereumJSというVMを作るプロジェクトがあるのですが、その中の暗号処理部分は、私のライブラリが使われています。その他多数のブロックチェーンプロジェクトでも採用されています。

書かれているペアリングとは何という話なのですが、難しいのでスキップします。これは昔書いた論文の一部をキャプチャしたものですが、詳しい話は『クラウドを支えるこれからの暗号技術』に書いてあります。PDFで無料で取れるのでご覧ください。

固定多倍長演算はどうやって計算するのか

ペアリングが難しいので、ちょっとだけブレイクダウンしていきます。ペアリングを使うには楕円曲線が必要になります。楕円曲線を実装するには、拡大体や有限体が必要です。有限体は、固定多倍長演算が必要になってようやくタイトルの文字が出てくるのですが、実際にはxやyやpを384bit、あるいは256bitの整数として足したり引いたり掛けたりした値を、pで割った余りをひたすら計算することになります。

そもそもこんな数字の足し算や掛け算をどうやってやるのというのが今日の本題です。x86-64で解説して、後半はWebAssemblyでどのようにするかを紹介します。これ以降使う記号として、":"でつなげた場合に、それぞれは32bitないし64bitの数字とします。例えばx=[x3:x2:x1:x0]の場合は64bitが4つなので全体で256bitの整数を表すと決めておきます。

小学校に戻って2桁の足し算をやってみます。36＋47を計算しようとすると6＋7で13、3＋4で7ですが、繰り上がりがあるので83になります。同じように64bitのレジスタa＋bをやると、本当は65bitになるはずです。C言語では64bitに切り捨てられていますが、IntelのCPUではadd a,bと書くと、これはaにbを足し込むという意味で、65bitの残り1bitはCarryフラグ（CF）というもので、値が入ります。

すなわちCFが1bitで、aが64bitで合わせて65bitの値がa＋bの値になっています。これを使って、例えば128bitの値の整数2つをそれぞれ64bitで足し算しようとすると、6と7の足し算がadd y0,x0で、y0にx0を足し込み、0か1の繰り上がりがCFに入ります。

次にadcという命令を使ってy1,x1とやると、y1にx1と今付いたCFが入って、繰り上がりを更新します。ここでは1がCFに相当します。Intelのaddとadcという命令は、AArch64というM1 Macや富岳のCPUではaddsとかadcsと呼ばれる命令です。

4桁の足し算をしようとすると64bitが4つで、256bitで足し込むのは、Intelだとadd y0,x0、adc y1,x1、adc y2,x2、adc y3,x3となります。これで一応足し算ができるようになりました。

次に掛け算もやってみます。73×7をやろうとすると7×3＝21に、7×7＝49で繰り上がりの足し算をします。x64ではmulという命令があって、これは64bit×64bitで128bitになる命令です。mul xと書くと、x×raxというレジスタの値をrdxというレジスタとraxレジスタのペアで128bitを表します。

AArch64では128bitをゲットする命令はありません。上位・下位64bitをそれぞれmulとumulhという2つを使って取得します。いずれにせよmul命令を使って128bitの値を作り、Carry付きのaddをして求めます。

256bit×64bitの計算ではCarryフラグが破壊されてしまう

256bit×64bitの計算をしようとすると、mul命令がCarryフラグを破壊するという問題が出てきます。これは8086という大昔からの流れです。128bit×xをやる時は、128bitの計算をして、次に128bitをまとめて、足し算をして次にここで求めてからまた隣の足し算を本当はやりたいのですが、この値を全部2×4の8個のレジスタにいったん保存してから足さないとCarryが壊れるのでうまくいきません。

ということで、Haswellからはmulxが登場します。これはCarryフラグを破壊しない命令です。mov rdx,xとやるとxの値がrdxに入って、そのあとにmulx H,L,yと書くとx×yの値が128bitのここに入ります。この命令を使うと256bit×64bitがz1×z0を計算して、隣のz2、ztに掛け算したあとに、足し算がすぐ始められます。

次にmulxをやるのですが、ここでCarryフラグは壊れないので、隣のadcというのをこのあたりに挟んで掛け算して足すると、中間レジスタがいらないので高速に実行できます。

では次に、256bit×256bitをやりましょう。この計算はy0×256bitでy×0に入ります。次にy1×yの値でy×1に入ると考えると、やっぱりy×0を計算して、y×1を計算している途中で下からピコピコと足していきたいのですが、問題が発生します。この1つを求める時に先ほどのCarryを破壊しないmulxを導入したので、adcを使って足せるんですが、それをやっている最中にこっちのaddというのは足せません。

要するに、y×0とy×1の2つの計算が終わってからでないと足し込めません。やはりレジスタを圧迫します。というわけで、Intelがadcxとadoxという命令が登場させました。問題点は、グローバル変数であるCFが1個しかなかったことです。2個あれば掛け算をしながら次のを足ます。adcxは従来のCF付きの加算なのですが、adoxはオーバーフラグという別のグローバル変数を用意して、これを独立で動くようにしました。

事前に計算した値で次の値を計算する時に、mulxで掛け算したあとにadcxを使って、足し算を始めます。隣の値を計算して次にadoxで足し算をします。今度はadcxでやると点線の矢印と赤い矢印は独立しているので、それぞれ中間レジスタを低減しながら足すことができます。BroadwellやAMDだったらRyzenから対応しています。最近はこういう命令を使って実装します。

（次回へつづく）