3 ms·

Possibly using this? https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing I think a lot of implement

Possibly using this? https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing I think a lot of implementations don't do anything clever and just have a fixed set of combinations they use each time, so the number of stored hashes is smaller.

KMag 6y ago
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 https://eprint.iacr.org/2020/852.pdf

KMag 6y ago

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 https://eprint.iacr.org/2020/852.pdf