💻 computer science

Information-Theoretic Distributed Point Functions with Shorter Keys

This paper introduces a novel, perfectly secure 1-private Information-Theoretic Distributed Point Function (ITDPF) over the group $\mathbb{Z}_p$ that achieves asymptotically shorter secret keys than existing schemes by leveraging a share conversion based on recent private information retrieval techniques.

Original authors: Hang Deng, Liang Feng Zhang

Published 2026-04-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Hang Deng, Liang Feng Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a secret treasure map that points to exactly one specific location on a giant grid (let's say a city with millions of blocks). You want to give copies of this map to a group of friends so that, together, they can figure out where the treasure is. However, you have a strict rule: no small group of friends (say, any two or fewer) should be able to figure out the location just by comparing their copies. They need to combine all their pieces to solve the puzzle.

This is the core problem of a Distributed Point Function (DPF). It's a cryptographic tool that splits a "point function" (a function that is zero everywhere except at one special point) into many "shares" (keys).

The Old Way vs. The New Way

The Old Way (The Heavy Backpacks):
Previous methods for doing this securely (specifically "Information-Theoretic" security, which means they are safe even against supercomputers with infinite power) required the friends to carry very heavy backpacks. These backpacks contained the "keys" needed to solve the puzzle. As the city (the data) got bigger, these backpacks grew exponentially larger, making the system slow and impractical.

The New Way (The Lightweight Satchels):
This paper introduces a new method that creates much lighter satchels. The authors, Hang Deng and Liang Feng Zhang, have built a system where the keys are significantly shorter (smaller) than any previous perfectly secure method, especially as the data gets huge.

How They Did It: The "Secret Recipe"

The authors didn't invent a new magic spell from scratch; they used a clever recipe (called the LKZ framework) that turns one type of secret-sharing tool into another.

The Ingredient (PIR): The secret sauce they used is a state-of-the-art tool called Private Information Retrieval (PIR). Think of PIR as a way to ask a librarian for a specific book without the librarian knowing which book you asked for. A recent breakthrough by Ghasemi, Kopparty, and Sudan made this "asking" process incredibly efficient.
The Conversion (The Magic Trick): The authors figured out how to translate the "asking" mechanism of this new PIR into the "key-splitting" mechanism needed for their DPF.
- Analogy: Imagine the old PIR was like asking a librarian for a book using a complex, 10-page form. The new PIR uses a tiny, 2-word code. The authors found a way to turn that tiny 2-word code into the secret keys for the treasure map, ensuring the keys remain tiny.

The Result: A Perfectly Secure, Tiny Key

The paper claims to have built a system that is:

Perfectly Secure: Even if a hacker has infinite computing power, they cannot learn anything about the secret location if they steal a few keys.
Efficient: The "keys" (the data each server holds) are asymptotically shorter. In plain English: As the amount of data grows, the size of the keys grows much slower than before.
Flexible: It works for any prime number size (a specific type of mathematical group), which covers a wide range of practical needs.

The Catch (Limitations)

The authors are honest about the trade-offs:

The "One-Server" Rule: Currently, this specific construction only guarantees that one server cannot learn the secret if they collude with others. If you want to protect against two or three servers colluding, the system would need to explode in size (requiring exponentially more servers), which is currently too inefficient to be useful.
Specific Math: It works best with specific types of mathematical groups (prime-order groups), though the authors suggest it could be extended to more complex groups in the future.

Summary

In short, this paper is like an engineer who found a way to shrink a massive, cumbersome security vault down to a pocket-sized safe without losing any of its strength. They did this by borrowing a highly efficient "lock-picking" technique from a different field (Private Information Retrieval) and adapting it to split secrets among servers. The result is a system that is mathematically unbreakable and much faster to use than anything that came before it.

1. Problem Statement

The paper addresses the construction of Information-Theoretic Distributed Point Functions (ITDPFs).

Definition: A $(t, n)$ -ITDPF allows a point function $f_{\alpha, \beta}(x)$ (which outputs $\beta$ at input $\alpha$ and $0$ elsewhere) to be split into $n$ secret keys. Any subset of $\le t$ servers learns absolutely nothing about the function (perfect security), while the sum of all $n$ servers' evaluations reconstructs the function value.
The Challenge: The primary metric for efficiency in DPFs is key size (the maximum size of the secret keys). Existing perfectly secure ITDPFs for the output group $G = \mathbb{Z}_p$ $G = Z_{p}$ (where $p$ $p$ is any prime) suffer from suboptimal key sizes.
- Previous works (e.g., Boyle et al., Li et al.) achieved key sizes with exponents involving functions like $\nu_r(N) = (\log N)^{1/r}(\log \log N)^{1-1/r}$ .
- The goal is to reduce the asymptotic key size while maintaining perfect security and supporting arbitrary prime $p$ .

2. Methodology

The authors propose a novel construction based on the LKZ Framework (Li, Kopparty, and Zhang) combined with state-of-the-art Private Information Retrieval (PIR) techniques.

A. The LKZ Framework

The framework transforms a Secret Sharing Scheme (SSS) into an ITDPF via Share Conversion.

Share Conversion: It requires converting shares from a $(t, n)$ -threshold SSS ( $L_1$ ) into shares of an additive SSS ( $L_2$ ) such that the sum of converted shares reveals a specific relationship to the original secret.
Bilinear Representation: The point function is represented as a bilinear function of the converted shares.
Key Insight: The key size of the resulting ITDPF is proportional to the communication complexity of the underlying PIR scheme used to generate the share conversion.

B. Leveraging GKS Derivative-Based PIR

The core technical innovation is utilizing the recent 1-private $n_r$ -server PIR scheme by Ghasemi, Kopparty, and Sudan (GKS, STOC 2025).

GKS Mechanism: Unlike previous PIR schemes that only query evaluations of a polynomial, GKS queries both evaluations and Hasse derivatives of the polynomial.
Mathematical Foundation:
- Uses $S$ -matching families and $S$ -decoding polynomials over finite fields.
- Introduces the 0-interpolation property with multiplicity. By asking for derivatives, the scheme can interpolate the constant term of a sparse polynomial using fewer servers or smaller parameters.
- Specifically, GKS achieves a communication complexity of $2^{O(\nu_{r+1}(N))}$ for $n_r$ servers, where $n_r$ depends on the number of prime factors of the modulus.

C. The Proposed Construction Steps

Setup:
- Select a modulus $M = m \cdot p$ (product of distinct primes).
- Construct an $S_M$ -matching family and an $S_M$ -decoding polynomial with multiplicity 2 (enabled by the derivative queries).
Share Conversion ($Conv$):
- The server holds a share $c_\ell$ derived from a random vector $w$ and the target index $\alpha$ .
- Given an input $x$ , the server computes a "core polynomial" $D_x(Z)$ restricted to a multiplicative line.
- Using the chain rule, the server computes the first-order Hasse derivative of $D_x(Z)$ at specific points $b_\ell$ .
- The server outputs a converted share involving the evaluation $D_x(b_\ell)$ and the derivative term, weighted by interpolation coefficients $a_{\ell, k}$ .
DPF Generation:
- The generator creates $2n_r$ keys. Each key consists of a pair: an additive share of the output value and a share from the underlying PIR-based SSS.
- The evaluation algorithm computes the inner product of the key components to recover the additive share of $f_{\alpha, \beta}(x)$ .

3. Key Contributions

Novel Share Conversion: The authors derive a new share conversion function directly from the GKS derivative-based PIR. This is the first application of derivative-based PIR to construct ITDPFs.
Improved Key Size: They construct a perfectly secure $(1, 2n_r)$ $(1, 2 n_{r})$ -ITDPF with output group $\mathbb{Z}_p$ $Z_{p}$ .
- Key Size: $O(2^{c_2(r) \cdot \nu_{r+1}(N)} \cdot \log p)$ .
- Improvement: This is asymptotically smaller than the best previous perfectly secure ITDPFs (e.g., Li et al.'s $2^{O(\nu_r(N))}$ ), effectively reducing the exponent from $\nu_r(N)$ to $\nu_{r+1}(N)$ .
Perfect Security: The construction maintains perfect security (information-theoretic security against computationally unbounded adversaries), unlike some statistical alternatives that trade security for efficiency.
Generality: The scheme works for any prime $p$ as the output group modulus, a significant generalization over some prior constructions.

4. Results

Theoretical Bounds: The paper proves that the proposed scheme satisfies the correctness and perfect security requirements of the LKZ framework.
Comparison (Table I):
- Compared to Thm. 10 of [10] (Li et al.), which has key size $O(2^{c_1(r) \cdot \nu_r(N)})$ , the new scheme achieves $O(2^{c_2(r) \cdot \nu_{r+1}(N)})$ . Since $\nu_{r+1}(N) < \nu_r(N)$ , the new keys are strictly shorter asymptotically.
- Compared to Thm. 1 of [2] (Boyle et al.), the new scheme is not worse and offers better asymptotic scaling for large $N$ .
Parameters: The number of servers required is $2n_r$ , where $n_r$ is defined by the number of prime factors in the PIR construction (e.g., $n_1=2, n_2=3, \dots$ ).

5. Significance

Efficiency in MPC and PIR: DPFs are fundamental building blocks for Secure Multi-Party Computation (MPC) and Private Information Retrieval (PIR). Reducing the key size directly translates to lower communication overhead and storage requirements in these protocols.
Bridging PIR and DPFs: The work demonstrates a powerful synergy between recent advances in PIR (specifically derivative-based approaches) and DPF construction. It suggests that improvements in PIR communication complexity can be directly translated into more efficient DPFs.
Future Directions:
- The current construction is limited to 1-private DPFs (security against 1 colluding server) because the underlying GKS PIR is 1-private. Extending this to $t$ -private DPFs with $t > 1$ without an exponential blowup in server count is an open challenge.
- Extending the output group from prime-order $\mathbb{Z}_p$ to arbitrary Abelian groups is identified as future work.

In summary, this paper presents a breakthrough in the efficiency of perfectly secure ITDPFs by leveraging the latest derivative-based PIR techniques, achieving the shortest known secret keys for prime-order output groups.