milionaire problem

A와 B가 서로 재산을 알리지 않고, 누가 더 재산이 많은지 판단 하려고 한다.

• initialize
  • Alice는 A={A1, A2, ...}
    Bob는 B={B1, B2,...}를 만든다.
  • Alice는 RSA를 위해 public key (n,e)와 Private key d를 만든다.
  • c1,...,c8을 만든다!
    
• Bob은 Alice에게 u를 보낸다.
  • Bob의 재산은 6이므로, c6을 고른다.
    $u=c6*r^emod$ n
• Alice는 Bob에게 v를 보낸다.
  • $v = u^d$ mod n
• v/r = B6 mod n.
  • B6으로부터, bob은 자기가 alice보다 부자인것을 알 수 있다.
  • 

socialist millionair problem

서로 재산을 밝히지 않고 같은 재산인지를 확인

Blind Signature : E-voting

기존 Digital signature

• RSA signature
  • signing
    • s = $H(m)^d$ mod n
  • verifying
    • $H(m)=s^e$ mod n

blind signature

• RSA blind signature
  • r = "blind factor"
  • signing
    • $s'=m'^d$ mod n
  • receiver
    • $m'=H(m)r^e$ mod n
    • $s = s'r^{-1}$ mod n = $H(m)^d$ mod n

anonymous E-voting

untraceable E-cash

A wants to pay B $1 without revealing its ID