# Shamir's secret sharing with passwords

I'm trying to design an extension to Shamir's Secret Sharing that would allow the participant to specify a password instead of remembering/storing a large integer or binary data. So far, I have two ideas, both based on some PBKDF:

• Run the password through a strong PBKDF to make $k_i$ then publish $(i, f(i)⊕ k_i)$ in a public, read-only location.
• Similarly, run the password through a strong PBKDF and then publish $(i, \text{AES}(\text{key}=k_i, \text{message}=f(i))$ in a public, read-only location

I like the simplicity of the first method, and rationally I haven't found anything wrong with using nothing more than XOR, but to my intuition it smells a bit fishy.

Am I divulging any information that would weaken the algorithm by using just XOR? What about with AES?

Well, the first thing comes to mind is "what if your 'read-only location' isn't quite as read-only as you had hoped; if someone could modify your $f(i) \oplus k_i$ share, could they modify the reconstructed shared secret in a controlled way.
In your first example, I believe they could. Let us assume that we are doing Shamir's Secret Sharing over the field $GF(2^k)$; let us further assume that the attacker has $N-1$ shares (where $N$ is the number of shares we need to reconstruct the secret). Which his $N-1$ shares, he can reconstruct that, when you add in your share $f(i)$, the reconstructed secret will be $s = c \times f(i) + d$, for some values $c, d$ he can compute (and $\times$ and $+$ are over $GF(2^k)$.
Now, $c \neq 0$, and so this doesn't give him any information about what the secret is (given that he doesn't know your share). However, if he wants to modify the secret, say, add $t$ to is, what he can do is modify your encoded share on the read-only location, replacing $(i, f(i) \oplus k_i)$ with $(i, f(i) \oplus k_i \oplus (t \times c^{-1}))$.
Then, when you reconstruct the secret, using his N-1 shares, and your modified share, you will decode your share as $F(i) + (t \times c^{-1})$ (remember, in $GF(2^k)$, addition and exclusive-or are the same operation); then, when you combine this decrypted share with his, you're come up with $c(F(i) + tc^{-1})+d = cF(i)+d + t = s+t$, resulting in the modified shared secret that the attacker selected.
• "he has not control over what the something else might be" as long as the pbkdf is non-malleable. $\:$ Otherwise, one also needs to worry about someone modifying its parameters. $\:$ – user991 Sep 19 '13 at 5:21