Develop with pleasure!

福岡でCloudとかBlockchainとか。

量子耐性のある署名アルゴリズムSQIsign

Cryptography PQC

少し前に量子耐性のある署名アルゴリズムを用いたBitcoinのアドレスフォーマットを提案するBIPドラフトが提案された↓

https://github.com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki

この中で量子耐性のある署名アルゴリズムとして紹介されていたSQIsignについて調べてみた。

SQIsign

SQISignは、楕円曲線上の同種写像の数学的性質を利用した同種写像暗号を利用した署名スキーム。

現在NISTで標準化が進められているポスト量子暗号の署名スキームは、既存の署名アルゴリズムと比較すると、いずれも鍵長/署名サイズが結構大きい↓

アルゴリズム セキュリティレベル 公開鍵サイズ 署名サイズ
FALCON NIST-I 897 byte 666 byte
FALCON NIST-V 1793 byte 1280 byte
SPHINCS+ NIST-I 32 byte 7856 byte
SPHINCS+ NIST-III 48 byte 16224 byte
SPHINCS+ NIST-V 64 byte 29792 byte
CRYSTALS-Dilithium NIST-II 1312 byte 2420 byte
CRYSTALS-Dilithium NIST-III 1952 byte 3293 byte
CRYSTALS-Dilithium NIST-V 2592 byte 4595 byte

FALCONおよびCRYSTALS-Dilithiumは格子暗号ベースで、SPHINCS+はハッシュベースの署名スキーム。

一方、NISTのポス量子暗号の最終候補には含まれていないものの、同種写像暗号ベースのSQIsignは、これらに比べて鍵/署名サイズが小さい↓

セキュリティレベル 公開鍵サイズ 署名サイズ
NIST-I 64 byte 177 byte
NIST-III 96 byte 263 byte
NIST-V 128 byte 335 byte

ブロックチェーンで主流なECDSAだと、公開鍵＝33 byte、署名サイズ70 byte未満というサイズ感なので、量子耐性のある署名アルゴリズムへの移行においては、これらのサイズ増加に伴うスケーラビリティの課題が懸念される。

※ サイズが小さい方が望ましいものの、現状SQIsignその安全性の評価について様々な研究がされている段階で、実際にどんな署名アルゴリズムが採用されるかは未定

同種写像問題

SQIsignは、超特異楕円曲線間で同種写像を見つけることが困難であることが安全性の仮定となっている。

楕円曲線上の同種写像（Isogeny）は、ある楕円曲線E1から別の楕円曲線E2への写像で、 {\phi:E1 \rightarrow E2}と表記される。

E1上の点をP＝（x, y）とした場合、Φ(P)は、2つの有理関数 {\phi_1, \phi_2}を使って {\phi(P) = (\phi_1(x, y), \phi_2(x, y))}を計算することで、導出される。また、この関数は加法群の構造を持っていて、任意のE1上の点P、Qに対して、 {\phi(P + Q) = \phi(P) + \phi(Q)}という準同型性が成立する。

同種写像問題というのは、2つの楕円曲線

  • E1： {y^{2} = x^{3} + ax + b}
  • E2： {y^{2} = x^{3} + a'x + b'}

が与えられた際に、この2つの曲線間の同種写像Φを見つける問題。E1とΦからE2を導出するのは簡単だが、E1とE2上からΦを見つけるのは困難であるという一方向性を持つ。この問題を解くためには膨大な数の写像を探索する必要があり、量子コンピューターでも多項式時間で解くことができないとされている。

SQISignプロトコル

SQISignはΣプロトコルとして設計されており、これをFiat-Shamir変換によって署名プロトコルとして動作するようにしている。まずは、基本となってるΣプロトコルの内容について。

超特異楕円曲線 {E_0}を公開パラメーターとした場合、証明者は、秘密の同種写像 {\tau}を計算し、 {\tau : E_0 \rightarrow E_A}を導出し、 {E_A}を公開鍵とし、 {\tau}の知識を証明する。

最初に、この証明で登場する表記について

  • 同種写像 {\phi:E_1 \rightarrow E_2}に対して、その逆方向の同種写像 {\hat{\phi}: E_2 \rightarrow E_1}が存在し、これを双対同種写像と呼ぶ。
  • 元の同種写像と双対同種写像を合成する（ {\phi \circ \hat{\phi}}）と、元の楕円曲線に対するスカラー倍写像になる。合成というのは、2つの同種写像を順に適用することを意味し、 {E_1}上の点Pに対して写像Φを適用すると {E_2}上の点Φ(P)が得られる。さらにこの点に対して {\hat{\phi}}を適用すると、 {E_1}上の点 {\hat{\phi}(\phi(P))}が得られる。この点は元の点PをN倍した点になる（Nは同種写像の次数）。

証明の手順は↓

  1. コミットメントフェーズ：
    証明者は、別のランダムな同種写像 {\psi : E_0 \rightarrow E_1}を計算し、コミットメントとして {E_1}のみを検証者に送る。
  2. チャレンジフェーズ：
    検証者は、ランダムな同種写像 {\phi : E_1 \rightarrow E_2}を計算し、チャレンジとして {\phi, E_2}を証明者に送る。
  3. レスポンスフェーズ：
    証明者は、 {\sigma = \phi \circ \psi \circ \hat{\tau}: E_A \rightarrow E_2} *1 を計算し、σを検証者に送信する。
  4. 検証：
    最後に検証者は、レスポンスの同種写像 {\sigma}が公開鍵 {E_A}から {E_2}への同種写像であることを検証する。

署名スキーム

SQISignの署名アルゴリズムは、上記のΣプロトコルのチャレンジの生成部分を署名対象のメッセージを使用したFiat-Shamir変換に置き換える。つまり、コミットメント {E_1}とメッセージをハッシュしてチャレンジ同種写像 {\phi : E_1 \rightarrow E_2}を導出する。

署名の検証は、メッセージと署名値σおよび公開鍵 {E_A}を入力として受取、署名が有効かどうかを検証する。具体的には、

  • 署名と公開鍵から {E_2}を計算し、
  • メッセージのハッシュからチャレンジの双対同種写像 {\hat{\phi}}を計算し、
  • {E_1}とメッセージが実際にチャレンジ同種写像を生成するか検証する

というのがSQIsignの署名スキームらしい。概要はふんわりと分かったけど、同種写像の生成（ランダムなイデアルのサンプリングや、KLPTとかIdealToIsogenyEichlerとか）や双対同種写像の計算とか実際にどういうアルゴリズムで計算できるのかはまだよく分かってない。

*1: \hat{\tau}は {\tau}の双対同種写像