Paper 2026/2229

Local Rewriting under Assumed Erasure

Abstract

We study local rewriting after an assumed erasure step in an ideal oblivious-transfer protocol. Bob transforms his retained record while Alice's actual record remains fixed. Exact rewriting between shared-source and independent-source records is possible in both directions precisely when the retained records of the shared source are independent. For balanced deterministic maps retaining $k$ and $\ell$ bits from an $n$-bit source, the optimal error over the maps is $\max\{0,1-2^{n-k-\ell}\}$. For fixed full-row-rank linear maps, it is $1-2^{-d}$, where $d$ is their row-space intersection dimension. A nonlinear example shows that an optimal approximate rewrite may change Bob's marginal distribution.