NAPS

根据设计有限次数代理需求阅读NAPS

Abstract：

DAPS（Double-authentication-preventing signatures），核心目的就是：如果签名者使用相同的地址（第一部分）和不同的载荷（第二部分）签名两条消息，则任何人都能从这两份签名中公开提取出该签名者的私密签名密钥。

应用：A prime application for DAPS is disincentivizing and/or penalizing the creation of two signatures on different payloads within the same address。

Introduction

数字签名是现代领域中提供强大完整性和真实性保证的核心密码学原语。

主要应用广泛的有两类：

基于大数分解的RSA-FDH
基于离散对数的数字签名算法（EC）DSA

数字签名的签名和验证以及安全性要求其满足选择消息攻击下的存在不可伪造性（EUF-CMA）

在本文中我们研究一种名为（dubbed）双重身份验证预防签名（DAPS）的签名方案变体（variant）

m=(a,p)

待签名消息$m$由地址（Address）$a$和载荷（payload）$p$

DAPS核心思想：

1.在没有针对同一地址$a$对不同载荷$p’ \neq p$进行签名，

其行为与传统签名完全一致，即在EUF-CMA意义下具有不可伪造性

2.如果签名者对同一地址$a$下的不同载荷$p’ \neq p$产生了两个签名（碰撞消息），那么任何人都可以从这两个签名中计算出签名者的私钥$sk$(双重签名提取性质)

现有的DAPS构造方案主要问题是没有基于广泛使用的签名方案，所以尚未看到在实际中被采用。

本文目标就是提供一种通用的构造方法能够将ECDSA等现有的广泛使用的签名方案增强为可证明安全的DAPS，且安全证明仅需要对签名方案进行黑盒使用。

Applications of DAPS

Accountable Assertions and Non-equivocation

可归责断言：

这是一种密码学机制，允许将陈述 (Statements) 与语境 (Contexts) 以可追溯责任的方式进行绑定。如果攻击者在同一语境下发布了两个相互矛盾的陈述，任何观察者都能从中提取出攻击者的私钥。DAPS 可以被视为可归责断言的一种更强形式，因为它额外要求满足“不可伪造性”。因此，高效的 DAPS 构造同时也为可归责断言提供了更高效的实例化方案

非歧义合约：（跟比特币有关）
运作机制：如果参与方 A 因违规行为需要被处罚， A 会创建一个新的比特币密钥对，并将其扩展为 DAPS 密钥对，随后在这个新密钥下存入一笔押金。执行过程：每当 A 需要在某个语境下发送一个陈述时，它必须同时发送一个对应 DAPS 密钥的签名。处罚结果：如果 A 产生了歧义（即双重签名），任何人都能从同一语境下的两个断言中提取出其私钥，进而将押金中的资金转移到自己控制的地址下。如果 A 保持诚信，则能继续完全控制这笔押金。

Disincentivizing Double-Signing（威慑双重签名）

Overview

A Working Path

秘密共享机制

对签名私钥（属于$\mathbb{Z}_q$）进行秘密共享。
为每个地址 a 关联一个一次多项式 $f_a(X)$。其中，常数项$f_a(0)$即为秘密签名密钥。
签名过程：每份签名都包含一个“份额” $z=f_a(p)$，即在载荷 $p$处对该多项式的求值结果。
提取过程：一旦在同一地址 a 下出现了两个针对不同载荷 p 和 p′ 的签名，就相当于获得了同一条直线上的两个点。根据拉格朗日插值法，任何人都能还原出$f_a(0)$，即提取出私钥。

Signature Schemes

1、三个概率多项式

$KGen_{Σ}(1^k)$

安全参数$k$,输出($sk_Σ，pk_Σ$)和及其关联的消息空间$M$

$Sign_Σ(sk_Σ，m)$

输入私钥$sk_Σ$和消息$m\in M$，输出签名$\sigma$

$Verify_Σ(pk_Σ,m,\sigma)$

输入公钥$(pk_Σ，m，\sigma)$，输出$b\in {0,1}$

2、EUF-CMA

对于所有PPT敌手A其在Fig.1获胜概率是安全参数 κ的可忽略函数，则称该方案在选择消息攻击下满足存在不可伪造性（EUF-CMA）

3、椭圆曲线群（Elliptic Curve Groups）

ECDSA签名方案

Double-Authentication-Preventing Signatures

Formal Model

消息空间$\mathcal{M} = \mathcal{A} \times \mathcal{P}$

消息：$m=(a,p)$

扩展了第四个算法Ex，用于从两条冲突消息的签名中提取私钥

冲突消息定义

m=(a,p)

我们现在有两条消息$m_1=(a_1,p_1)$,$m_2=(a_2,p_2)$

if $a_1=a_2$,$p_1\neq p_2$就说这两条消息冲突（colliding）

DAPS定义

1、四个PPT算法

（$KGen_D,Sign_D,Verify_D,Ex_D$）

前三个就是正常签名验证流程，主要是第四个提取密钥

$Ex_D(pk_D,m_1,m_2,\sigma_1,\sigma_2)->sk_D$

2、EUF-CMA

对于所有PPT敌手A其在Fig.2获胜概率是安全参数 κ的可忽略函数，则称该方案在选择消息攻击下满足存在不可伪造性（EUF-CMA）

3、双重签名提取性DSE

DSE安全：当有冲突消息是$Ex$失败的概率可忽略

$\Pr\left[\mathbf{Exp}^{\text{DSE}}_{\mathcal{A}, \text{DAPS}}(\kappa) = 1\right] \leq \varepsilon(\kappa)$

现有DAPS构造方案大多仅支持在诚实生成密钥的提取性DSE。

Short DAPS in the DL Setting

基于离散对数且满足EUF-CMA安全的签名方案中构造通用DAPS，尽量保持‘非侵入性’

1、keypoint将签名方案和可验证秘密共享VSS结合

VSS:

Shamir秘密共享

允许将秘密 s 分享给 ℓ 个参与方，使得获得 k 个份额即可重建秘密，而少于 k 个份额则无法获得任何信息。秘密 s 作为 k−1 次多项式 f(X) 的常数项，份额即为 f(i)。

Feldman方案

利用群同态性公开多项式系数的映射，从而允许任何人非交互式地验证份额的正确性。

2、ElGmal加密

具有乘法同态性并且在判定Diffie-Hellman（DDH）假设下IND-CPA安全的

3、Σ-协议（重要）

设$L\in X$是一个NP语言，具有相应见证关系$R$使得$L={x|∃w:R(x,w)=1}$

$L$是Σ-协议prover和verifier之间的一个交互式三轮协议，证明者向验证者证明其知道命题$x\in L$的一个witness($w$)

用于DDH元组的Σ协议：素数阶群$\mathcal{G}$的元素($g_1,g_2,u_1,u_2$)

关系R定义相应的语言作为见证关系

$(($g_1,g_2,u_1,u_2,w$))\in R<->g_1^w=u_\land g_2^w=u_2$

4、NIZK(Non-Interactive Zero-Knowledge Proof)

零知识证明ZPK

证明者能够向验证者证明自己知道莫格秘密，但除了“我知道这个秘密之外”，不泄露任何关于秘密的信息
NIZK，把多轮交互变成只发送一次Proof，验证者收到Proof后即可验证

Π系统是一个三元组算法（$Setup_Π,Proof_Π,Verify_Π$）

$Setup_Π(1^k)$:以安全参数$k$为输入，输出crs（common reference string）

$Proof_Π(crs,x,w)$:输出一个证明$\pi$

$Verify_Π(crs,x,\pi)$:输出$b\in {0,1}$

5、Σ签名密钥的提取

定义前两个较弱的“双重签名提取”概念，分别针对honestly和maliciously 生成的DAPS密钥，覆盖底层签名方案签名密钥的提取。弱双重签名提取（wDSE）与恶意密钥下的弱双重签名提取（wDSE*）

6、DAPS IN DL

ElGamal（$x_E,pk_E$）

对于每一个可能的地址$i$,均匀选取$ρ_i\in \mathbb{Z}q$,并额外在DAPS公钥中包含$g^{ρ_i}$的一个加密$(C{i,1},C_{i,2})$

消息$m=(i,p)\in [n]\cdot\mathbb{Z}_q$,对m进行签名，然后用一个关于$sk_Σ$的秘密份额对其进行扩展

$f_i(X)=ρ_iX+sk_Σ$,并将$z=f_i(p)$包含进签名中

当两条消息碰撞消息进行签名时我们可以得到多项式$f_i$的两个份额，可以重构出$sk_Σ$。

为确保$z$的计算时正确的，每个签名而外附带一个关于R的证明,用于验证

提取算法在应用于碰撞签名时，只会揭示秘密签名密钥$sk_Σ$,不会揭示$r_i$和$ρ_i$.无法达到更强的DSE只能获得wDSE安全性。

7、DAPS IN ECDSA

怎么应用到SM9

结合SM9这篇进行构造