Author |
Topic: HARD: Message Reconstruction (Read 2963 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
HARD: Message Reconstruction
« on: Oct 26th, 2002, 10:19am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
mk
Newbie
Posts: 1
|
|
Re: HARD: Message Reconstruction
« Reply #1 on: Jan 8th, 2010, 11:35pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print