Lamport One Time Signature

Lamport 是第一个 OTS(One Time Signature) 算法，由 Leslie Lamport 于 1979 年提出，论文可见 Constructing Digital Signatures from One Way Function ，一对密钥只能签名一次，不能重复使用。

下面按照 $(GEN, SIG, VER)$ 三元组描述该算法。

密钥生成($GEN$)

$$(pk, sk) \leftarrow GEN(1^k)$$

首先我们需要确定安全参数 $k$，不过实际操作中我们一般只需要确定输出的摘要长度 $n$。

通过随机数生成器(PRG, Pseudo Random Generator)，生成 $n$ 对随机数，每一对包含两个随机数，每一个随机数 $n$ bits，总共 $2\times n\times n$ bits，此为私钥。

对每一个随机数进行哈希，生成 $2\times n$ 个摘要，每一个 $n$ bits，也是 $2 \times n \times n$ bits，此为公钥。

形式化表示为：

$$sk = (sk_{0,0}, sk_{0,1}, \dotsm, sk_{n-1, 0}, sk_{n-1, 1}) \\
pk = (pk_{0,0}, pk_{0,1}, \dotsm, pk_{n-1, 0}, pk_{n-1, 1})$$

图示：

消息签名($SIG$)

$$ \sigma(M) \leftarrow SIG(M, sk)$$

对于输入 $M \in \{0, 1\}^*$，首先使用哈希函数进行处理，生成 $n$ bits 的摘要。

$$m = (m_0, m_1, \dotsm, m_{n-1})$$

对于摘要中的每一个 bit，进行下面的操作：对于摘要中的第 $i$ 个 bit $m_i$，如果该 bit 为 0，那么取 $sk_{i,0}$，否则该 bit 位为 1，取 $sk_{i,1}$，最后签名为

$$\sigma =(\sigma_0, \sigma_1,\dotsm \sigma_{n-1}) = (sk_{0,m_0}, sk_{1,m_1}, \dotsm, sk_{n-1,m_{n-1}})$$

比如说输入的 $M$ 经过哈希之后得到

$$(0,1,0,1,1,0,0,1)$$

那么签名结果是

$$\sigma= (sk_{0,0}, sk_{1,1}, sk_{2,0},sk_{3,1},sk_{4,1},sk_{5,0},sk_{6,0},sk_{7,1})$$

图示：

消息校验($VER$)

$$ false/true \leftarrow VER(M, \sigma(M), pk) $$

对于消息 $M \in \{0,1\}^*$，首先进行哈希，得到 $n$ bits 的摘要。

$$m = (m_0, m_1, \dotsm, m_{n-1})$$

对于摘要中的每一个 bit，进行下面的操作：对于摘要中的第 $i$ 个 bit $m_i$，如果该 bit 为 0，那么取 $pk_{i,0}$，否则该 bit 位为 1，取 $pk_{i,1}$，最后得到

$$v= (pk_{0,m_0}, pk_{1,m_1}, \dotsm, pk_{n-1,m_{n-1}})$$

对于签名 $\sigma$ 中的每一个部分进行哈希，得到

$$v^{\prime}= (pk_{0,m_0}^{\prime}, pk_{1,m_1}^{\prime}, \dotsm, pk_{n-1,m_{n-1}}^{\prime})$$

如果 $v=v^{\prime}$，则签名校验通过，返回 $true$，否则校验失败，返回 $false$。

图示：