[Cryptography] Mixing public key crypto systems?

[Jeff Burdges]

On Sun, 2016-03-27 at 17:25 -0700, Henry Baker wrote:
> Inspired by the 'monoculture' thread, I'm curious as to whether it is possible to mix different public key crypto systems.
> 
> For example, Alice might use some version of RSA, while Bob might use some version of El Gamal.
> 
> Alice posts her public key in her chosen PK system; Bob posts his public key in his chosen PK system.  Each has to use the type of encryption chosen by the addressee of the message.
> 
> Does everything still work?

No.  

First, Alice wants her security properties for the messages she sends,
not just the message she receives.  

Second, we must assume that Bob's messages to Alice leak information
about Alice's messages to Bob, so using both PK systems like this gives
you the weaker security of the two.

Instead you should use both systems all the time.  For that, you need a
hash construct like HC(DH_1,DH_2) = H( H(DH_1), H(DH_2) ) and a proof of
security that:

Assume H has reasonable properties for a cryptographic hash function.
If we replace DH_i with an adversary controlled value, representing a
very bad break, but the adversary does not learn DH_j with j=3-i, then
the adversary gains no knowledge about HC(DH_1,DH_2).  

In addition, if the adversary learns HC(DH_1,DH_2) too, then they should
learn nothing about DH_j, but that's simply pre-image resistance.

There should be general proofs this effect in the literature for various
HC constructions for when the DH_i represent either both Diffie-Hellman
key exchanges and for public key encryption operations, but..

I do not know where to find such proofs right now.  I'd love it if
anyone can fill that in, but otherwise I'll go hunting eventually. 

I've describe an HC as similar to double keyed HMAC because HMAC
provides some protection against malicious values like this, but some
current hash functions like SHA3 often make HMACs redundant, so simply
HC(DH_1,DH_2) = SHA3(DH_1 || DH_2) probably works.  A priori, if you use
SHA1 then HC should be a full HMAC construction, meaning like five
invocations of SHA1, but maybe someone can correct me.

Jeff

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160328/9ce10fb2/attachment.sig>