Paul v. Scientific American
[Editor's note: Sent to the editors in question. By some corollary to Skitt's Law, naturally, I managed to screw up the second set of page references in the copy I sent them. Sigh.]
In the June 2007 Scientific American article “Breaking Network Logjams”, the sidebar on page 83 claims “Still, when neither a nor b is 0, both receivers can retrieve the proper messages successfully.” Alas, selecting codes is not quite that easy: a and b must be relatively prime to 2m (where m is the number of bits per message). Only then is
a * X + b * Y = E (modulo 2m)
guaranteed to have a unique solution when all variables except either X or Y are known. a and b needing to be nonzero is merely a special case of this requirement.
Luckily, since 2m will never have any prime factors besides 2, choosing odd numbers for a and b guarantees they will be relatively prime to 2m. Although this means that a purely random choice for a and b will only work 25% of the time, it is trivial to restrict the random choice to only odd numbers to begin with.
The example on pages 82 and 83 in fact demonstrates what happens when a and b are chosen poorly. In the example, a = 3 is a safe choice, but b = 20 is poor, since 20 and 32 have a common factor (4). In solving
3 * 21 + 20 * Y = 23 (modulo 32)
there are four possible values for Y: 6, 14, 22, and 30. There is no way to tell which possible value for Y corresponds to Ben’s message; as a result, Carl is unable to receive Ben’s message reliably.
6 Responses
Without even reading the article, I’m betting on Paul, now to read the article.
Also, later on the article suggests using a scheme related to network coding to split a file into pieces, which can be combined in different ways to recover the original file. It’s a neat idea. I’m pretty sure Adi Shamir also thought so when he proposed the scheme in 1979.
Didn’t the editors run this article past someone who’s taken an undergraduate-level cryptography course? Sheesh.
the best picture of Adi Shamir available was one of him appearing to dunk a fork full of peanut butter into a glass of cola?
…
wow…
oh, and while simultaneously licking his lips and appearing to be thinking “mmmm peanut butter sure is be scrum-diddily-umptious… glad mom packed me JIF…”
…
i’m just saying… for a hella smart man, you’d think there would be something a bit more… intelligent?
(and sorry bout the double post thing)
You obviously haven’t met many cryptographers.
And OK, upon further consideration, the network-coding-on-files thing isn’t quite what secret sharing does, though it sounds pretty similar, especially given the vague mention of it in the article. But still.