Re: 位数ペアリング版BGNの実装
コード整理した. とりあえず試せるレベルにはなったか.
約10年振り知人に会う. 元気そうでなにより.
Re: 位数ペアリング版BGNの実装
コード整理した. とりあえず試せるレベルにはなったか.
約10年振り知人に会う. 元気そうでなにより.
Re: 位数ペアリング版BGNの実装
キャッシュを使った復号処理の実装を追加した. GT::powって下手したらpairingより遅い. 復号時必要なのでGLV版を用意するか.
応用しようとするといろいろ細かい部分で作らないといけなくて大変だ.
wasmの演算
semanticsを見る限り, 32bit/64bitレジスタはあるけどcarryつき加算・減算や64bit x 64bit→128bit乗算命令がない. これはかなり辛い.
LLVMのbitcodeとはツールで簡単に変換できるのかと思っていたけどi128を含むLLVMコードをemccに食わせたら
LLVM ERROR: Binary operator type not yet supported for integer types larger than 64 bits
あれー. 予想していたよりいろいろ使えない.
wasm
本当は【第19回 数学カフェ】超越数回に参加したかったのだが喉や頭の痛みが治らず断念.
仕方がないので自宅でWebAssemblyの勉強のためemsdkをインストール. 途中でエラーになったと思ったら使っていたVMがdisk full.
仮想ディスクを追加してfdiskでパーティションをいじってサイズを増やす. そのあとe2fsckを使ったら,
/dev/sdb1 has unsupported feature(s): metadata_csum e2fsck: Get a newer version of e2fsck!
みたいなエラー. 素のUbuntu 16.04なんだけどなあ. e2fsprogsからソースをダウンロードしてビルドしてfsckしてからresize2fsしたらうまくいった.
emsdkはC++11などは普通に使えるようだ. まずGMPを動かすのを目標にする.
位数ペアリング版BGNの実装
とりあえず最低限のコードは書いた(bgn.hpp). 復号は離散対数問題を解かないといけないのでどうキャッシュを構築するかが問題.
同窓会
修士1年のときにお世話になった先生の東京方面での小さな食事会. 20年振りぐらい. 不肖の弟子(といえることは何もしていない)ながらも(ありがたいことに)覚えてくださっていた.
名前や顔の記憶が怪しくてもセミナーで使っていたテキストはしっかり覚えてるものだなあ.
合成数位数ペアリングを素数位数ペアリングに変換する
Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups. 部分群決定問題ってなんか昔似たようなことを考えたなあと思ったら自分の論文が引用されていた.
当時(2002年頃)は, 楕円曲線の2次元Fpベクトル空間としての構造を使ってなんとか情報を暗号文に追加できないかと考えていたのだった. 結果的にそれは否定的な結論を得て, The Vector Decomposition Problemというのにつながったのだった.
それはさておき論文が微妙に一般的な個数でやっていて分かりにくい(自分には). 一度だけ乗算可能なSHEをメモしておく.
xi, yi, zi(i = 1, 2); 秘密鍵 e : G1 × G2 → GT ; ペアリング G1 = <P1>, G2 = <P2> 暗号化 Enc(m) := (C1, C2) ; Ci ∈ Gi^2 Ci := (Si, Ti) = ((m yi + ri)Pi, (m zi + xi ri)Pi) Si, Ti ∈ Gi 復号 Dec(Ci) xi Si - Ti = (m xi yi + xi ri - m zi - xi ri)Pi = m(xi yi - zi)Pi これが(xi yi - zi)Piの何倍か 加算 Add(Ci, Ci') := Ci + Ci' := (m yi + ri)Pi + (m' yi + ri')Pi = ((m + m')yi + (ri + ri'))Pi 乗算 Mul((S1, T1), (S2, T2)) := (e(S1, S2), e(S1, T2), e(T1, S2), e(T1, T2)) = (s, t, u, v) 乗算復号 Dec(s, t, u, v) s^(x x') v / (t^x u^x') = e(x S1, s' S2) e(T1, T2) / (e(x S1, T2) e(T1, x' S2)) = e(x S1 - T1, x' S2 - T2) = e((m(x1 y1 - z1)P1, m'(x2 y2 - z2)P2) = e(P1, P2)^((x1 y1 - z1)(x2 y2 - z2) m m') これがe(P1, P2)^((x1 y1 - z1)(x2 y2 - z2))の何倍か 乗算後の加算 (s, t, u, v) + (s', t', u', v') := (s s', t t', u u', v v')
乗算後の暗号文はBN曲線だとFp^12の4倍でp=256bitでも256 * 12 * 4 = 12KiBと結構大きい.
合成数位数ペアリングを使ったSHE
合成位数ペアリングは食わず嫌いで全然勉強してなかったけど一度だけ乗算可能なHEがある(2005年?)というので調べた(Evaluating 2-DNF formulas on ciphertexts).
p, q ; 素数 n = pq P ; 位数nの点 Q = pP e : G × G → G' ; ペアリング 秘密鍵 ; q 公開鍵 ; n, P, Q 暗号化 C = Enc(m) := mP + rQ ; rは乱数 復号 qC = qmP + qrQ = mqP ; これがqPの何倍か求めて復号 加算 Enc(m1) + Enc(m2) := C1 + C2 = (m1 + m2)P + (r1 + r2)Q 乗算 Enc(m1) * Enc(m2) := e(Enc(m1), Enc(m2)) 乗算の復号 e(C1, C2) = e(m1P + r1Q, m2P + r2Q) = e(m1P, m2P)e(m1P, r2Q)e(r1Q, m2P)e(r1Q, r2Q) e(C1, C2)^q = e(P, qP)^(m1 m2) これがe(P, qP)の何乗かを求めて復号
風邪引いた
喉が酷く痛い.
Re: BN曲線のG2用GLV実装完了
G2の元の変更メソッドの中で位数が正しい素数rになっているかr倍して0になるかチェックしていたのだけど, そこがr倍する関数G2::mulがGLVアルゴリズムになってしまって常に0になるようになってしまっていた.
ここもGLV::mulは使ってはいけなかった.
サウナと眼鏡
10年振り(?)ぐらいにサウナに5分だけサウナに入ってみたら出たあとどうも視界が悪い. よくみたら眼鏡のレンズに細かいヒビが入って使い物にならなくなっていた. あっちゃ. 眼鏡をして入ってはいけなかった. えらい想定外の出費だ.
BN曲線のG2用GLV実装完了
テストでは動くのに本体に組み込むと動かなくてなんでかなと思ったら, G2の元のmapToPoint関数でcofactor倍するところではGLVは使えないのを忘れていたせいだった(G2の元じゃないから).
第9回「広域センサーネットワークとオーバレイネットワークに関するワークショップ」参加
予想以上に(失礼)おもしろかった. Bitcoinの人材募集(と選別)のために最小限のブロックチェーン実装をしたのすごい.
C++WG
C++17DISでの変更点いろいろチェック.
std::string s;でs[str.size()] = ?;は今まで未定義動作だったのが,?=CharT()のときだけはOKになったのがへえと思った.
BN曲線のG2用GLVアルゴリズムの実装開始
なんかうまくいかないと思ったらいろいろ初歩的なミスが続いていた. 早く終わらせて次にいきたい.
one-way aggregate signatureをどう構成してるのか知りたかったけどその話題はなかった. 関連文献をみてみるか.
『エクサスケールの衝撃』(齊藤元章)
PEZYの人の本. スパコンの実績はすばらしいが, それに続く未来は壮大なほら話. 衣食住のインフラを整えるコストが全然考慮されてないし, なんでもスパコンで解決できるわけでも無い.