リング署名

暗号化において、リング署名は、それぞれが鍵を持つユーザー セットの任意のメンバーによって実行できるデジタル署名の一種です。したがって、リング署名で署名されたメッセージは、特定のグループのメンバーによって承認されます。リング署名のセキュリティ特性の 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]

元の論文では、リベスト、シャミール、タウマンは、リング署名を秘密を漏らす方法として説明しました。たとえば、リング署名を使用すると、「ホワイトハウスの高官」からの匿名署名を提供できますが、どの高官がメッセージに署名したかは明らかにされません。リング署名の匿名性は取り消すことができず、リング署名のグループは即興で作成できるため、リング署名はこの用途に適しています。

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

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

閾値リング署名

^[3]標準的な「t -out-of -n」しきい値署名とは異なり、n人のうちt人がメッセージに署名するために協力する必要がありますが、このリング署名の変種では、t人のユーザーがリング署名プロトコルで協力する必要があります_{。つまり、} t人の当事者S1、...、St∈ { P1、...、Pn _}は、入力( m、S1、...、St、_P1、...、Pn ₎に基づいて、メッセージmの( t、n )リング_署名σを計算できます。

リンク可能なリング署名

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

追跡可能なリング署名

^[5]前述の方式に加えて、署名者の公開鍵が公開されます（同じ秘密鍵で複数の署名を発行する場合）。このプロトコルを使用して電子投票システムを実装できます。

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

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

 os
をインポート hashlibを
インポート random を
インポート Crypto.PublicKey.RSA をインポート

 関数ツールをインポートする

クラス 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_range
          
            

         i が 全範囲にある 場合: 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 = v
               
                
                
                   
                  

        s [ z ]  =  self . _g ( v  ^  u ,  self . k [ z ] . d ,  self . k [ z ] . n )
        戻り 値 [ c ]  +  s

    def  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 )を返し ます。​​​​ 

キー =  map ( _rn ,  range (サイズ))
キー =  list (キー)

r  = リング（キー）

 iが range ( size )の 場合: signature_1 = r . sign_message ( msg1 , i ) signature_2 = r . sign_message ( msg2 , i ) r . verify_message ( msg1 , signature_1 )かつr . verify_message ( msg2 , signature_2 )であり、 r . verify_message ( msg1 , signature_2 )ではない
       
       
             

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

• 証人が区別できない証拠

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