New Threshold PKC
KEY GEN: PK = (g1, g2 , a=g1x1g2x2, h= g1z)
SK: each decryption server holds a share of x1,x2,y1,y2,z (using polynomial secret sharing,
e.g. x1i = X1(i) where X1(0) =x1, deg (X1) = t )
ENC: Same as in single server case
DEC(SK,c): Let s be random and S a deg t polynomial s.t
(u1,u2, e, tag ) S(0)=s and each server I has S(i)=si
- Server i computes tagi’ = u1x1iu2x2i and sends the user
gQ(i) = (tag/tagi’)si hzi
- User combines shares to obtain
gQ(0) = (tag/tag’)shz and lets m = e/ (tag/tag’)shz