Scalable Fuzzy Private Information Retrieval:Homomorphic Record Linkage in the Hamming Metric

Recent Fully Homomorphic Encryption (FHE) advances have enabled practical Private Information Retrieval (PIR); however, these polynomial-based architectures strictly require bit-level exact matching. This renders them inapplicable for real-world ``noisy'' datasets like typo-prone logs or biometrics. In this paper, we propose Fuzzy A-PIR, a novel single-server architecture that enables scalable privacy-preserving fuzzy search directly in the Hamming metric. Rather than relying on computationally heavy FHE multiplication, Fuzzy A-PIR utilizes standard additive homomorphism over elliptic curves coupled with a deterministic Base-3 packing technique. A profound architectural advantage of our construction is the application of the Code-Offset mechanism strictly on the Client side. By transmitting queries as Interleaved Reed-Solomon codewords masked by ephemeral noise, the Server evaluates homomorphic point additions completely oblivious to the underlying algebraic structure. The Client subsequently resolves the short-interval ECDLP to unmask the payload, where the algebraic interleaving naturally absorbs and corrects dense burst errors. Furthermore, by employing Locality-Sensitive Hashing (LSH) and a matrix-based retrieval structure, our protocol achieves an optimal sublinear communication complexity of $\mathcal{O}(\sqrt{N})$ while strictly mitigating metadata intent leakage. Ultimately, Fuzzy A-PIR provides a robust, constant-time solution for privacy-preserving record linkage.