本文主要对2021年CCS的论文《Efficient Online-friendly Two-Party ECDSA Signature》这篇论文方案进行简述，并对椭圆曲线数字签名进行了安全性证明
文章目录
前言
由于双方ECDSA签名在加密货币中广泛部署，因此受到了广泛关注。根据是否需要消息，我们可以将双方签名分为两个不同的阶段，即离线和在线。理想情况下，在线阶段应该尽可能地轻量级。同时，离线阶段的成本应该保持与正常签名生成的成本相似。然而，现有的ECDSA双向协议并不是最优的:它们的在线阶段需要对密文进行解密，或者离线阶段需要至少执行两次乘法到加法的转换，这在总体复杂度上占主导地位。本文提出了一种在线友好的两方ECDSA，该ECDSA具有轻量级的在线阶段和单一的乘加函数的离线阶段。
它是由密钥的再共享和nonce的线性共享的新颖设计构成的。该方案显著改进了以往基于无关传输和同态加密的协议。
背景知识
椭圆曲线密码学
私钥为d，其中d是集合{1,2,…,n-1}中的一个元素，其中n是子群的阶
公钥是一个点H=dG，其中G是子群的一个基点
根据d和G求H很容易，根据H和G求解d很困难（根据离散对数难解问题）
ECDH
首先，有两个实体Alice和Bob
Alice持有私钥
d
A
d_A
dA和公钥
H
A
=
d
A
G
H_A=d_AG
HA=dAG
Bob持有私钥
d
B
d_B
dB和公钥
H
B
=
d
B
G
H_B=d_BG
HB=dBG
此时Alice和Bob通过非安全信道交换公钥
H
A
H_A
HA和
H
B
H_B
HB
#mermaid-svg-K85Jqi937E7XEfBV {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-K85Jqi937E7XEfBV .error-icon{fill:#552222;}#mermaid-svg-K85Jqi937E7XEfBV .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-K85Jqi937E7XEfBV .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-K85Jqi937E7XEfBV .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-K85Jqi937E7XEfBV .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-K85Jqi937E7XEfBV .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-K85Jqi937E7XEfBV .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-K85Jqi937E7XEfBV .marker{fill:#333333;stroke:#333333;}#mermaid-svg-K85Jqi937E7XEfBV .marker.cross{stroke:#333333;}#mermaid-svg-K85Jqi937E7XEfBV svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-K85Jqi937E7XEfBV .actor{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-K85Jqi937E7XEfBV text.actor>tspan{fill:black;stroke:none;}#mermaid-svg-K85Jqi937E7XEfBV .actor-line{stroke:grey;}#mermaid-svg-K85Jqi937E7XEfBV .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333;}#mermaid-svg-K85Jqi937E7XEfBV .messageLine1{stroke-width:1.5;stroke-dasharray:2,2;stroke:#333;}#mermaid-svg-K85Jqi937E7XEfBV #arrowhead path{fill:#333;stroke:#333;}#mermaid-svg-K85Jqi937E7XEfBV .sequenceNumber{fill:white;}#mermaid-svg-K85Jqi937E7XEfBV #sequencenumber{fill:#333;}#mermaid-svg-K85Jqi937E7XEfBV #crosshead path{fill:#333;stroke:#333;}#mermaid-svg-K85Jqi937E7XEfBV .messageText{fill:#333;stroke:#333;}#mermaid-svg-K85Jqi937E7XEfBV .labelBox{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-K85Jqi937E7XEfBV .labelText,#mermaid-svg-K85Jqi937E7XEfBV .labelText>tspan{fill:black;stroke:none;}#mermaid-svg-K85Jqi937E7XEfBV .loopText,#mermaid-svg-K85Jqi937E7XEfBV .loopText>tspan{fill:black;stroke:none;}#mermaid-svg-K85Jqi937E7XEfBV .loopLine{stroke-width:2px;stroke-dasharray:2,2;stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);}#mermaid-svg-K85Jqi937E7XEfBV .note{stroke:#aaaa33;fill:#fff5ad;}#mermaid-svg-K85Jqi937E7XEfBV .noteText,#mermaid-svg-K85Jqi937E7XEfBV .noteText>tspan{fill:black;stroke:none;}#mermaid-svg-K85Jqi937E7XEfBV .activation0{fill:#f4f4f4;stroke:#666;}#mermaid-svg-K85Jqi937E7XEfBV .activation1{fill:#f4f4f4;stroke:#666;}#mermaid-svg-K85Jqi937E7XEfBV .activation2{fill:#f4f4f4;stroke:#666;}#mermaid-svg-K85Jqi937E7XEfBV .actorPopupMenu{position:absolute;}#mermaid-svg-K85Jqi937E7XEfBV .actorPopupMenuPanel{position:absolute;fill:#ECECFF;box-shadow:0px 8px 16px 0px rgba(0,0,0,0.2);filter:drop-shadow(3px 5px 2px rgb(0 0 0 / 0.4));}#mermaid-svg-K85Jqi937E7XEfBV .actor-man line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-K85Jqi937E7XEfBV .actor-man circle,#mermaid-svg-K85Jqi937E7XEfBV line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;stroke-width:2px;}#mermaid-svg-K85Jqi937E7XEfBV :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}
Alice
Bob
A的公钥HA
B的公钥HB
都计算出dadbG
Alice
Bob
用ECDSA进行签名
要传递的信息m的截断哈希值z,
Alice：
选取一个随机数k，k是{1,2，…,n-1}中的一个元素
然后计算出点P=kG,
计算r=
x
p
x_p
xpmod n;
然后计算s=
k
−
1
(
z
+
r
d
A
)
k^{-1}(z+rd_A)
k−1(z+rdA) mod n
把（r，s）发送给Bob
Bob：
计算u1=
s
−
1
r
s^{-1}r
s−1r mod n
计算u2=
s
−
1
z
s^{-1}z
s−1z mod n
计算P=
u
1
G
u_1G
u1G+
u
2
u_2
u2
H
A
H_A
HA
验证r=
x
p
x_p
xp mod n是否成立，若成立则Alice签名有效
MtA
根据k和x的分量计算k的逆和k的逆乘x代价很高。所以利用k和x的乘法份额和加法同态加密方案Paillier，由此产生的签名程序只涉及同态操作和解密操作，可以降低通信代价。本篇论文引入了MtA函数，将乘法转化为加法共享运算。
但是MtA函数的证明需要使用零知识证明的知识。
调用两次MTA根据k的加法分量计算
k
−
1
k^{-1}
k−1的分量，再调用**两次MTA**根据
k
−
1
k^{-1}
k−1的分量和x的分量计算
k
−
1
x
k^{-1}x
k−1x的分量
离线和在线签名
MPC可以分为在线和离线阶段，其中
离线阶段：计算和用户输入无关的消息，（预计算），减少在线阶段的计算量，提高通信效率
在线阶段：计算和用户消息相关的部分
如果在线阶段是非交互式的，并且其成本与单一签名验证相同，阈值签名的在线阶段是最佳的。如果该方案的在线阶段是最优的，则被称为在线友好方案
有些方案采用乘法共享以及加法同构特性，在线阶段需要解密密文，在线阶段不是最优。以前的协议要么需要相对缓慢的在线计算，要么在离线阶段需要调用2到4次MtA，而在线阶段是最佳的；但是这样总体方案的代价不是最佳，所以我们的目标：尽可能最少次数调用MtA，而且获得最优的在线性能
本文简介
提出了一个在线友好的双方ECDSA，即2ECDSA，这样它的在线计算几乎是最优的，而且它的离线阶段只需要调用一次MtA。
具体贡献
1.在线阶段最优
在线阶段是非交互式的，并且只需要传输一个单独的元素，所以在线阶段最优；
离线阶段只需要调用一次MtA
提出了两种新的分享方案：
①k=k1(r1+k2)
②x=x1’k2+x2’
2.具体实例化
在Rust中提供了我们的两方2ECDSA协议的实现，并对Paillier加密、CL加密和遗忘传输中的MtA功能进行了实例化
3.门限秘密共享
提出的两方ECDSA可以和门限秘密共享进行结合，从而实现2-n的ECDSA方案。
技术概述
出发点：使用简单的乘法共享和加法共享来实现双方ECDSA
第一次尝试
使用x的秘密重分享
具体来说，离线阶段：引入k2前, 原始状态：x=x1+x2
引入k2后，现在状态：x=x1’k2+x2’(调用一次MTA)
在线阶段：P2计算S2，P1根据s2,k1,x1’计算s
更具体，在离线阶段：
P1选择x1’,P1和P2 调用MTA，分别输入x1’和k2, 输出结果为tA+tB=x1’*k2;
这之后，P1持有tA和x1,x1’; P2持有tB,x2
然后进行交互，P1向P2发送cc=tA-x1; 然后P2计算x2’=-tB-cc+x2;
这样就完成了x的重分享
安全分析：在这种情况下，x1=x1’k2-tB-cc,P2只需设置K2=0就可以得知x1，此时是不安全的
第二次尝试
主要思想：增加一个x1的掩码r1,在P2选择k2之后，P1选择一个随机数r1，从而满足x=x1’(k2+r1)+x2’,这样就可以排除k2=0对x1泄露的可能性
之后再对论文具体方案进行补充
原始ECDSA方案安全性证明
下面主要对原始ECDSA方案的安全性进行规约证明。
首先，要证明一个加密或者签名算法的安全性，最常见的做法是将其规约到一个数学困难问题上，又因为数学问题是难解的，所以说这个加密或者签名方案就是难以攻破的，从而证明其安全性。
对于ECDSA椭圆曲线签名方案来说，它是基于ECDLP问题的，即
私钥为d，其中d是集合{1,2,…,n-1}中的一个元素，其中n是子群的阶
公钥是一个点H=dG，其中G是子群的一个基点
根据d和G求H很容易，根据H和G求解d很困难
签名算法持有公钥和私钥，但是私钥是保密的，公钥是公开的；
下面介绍攻击模型，该模型包括一个敌手 A和算法 B，他们之间进行交互式游戏。算法B接收一个随机的 ECDLP问题实例 Y = xG，他的目标是计算出 x 。算法 B把敌手 A作为子程序，算法 B扮演敌手 A的挑战者。如果最后A能根据伪造的消息和签名求出k，那么说明解决了ECDLP问题。
具体证明流程：
（1）设置阶段：算法B将一些系统公共参数发送给A，然后算法B维护一张
L
h
L_h
Lh列表（*存放一些（消息，哈希值）对*），并初始化该列表为空，
（2）查询阶段：（敌手A可以向算法B查询消息m对应的哈希值和签名）
①哈希查询：
敌手A可以向B发送消息m以查询其对应的哈希值，最初
L
h
L_h
Lh列表为空，此时B对
L
h
L_h
Lh列表进行查询，
L
h
L_h
Lh列表不存在（m,e）,所以此时算法B**随机选择一个e∈{0,1}
n
^{n}
n**,返回给敌手A，并将对应（m,e）存入
L
h
L_h
Lh列表中；
后续进行查询时也是相同逻辑，算法 B首先检查消息 m是否已经出现在列表 LH中。若已存在，算法 B直接将 e返回给敌手 A;否则，算法 B从 {0，1} n中任意选择 e，并将(m，e)存储进
L
h
L_h
Lh列表中，然后将 e返回给敌手 A
特别地，在
q
h
q_h
qh次查询中，不能全都返回给敌手A随机数，要*随机选择*一个消息记为
m
∗
m^{*}
m∗,对于该消息 算法B通过查询**随机预言机**返回给敌手A消息
m
∗
m^{*}
m∗**真正的哈希值**
H
(
m
∗
)
H(m^{*})
H(m∗)
②签名查询：（在该阶段，敌手A可以向算法B查询一些消息的对应签名）
签名查询。敌手 A向算法 B提交消息 m ，算法 B任意选择随机数 k ∈ ［1，n － 1］，然后计算 Ｒ =kG = (x1，y1) ，提取 r = x1 mod n 。算法 B在
L
h
L_h
Lh列表中
搜索(m，e) ，若列表 L中不存在(m，e)（说明敌手A并没有进行过哈希查询，如果此时返回签名则会被A察觉到不是真实执行） ，则返回符号“⊥”，查询终止;
否则，算法 B计算 s =
k
−
1
(
H
(
m
)
+
x
r
)
k^{-1}(H(m)+xr)
k−1(H(m)+xr)mod n;然后，将签名结果(r，s)返回给敌手 A
（3）伪造阶段：（在此阶段，敌手A有效地伪造出消息
m
∗
m^{*}
m∗对应的签名（
r
∗
r^{*}
r∗,
s
∗
s^{*}
s∗））
若算法 B在查询阶段没有终止退出，那么敌手 A将以至少为 ε的优势输出伪造消息
m* 和有效伪造签名(e* ，s* ) 。由于敌手 A执行哈希查询的次数大于 1/
q
H
q_H
qH ，所以敌手 A至少以**ε’ ＞ ε /
q
H
q_H
qH的优势**计算出 k =
(
s
∗
)
−
1
(s^{*})^{-1}
(s∗)−1 ( H(m)+xr ) ，从而 ECDLP问题被解决.
又因为ECDLP是困难问题，暂时没有多项式时间算法可以以不可忽略的优势ε来解决ECDLP问题，所以不存在能够在 t时间内以不可忽略的优势 ε攻破改进方案的敌手。因此，方案是安全的。
版权归原作者 白开水呀呀 所有， 如有侵权，请联系我们删除。