<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Oct 9, 2015 at 5:35 PM, Nathaniel McCallum <span dir="ltr"><<a href="mailto:npmccallum@redhat.com" target="_blank">npmccallum@redhat.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Alice does an independent ECDH (using private key X) with n parties (in<br>
this case 3: A, B, C) such that she has:<br>
<br>
k1 = g^(XA)<br>
k2 = g^(XB)<br>
k3 = g^(XC)<br>
<br>
She has now discarded X.<br>
<br>
She would like to encrypt a secret S such that any combination of r (in<br>
this case 2) keys will allow decryption. Normally, she'd use Shamir's<br>
Secret Sharing. But she doesn't know of any way to apply SSS to<br>
elliptic curve points.<br>
<br>
Are there any methods commonly available?<br>
<br>
Can the simple "brute-force" method work without revealing any data<br>
about the keys? For example:<br>
<br>
c1 = S + g^(XA) + g^(XB)<br>
c2 = S + g^(XA) + g^(XC)<br>
c3 = S + g^(XB) + g^(XC)<br></blockquote><div><br></div><div>What I would do is encrypt the data under key S, then split that into SA, SB, SC and encrypt SA under a key agreed with XA, SB under a key agreed with XB, etc.</div><div><br></div><div>There are extensive games that you can play with the DH cryptopuzzle. In fact it is rather more open to them in many ways than RSA is. If P and Q are DH public keys, then so is P+Q. And you can calculate X^(P+Q) = X^P . X^Q</div><div><br></div><div>There are some IP claims but the one that gets in the way should expire in 2019. <br></div></div></div></div>