Cryptography
以前のW-OTS+の記事で少し触れたけど↓ techmedia-think.hatenablog.com NISTのポスト量子暗号の1つであるハッシュベースのデジタル署名アルゴリズムSPHINCS+は、 （↑の）W-OTS+ ハイパーツリー FORS（Forest of Random Subsets） を組み合わせてステートレス…
BitVM 0、BitVM 1、BitVM 2、BitVM Xに続いて、最近新たにBitVM 3が提案された↓ https://bitvm.org/bitvm3-rsa.pdf （2025.07.17追記：その後、セキュリティ仮定に誤りがあることが報告され、この論文は廃止され、RSAベースのガーブリングに代わる新たなBitV…
最近公開されたBitVM 3のヒントとなったJeremy Rubinによるドラフト論文Delbrag↓ https://rubin.io/public/pdfs/delbrag.pdf この論文では、Garbled Circuitを利用して、Bitcoin上で任意の計算の検証を可能にするBitVMを効率的に実現する方法を提案している…
ECDSAベースの閾値署名というと、GG18/20あたりが有名↓ techmedia-think.hatenablog.com これらのプロトコルは加法準同型性のある暗号化方式であるPaillier暗号に依存しており、署名の生成に6ラウンドの通信を必要とする。 その後提案されたDKLS23という署名…
3ラウンドECDSA閾値署名プロトコルDKLS23について調べてたいたら、そこで登場する構成要素についてまず理解しておく必要があったので、署名プロトコルにいく前に、まず紛失通信（Oblivious Transfer）とVOLE（Vector Oblivious Linear Evaluation）について…
Ligeroは、証明者が秘密の値を知っていることを、その秘密の値を明らかにすることなく検証者に納得させるゼロ知識証明プロトコルの一種↓ eprint.iacr.org スキームの仕組みについて、SHA-256のプリイメージを知っていることを証明するユースケースで見ていく…
今回は、zk-SNARKs/STARKsなどゼロ知識証明系のプロトコルでよく登場するSumcheckプロトコルについて。 Sumcheckプロトコルは1992年に発表された多変数多項式を利用したプロトコル。多変数多項式は複数の変数で構成される多項式で、例えば2つの変数xとyで構…
先日Besuに存在していたBN254曲線上の点の検証ロジックのバグが開示された↓ blog.ethereum.org このバグの内容とは直接関係ないけど*1、解説の中に登場していた楕円曲線上の点が部分群に属しているかどうかのメンバーシップチェックの方法がいろいろあるよう…
少し前に発表された集約署名の新しいスキームDahLIAS↓ eprint.iacr.org 自分も異なる文脈で集約署名という言葉を使ってるので紛らわしいけど、↑の集約署名というのは、MuSigやFROSTのように複数の署名者（公開鍵）が同じメッセージに署名するマルチシグの集…
先日マージされたBIP-374↓は、楕円曲線のベースポイントGともう１つの点Bを基に、それぞれに同じスカラー値aを乗算した点A = aGと点C = aBが同じ、同じスカラー値（離散対数）aによって導出された点であることをaの値を明かすことなく証明する＝離散対数の等…
Great Script Restoration Great Script Restoration（GSR）は、2010年にBitcoinで無効化されたopcode群に対して、重みベースのバジェットを付与して再導入するRusty Russellの提案↓ https://github.com/rustyrussell/bips/blob/890656f624e03ebbd31560f6511…
2010年にOP_CATを含む複数のopcodeがBitcoinで無効になり、その後の研究でこの時無効になったopcodeがあれば、実はBitcoinでコベナンツを実現できることが判明するも、無効化された現状のBitcoinでコベナンツを実現する方法はこれまでなかった。ところが最近…
アダプター署名と言えば、HTLCに代わるPTLCや、スクリプトレスなAtomic Swapを行う際に利用される暗号プリミティブ。簡単にSchnorr署名の例で説明すると*1、 鍵ペアをP = xG（P：公開鍵、x：秘密鍵、G：ベースポイント）として、メッセージmに署名する場合、…
少し前に、Schnorrベースの閾値署名スキームFROST用にChillDKGという分散鍵生成スキームのBIPドラフトが発表された↓ https://github.com/BlockstreamResearch/bip-frost-dkg FROSTはShcnorrベースの閾値（t-of-n）のマルチシグに対応した署名スキームだけど…
ハードウェアウォレットからマスターシードを流出させるDark Skippyという新しい攻撃手法が最近公開された↓ https://darkskippy.com/ 悪意ある署名デバイスによる攻撃 Dark Skippyも、ハードウェアウォレットのような署名デバイスで悪意あるファームウェアが…
少し前に量子耐性のある署名アルゴリズムを用いたBitcoinのアドレスフォーマットを提案するBIPドラフトが提案された↓ https://github.com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki この中で量子耐性のある署名アルゴリズムとして紹介されていたSQIs…
先月Bitcoin-Devメーリングリストに投稿されたBitcoinにランポート署名を導入する提案↓ Signing a Bitcoin Transaction with Lamport Signatures (no changes needed) 以前、OP_CATを利用した提案はあったけど↓、↑はOP_CATを必要とせず現状のBitcoinで動作す…
最近、よく見かけるRistrettoについて調べてみた↓ https://ristretto.group/ Ristrettoが解決すること Ristrettoは、楕円曲線の内、曲線上の有効な点の総数（位数）が素数ではない楕円曲線から、位数が素数となる群を構築する抽象化レイヤーを提供するための…
FROSTはSchnorrベースの閾値署名方式で、プロトコルの内容については過去の記事↓やGBEC動画参照。 techmedia-think.hatenablog.com このFROSTを利用してBitcoinでマルチシグウォレットの開発を進めているFrostsnapというプロジェクト↓ https://frostsnap.com…
最近、Schnorrベースの閾値署名スキームFROSTをベースにして、暗号技術だけでt-of-nのマルチシグの設定を動的に調整可能にする提案が行われている。その中で、母数nの数を増やす際に利用されているのが、RTS（Repairable Threshold Scheme）。 RTSは、シャミ…
Inner Product Argument（IPA）は、内積の関係を証明するプリミティブで、いくつかの証明システムに組み込まれて使用されている。IPAの解説については、GBEC動画 or 過去記事参照↓ goblockchain.network techmedia-think.hatenablog.com IPAは、多項式コミッ…
BitVMやZeroSyncの開発者であるRobin Linusが先日公開したBitStreamのペーパー↓ https://robinlinus.com/bitstream.pdf 分散型のコンテンツホスティングネットワークに対して（最近ユーザーが増えてるNostrとか）、持続可能なインセンティブを持たせるため、…
GG18のプロトコルについて、ざっと確認したので↓ techmedia-think.hatenablog.com 秘密鍵を抽出できるという脆弱性CVE-2023-33241の内容について見ていく。ペーパーは↓ https://eprint.iacr.org/2023/1234.pdf 攻撃を成功するためには、攻撃者は署名プロセス…
GG18/GG20の脆弱性CVE-2023-33241が今年の夏くらいに公開されていた模様↓ www.fireblocks.com GG18/GG20は閾値ECDSA署名をサポートするMPCプロトコルで、ブロックチェーン界隈のMPC系のウォレット実装でよく利用されているらしい。CVE-2023-33241は、この2つ…
ペアリングに適した楕円曲線の1つであるBLS12-381の各曲線E, E'上の点のシリアライゼーションフォーマットについて（もともとZcashで定義された仕様）↓ https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-pairing-friendly-curves-11#appendix-C BLS12…
FROSTは、Schnorrベースの閾値署名方式↓ techmedia-think.hatenablog.com GBECの解説動画はこちら。 最近、Zcash Foundationから、FROSTの署名生成時のスカラー乗算処理を最適化した記事が公開されてたので見てみる↓ zfnd.org 最適化のポイント FROSTでは、…
多項式コミットメントの１つであるKZG commitmentについて↓ techmedia-think.hatenablog.com より詳しく理解するためにRubyで実装してみた↓ https://github.com/azuchi/kzg/ セットアップ KZG commitmentはまず最初に公開パラメーターを生成する。これは基本…
楕円曲線を使用したPedersen CommitmentやBLS署名など、誰もその離散対数を知らない点を利用する暗号プロトコルを最近よく見かける。ただ、プロトコルの説明では、そのような点の導出方法があまり詳しく書かれていなかったりすることもあり、アルゴリズムの…
Bitcoinの新しいトランザクションリレープロトコルの提案Erlay↓ techmedia-think.hatenablog.com のコアとなる実装の1つがMinisketch。 Minisketchは、2つの集合の対称差を求めるアルゴリズムPinsketchを実装したライブラリ。つまりAとBという2つの集合があ…
検証可能なwitness encryptionという新しい暗号プリミティブを利用してDLCを構成する新しい提案のペーパーが発表されてたので↓ https://eprint.iacr.org/2022/499.pdf 「II. TECHNICAL OVERVIEW」の内容を見てみた（まだ一部よく分かってない）。 BLS署名 ペ…
