はじめに
この記事では，Chalkias et al. による論文 "Non-interactive half-aggregation of EdDSA and variants of Schnorr signatures" 1において提案されている，EdDSAによる署名を伝送する際の通信情報量を削減するアルゴリズムの解説を行います．
EdDSAの概観
この節では，EdDSAの署名スキームについて，この論文の内容に合わせた形で概説します．
\(\, m\,\) を送りたいメッセ―ジとする．\(\, q\,\)を十分大きい素数，\(\, G\,\)を\(\, \mathbb{F}_q \,\)上のなんらかの楕円曲線上の点のなす群，\(\, B \in G\,\)を\(\, G \,\)の巡回部分群の生成元，\(\, H_i \,\)を適当なハッシュ関数とする．\(\, \lambda \,\)ビットの安全性を確保するためには，\(\, q \approx 2^{2\lambda}\,\)と取ればよいことが知られており，実際に用いられているEd25519では，128ビットの安全性を得るために\(\, q = 2^{255} - 19 \,\)を用いている．したがって，以下では\(\, q \,\)をこの程度の大きさとし，特に\(\, \mathbb{F}_q, G \,\)の元は\(\, 2\lambda \,\)ビットで表されていると仮定する．以下のアルゴリズムの説明では，アルファベット小文字を\(\, \mathbb{F}_q \,\)の元を，大文字を\(\, G \,\)の元を表す記号として用いる．また，\(\, G \,\)の元の\(\, \mathbb{F}_q \,\)ベクトル空間としてのスカラー倍には\(\, \cdot \,\)を用い，\(\, \mathbb{F}_q \,\)の元どうしの積は単に\(\, xy \,\)などと書く．
鍵生成
秘密鍵\(\, \mathsf{sk} \in \{0, 1\}^{2\lambda} \,\)を一様ランダムに取る．ハッシュ関数を用いて，\(\, (s, k) = H_1(\mathsf{sk}) \,\)と\(\, 2\lambda \,\)ビットずつの整数に分解する．\(\, A = s\cdot B \,\)として，\(\, (\mathsf{sk}, \mathsf{pk} = A) \,\)をそれぞれ秘密鍵・公開鍵として出力する．
署名
別のハッシュ関数を用いて，\(\, r= H_2(k, m) \,\)を計算する．これを用いて，楕円曲線上の点\(\, R = r\cdot B \,\)と\(\, \mathbb{F}_q \,\)の元\(\, t = r + sH_0(R, A, m) \,\)を計算し，署名\(\, \sigma = (R, t) \,\)を出力する．
検証
受け取った署名\(\, \sigma = (R, t) \,\)と公開鍵\(\, \mathsf{pk} = A \,\)について，\[t\cdot B = R + H_0(R, A, m) \cdot A\]なら署名を受理，そうでなければ拒否する．
情報の圧縮
上のEdDSAの署名スキームをよく見ると，署名を定めている本質的な情報は秘密鍵\(\, \mathsf{sk} \in \{0, 1\}^{2\lambda} \) のみであるにもかかわらず，署名としては組\(\, \sigma = (R, t)\in G\times \mathbb{F}_q\, \)という\(\, 4\lambda\, \)ビットの情報をやりとりしていることがわかります．この冗長性は安全性の確保のために必要なものではありますが，通信する情報量を減らせるに越したことはありません．この記事では，大きい\(\, n\,\)について，\(\, n\,\)個の署名を伝送する際の通信情報量を，安全性を損なうことなく削減する手法について説明します．
アルゴリズムの概要
署名者は，ある関数\(\, \mathsf{AggregateSig}\,\)を用いて，\(\, n\,\)個のメッセージと，EdDSAによって生成された公開鍵・署名の組\(\, (m_i, \mathsf{pk}_i, \sigma_i)\,\)から，圧縮された1つの署名\(\, \sigma_{\mathsf{aggr}}\in G\,\)を生成し，これを伝送します．この\(\, \sigma_{\mathsf{aggr}}\,\)は\(\, 2(n + 1)\,\)ビットのメモリを用いて表すことができて，ナイーブに署名を伝送した場合の\(\, 4n\lambda \,\)ビットからおよそ半分の通信情報量になっています．
検証者は，別の関数\(\, \mathsf{AggregateVerify} \,\)を用いて，\(\, n \,\)個のメッセージと公開鍵，および伝送された\(\, \sigma_{\mathsf{aggr}} \,\)が正当な署名であるかを検証します．
アルゴリズムの詳細
\(\, \mathsf{AggregateSig} \,\)は以下のように定義されます．
\(\, n \,\)個のメッセージ\(\, m_i \,\)，署名\(\, \sigma_i = (R_i, t_i) \,\)，公開鍵\(\, \mathsf{pk}_i = A_i \,\)から，\(\, n \,\)個のハッシュ値 \[e_i = H_1(R_1, A_1, m_1, \ldots, R_n, A_n, m_n, i) \in \mathbb{F}_q\]を計算し，\[ t_{\mathsf{aggr}}= \sum_{i=1}^n e_it_i\] と定める．圧縮された署名\( \sigma_{\mathsf{aggr}}\)を\[\sigma_{\mathsf{aggr}} = \mathsf{AggregateSig}((m_i, \mathsf{pk}_i, \sigma_i)_{i = 1}^n ) = [R_1, \ldots, R_n, t_{\mathsf{aggr}}]\]
と定め，これを\( n \)個のメッセージ\(\, (m_i)_{i=1}^n \,\)に対する署名として用いる．このとき，各\(\, R_i \,\)は\(\, G \,\)の，\(\, t_\mathsf{aggr} \,\)は\(\, \mathbb{F}_q \,\) の元なので，\(\, \sigma_{\mathsf{aggr}} \,\)は\(\,2(n+1)\lambda\, \)ビットで表すことができる．
\(\, \mathsf{AggregateVerify} \,\)は以下のように定義されます．
検証者は\(\,\sigma_{\mathsf{aggr}} = [R_1, \ldots, R_n, t_{\mathsf{aggr}}]\,\)を受け取る．\(\, \mathsf{AggregateSig} \,\)に用いたのと同じハッシュ関数\(\, H_1 \,\)を用いて，各\(\, i \,\)について\[e_i = H_1(R_1, A_1, m_1, \ldots, R_n, A_n, m_n, i) \]を計算する．
\[\sum_{i=1}^n e_i(R_i + H_0(R_i, A_i, m_i))\cdot A_i = t_{\mathsf{aggr}}\cdot B\]であるとき，署名を受理し，そうでないとき拒否する．署名が正当なEdDSAスキームと\(\, \mathsf{AggregateSig} \,\)によって生成されているときは明らかに受理される．
安全性
上の署名圧縮スキームは，EdDSAが十分安全であるという仮定のもとで，安全性が保証されます．つまり，この圧縮署名を高い確率で偽造できるアルゴリズムが存在すると仮定すると，そのアルゴリズムを用いてEdDSAを偽造できるアルゴリズムを作れてしまう，ということを安全性の担保としています．このロジックはRSA暗号が素因数分解の困難性を，EdDSAが離散対数問題の困難性を利用しているのと同じです．証明には " 分岐補題(Forking Lemma)の解説と具体例 " 2で解説されている一般分岐補題を用います．
さらなる圧縮
この論文では，さらに任意の\(\, \varepsilon > 0 \,\)について，EdDSAの署名を\(\, 2(n + \varepsilon)\lambda \,\)ビットに圧縮する方法が提案されています．
