News for hackers. Stuff that matters.
Re:Substack's UI and 1Password temporarily cost me $2k by KMag on Tuesday March 23, 2021 @06:55AM (#26553476)
I thought about something similar to Shamir's Secret Sharing, polynomial fitting over a finite field, but in this case, information theory is working against you.

With Shamir's Secret Sharing, you start out with your secret expressed as a finite field element, and pick N-1 polynomial coefficients uniformly randomly from your finite field, and give M different participants values of the polynomial evaluated at different points. Information theory shows that having at most N-1 points on the polynomial still leaks no information about F(0). It's as secure as a one-time pad, and in the degenerate case of N=2 over a Galois field, is in fact a XOR-based one-time-pad. The amount of entropy added at generation time is greater than the amount of entropy in the secret.

In this partial password case, you'd want the "shared secret" to be a single value, and construct a polynomial such that, say 4 field elements, would always be sufficient to recover the same "secret". You're running the algorithm the wrong way, and unless you're forcing a password on the person, those letters are actually low-entropy instead of maximal entropy field points as in Shamir Secret Sharing.

I really don't see a way to use polynomial interpolation in this way without leaking entropy. I thought about using something similar to Schnorr threshold signatures[0] to solve the information leakage, but then you end up storing one elliptic curve public key per password letter, and the private key for each public key is a single letter, so trivial to bruit-force.

[0] https://eprint.iacr.org/2020/852.pdf

There are no comments on this comment yet.