ROUGH DRAFT

Verifiably Signed Secret Sharing A Tool for Identity Escrow

Chris Laas

June 69, 2000

1 Related Work

Verifiable Signature Sharing (VΣS)

Secure distributed computation Anonymous cash?

2 Model and Definitions

CA, dealer, proxies, reconstructor.

Issuing protocol, sharing protocol, reconstructing protocol. All communications assumed private and unmodifiable in transit.

t-Resilience. Secret sharing.

3 A Simple Identity Escrow Scheme

Public parameters:

• Large primes p, q such that q|p − 1

• A generator g with order q in ℤ_{p}^{∗}

The CA has a secret key x ∈ ℤ_{q}^{∗}; its public key is y = g^{x} mod p. Issuing protocol: a message m may specify attributes of the identity, or

may be set to 1 (it may not be zero). The CA signs m with an ElGamal (-like? XXX) signature by choosing a unique value k ∈_{R} ℤ_{q}^{∗}, and calculating

r = g^{k} mod p  (1)
s = k^{−1}(m + xr) mod q  (2)

The signature pair (r, s) (along with m if necessary) is sent to D.

Sharing protocol. Summary: the message m and public part of the signature pair r are split into multiplicative shares and distributed. The proxies cooperate to calculate ρ = r^{e_{1}e_{2}} mod p for randomly chosen e_{1} and e_{2}; D then proves knowledge of the discrete logarithm of g^{m}y^{r} with respect to the base r by answering the challenge of ρ.

1. D chooses a random value k_{1} ∈_{R} ℤ_{q}^{∗}, and calculates r_{1} = g^{k_{1}} mod p and r_{2} = r/r_{1} mod p. D sends r_{1} to P_{1} and sends r_{2} to P_{2}.

2. In the case in which m is not identically 1, D chooses a random value j_{1} ∈_{R} ℤ_{q}^{∗}, and calculates m_{1} = g^{j_{1}} mod p and m_{2} = m/m_{1} mod p. D sends m_{1} to P_{1} and sends m_{2} to P_{2}. (If m is identically 1, m_{1} = m_{2} = m = 1.)

3. P_{1} chooses a random value e_{1} ∈_{R} ℤ_{q}^{∗}, calculates h = g^{m_{1}e_{1}} mod p, z = y^{r_{1}e_{1}} mod p, and u_{1} = r_{1}^{e_{1}} mod p, and sends h, z, and u_{1} to P_{2}.

4. P_{2} chooses a random value e_{2} ∈_{R} ℤ_{q}^{∗}, calculates u_{2} = r_{2}^{e_{2}} mod p, and sends u_{2} to P_{1}.

5. P_{1} calculates v_{2} = u_{2}^{e_{1}} mod p and sends v_{2} to P_{2}.

6. P_{2} calculates ρ = u_{1}^{e_{2}}v_{2} mod p and sends ρ to D.

7. D calculates γ = ρ^{s} mod p and sends γ to P_{2}.

8. P_{2} accepts if and only if γ = (h^{m_{1}}z^{r_{2}})^{e_{2}} ( mod p).

Proposition 1: If D can fool P_{2} into accepting despite not having been issued an (r, s) pair by the CA, then D can forge an ElGamal signature on the message m, or can break the zero-knowledge proof of knowledge of a discrete logarithm used here.

Proposition 2: If D and P_{2} follow the protocol, P_{1} learns no value correlated with r or m from its view of the protocol. (Information-theoretic.)

Speculation 3: If D and P_{1} follow the protocol, P_{2} learns no value correlated with r or m from its view of the protocol. (Not sure. Heuristic.)

Reconstruction protocol: P_{1} and P_{2} send their values r_{1}, m_{1}, r_{2}, and m_{2} to R. R calculates r = r_{1}r_{2} and m = m_{1}m_{2}.

Chris Laas  Title Here  3

References

Verifiable Signature Sharing (EUROCRYPT ’95)