暗号理論においてリング署名()とは、デジタル署名の一種であって、複数の鍵のうちいずれかで署名されたことは検証できるが、どの鍵を使って署名されたのか知るのが困難であるような署名方法である。リング署名はに似ているが、2つの重要な点で異なる。1つ目は、個々の署名の匿名性を取り消す方法がない点である。2つ目は、複数人で協力する必要がなく、1つの鍵ペアと任意の公開鍵(他人が公開しているものでよい)をいくつか準備すれば署名が作れる点である。
リング署名はロナルド・リベスト、アディ・シャミア、によって発明され、2001年ので発表された。リング署名という名前は、署名アルゴリズムのリング状の構造に由来する。
定義
公開鍵と秘密鍵のペア(P1, S1), (P2, S2), ..., (Pn, Sn)をそれぞれ持つエンティティの集合があると仮定する。参加者iは、入力(m, Si, P1, ..., Pn)に基づいて、メッセージmに対するリング署名σを計算できる。そして誰でもσ、m、および関連する公開鍵P1, ..., Pnが与えられれば、リング署名の妥当性を確認できる。リング署名が正しく計算されていれば、チェックに合格するはずである。一方、どのようなメッセージに対しても、どのような署名者集合に関しても、その集合に含まれるいずれかの秘密鍵を知らない限り、有効なリング署名の作成は誰にとっても困難であるはずである。
応用と変種
最初の論文で、リベスト、シャミア、タウマンは、リング署名を秘密情報を流出させる方法として説明した。たとえば、リング署名を使用して、「ホワイトハウス高官」からの匿名署名を、どの高官がメッセージに署名したのか明らかにすることなく、提供できる。リング署名は匿名性を取り消せず、また、リング署名のグループを即興で作成できるため、このような用途に適している。
元の論文で説明されているもう1つの用途は否認可能署名()である。その際、メッセージの送信者と受信者はリング署名のグループを形成する。すると署名は受信者に対しては有効であるが、他の誰かにとっては受信者と送信者のどちらが実際の署名者であるか確信が持てない。したがって、このような署名は受信者を納得させられるが、意図した受信者以外に転送できない。
リング署名に対して新しい機能を追加する研究や異なる仮定に基づく研究が存在する:
閾値リング署名() n人のユーザのうちのt人がメッセージに署名するために協力する必要がある標準的な"t-out-of-n"とは異なり、このリング署名の変種では、リング署名の下にt人のユーザが協力する必要がある。つまり、tの関係者S1, ..., St ∈ {P1, ..., Pn}は、入力(m, S1, ..., St, P1, ..., Pn)に対して、メッセージmに対する(t, n)-リング署名σを計算できる。 リンク可能リング署名() リンク可能性という特性を持つ場合、2つの署名が同じメンバーによって(同じ秘密鍵を使って)生成されたかどうかを判断できるようになる。それでも署名者の身元は保護される。考えられる用途の1つは、オフラインデジタル通貨システムである。 追跡可能リング署名() 前のスキームに加えて、署名者の公開鍵が明らかにされる(同じ秘密鍵で複数の署名を発行した場合)。電子投票システムがこのプロトコルを使用して実装できる。
効率
提案されているアルゴリズムのほとんどは、漸近的な出力サイズがである。つまり、結果の署名のサイズは入力のサイズ(公開鍵の数)に比例して増加する。これは、十分に大きい(たとえば、数百万人の参加者による電子投票)では、このようなスキームは実用できないことを意味する。しかし、中央値が比較的小さな入力サイズを持つ一部の用途では、このような計算量の見積りは許容できる場合がある。は、P2P決済において送信者の追跡不能性を実現するために、藤崎と鈴木によるリング署名スキームを実装している。
最近、より効率的なアルゴリズムが登場した。署名のサイズが線形未満の方式と、定数サイズの方式がある。
実装
オリジナルのスキーム
元の論文は、RSA暗号に基づくものと、Rabin暗号に基づくリング署名スキームを説明している。彼らは、鍵、初期値、および任意の値のリストを受け取る鍵付き「結合関数」 を定義している。はとして定義され、ここではトラップドア関数である(例えばRSAベースのリング署名の場合は公開鍵による暗号化関数である)。
関数はリング方程式と呼ばれ、以下のように定義される。方程式は共通鍵暗号による暗号化関数に基づいている。
これは単一の値を出力し、これがと等しくなるように制約を付ける。方程式は、少なくとも1つの(およびそこから導出される)を自由に選択できる限り解ける。RSAの仮定の下では、これはトラップドア関数の逆関数(つまり秘密鍵による復号関数)の少なくとも1つを知っていることを意味する。なぜならであるからである。
署名生成
リング署名の生成には6つのステップが含まれる。平文はで表され、リングの公開鍵はで表される。
暗号学的ハッシュ関数を使用して、鍵を計算する。このステップでは、がの鍵として使用されるため、にランダムオラクルを想定している。 糊となる値としてランダムなを選択する。 自分以外のすべてのリングメンバーに対してランダムなを選び(は署名者の秘密鍵を使用して計算される)、対応するを計算する。 リング方程式をについて解く。 署名者の秘密鍵を使用してを計算する: リング署名は -タプル となる。
署名検証
署名検証には3つのステップが含まれる。
すべてのに公開鍵トラップドアを適用する: 。 共通鍵を計算する。 リング方程式が成り立つかどうかを確認する。
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) return r == X
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および他のいくつかの暗号通貨はこの技術を利用している。
関連項目
参考文献