0
$\begingroup$

I have two devices, and each has a private key xPriv-i. Each device computes the corresponding EC public key xPub-i, shares it, and the linear combination of the keys is the "real" public key xPub. As a simplification, please assume this is all done securely and correctly.

I use ECIES to encrypt an archival file: I compute a shared secret between the ephemeral key e and xPub == e * xPub. Then I use the hash of that as the input to a symmetric encryption algo. The file's public key ePub is placed in the file. Again, this mechanism works today and is done correctly.

My friend Bob also has two devices. His combined key is zPub

I would like to give my friend Bob access to my file, without decrypting it or reducing the security beyond trust in Bob.

The trivial solution is for each device to compute xPriv-i and encrypt it for Bob's zPub. These can be safely sent to Bob and he can archive them, without decrypting them.

What I need, eventually, is to compute a new value that ePub-prime ... such that if Bob computes ePub-prime * zPriv ... it will equal to ePub * xPriv. In other words... i need a new ePubBob

So, instead I encrypt and send each ePub * xPriv-i individually to each of Bob's devices. Each device can then compute ePub * xPriv-i * modular-multiplicative-inverse(zPriv-i). Then the fragments can be safely linearly combined into ePub * xPriv/zPriv by any device ... and stuck in the original file as a share-key.

I would like the linear combination to work with M of N devices, so I use Lagrange interpolation similar to Shamir's secret sharing algorithm to perform the combinations. However, there's a problem, the "mminverse(zPriv-i) fragments" can't be recombined....

If I simply recombine them, I wind up with ePub * xPriv * mminverse(zPriv-i1) * mminverse(zPriv-i2) instead of ePub * xPriv * mminverse(zPriv). That's because the mminverse's can't be linearly recombined ... they are essentially "in the denominator"... and the polynomial won't work.

Either:

  1. The devices need to securely and in some distributed manner compute the EC private key's modular inverse... and then appropriately fragment it along the same polynomial. If so, how can this be done?
  2. There's some other thing I'm missing... what is it?

(Please ask me if there's more clarifying information you need)

Actually it looks like this answer may solve my problem:

Shamir's Secret Sharing of modular inverse

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.