Privacy-Preserving Record-Linkage (PPRL) techniques provide an error-tolerant way of linking data records from different sources based on quasi-identifiers while keeping these identifying attributes private. Many practical use cases require non-interactive PPRL, where the data holders merely prepare their data and outsource data linkage to a third party. While many such schemes have been proposed and some are even used in practice, almost all of them are either insecure or impractical for various reasons. This work presents a novel PPRL scheme which utilizes a technique called ‘Polynomial Sparsity Testing’. We provide extensive theoretical and experimental evidence for the high linkage quality and security of the scheme, which is on par with the state of the art: Using comparable parameter choices in terms of security, our scheme achieves a \(F_1\) -measure of \(94.3\%\) at a precision of \(100\%\) , while comparing a record pair takes less than 0.4 ms.