リング署名

暗号学において、リング署名は、それぞれが鍵を持つユーザー セットの任意のメンバーによって実行できるデジタル署名の一種です。したがって、リング署名で署名されたメッセージは、特定のグループのメンバーによって承認されます。リング署名のセキュリティ特性の 1 つは、セットのメンバーのどの鍵が署名の作成に使用されたかを計算的に判断することが不可能であることです。リング署名はグループ署名に似ていますが、2 つの重要な点で異なります。1 つ目は、個々の署名の匿名性を失効させる方法がないことです。2 つ目は、追加の設定なしで任意のユーザー セットを署名セットとして使用できることです。

リング署名はロン・リベスト、アディ・シャミール、ヤエル・タウマン・カライによって発明され、2001年にASIACRYPTで発表されました。 ^{[ 1 ]}リング署名という 名前は、署名アルゴリズムのリングのような構造に由来しています。

意味

一組のエンティティがそれぞれ公開鍵と秘密鍵のペア ( P ₁ , S ₁ ), ( P ₂ , S ₂ ), ..., ( P _n , S _n ) を持っているとします。パーティi は、入力 ( m , Si _, P ₁ , ..., P _n ) に対して、メッセージmのリング署名 σ を計算できます。σ、 m、および関連する公開鍵P ₁ , ..., P _nが与えられれば、誰でもリング署名の有効性を確認できます。リング署名が適切に計算されていれば、チェックに合格するはずです。一方、ある集合のメッセージに対して、その集合の秘密鍵を知らずに有効なリング署名を作成することは困難であるはずです。^{[ 2 ]}

アプリケーションと変更

Rivest、Shamir、Taumanリング署名方式の挙動

原論文では、リベスト、シャミール、タウマンはリング署名を秘密漏洩の手段として説明しました。例えば、リング署名は「ホワイトハウスの高官」による匿名署名を提供し、どの高官がメッセージに署名したかを明らかにすることなく提供することができます。リング署名は匿名性を失効させることができず、また、リング署名のグループを即興で作成できるため、この用途に適しています。

原論文でも説明されているもう一つの応用は、否認可能署名です。この場合、メッセージの送信者と受信者がリング署名のグループを形成します。この場合、署名は受信者にとって有効ですが、それ以外の人にとっては、受信者と送信者のどちらが実際の署名者であるかは不明です。したがって、このような署名は説得力がありますが、意図した受信者以外には転送できません。

さまざまな前提に基づき、新しい機能を導入したさまざまな作品がありました。

閾値リング署名

^{[ 3 ]} nのうちt人が協力してメッセージに署名する標準的な「t-out-of-n」しきい値署名t人のユーザーがリング署名プロトコル。つまり、t人の当事者S₁, ...,S _t ∈ {P₁, ...,P _n }は、入力(m,S₁, ...,S _t ,P₁, ...,P _n )に基づいて、メッセージmt,n)-リング署名σを計算できる。

リンク可能なリング署名

^{[ 4 ]}リンク可能性により、任意の2つの署名が同じメンバー（同じ秘密鍵）によって作成されたかどうかを判断できます。署名者の身元は保持されます。考えられる応用例の一つとして、オフラインの電子キャッシュシステム。

追跡可能なリング署名

^{[ 5 ]}前述の方式に加えて、署名者の公開鍵が明らかになる（同じ秘密鍵で複数の署名を発行する場合）。電子投票システムを実装することができる。

効率

提案されているアルゴリズムのほとんどは、出力サイズが漸近的である。つまり、結果として得られる署名のサイズは、入力サイズ（公開鍵の数）に比例して増加する。つまり、このような方式は、入力サイズが十分に大きい実際のユースケース（例えば、数百万人の参加者がいる電子投票など）には実用的ではない。しかし、入力サイズの中央値が比較的小さいアプリケーションでは、このような推定値は許容できる可能性がある。CryptoNoteは、送信者の追跡不可能性を実現するために、藤崎と鈴木によるリング署名方式^{[ 5 ]}をP2P決済に 実装している。${\displaystyle O(n)}$ ${\displaystyle n}$ ${\displaystyle O(n)}$

最近、より効率的なアルゴリズムが登場しています。署名のサイズが線形以下である方式^{[ 6 ]}や、署名のサイズが一定である方式^{[ 7 ]があります。}

実装

オリジナルのスキーム

原論文では、 RSAベースのリング署名方式と、Rabinベースの方式について説明されています。これらの論文では、鍵、初期値、および任意の値のリストを受け取る鍵付き「結合関数」が定義されています。は と定義され、ここではトラップドア関数（つまり、RSAベースのリング署名の場合はRSA公開鍵）です。 ${\displaystyle C_{k,v}(y_{1},y_{2},\dots ,y_{n})}$ ${\displaystyle k}$ ${\displaystyle v}$ ${\displaystyle y_{1},\dots y_{n}}$ ${\displaystyle y_{i}}$ ${\displaystyle g_{i}(x_{i})}$ ${\displaystyle g_{i}}$

この関数は環方程式と呼ばれ、以下のように定義されます。この方程式は対称暗号化関数に基づいています。 ${\displaystyle C_{k,v}(y_{1},y_{2},\dots ,y_{n})}$ ${\displaystyle E_{k}}$

${\displaystyle C_{k,v}(y_{1},y_{2},\dots ,y_{n})=E_{k}(y_{n}\oplus E_{k}(y_{n-1}\oplus E_{k}(\dots \oplus E_{k}(y_{1}\oplus v)\dots )))}$

出力は単一の値で、この値は と等しくなるように強制されます。この方程式は、少なくとも1つの、そして拡張して を自由に選択できる 限り、解くことができます。RSAの仮定のもとでは、これはトラップドア関数の逆関数（つまり秘密鍵）の少なくとも1つを知っていることを意味します。なぜなら だからです。 ${\displaystyle z}$ ${\displaystyle v}$ ${\displaystyle v=C_{k,v}(y_{1},y_{2},\dots ,y_{n})}$ ${\displaystyle y_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle g_{i}^{-1}}$ ${\displaystyle g_{i}^{-1}(y_{i})=x_{i}}$

署名生成

リング署名の生成には6つのステップがあります。平文は、リングの公開鍵はで表されます。 ${\displaystyle m}$ ${\displaystyle P_{1},P_{2},\dots ,P_{n}}$

1. 暗号ハッシュ関数を用いて鍵 を計算します。このステップでは、が の鍵として使用されるので、のランダムオラクルを前提としています。${\displaystyle k={\mathcal {H}}(m)}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle k}$ ${\displaystyle E_{k}}$
2. ランダムな接着値を選択します。${\displaystyle v}$
3. 自分以外のリングメンバー全員についてランダムに選択し（署名者の秘密鍵を使用して計算されます）、対応する を計算します。${\displaystyle x_{i}}$ ${\displaystyle x_{s}}$ ${\displaystyle y_{i}=g_{i}(x_{i})}$
4. 環方程式を解く${\displaystyle y_{s}}$
5. 署名者の秘密鍵を使用して計算します。${\displaystyle x_{s}}$ ${\displaystyle x_{s}=g_{s}^{-1}(y_{s})}$
6. リング署名は -タプル${\displaystyle (2n+1)}$ ${\displaystyle (P_{1},P_{2},\dots ,P_{n};v;x_{1},x_{2},\dots ,x_{n})}$

署名検証

署名の検証には 3 つのステップがあります。

1. 公開鍵トラップドアをすべての に適用します: 。${\displaystyle x_{i}}$ ${\displaystyle y_{i}=g_{i}(x_{i})}$
2. 対称キーを計算します。${\displaystyle k={\mathcal {H}}(m)}$
3. 環方程式が成り立つことを確認します。${\displaystyle C_{k,v}(y_{1},y_{2},\dots ,y_{n})=v}$

Python実装

RSAを使用した元の論文のPython実装を以下に示します。サードパーティ製モジュール PyCryptodome が必要です。

osをインポート、 hashlibをインポート、 randomをインポート、 Crypto.PublicKey.RSAをインポートfunctoolsをインポートするクラスRing : """RSA 実装。"""def __init__ ( self , k , L : int = 1024 ) -> None : self . k = k self . l = L self . n = len ( k ) self . q = 1 << ( L - 1 )def sign_message ( self , m : str , z : int ): """メッセージに署名します。""" self . _permut ( m ) s = [ None ] * self . n u = random . randint ( 0 , self . q ) c = v = self . _E ( u )first_range = list ( range ( z + 1 , self.n ) ) second_range = list ( range ( z ) ) whole_range = first_range + second_rangei が全範囲にわたる場合: s [ i ] = random . randint ( 0 , self . q ) e = self . _g ( s [ i ] , self . k [ i ] . e , self . k [ i ] . n ) v = self . _E ( v ^ e ) if ( i + 1 ) % self . n == 0 : c = vs [ z ] = self . _g ( v ^ u , self . k [ z ] . d , self . k [ z ] . n )を返す[ c ] + sdef verify_message ( self , m : str , X ) -> bool : """メッセージを検証します。""" self . _permut ( m )def _f ( i ) : self._g ( X [ i + 1 ] , self.k [ i ] .e , self.k [ i ] .n )を返す​​​​​y = map ( _f , range ( len ( X ) - 1 )) y = list ( y )def _g ( x , i ): self . _E ( x ^ y [ i ] )を返しますr = functools.reduce ( _g , range ( self.n ) , X [ 0 ] )戻り値r == X [ 0 ]​def _permut ( self , m ): msg = m . encode ( "utf-8" ) self . p = int ( hashlib . sha1 ( msg ) . hexdigest (), 16 )def _E ( self , x ): msg = f " { x }{ self . p } " . encode ( "utf-8" ) return int ( hashlib . sha1 ( msg ) . hexdigest (), 16 )def _g ( self , x , e , n ): q , r = divmod ( x , n ) if (( q + 1 ) * n ) <= (( 1 << self . l ) - 1 ): result = q * n + pow ( r , e , n ) else : result = x return result

4 人のユーザーのリング内の 2 つのメッセージに署名して検証するには:

サイズ= 4 msg1 、msg2 = "hello" 、"world!"def _rn ( _ ) : Crypto.PublicKey.RSA.generate ( 1024 , os.urandom )を返す​​​​​​key = map ( _rn , range ( size )) key = list ( key )r =リング（キー）i がrange ( size )の場合: signature_1 = r . sign_message ( msg1 , i ) signature_2 = r . sign_message ( msg2 , i ) assert r . verify_message ( msg1 , signature_1 )かつr . verify_message ( msg2 , signature_2 )であり、 r . verify_message ( msg1 , signature_2 )ではない

暗号通貨

Monero ^{[ 8 ]}や他のいくつかの暗号通貨はこの技術を使用しています。

参照

• 証人が区別できない証拠
• ラウンドロビン（ドキュメント）

参考文献

 この記事には、CC BY-SA 4.0ライセンスに基づいて利用可能なテキストが組み込まれています。

1. Rivest, Ronald L. ; Shamir, Adi ; Tauman, Yael (2001). 「秘密を漏らす方法」 . Advances in Cryptology — ASIACRYPT 2001. Lecture Notes in Computer Science. Vol. 2248. pp.  552– 565. doi : 10.1007/3-540-45682-1_32 . ISBN 978-3-540-42987-6。
2. デブナス、アシュミタ;シンガラヴェル、プラディープクマール。ヴェルマ、シェカール（2012年12月19日）。「センサーネットワークのための効率的な空間プライバシー保護スキーム」。中央ヨーロッパ工学ジャーナル。3 (1): 1–10 .土井: 10.2478/s13531-012-0048-7。S2CID 137248994。 
3. E. ブレッソン、J. スターン、M. シド・ロ (2002). 「閾値リング署名とアドホックグループへの応用」(PDF) .暗号学の進歩 — CRYPTO 2002.コンピュータサイエンス講義ノート. 第2442巻. pp.  465– 480. doi : 10.1007/3-540-45708-9_30 . ISBN 978-3-540-44050-5。
4. Liu, Joseph K.; Wong, Duncan S. (2005). 「リンク可能なリング署名：セキュリティモデルと新しいスキーム」.計算科学とその応用 – ICCSA 2005.コンピュータサイエンス講義ノート. 第2巻. pp.  614– 623. doi : 10.1007/11424826_65 . ISBN 978-3-540-25861-2。{{cite book}}:|journal=無視されました (ヘルプ)
5. 藤崎英一郎、鈴木幸太郎 (2007). 「追跡可能なリング署名」.公開鍵暗号: 181–200 .
6. 藤崎英一郎 (2011). 「ランダムオラクルを用いないサブ線形サイズ追跡可能なリング署名」.電子情報通信学会論文誌. 95 (1): 393– 415. Bibcode : 2012IEITF..95..151F . doi : 10.1587/transfun.E95.A.151 .
7. Au, Man Ho; Liu, Joseph K.; Susilo, Willy; Yuen, Tsz Hon (2006). 「定数サイズのIDベースリンク可能かつ取り消し可能な-iff-リンクリング署名」. Progress in Cryptology - INDOCRYPT 2006 . コンピュータサイエンス講義ノート. 第4329巻. pp.  364– 378. doi : 10.1007/11941378_26 . ISBN 978-3-540-49767-7。
8. 「Bulletproof実装の評価」（PDF） . Quarkslab.