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

  1. Without even reading the article, I’m betting on Paul, now to read the article.

  2. 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.

  3. 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…

  4. 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)

  5. You obviously haven’t met many cryptographers.

  6. 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.

Comments are closed.