Partial Fraction Techniques for Cryptography

Partial fraction decomposition is a fundamental technique in mathematics where products of rational functions can be expressed as sums of fractions. While rational functions have been used in various cryptographic constructions, their rich algebraic structure has not been systematically explored as a direct foundation for building cryptographic primitives. In this work, we describe and exploit two key properties of partial fraction decomposition:
(1) the decomposition property itself, which enables efficient set membership testing, and (2) a novel linear independence property arising from the non-singularity of Cauchy matrices, which enables threshold cryptography.

We present two main applications. First, we construct a key-value commitment scheme where a dictionary is represented as a linear combination of partial fractions $\sum_i \frac{v_i}{X + k_i}$. Our scheme achieves constant-size commitments (a single group element) and proofs, supports homomorphic updates enabling stateless operation, and provides efficient membership and non-membership proofs through simple pairing equations. We also introduce \emph{Credential-based Key-Value Commitments}, where keys are registered via Boneh-Boyen signatures, enabling applications in permissioned settings.

Second, we construct a dynamic threshold encryption scheme leveraging the linear independence of partial fraction products. For an authorized set $S$ and threshold $t$, parties with secret keys corresponding to partial fractions $\frac{1}{X+i}$ can produce decryption shares that, together with publicly derivable shares, form a full-rank linear system structured as a special Cauchy matrix. Our scheme achieves compact ciphertexts, supports public preprocessing of public keys to a succinct encryption key, enables dynamic threshold selection at encryption time, and provides robustness through share verification without random oracles. The combining algorithm exploits efficient Cauchy matrix inversion via barycentric interpolation.

We prove security of our constructions in the standard model under new $q$-type assumptions and establish their generic hardness in the generic bilinear group model. Our work demonstrates that working directly with the algebraic structure of rational fractions, rather than converting to polynomial representations, yields elegant and efficient cryptographic constructions with concrete advantages over prior work.