Key Pair Agreement?

[Jeroen C. van Gelderen]

Hi,

Here is a scenario: Scott wants Alice to generate a key pair after 
which he will receive Alice's public key. At the same time, Scott wants 
to make sure that this key pair is newly generated (has not been used 
before).

I do not know what the proper terminology is to discuss this. Assuming 
there is none, I will call the solution Key Pair Agreement.

 From HAC we know that "Key Agreement is a key establishment technique 
in which a shared secret is derived by two (or more) parties ... such 
that no party can pre-determine the resulting value".

Let's see if we can come up with a informal definition of Key Pair 
Agreement:

Key Pair Agreement is a protocol in which two parties A and S interact 
such that
  - A generates a private key Kpriv and the corresponding public
    key Kpub
  - S can randomize the key generation process by providing a
    SEED1 such that A cannot pre-determine either Kpriv or Kpub
  - S cannot not learn anything about Kpriv
    (S cannot pre-determine either Kpriv or Kpub)
  - Given SEED1 and Kpub one can determine if the Key Pair
    generation process was randomized by SEED1.

It would seem that the DSA key structure facilitates this:

1. Scott sends SEED1 to Alice.
2. Alice picks a random number SEED2.
3. Alice sets SEED=SHA1(SEED1 || SEED2).
4. Alice generates a set of DSA parameters P, Q, G using the
    algorithm in Appendix 2, FIP-186-2.
5. Alice generates a key pair (x,y) using the parameters from (4).
6. Alice sends SEED2, counter, P, Q, G, y to Scott.
7. Scott generates P', Q', G' based on SEED=SHA1(SEED1 || SEED2),
    counter, and compares them to P, Q, G.

This is a very expensive key generation operation but it would
seem to work.

My questions are:
0) who has invented this before?
1) does it achieve what I think it achieves?
2) does anybody know of more efficient algorithms?


Cheers,
Jeroen


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com