（注）私は量子計算の専門家でも，情報の専門家でもありません。不適切な表現がありましたら，ご指摘いただけると幸いです。

はじめに

今回は，抗量子アルゴリズム(Quantum Resistant Algorithm，以降QRAと呼ぶ)で用いられる，Winternitz OTS+を作ってみようと思います。いつものように備忘録程度の内容になります。ご容赦ください。

抗量子アルゴリズムの種類

非対称鍵交換および署名において，QRAであると考えられているものは主に4種類あります。

格子暗号
符号ベース暗号
多変数暗号
ハッシュベース暗号

今回取り上げたのはハッシュベース暗号，特にXMSS(eXtended Merkle Signature Scheme)で用いられているWinternitz OTS+です。Lamport署名についてはすでにこちらで取り上げられているので割愛します。なお，OTSはほかにもThe Bleichenbacher-Maurer OTS，The BiBa OTS，HORSなど色々提案されています。

Winternitz OTSからWinternitz OTS+まで

Winternitz OTS，Variant of Winternitz OTSという過程を経て，Wintertnitz OTS+が提案されています。簡単にそれらについて書き留めます。

Winternitz OTS

Winternitz OTS(以降，W-OTS)は，Lamport署名と比較して，ハッシュ値の対の片方を公開する代わりに，関数の連鎖の出力$h^w(x)$を公開するところが異なります（ここで，$w$はパラメータ，$h$はハッシュ関数）。有効な署名を偽造されないようにするため，チェックサムがメッセージの後ろに追加されます。

Variant of Winternitz OTS

2011年にBuchman et alによってW-OTSのアップデートがなされました。これは，鍵でパラメタライズされた関数族を利用したものです。こちらもチェックサムが適用されています。

Winternitz OTS+

今回取り上げるのがこのWinternitz OTS+(以降，W-OTS+)です。W-OTS+は攻撃者のオラクルへの問い合わせが1回に制限されている限り，安全（正確には，EU-CMA安全；詳細は論文参照のこと）であるとされています。

W-OTS+は，ランダムな入力について関数の連鎖（ここではハッシュ連鎖）を使用することが基礎となっています。ランダムな入力とは，ここでは秘密鍵です。一方，ハッシュ連鎖の最後の出力は公開検証鍵となります。

Winternitz OTS+

概要

W-OTS+は，セキュリティパラメータ$\,\,n\in \mathbb{N}$，メッセージ長$m$，時間とメモリ使用量のトレードオフを決定するWinternitzパラメータ$\,\,w\in\mathbb{N}\,\, ,\,\,w>1$によってパラメタライズされます。また，$w$と$m$は次の値を計算するために計算されます。

l_1 = \left\lceil \frac{m}{\text{log}(w)} \right\rceil,
\,\,\,
l_2 = \left\lfloor \frac{\text{log}(l_1(w-1))}{\text{log}(w)} \right\rfloor + 1,
\,\,\,
l = l_1 + l_2

さらに，W-OTS+は鍵空間$\mathcal{K_n}$で関数族$\mathcal{F_n}\,\, ${$ f_k:${$0,1$}$^n \to ${$0,1$}$^n| k\in \mathbb{K_n} $}を使用します。圧縮無しの暗号学的な一方向性のハッシュ関数だと考えてもらって大丈夫です。$\mathcal{F_n}$を使って，次のハッシュ連鎖を定義します。

ハッシュ連鎖 $c^i_k(x,\textbf{r})$：入力値$x\in ${$0,1$}$^n$，イテレーションカウンタ$i\in \mathbb{N}$，鍵$k\in \mathcal{K}$，ランダム化要素$\textbf{r}=(r_1,...,r_j)\in ${$0,1 $}$^{n\times j}(j\geq i)$とすると，連鎖関数は次のように働きます。$i=0$のとき，$c$は$x$を返します($c^0_k(x,\textbf{r})=x$)。$i>0$のとき，再帰的に定義します。

c^i_k(x,\textbf{r}) = f_k(c^{i-1}_k(x,\textbf{r})\oplus r_i)

つまり，各ハッシュ連鎖では，関数は最初に中間値と$r$のビットごとのXORをとり，その結果に対してハッシングします。

鍵生成アルゴリズム

セキュリティパラメータ$n$を入力として，鍵生成アルゴリズムは$l+w-1$個の$n$ビットの文字列をランダムに一様に選択します。秘密鍵$\textbf{sk}=(\text{sk} _1,...,\text{sk} _l)$は，最初の$l$個のランダムなビット列から構成されています。残りの$w-1$個のビット列は，$c$のためのランダム化要素$\textbf{r}=(r _1,...,r _{w-1})$として使用されます。公開検証鍵$\textbf{pk}$は次のように計算されます。

\textbf{pk} = (\text{pk}_0,\text{pk}_1,...,\text{pk}_l) =
    ( (\textbf{r},k), c^{w-1}_k (\text{sk}_1,\textbf{r}) , \cdots,c^{w-1}_k (\text{sk}_l,\textbf{r}) ).

署名アルゴリズム

$m$ビットのメッセージ$M$，秘密署名鍵$\textbf{sk}$およびランダム化要素$\textbf{r}$を入力として，署名アルゴリズムはまず，$M$の$w$基底表現を計算します。つまり，$M=(M_1...M_{l_1}) \,\,,\,\, M_i \in ${$0,...,w-1 $}。したがって，$M$は自然数のバイナリ表現として扱われて，そのあと$w$の基底表現が計算されます。

次にチェックサムを以下のように計算します。

    C = \sum^{l_1}_{i=1}(w-1-M_i)

そして，その$w$基底表現$C=(C_1,...,C_{l_2})$を計算します。そのあと$M$と$C$の$w$基底表現の連結である$B=(b_1,...,b_l)=M\,\,||\,\,C$をつくります。署名は次のように計算されます。

\sigma = (\sigma_1,...,\sigma_l) = (c^{b_1}_k(\text{sk}_1,\textbf{r}),...,c^{b_l}_k(\text{sk}_l,\textbf{r})).

検証アルゴリズム

バイナリ長$m$のメッセージ$M$，署名$\sigma$，そして公開検証鍵$\textbf{pk}$を入力として，
検証アルゴリズムは，上述したようにまず$b_i,1\leq i \leq l$を計算します。
それから以下のように比較されます。

\begin{align}
    \textbf{pk}
    & = (\textbf{pk}_0,\textbf{pk}_1,...,\textbf{pk}_l) \nonumber \\
    & \overset{?}{=}
    ( (\textbf{r},k), c^{w-1-b_1}_k(\sigma_1, \textbf{r}_{b_1 + 1,w-1}),...,c^{w-1-b_l}_k(\sigma_l, \textbf{r}_{b_l + 1,w-1}) ) 
    \nonumber
\end{align}

比較が成立する場合はtrueを返し，そうでない場合はfalseを返します。

実装

Python 3.6 を用いて実装します。また，Winternitzパラメータ$w=16$とします。

Wintertnitzパラメータ

上述した定義にしたがって計算します。

from math import ceil, floor, log

#--- winternitz parameters
def winternitz_param(w):
    l_1 = ceil(256/log(w,2))
    l_2 = floor(log(l1*(w-1),2)/log(w,2))+1
    l = l_1 + l_2
    return l_1, l_2, l

疑似乱数生成

便宜上，urandomを用いますが，より良い疑似乱数生成アルゴリズムを使用するべきです。

from binascii import unhexlify, hexlify
from os import urandom

def random_key(n=32):
    return hexlify(urandom(n))

SHA256

ハッシュ連鎖で使用する一方向性のハッシュ関数を用意します。今回はSHA256を使用します。

import hashlib 

#--- Hexを返す
def sha256(message):
    return hashlib.sha256(message).hexdigest()

ハッシュ連鎖

W-OTS+のコアとなる部分です。署名用・検証用と分けて書きました。

#--- ハッシュ関数
def fn_k(x, k):
    return sha256(k+x)

#--- 署名用のハッシュ連鎖
def chain_fn(x, r, i, k, w):
    if i == 0:
        return x
    else:
        for j in range(i):
            # w基底表現でビットXOR(^)したのち，ハッシュ関数を通す
            # kは常に同一
            x = fn_k(hex(int(x,w)^int(r[j],w))[2:-1].encode('utf-8'), k)
    return x

#--- 検証用のハッシュ連鎖
def chain_fn4vf(x, r, i, k, w):
    # w-1-i回
    for j in range(i, w-1):
        # w基底表現でビットXOR(^)したのち，ハッシュ関数を通す
        # kは常に同一
        x = fn_k(hex(int(x,w)^int(r[j],w))[2:-1].encode('utf-8'),k)
    return x

鍵生成

def Kg_wotsp(w=16):

    # 署名に必要なWinternitzパラメータを計算
    l_1, l_2, l = winternitz_param(w)

    temp = []
    pk = []

    # l+w-1個のnビット(256bit default)の文字列をランダムに一様に選択
    for i in range(l+w-1):
        temp.append(random_key())

    # skは最初のl個から構成される。一時的にprivにいれる
    sk = temp[:-(w-1)]
    # ランダム化要素r（残りのw-1個）
    r = temp[l:]

    # pk_0だけ計算，pk_0 = (r,k)
    k = random_key()
    pk.append((r,k))

    for sk_ in sk:
        pk.append(chain_fn(sk_, r, w-1, k, w))

    return sk, pk

署名

アリスは下記の通り署名したあと，messageとpkとsignatureをボブに渡します。

def Sign_wotsp(sk,message,pk,w=16):
    # Default: w = 16 (16進数)
    # メッセージ長mを256bitとする
    m = 256

    # 署名に必要なWinternitzパラメータを計算
    l_1, l_2, l = winternitz_param(w)

    #ハッシュ関数を通す
    message = sha256(message.encode('utf-8'))

    # チェックサムおよびチェックサムとメッセージの連結Bを初期化
    checksum = 0
    b = []

    # メッセージMをw基底表現に変換しsに格納
    # チェックサムCはchecksumで計算
    for i in range(int(l_1)):
        j = int(message[i], w)
        b.append(j)
        checksum += w - 1 - j

    # int to hex. 最初の'0x'は除く
    c = (hex(checksum))[2:]

    # チェックサムを連結
    for i in range(int(l_2)):
        j = int(c[i], w)
        b.append(j)

    # 署名 初期化
    signature = []
    # 署名(pk[0][0]=r, pk[0][1]=k)
    # b[i]は式中，上付き文字
    for i in range(int(l)):
        signature.append(chain_fn(sk[i], pk[0][0],b[i], pk[0][1],w))

    return signature

検証

ボブはそれらを用いて検証を行います。

def Vf_wotsp(signature, message, pk, w=16):
    # Default: w = 16 (16進数)
    # メッセージ長mを256bitとする
    m = 256

    # 署名に必要なWinternitzパラメータを計算
    l_1, l_2, l = winternitz_param(w)   

    # ハッシュ関数を通す
    message = sha256(message.encode('utf-8'))

    # チェックサムおよびチェックサムとメッセージの連結Bを初期化
    checksum = 0
    b = []

    # メッセージMをw基底表現に変換しsに格納
    # チェックサムCはchecksumで計算
    for i in range(int(l_1)):
        j = int(message[i], w)
        b.append(j)
        checksum += w - 1 - j

    # int to hex. 最初の'0x'は除く
    c = (hex(checksum))[2:]

    # チェックサムを連結
    for i in range(int(l_2)):
        j = int(c[i], w)
        b.append(j)

    # 検証 初期化
    vk = []

    for i in range(int(l)):
        # w-1-b[i]回ハッシュ連鎖を処理
        vk.append(chain_fn4vf(signature[i], pk[0][0], b[i], pk[0][1],w))

    # 検証を行う([0]は(n,k)なので[1]から比較)
    if vk == pk[1:]:
        return True

    return False

Lamport, W-OTS，W-OTS+などのワンタイム署名の欠点

これらは量子コンピュータ耐性があると考えられていますが，問題は，安全である条件としてこのままでは一度しか署名に使えない点です。

そういった問題を解決するため，Merkle木などを利用して多い回数署名できるようにする方法が提案されています。記事冒頭で一度触れたXMSSやSPHINCSがそれにあたります。

これらはPQCRYPTO ICT-645622によって耐量子として公開鍵署名に推奨されているようです(SPHINCSは正確にはSPHINCS-256)。

おわりに

今回は量子計算から少し離れましたが，抗量子アルゴリズムで使用されるWinternitz OTS+について，備忘録としてまとめました。

ここまで読んでくださってありがとうございました。

抗量子アルゴリズムで用いられるWinternitz OTS+を作る

はじめに

抗量子アルゴリズムの種類

Winternitz OTSからWinternitz OTS+まで

Winternitz OTS

Variant of Winternitz OTS

Winternitz OTS+

Winternitz OTS+

概要

鍵生成アルゴリズム

署名アルゴリズム

検証アルゴリズム

実装

Wintertnitzパラメータ

疑似乱数生成

SHA256

ハッシュ連鎖

鍵生成

署名

検証

Lamport, W-OTS，W-OTS+などのワンタイム署名の欠点

おわりに

参考文献