A simple example of reduction procedure

This page presents a simple example of reduction procedure similar (in the spirit) to the vandermonde reduction procedure used by PPETP. We will simplify the exposition by working with real numbers rather than with bytes.

We will consider the following scenario

• Alice is connected to five upper peers (Bob, Chiarlie, David, Eve and Fonzie) and receives data from them.
• The data that Alice is interested in is a triplet of real numbers c₀, c₁, c₂.
• Every node can transmit at most one real number
• The five upper peers of Alice cannot coordinate each other
• The data sent from an upper peer to Alice can get lost (e.g. because of network congestion)

Since each node can transmit at most one real number, the most obvious solution where a node (say, Bob) sends all the three values to Alice is not admissible.

A possible solution could be that each upper peer of Alice chooses one of the three values (c₀, c₁, c₂) and sends it to Alice. Unfortunately, this approach has the drawback that it is not granted that a value will be chosen by at least one peer. For example, if Bob, Charlie and David chose c₀, while Eve and Fonzie choose c₁, Alice will never be able to recover the whole triplet.

An alternative, more robust solution is the following:

1. All the upper peers of Alice create the polynomial of degree two P(x) = c₂ x² + c₁ x¹ + c₀ x⁰ whose coefficients are the entries of the triplet to be transmitted.
2. Every upper peer chooses a random real number. Let X_k, k=1, 2, ..., 5 denote, rispectively, the number chosen by the k-th upper peer of Alice. The chosen X_k is sent to Alice at handshaking time. Note that the probability that two peers choose the same value is negligible.
3. Every peer evaluates the polynomial P in the chosen value. In other words, the k-th peer computes Y_k = P(X_k)
4. Every peer sends the computed Y_k to Alice.

How can Alice recover the original triplet? Alice chooses three of the received values (let be them Y₁, Y₂ and Y₃ for concreteness). Alice knows that polynomial P(x) is a degree-two polynomial and knows that its graph goes through the three points (X₁, Y₁), (X₂, Y₂) and (X₃, Y₃). Since for every triplet of points there is one and only one parable that goes trhough the chosen triplet, from the knowledge of the above three points, Alice can recover the polynomial P(x) and, therefore, its coefficients.

Note that this approach has several interesting advantages

• Alice can recover the data as soon as she receives three values. This implies that even if two out of five data are lost, Alice can still recover the data.
• Since there are many real numbers, the probability that two peers choose the same number is negligible and this allows this scheme to work even without coordination between the peers
• Suppose that one of the peers (say, Eve) is malitious and tries to send to Alice a bogus value B₄ different from the correct one Y₄ (in other words, Eve tries a "stream poisoning" attack). Alice can become aware of the attack by using the following procedure
  1. Alice recovers the c_i by using the data received, say, from Bob, Charlie and David
  2. Alice verifies that the recovered polynomial P(x) goes through the points associated with Eve and Fonzies.
  3. If the check is positive, the data are correct and Alice can use them
  4. If one point misses the curve, it means that the point is not correct and maybe the corresponding peer tried to poison us
  5. If both points miss the curve, it probably means that at least one of the three points that Alice used to recover P(x) is wrong. In order to find the bad data, Alice can try to recover P(x) using a different set of data