|
||
Title: HARD: Message Reconstruction Post by Icarus on Oct 26th, 2002, 10:19am I've searched several times for a thread on this and can't find one, so here is my approach: First, Alice treats her message as one long integer M1. Second, Alice chooses n-1 additional random integers Mi of roughly the same magnitude as M1. Third, for each recipient Alice chooses a linear equation in the Mi. She chooses these equations so that any set of n equations are linearly independent (this is not hard to do). Fourth, Alice sends one of the equations to each recipient. Any set of n-1 or fewer recipients, if they pool their equations together, do not have enough information to solve them completely and determine M1. In fact, from their information, M1 could still be any integer. Only when n recipients combine their equations can they solve the them completely, find M1, and figure out what Alice said. |
||
Title: Re: HARD: Message Reconstruction Post by mk on Jan 8th, 2010, 11:35pm The first thing that came to my mind is a storage system employing RAID with some parity mechanism. For example, let's say Alice is splits her bit message up into 4 messages and 1 parity message (using XOR). Say R=5, n=4, n-1=3: Original message=0010110010010101 This gives us 4 data messages and 1 parity message: 0010 1100 1001 0101 0010 (parity msg) Take the easy case where she sends the 4 non-parity messages in order to n1, n2, n3, n4. The message is easy to reconstruct. Now she sends the first 3 messages and the parity message to n1-n4: 0010 1100 1001 xxxx (unset) 0010 (parity msg) It's easy to get message 4 and thus the whole original message by finding the bits that work for the XOR parity value. For a proof see http://www.pcguide.com/ref/hdd/perf/raid/concepts/genParity-c.html |
||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |