リング署名のソースを表示

[[暗号理論]]において'''リング署名'''({{lang-en-short|ring signature}})とは、[[デジタル署名]]の一種であって、複数の[[鍵 (暗号)|鍵]]のうちいずれかで署名されたことは検証できるが、どの鍵を使って署名されたのか知るのが困難であるような署名方法である。リング署名は{{仮リンク|グループ署名|en|group signature}}に似ているが、2つの重要な点で異なる。1つ目は、個々の署名の匿名性を取り消す方法がない点である。2つ目は、複数人で協力する必要がなく、1つの鍵ペアと任意の公開鍵(他人が公開しているものでよい)をいくつか準備すれば署名が作れる点である。

リング署名は[[ロナルド・リベスト]]、[[アディ・シャミア]]、{{仮リンク|ヤエル・タウマン・カライ|en|Yael Tauman Kalai}}によって発明され、2001年の{{仮リンク|ASIACRYPT|en|ASIACRYPT}}で発表された<ref>{{Cite book |last1=Rivest |first1=Ronald L. |title=Advances in Cryptology — ASIACRYPT 2001 |last2=Shamir |first2=Adi |last3=Tauman |first3=Yael |year=2001 |isbn=978-3-540-42987-6 |series=Lecture Notes in Computer Science |volume=2248 |pages=552–565 |chapter=How to Leak a Secret |doi=10.1007/3-540-45682-1_32 |author-link=ロナルド・リベスト |author-link2=アディ・シャミア |author-link3=ヤエル・タウマン・カライ |chapter-url=https://doi.org/10.1007%2F3-540-45682-1_32}}</ref>。''リング署名''という名前は、署名[[アルゴリズム]]のリング状の構造に由来する。

==定義==
<!-- 訳注: 原文ではMissing informationテンプレートであるが日本語版にはないため節スタブで代用する。 -->
{{節スタブ|1=定義。このセクションは現在、リング署名の一部の有用な特性を記述しているが、数学的な定義は記述していない|date=2022年4月}}
公開鍵と秘密鍵のペア(''P''<sub>1</sub>, ''S''<sub>1</sub>), (''P''<sub>2</sub>, ''S''<sub>2</sub>), ..., (''P''<sub>''n''</sub>, ''S''<sub>''n''</sub>)をそれぞれ持つエンティティの集合があると仮定する。参加者''i''は、入力(''m'', ''S''<sub>''i''</sub>, ''P''<sub>1</sub>, ..., ''P''<sub>''n''</sub>)に基づいて、メッセージ''m''に対するリング署名σを計算できる。そして誰でもσ、''m''、および関連する公開鍵''P''<sub>1</sub>, ..., ''P''<sub>''n''</sub>が与えられれば、リング署名の妥当性を確認できる。リング署名が正しく計算されていれば、チェックに合格するはずである。一方、どのようなメッセージに対しても、どのような署名者集合に関しても、その集合に含まれるいずれかの秘密鍵を知らない限り、有効なリング署名の作成は誰にとっても困難であるはずである<ref>{{cite journal| last=Debnath| first=Ashmita| author2=Singaravelu, Pradheepkumar |author3=Verma, Shekhar |title=Efficient spatial privacy preserving scheme for sensor network|journal=Central European Journal of Engineering|date=19 December 2012| volume=3|issue=1|pages=1–10|doi=10.2478/s13531-012-0048-7|s2cid=137248994|doi-access=free}}</ref>。

==応用と変種==
[[File:Ring-signature.svg|thumb|upright=1.5|リベスト・シャミア・タウマン リング署名スキームの動作]]

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

元の論文で説明されているもう1つの用途は[[否認可能署名]]({{lang-en-short|deniable signature}})である。その際、メッセージの送信者と受信者はリング署名のグループを形成する。すると署名は受信者に対しては有効であるが、他の誰かにとっては受信者と送信者のどちらが実際の署名者であるか確信が持てない。したがって、このような署名は受信者を納得させられるが、意図した受信者以外に転送できない。

リング署名に対して新しい機能を追加する研究や異なる仮定に基づく研究が存在する:

;閾値リング署名({{lang-en-short|Threshold ring signatures}}):<ref>{{cite book|last1=E. Bresson|last2=J. Stern|last3=M. Szyd lo|title=Advances in Cryptology — CRYPTO 2002 |chapter=Threshold Ring Signatures and Applications to Ad-hoc Groups |series=Lecture Notes in Computer Science|date=2002|volume=2442|pages=465–480| doi=10.1007/3-540-45708-9_30| isbn=978-3-540-44050-5| chapter-url=https://www.di.ens.fr/~bresson/papers/BreSteSzy02.pdf|doi-access=free}}</ref> ''n''人のユーザのうちの''t''人がメッセージに署名するために協力する必要がある標準的な"''t''-out-of-''n''"{{仮リンク|閾値暗号システム|en|Threshold cryptosystem}}とは異なり、このリング署名の変種では、リング署名{{仮リンク|暗号プロトコル|en|Cryptographic protocol|label=プロトコル}}の下に''t''人のユーザが協力する必要がある。つまり、''t''の関係者''S''<sub>1</sub>, ..., ''S''<sub>''t''</sub> ∈ {''P''<sub>1</sub>, ..., ''P''<sub>''n''</sub>}は、入力(''m'', ''S''<sub>1</sub>, ..., ''S''<sub>''t''</sub>, ''P''<sub>1</sub>, ..., ''P''<sub>''n''</sub>)に対して、メッセージ''m''に対する(''t'', ''n'')-リング署名σを計算できる。
;リンク可能リング署名({{lang-en-short|Linkable ring signatures}}):<ref>{{cite book|last1=Liu|first1=Joseph K.|last2=Wong|first2=Duncan S.|title=Computational Science and Its Applications – ICCSA 2005 |chapter=Linkable Ring Signatures: Security Models and New Schemes | journal=ICCSA| date=2005 |volume=2| pages=614–623|doi=10.1007/11424826_65|series=Lecture Notes in Computer Science|isbn=978-3-540-25861-2}}</ref> リンク可能性という特性を持つ場合、2つの署名が同じメンバーによって(同じ秘密鍵を使って)生成されたかどうかを判断できるようになる。それでも署名者の身元は保護される。考えられる用途の1つは、オフライン[[デジタル通貨]]システムである。
;追跡可能リング署名({{lang-en-short|Traceable ring signature}}):<ref name="FS07">{{cite journal| last1=Fujisaki|first1=Eiichiro| last2=Suzuki| first2=Koutarou|title=Traceable Ring Signature|journal=Public Key Cryptography| date=2007| pages=181–200}}</ref> 前のスキームに加えて、署名者の公開鍵が明らかにされる(同じ秘密鍵で複数の署名を発行した場合)。[[電子投票]]システムがこのプロトコルを使用して実装できる。

==効率==

提案されているアルゴリズムのほとんどは、[[ランダウの記号|漸近的な]]出力サイズが<math>O(n)</math>である。つまり、結果の署名のサイズは入力のサイズ(公開鍵の数)に比例して増加する。これは、十分に大きい<math>n</math>(たとえば、数百万人の参加者による電子投票)では、このようなスキームは実用できないことを意味する。しかし、[[中央値]]が比較的小さな入力サイズを持つ一部の用途では、このような計算量の見積りは許容できる場合がある。{{仮リンク|CryptoNote|en|CryptoNote}}は、P2P決済において送信者の追跡不能性を実現するために、藤崎と鈴木による<math>O(n)</math>リング署名スキームを実装している<ref name="FS07" />。

最近、より効率的なアルゴリズムが登場した。署名のサイズが線形未満の方式<ref>{{cite journal|last1=Fujisaki|first1=Eiichiro|title=Sub-linear size traceable ring signatures without random oracles|journal= IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences|date=2011|volume=95|issue=1|pages=393–415| doi=10.1587/transfun.E95.A.151|bibcode=2012IEITF..95..151F}}</ref>と、定数サイズの方式<ref>{{cite book|last1=Au|first1=Man Ho|last2=Liu|first2=Joseph K. |last3=Susilo| first3=Willy| last4=Yuen|first4=Tsz Hon|title=Progress in Cryptology - INDOCRYPT 2006 |chapter=Constant-Size ID-Based Linkable and Revocable-iff-Linked Ring Signature |series=Lecture Notes in Computer Science | date=2006|volume=4329|pages=364–378| doi=10.1007/11941378_26|isbn=978-3-540-49767-7| url=https://ro.uow.edu.au/cgi/viewcontent.cgi?article=10250&context=infopapers}}</ref>がある。

==実装==

===オリジナルのスキーム===

元の論文は、[[RSA暗号]]に基づくものと、[[Rabin暗号]]に基づくリング署名スキームを説明している。彼らは、鍵<math>k</math>、初期値<math>v</math>、および任意の値<math>y_1, \dots, y_n</math>のリストを受け取る[[鍵 (暗号)|鍵付き]]「結合関数」<math>C_{k,v}(y_1, y_2, \dots, y_n)</math> を定義している。<math>y_i</math>は<math>g_i(x_i)</math>として定義され、ここで<math>g_i</math>はトラップドア関数である(例えばRSAベースのリング署名の場合は公開鍵による暗号化関数である)。

関数<math>C_{k,v}(y_1, y_2, \dots, y_n)</math>はリング方程式と呼ばれ、以下のように定義される。方程式は[[共通鍵暗号]]による暗号化関数<math>E_k</math>に基づいている。

: <math>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)))</math>

これは単一の値<math>z</math>を出力し、これが<math>v</math>と等しくなるように制約を付ける。方程式<math>v = C_{k,v}(y_1, y_2, \dots, y_n)</math>は、少なくとも1つの<math>y_i</math>(およびそこから導出される<math>x_i</math>)を自由に選択できる限り解ける。RSAの仮定の下では、これはトラップドア関数の逆関数<math>g^{-1}_i</math>(つまり秘密鍵による復号関数)の少なくとも1つを知っていることを意味する。なぜなら<math>g^{-1}_i(y_i) = x_i</math>であるからである。

====署名生成====

リング署名の生成には6つのステップが含まれる。平文は<math>m</math>で表され、リングの公開鍵は<math>P_1, P_2, \dots, P_n</math>で表される。

# [[暗号学的ハッシュ関数]]を使用して、鍵<math>k = \mathcal{H}(m)</math>を計算する。このステップでは、<math>k</math>が<math>E_k</math>の鍵として使用されるため、<math>\mathcal{H}</math>に[[ランダムオラクル]]を想定している。
# 糊となる値としてランダムな<math>v</math>を選択する。<!-- 訳注: おそらイメージとしては管の両端を接着してリングにするための糊のような値という意味。 -->
# 自分以外のすべてのリングメンバーに対してランダムな<math>x_i</math>を選び(<math>x_s</math>は署名者の秘密鍵を使用して計算される)、対応する<math>y_i = g_i(x_i)</math>を計算する。
# リング方程式を<math>y_s</math>について解く。
# 署名者の秘密鍵を使用して<math>x_s</math>を計算する: <math>x_s = g_s^{-1}(y_s)</math>
# リング署名は <math>(2n+1)</math>-タプル<math>(P_1, P_2, \dots, P_n; v; x_1, x_2, \dots, x_n)</math> となる。

====署名検証====

署名検証には3つのステップが含まれる。

# すべての<math>x_i</math>に公開鍵トラップドアを適用する: <math>y_i = g_i(x_i)</math>。
# 共通鍵<math>k=\mathcal{H}(m)</math>を計算する。
# リング方程式<math>C_{k,v}(y_1, y_2, \dots, y_n) = v</math>が成り立つかどうかを確認する。

==== Python実装 ====

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

<syntaxhighlight lang="python">
import os
import hashlib
import random
import Crypto.PublicKey.RSA

import functools

class Ring:
    """RSA implementation."""

    def __init__(self, k, L: int = 1024) -> None:
        """初期化する。

        Args:
            k: 鍵のリスト。署名者の分に関しては公開鍵と秘密鍵のペア
            L: 鍵の長さ
        """
        self.k = k
        self.l = L
        self.n = len(k)
        self.q = 1 << (L - 1)

    def sign_message(self, m: str, z: int):
        """メッセージに対する署名を返す。

        Args:
            m: 署名対象のメッセージ
            z: リストkの中で署名者の位置

        Returns:
          整数のリスト。最初の値は糊値であり、残りはトラップドア関数への
          引数x_iである。
        """

        # 方針:
        # リングは輪になっているので、どこから計算を始めても1周すると元の値に
        # 戻る。
        # そこで、zの位置から計算を始めて、戻ってきた値が繋がるように
        # y_zおよびx_zを決める。

        # self.pにmのハッシュ値を入れる。
        self._permut(m)
        # x_iのリスト。
        s = [None] * self.n
        # y_z ⊕ E_k(y_{z-1} ⊕ E_k(... ⊕ E_k(y_1 ⊕ c)))
        # ただしcはC_{k,v}(y_1, y_2, ..., y_n)。
        u = random.randint(0, self.q)
        # cは最終的にC_{k,v}(y_1, y_2, ..., y_n)となる値。
        # vは最終的にE_k(y_{z-1} ⊕ E_k(... ⊕ E_k(y_1 ⊕ c)))となる値。
        c = v = self._E(u)

        # 範囲 [z + 1, n)
        first_range = list(range(z + 1, self.n))
        # 範囲 [0, z)
        second_range = list(range(z))
        # [z + 1, z + 2, ..., n, 0, 1, ..., z - 1] (zは含まない)
        whole_range = first_range + second_range

        for i in whole_range:
            # x_iをランダムに決める。
            s[i] = random.randint(0, self.q)
            # y_iに相当する値。x_iを鍵k_iで暗号化した値。
            e = self._g(s[i], self.k[i].e, self.k[i].n)
            # E_k(y_i ⊕ E_k(y_{i-1} ⊕ E_k(... ⊕ E_k(y_1 ⊕ c))))
            v = self._E(v ^ e)
            if (i + 1) % self.n == 0:
                c = v

        # この時点において、
        # v = E_k(y_{z-1} ⊕ E_k(... ⊕ E_k(y_1 ⊕ c)))となっている。
        # 一方、リングが繋がるためには
        # u = y_z ⊕ v
        # である必要がある。
        # よって
        # y_z = v ⊕ u
        # これをzの秘密鍵で復号してx_zを得る。
        s[z] = self._g(v ^ u, self.k[z].d, self.k[z].n)
        return [c] + s

    def verify_message(self, m: str, X) -> bool:
        """メッセージmと署名Xを検証する。"""

        # リングを先頭から計算していき、最初の値に戻ればOKとする。

        self._permut(m)

        def _f(i):
            return 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):
            return self._E(x ^ y[i])

        r = functools.reduce(_g, range(self.n), X[0])
        return r == X[0]

    def _permut(self, m):
        """self.pにmのハッシュ値を入れる。"""
        msg = m.encode("utf-8")
        self.p = int(hashlib.sha1(msg).hexdigest(), 16)

    def _E(self, x):
        """xとmのハッシュ値を連結したもののハッシュ値を返す。"""
        msg = f"{x}{self.p}".encode("utf-8")
        return int(hashlib.sha1(msg).hexdigest(), 16)

    def _g(self, x, e, n):
        """xを鍵(e, n)を使ってRSAによる暗号化(あるいは復号)をして返す。"""
        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
</syntaxhighlight>

4人のユーザからなるリングにおいて、2つのメッセージの署名と検証をする場合:

<syntaxhighlight lang="python">
size = 4
msg1, msg2 = "hello", "world!"

def _rn(_):
    return Crypto.PublicKey.RSA.generate(1024, os.urandom)

key = map(_rn, range(size))
key = list(key)

r = Ring(key)

for i in range(size):
    signature_1 = r.sign_message(msg1, i)
    signature_2 = r.sign_message(msg2, i)
    assert r.verify_message(msg1, signature_1) and r.verify_message(msg2, signature_2) and not r.verify_message(msg1, signature_2)
</syntaxhighlight>

== 暗号通貨  ==
[[Monero]]および他のいくつかの[[暗号通貨]]はこの技術を利用している{{要出典|date=2024年2月}}。

== 関連項目 ==

* {{仮リンク|証拠識別不能証明|en|Witness-indistinguishable proof}}

==参考文献==
{{Creative Commons text attribution notice|url=https://www.getmonero.org/resources/moneropedia/ringsignatures.html|cc=bysa4}}
<references />

[[Category:公開鍵暗号]]