Timeline for Applications of the Chinese remainder theorem
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 23, 2020 at 23:07 | comment | added | David E Speyer | @MarcvanLeeuwen I realize that this is a 7 year old comment, but if you want to do this using linear indep, you need to find a $k+1$-dimensional vector space and a collection of $N$ vectors where every $k+1$ of them form a basis. There are probably other ways to do this, but the Lagrange interpolation method is the easiest I know. | |
| Oct 23, 2020 at 21:45 | comment | added | sdcvvc | @MarcvanLeeuwen The point of secret sharing is that with less than $k+1$ people, absolutely no information about the code can be extracted. If I understand correctly your example, it does not have this property. (For example, Shamir's secret sharing can be used to share a word in dictionary, while the linear algebra method would likely be breakable.) | |
| Dec 10, 2013 at 18:18 | comment | added | Marek | Agree with @Marc. Many of the other answers are cool but this is one is hardly more spectacular than any protocol using mere linear independence. No idea why people upvote it so much. | |
| Oct 7, 2013 at 12:33 | comment | added | Marc van Leeuwen | First, I think this example shows that the Chinese Remainder Theorem for polynomials is not the same as the one for integers (which cannot be used in the above manner). But more importantly, this form of secret sharing does not depend on any CRT. The idea is just to have a point in a $d=k+1$-dimensional vector space as code, and a bunch of linear equations that this point satisfies as secrets, such that any $d$-subset of them forms a Cramer system that can be uniquely solved, while fewer than $d$ of them of course do not allow this. | |
| May 16, 2013 at 2:33 | comment | added | David E Speyer | Lagrange interpolation is a special case of CRT. See artofproblemsolving.com/Forum/blog.php?b=10595 | |
| May 15, 2013 at 17:13 | comment | added | Greg Martin | I agree that any $k+1$ people can compute $f$, using, say, Lagarange interpolation ... but, using the Chinese remainder theorem? I don't see $k+1$ different moduli here - only (mod $p$). | |
| Dec 2, 2010 at 13:49 | comment | added | Cam McLeman | FYI this is called Shamir secret-sharing. Am I right in thinking that the reason we work over $\mathbb{Z}/p$ is that one can sensibly talk about random polynomials (with the implicitly-chosen uniform distribution on each coefficient), and not have to specify a more-or-less arbitrary distribution if we, say, took real coefficients? | |
| Aug 18, 2010 at 3:38 | comment | added | senti_today | Sorry, I misread the second sentence. | |
| Aug 17, 2010 at 21:38 | comment | added | David E Speyer | Because N is larger than k+1. | |
| Aug 17, 2010 at 21:23 | comment | added | senti_today | This may be a dumb comment, but... Why not do the following instead? Choose a large prime $p$ and elements $a_1,a_2,...,a_{k+1}$ in $\mathbb{Z}/p$. Tell person $j$ the value of $a_j$, for each $j$. Set up the missiles to only launch when $\sum_{j=1}^{k+1}a_j$ is input. I am not sure if there is an essential difference between this and your suggestion. | |
| Dec 29, 2009 at 16:52 | history | made wiki | Post Made Community Wiki by Anton Geraschenko | ||
| Dec 29, 2009 at 11:32 | history | answered | David E Speyer | CC BY-SA 2.5 |