# Tag Info

Write $x = (x_h,x_l)$ and $y = (y_h,y_l)$, where $x_h,y_h$ are the high-order parts. Alice sends $x_h$ to Bob ($n/2$ bits). Bob sends Alice two bits, indicating which of the following holds: $x_h > y_h$, $x_h = y_h$, $x_h < y_h$. The protocol then proceeds as follows: If $x_h > y_h$, then Alice sends Bob $x_l$ ($n/2$ bits). If $x_h < y_h$, then ...