Probabilistic CPISync

Figure 3.8: Probabilistic scheme

An extension of CPISync when the upper bound on the number of differences between the reconciling hosts is not know is performed in the following manner.

• 1. Hosts $A$ and $B$ guess an upper bound $\overline{m}$ and perform the deterministic CPISync described in the previous section, resulting in host $B$ computing a rational function $F(X) = \frac{P(X)}{Q(X)}$ as described in 3.2 on page  . If the function $F(X)$ corresponds to the differences between the two host sets, that is if

  $$F(X) = \frac{\chi_A(X)}{\chi_B(X)}$$ (3.1)

  
  
  then the zeros of $F(X)$ will determine precisely the mutual difference between the two sets. In order to check this, host $A$ (PDA) chooses $k$ random sample points $r_i$ and sends their evaluations $\chi_A(r_i)$ to host $B$ (PC), which uses these evaluations to compute evaluations

  $$G(r_i) = \frac{\chi_A(r_i)}{\chi_B(r_i)}$$ (3.2)

  
  
  by comparing the evaluations $F(r_i)$ and $G(r_i)$, the PC (host B) can assess whether F(X) is indeed the correct interpolation for the rational function $\frac{\chi_A(X)}{\chi_B(X)}$.
• 2. In case each $G(r_i)$ does not correspond to $F(r_i)$ for each $r_i$ we repeat step $1$ for a larger value of $\overline{m}$

In general, the two hosts keep guessing $\overline{m}$ until the resulting polynomials agree in all $k$ sample points. A precise probabilistic analysis in [14] shows that such an agreement corresponds to a probability of error

$$\epsilon = m {\biggl(\frac{\vert S_A\vert + \vert S_B\vert - 1}{s^b}\biggr)}^k$$ (3.3)

where $m$ is the number of differences between the two reconciling hosts $A$ and $B$. Using a trivial upper bound $m \leq \vert S_A\vert + \vert S_B\vert$ we see that an arrangement of

$$k = \biggl\lceil log_{\rho}\biggl(\frac{\epsilon}{\vert S_A\vert + \vert S_B\vert}\biggr)\biggr\rceil$$ (3.4)

samples (where $\rho = \frac{\vert S_A\vert + \vert S_B\vert -1}{2^b}$) to get a probability of error $\epsilon$ for the whole protocol. Thus, for example reconciling host sets of $10^6$, $64$-bit integers with error probability $\epsilon = 10^{-20}$ would require agreement of $k = 2$ random samples. This verification protocol requires the transmission of at most $m + k$ samples and one random number seed (for generating random sample points) to reconcile two sets; the value $k$ is determined by the desired probability of error $\epsilon$ using the above expression for $k$. The $m$ sample points are used to interpolate a rational function, corresponding to a guess of the differences between the two machines, and the latter $k$ points are used to verify the correctness of this guess. If the verification succeeds, the synchronization is complete. On the other hand, if verification fails, then the PC collects all the sample points seen so far into a guess of the differences between the two machines at the same time requesting $k$ additional random evaluations from the PDA to confirm its new guess. This procedure is iterated until the verification succeeds, at which point the synchronization is complete. Since $m$ evaluations will necessarily be enough to completely determine up to $m$ differences, verifications will necessarily succeed after at most $m + k$ transmissions. Figure 3.8 shows a flowchart of probabilistic CPISync. Thus, though the verification protocol will require more rounds of communication for synchronization that the Deterministic CPISync, it will not require transmission of significantly more bits of information. We see in the next section that the computational overhead of this protocol is also not large.