[Cryptography] Mathematically, how do proxy signatures work?

[Natanael]

2014-03-20 19:32 GMT+01:00 Bear <bear at sonic.net>:
>
> I hope that I have at least gotten "proxy signatures" correct as the
> proper name of what I want to ask about...  If not, then please correct
> me.

The Bitcoin folks calls it Stealth addresses (which then refers
specifically to the published public key + the method of generating
secondary keypairs).

> I have recently seen a feature in Bitcoin, called BIP38 -- but despite
> reading their wiki pages and linked materials I can't figure out
> exactly how it works.

BIP38 is mainly for encryption of keys. But yes, it does have one
feature that enables you to create "intermediate codes" you can send
to a physical cold storage wallet maker can imprint, for which your
password decrypts a private key they don't know. And the intermediate
code works like the stealth addresses mentioned above, you can
generate multiple possible outputs from it that all decodes to a
private key that you can decrypt.

> It acts like Alice's persistent public key is one side of a
> non-interactive Diffie-Hellman key exchange, except that I have
> no idea what "non-interactive" and "Diffie-Hellman key exchange"
> could possibly mean when used together.  So it seems magical.

This isn't the original Diffie Hellman. This is Elliptic Curve Diffie
Hellman (ECDH).

And the magical bit here is that EC allows for transformations of keys
that translates to the other key from a given pair. You can modify a
public key, tell the owner of that keypair how you modified it, and he
can do the same to his private key - and now he has a private key
which matches that new public key. To generate the shared secret that
modifies the keys, ECDH is used, since ECDH(Public key A, Private key
B) = ECDH(Public key B, Private key A), thus both parties only need to
know the public key of the other part, other than knowing their own
keypairs. What's used here to generate the new keys is called point
multiplication, based on the ECDH computed secret.

Here you go: https://github.com/bitcoin/bips/blob/master/bip-0038.mediawiki#Encryption_when_EC_multiply_mode_is_used

It's used pretty much the same way for Stealth addresses.

> I would like to understand the mathematics that allow these derived
> keys to be created and the mathematics that allow Alice to identify
> and decrypt messages encrypted using these derived keys.  I would
> like to know what Hard mathematical problem prevents Carol, Dave,
> etc, from being able to identify Bob's derived key as being part
> of the set derived from Alice's persistent key.  And if there are
> any special properties that the persistent key Alice publishes must
> have in order to work with this scheme, I would like to understand
> those too.

The identification is actually the hard part. If you don't know which
keys are derived from your keypair, you have to try performing an ECDH
key exchange plus EC multiply keypair generation for every single
public key. Not until then do you know which of the keys something
have been sent to that you have the private key for. That's why
there's talk about using various "filters" and prefixes and tags and
other such things to reduce load and still maintain privacy.

> I do not know whether Alice can recover the nonce Bob used when
> decrypting the message, but that would also be an interesting
> thing to know for security purposes. Should the nonce be treated
> as a shared secret between Bob and Alice?  If so then what are the
> downsides of later using the nonce as a shared secret for other
> protocol steps?

The value that is computed with ECDH should be kept secret, because
otherwise anybody who knows the Stealth address and that value can
compute the same secret recipient address, and thus it isn't secret
anymore.