敏感条约签订协议
Sensitive Contract Signing Protocol
1.参与者
协议需要三个参与者:Alice、Bob和Trent。其中:
Alice
和Bob
是参与敏感条约签订的两方Trent
是可信的第三方;不会欺骗协议中的任何一方,也不会帮助任何一方骗取另一方的隐秘信息。
2.协议目标
- 若条约签订成功,则三个参与者均会得知。
- 若条约签订失败,
Alice
和Bob
中不同意签订条约的人无法得知对方的选择。 - 若条约签订失败,
Trent
无法得知是谁选择拒绝,也无法得知有几人选择拒绝。
3.协议原理
首先,三方协定三个大整数数:Alice
:$a$,Bob
:$b$,Trent
:$N$。其中,$a$和$b$是素数,$N=a\times b$。然后,每当需要签订条约时,三方协定一个指数$s$和一个无法分解的大合数$M$。Alice
和Bob
分别计算$A\equiv a^s\pmod M$和$B\equiv b^s\pmod M$并将其发送给Trent
。然后Trent
对签订结果进行判定:若$AB\equiv N^s\pmod M$则说明双方均同意该条约,签订成功;反之则说明至少有一方不同意该条约,签订失败。此过程中,Alice
和Bob
都无法单独通过已有的信息和拦截的信息来判断另一方的选择,若条约签订失败,Trent
也无法判断是谁选择拒绝条约。
4.协议描述
【准备部分】 准备部分的任务是协定$a$、$b$、$N$($a$与$b$是素数,$N=ab$)以供后续条约签订使用。所协定的$a$、$b$、$N$可供以后多次使用。准备部分协议有多种实现方式。本文给出其中较为易于实现的一种。
Step1.1:Trent
使用RSA算法
生成公钥$(e,n)$和私钥$(d)$,并将公钥发送给Alice
.
Step1.2:Alice
选定素数$a$,计算$A_0\equiv a^e\pmod n$,并将$A_0$发给Bob
.
Step1.3:Bob
选定素数$b$,计算$B_0\equiv b^e\pmod n$、$N_0\equiv A_0B_0\pmod n$,并将$N_0$发送给Trent
.
Step1.4:Trent
计算$N\equiv N_0^d\pmod n$.
【签约部分】 签约阶段包含两个阶段,第一部分是协定无法分解的大合数$M$;第二阶段是双方的态度声明与第三方的结果判定。
Step2.1:Alice
和Bob
分别生成大合数$P$和$Q$,并将其发送给Trent
.
Step2.2:Trent
选定一个大整数$s$,计算$M=PQ$,并将$s$和$M$发送给Alice
和Bob
.
Step2.3(Alice): 若Alice
同意该条约,计算$A\equiv a^s\pmod M$,并将其发送给Trent
;若不同意该条约,则随意选择一个小于$M$的整数$A$发送给Trent
.
Step2.3(Bob): 若Bob
同意该条约,计算$B\equiv b^s\pmod M$,并将其发送给Trent
;若不同意该条约,则随意选择一个小于$M$的整数$B$发送给Trent
.
Step2.4:Trent
判定等式$AB\equiv N^s\pmod M$是否成立:若成立则说明双方均同意,签订成功,若不成立则说明有人不同意,签订失败。将判定结果发送给Alice
和Bob
即可.
5.应用场景
本协议可以解决很多敏感条约签订时一方同意一方拒绝的尴尬,也可以在很多提议场合使用,减少许多提议被拒绝的尴尬。另外,面对诸如社交软件中删好友后的重加问题,情侣吵架分手后的复合问题,表白问题等许多具有敏感性提议、敏感性条约的问题,本协议都可以很好的避免尴尬。
6.协议推广
将敏感条约签订协议中的两方条约签订推广至多方,具体的实现也很容易。假设一共有$k$个人,只需要将准备部分的Step1.2和Step1.3多次执行,每次将前$i$个人的信息乘积$N_i\equiv(\prod^i_{j=1}a_j)^e\pmod n$发给第$i+1$个人$(i=1,2,3\cdots,k)$,再由Trent
将最终的信息$N_k\equiv(\prod^k_{j=1}a_j)^e\pmod n$按照Step1.4解码求出$N\equiv N_k^d\pmod n$即可完成对准备部分对$N$的协定。签约部分也可以直接按照原协议进行很显然的推广至有$k$个人的情形。
值得一提的是,上文所述协议准备部分中的这种链式的累积乘法配合层层加密可以更好的保护每个人的隐私$(a_i)$,即想要获得某一方的$a_i$,就需要买通所有其他参与者才行。虽然足够安全,但这种方式会大大延长协议的执行时间。因此对于速度要求高的场景可以选用树形结构来使传输通信时间由$O(k)$缩短至$O(\log_2k)$,但这样一来,只需要买通树高那么多的参与者(约有$log_2k$个)即可获得某一方的$a_i$,从而使得秘密稍容易被获取。
由于协议是以 “与” 作为最终结果的逻辑,因此在双方协议中可以很好的避免同意者的尴尬,但在推广的多方协议中,大多数情况下最终结果都是“失败”,因此协议更多情况下可以避免少数拒绝者的尴尬。因此,推广的协议可以在道德绑架下的群体表态场景下选择拒绝而不被别人发现。这个场景很类似桌游《阿瓦隆》中反派莫德雷德
的行为。因此将扩展至多方的SCS协议
命名为“Leave Quietly as Mordred Protocol”或“LQM Protocol”,即“像莫德雷德一样悄悄离开”的协议。
使用德摩根公式,可以将协议的结果逻辑变为 “或” 逻辑,即: $$ \bigvee_{i=1}^ka_i=\neg{(\bigwedge_{i=1}^k\neg{a_i})} $$