リング署名

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

リング署名はロナルド・リベスト、アディ・シャミア、ヤエル・タウマン・カライ（英語版）によって発明され、2001年のASIACRYPT（英語版）で発表された^[1]。リング署名という名前は、署名アルゴリズムのリング状の構造に由来する。

定義

公開鍵と秘密鍵のペア(P₁, S₁), (P₂, S₂), ..., (P_n, S_n)をそれぞれ持つエンティティの集合があると仮定する。参加者iは、入力(m, S_i, P₁, ..., P_n)に基づいて、メッセージmに対するリング署名σを計算できる。そして誰でもσ、m、および関連する公開鍵P₁, ..., P_nが与えられれば、リング署名の妥当性を確認できる。リング署名が正しく計算されていれば、チェックに合格するはずである。一方、どのようなメッセージに対しても、どのような署名者集合に関しても、その集合に含まれるいずれかの秘密鍵を知らない限り、有効なリング署名の作成は誰にとっても困難であるはずである^[2]。

応用と変種

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

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

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

閾値リング署名(英: Threshold ring signatures): ^[3] n人のユーザのうちのt人がメッセージに署名するために協力する必要がある標準的な"t-out-of-n"閾値暗号システム（英語版）とは異なり、このリング署名の変種では、リング署名プロトコル（英語版）の下にt人のユーザが協力する必要がある。つまり、tの関係者S₁, ..., S_t ∈ {P₁, ..., P_n}は、入力(m, S₁, ..., S_t, P₁, ..., P_n)に対して、メッセージmに対する(t, n)-リング署名σを計算できる。
リンク可能リング署名(英: Linkable ring signatures): ^[4] リンク可能性という特性を持つ場合、2つの署名が同じメンバーによって(同じ秘密鍵を使って)生成されたかどうかを判断できるようになる。それでも署名者の身元は保護される。考えられる用途の1つは、オフラインデジタル通貨システムである。
追跡可能リング署名(英: Traceable ring signature): ^[5] 前のスキームに加えて、署名者の公開鍵が明らかにされる(同じ秘密鍵で複数の署名を発行した場合)。電子投票システムがこのプロトコルを使用して実装できる。

効率

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

最近、より効率的なアルゴリズムが登場した。署名のサイズが線形未満の方式^[6]と、定数サイズの方式^[7]がある。

実装

オリジナルのスキーム

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

関数 $C_{k,v}(y_{1},y_{2},\dots ,y_{n})$ はリング方程式と呼ばれ、以下のように定義される。方程式は共通鍵暗号による暗号化関数 $E_{k}$ に基づいている。

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 )))

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

署名生成

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

暗号学的ハッシュ関数を使用して、鍵 $k={\mathcal {H}}(m)$ を計算する。このステップでは、 $k$ が $E_{k}$ の鍵として使用されるため、 ${\mathcal {H}}$ にランダムオラクルを想定している。
糊となる値としてランダムな $v$ を選択する。
自分以外のすべてのリングメンバーに対してランダムな $x_{i}$ を選び( $x_{s}$ は署名者の秘密鍵を使用して計算される)、対応する $y_{i}=g_{i}(x_{i})$ を計算する。
リング方程式を $y_{s}$ について解く。
署名者の秘密鍵を使用して $x_{s}$ を計算する: $x_{s}=g_{s}^{-1}(y_{s})$
リング署名は $(2n+1)$ -タプル $(P_{1},P_{2},\dots ,P_{n};v;x_{1},x_{2},\dots ,x_{n})$ となる。

署名検証

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

すべての $x_{i}$ に公開鍵トラップドアを適用する: $y_{i}=g_{i}(x_{i})$ 。
共通鍵 $k={\mathcal {H}}(m)$ を計算する。
リング方程式 $C_{k,v}(y_{1},y_{2},\dots ,y_{n})=v$ が成り立つかどうかを確認する。

Python実装

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

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

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

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)

暗号通貨

Moneroおよび他のいくつかの暗号通貨はこの技術を利用している^[要出典]。

参考文献

This article incorporates text available under the CC BY-SA 4.0 license.

^ Rivest, Ronald L.; Shamir, Adi; Tauman, Yael (2001). “How to Leak a Secret”. Advances in Cryptology — ASIACRYPT 2001. Lecture Notes in Computer Science. 2248. pp. 552–565. doi:10.1007/3-540-45682-1_32. ISBN 978-3-540-42987-6
^ Debnath, Ashmita; Singaravelu, Pradheepkumar; Verma, Shekhar (19 December 2012). “Efficient spatial privacy preserving scheme for sensor network”. Central European Journal of Engineering 3 (1): 1–10. doi:10.2478/s13531-012-0048-7.
^ E. Bresson; J. Stern; M. Szyd lo (2002). “Threshold Ring Signatures and Applications to Ad-hoc Groups”. Advances in Cryptology — CRYPTO 2002. Lecture Notes in Computer Science. 2442. pp. 465–480. doi:10.1007/3-540-45708-9_30. ISBN 978-3-540-44050-5
^ Liu, Joseph K.; Wong, Duncan S. (2005). “Linkable Ring Signatures: Security Models and New Schemes”. Computational Science and Its Applications – ICCSA 2005. Lecture Notes in Computer Science. 2. 614–623. doi:10.1007/11424826_65. ISBN 978-3-540-25861-2
^ ^a ^b Fujisaki, Eiichiro; Suzuki, Koutarou (2007). “Traceable Ring Signature”. Public Key Cryptography: 181–200.
^ Fujisaki, Eiichiro (2011). “Sub-linear size traceable ring signatures without random oracles”. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 95 (1): 393–415. Bibcode: 2012IEITF..95..151F. doi:10.1587/transfun.E95.A.151.
^ Au, Man Ho; Liu, Joseph K.; Susilo, Willy; Yuen, Tsz Hon (2006). “Constant-Size ID-Based Linkable and Revocable-iff-Linked Ring Signature”. Progress in Cryptology - INDOCRYPT 2006. Lecture Notes in Computer Science. 4329. pp. 364–378. doi:10.1007/11941378_26. ISBN 978-3-540-49767-7

[1] Rivest, Ronald L.; Shamir, Adi; Tauman, Yael (2001). “How to Leak a Secret”. Advances in Cryptology — ASIACRYPT 2001. Lecture Notes in Computer Science. 2248. pp. 552–565. doi:10.1007/3-540-45682-1_32. ISBN 978-3-540-42987-6

[2] Debnath, Ashmita; Singaravelu, Pradheepkumar; Verma, Shekhar (19 December 2012). “Efficient spatial privacy preserving scheme for sensor network”. Central European Journal of Engineering 3 (1): 1–10. doi:10.2478/s13531-012-0048-7.

[3] E. Bresson; J. Stern; M. Szyd lo (2002). “Threshold Ring Signatures and Applications to Ad-hoc Groups”. Advances in Cryptology — CRYPTO 2002. Lecture Notes in Computer Science. 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). “Linkable Ring Signatures: Security Models and New Schemes”. Computational Science and Its Applications – ICCSA 2005. Lecture Notes in Computer Science. 2. 614–623. doi:10.1007/11424826_65. ISBN 978-3-540-25861-2

[FS07-5] Fujisaki, Eiichiro; Suzuki, Koutarou (2007). “Traceable Ring Signature”. Public Key Cryptography: 181–200.

[6] Fujisaki, Eiichiro (2011). “Sub-linear size traceable ring signatures without random oracles”. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 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). “Constant-Size ID-Based Linkable and Revocable-iff-Linked Ring Signature”. Progress in Cryptology - INDOCRYPT 2006. Lecture Notes in Computer Science. 4329. pp. 364–378. doi:10.1007/11941378_26. ISBN 978-3-540-49767-7

[1]

[2]

[3]

[4]

[5]

[6]

[7]

定義