上课笔记[0]

关于系统可靠性

  • 错误–>停止—–>解决方法:冗余

  • 错误–>随机————>拜占庭将军问题  大于三分之一时候可行——>信息爆炸:OM(n,m)=O(n^m+1)

密码员进餐问题 Dining cryptographers

  • A,B,C希望匿名支付账单:可能一个密码员付了帐,也可能是由NSA付账。
  • A,B,C希望有匿名支付账单的权利(没人知道是谁付了帐),但是要知道NSA是否付了帐单。

抛币协议:

  1. 每个人抛一次硬币(随机获得数字0或1),并且把结果告诉右手边的人
  2. 每个人把得到的数字与自己的数字比较,假如这个人没买单,就如实说比较结果(相同/不同),假如这个人买了单,就说出相反的结果(相同说成不同,不同说成相同)。
  3. 假如有奇数个相同,没人买单(NSA买单),假如有偶数个相同,则有人买单。

(3种人的情况假如没人买单,只有2种可能:3个相同||2个不同+1个相同)

实现匿名通信:(1————>买单)(0————>没买单)

推广到n个用户通信:

  • 每个用户自己选择a1..M..an,(an=0或1),信息发送者选择自己想发的信息M(M=0或1)。

  • 每个人把信息发送给右边的人
  • 每个人对自己手中的2个信息进行XOR运算,信息发送者可以不用进行运算,得到(b1…M…bn)
  • 每个人发出自己的结果,而信息发送者发出M,
  • 则M=b1 XOR b2 XOR ….XOR M XOR…..XOR bn

 


匿名系统

TOR  洋葱路由(Onion Routing)

 

crowds system(概率转发)

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注