Information-Theoretic Distributed Point Functions with Shorter Keys
arXiv:2604.24385v1 [cs.CR] 27 Apr 2026
Hang Deng and Liang Feng Zhang
Abstract—A t-private n-server Information-Theoretic Distributed Point Function ((t, n)-ITDPF) allows one to convert any point function fα,β (x) : [N ] → G into n shares (secret keys), such that each server can compute an additive share of fα,β (x) with a key while any ≤ t servers learn absolutely no information about the function. This paper constructs a novel share conversion based on the private information retrieval (PIR) of Ghasemi, Kopparty, and Sudan (STOC 2025) and proposes a perfectly secure 1-private ITDPF with output group G = Zp , where p can be any prime. Compared with the existing perfectly secure ITDPFs for the same output group, the proposed ITDPF is more efficient with asymptotically shorter secret keys.
I. I NTRODUCTION A t-private n-server Distributed Point Function ((t, n)-DPF) [2], [8] can convert any point function fα,β : [N ] → G (i.e., a function such that fα,β (α) = β and fα,β (x) = 0 for all x ̸= α) into n shares (called secret keys) k0 , . . . , kn−1 such that every key ki enables the computation of an additive share of fα,β (x) but any ≤ t shares leak no information about the function. In particular, the range G of the function is an Abelian group and called the output group. The communication efficiency of a DPF may be measured by its key size, i.e., the maximum size of the n keys k0 , . . . , kn−1 , as a function of the domain size N . Ideally, DPFs with shorter keys are preferred for any given t, n and output group G. DPFs have numerous applications, e.g., in constructing secure multiparty computation (MPC) protocols and specifically Private Information Retrieval (PIR) [4] protocols [11], [12]. While computational DPFs [8] are secure against the collusion of any t polynomial-time servers, Information-Theoretic DPFs (ITDPFs) [2] offer stronger security by tolerating computationally unbounded servers and are our focus in this paper. Boyle et al. [2] and Li et al. [10] constructed ITDPFs (see TABLE I) that gave various trade-offs among the security, the key size, the number of servers, and the generality of output groups. In particular, for G = Zp , where p may be any prime, Li et al. [10] constructed a perfectly secure (t, d(t + 1))ITDPF with polynomial key size. Boyle et al. [2] and Li et al. [10] proposed perfectly secure (1, 4)-ITDPF and (1, 2nr )ITDPF with subpolynomial key sizes 2O(ν2 (N )) and 2O(νr (N )) respectively, where O may hide a factor in p and νr (N ) = (log N )1/r (log log N )1−1/r ,
(1)
Hang Deng ([email protected].) is with the Institute of Mathematical Sciences, ShanghaiTech University, Shanghai, China. Liang Feng Zhang ([email protected]) is with the School of Information Science and Technology, ShanghaiTech University, Shanghai, China. This work was supported in part by the National Natural Science Foundation of China (No. 62372299)
2, r = 1; r/2 3 , 1 < r ≤ 103, 2|r; nr = 8 · 3(r−3)/2 , 1 < r ≤ 103, 2 ∤ r; (3/4)51 · 2r , r ≥ 104.
(2)
Boyle et al. [2] and Li et al. [10] also developed statistically secure ITDPFs with subpolynomial key sizes, which however trade off the stronger perfect security for a smaller number of required servers. Underlying [2], [10] is a framework that firstly builds share conversions from PIR and then represents point functions as bilinear functions of share conversions. In particular, the key size of the resulting ITDPF is propositional to the communication complexity of the underlying PIR. Recently, Ghasemi et al. [7] proposed the state-of-the-art 1-private PIR, which makes it promising to construct ITDPFs with asymptotically shorter secret keys using the framework of [2], [10]. TABLE I Perfectly secure (t, n)-ITDPFs with output group Zp Constructions t n Key size Thm. 7, [10] ≥ 1 d(t + 1) O N 1/⌊(2d−1)/t⌋ · log p Thm. 1, [2] 1 4 O 22p·ν2 (N ) · log p (p ≥ 3) Thm. 8, [10] 1 8 O 210·ν2 (N ) + log p Thm. 10, [10] 1 2nr O 2c1 (r)·νr (N ) · log p c (r)·ν (N ) r+1 This paper 1 2nr O 2 2 · log p c1 (r) ≈ the (r + 1)th smallest prime; c2 (r) = max{p, the (r + 1)th smallest prime}
Our contributions. In this paper, we construct a perfectly secure (1, 2nr )-ITDPF with output group G = Zp , where p can be any prime and nr is defined by Eq. (2). The proposed ITDPFs achieve a subpolynomial key size of 2O(νr+1 (N )) , which is asymptotically smaller than that of [10]. Our core technical contribution is a novel share conversion based on the derivative-based PIR of Ghasemi et al. [7]. II. P RELIMINARIES A. Notation For any integer n > 0, we denote [n] = {1, . . . , n}. For any integer m > 0, we denote by Zm the ring of integers modulo m. For any prime power q, we denote by Fq the finite field of order q and denote by F∗q the multiplicative group of Fq . We denote any vectors with lower case boldface letters. For any vectors u = (u1 , . . . , uk ), v = (v1 , . . .P , vk ) over a ring, we k denote their inner product with u · v = i=1 ui vi and denote their pointwise product with u ⊙ v = (u1 v1 , . . . , uk vk ). We use δα,x to denote the Kronecker symbol, i.e., δα,x = 1 when x = α and δα,x = 0 when α ̸= x.
B. Point functions
D. LKZ Framework for Constructing ITDPFs
Let N > 0 be an integer and let G be an Abelian group. For any α ∈ [N ] and β ∈ G, the point function fα,β : [N ] → G is defined by fα,β (x) = β · δα,x .
Li et al. [10] has a framework that may transform certain secret sharing schemes to perfectly secure ITDPFs via share conversions [1]. Secret sharing scheme (SSS). An SSS L = (Share, Rec) for n participants allows a dealer to convert a secret s ∈ S into n shares (c0 , . . . , cn−1 ) ← Share(s) in a share space C, such that any authorized set A ⊆ {0, 1, . . . , n − 1} can reconstruct s as s ← Rec({cj }j∈A ) but any unauthorized set gives no information about s. A (t, n)-threshold SSS (TSSS) is an SSS where the authorized sets are subsets of cardinality > t. An additive SSS is an (n − 1, n)-TSSS where the secret space is an additive group and s = c0 + · · · + cn−1 is the sum of n random group elements. Share conversion. Let (L1 , S1 ) = ((Share1 , Rec1 ), S1 ) and (L2 , S2 ) be two SSSs. Let R ⊆ S1 × S2 be a binary relation such that, for every s1 ∈ S1 there exists an s2 ∈ S2 satisfying (s1 , s2 ) ∈ R. The scheme L1 is locally convertible to L2 w.r.t. R if there exist n share conversion functions g0 , . . . , gn−1 : C1 → C2 such that: for any s1 ∈ S1 and any (c0 , . . . , cn−1 ) ← Share1 (s1 ), (g0 (c0 ), . . . , gn−1 (cn−1 )) is a valid sharing of an s2 ∈ S2 that satisfies (s1 , s2 ) ∈ R. The framework. Let (L1 , S1 ) = ((Share1 , Rec1 ), [N ]) be a (t, n)-TSSS with share space C1 and let (L2 , S2 ) be an additive SSS with share space C2 = S2 . Suppose that (L1 , S1 ) is locally convertible to (L2 , S2 ) w.r.t. a binary relation R ⊆ S1 ×S2 . To obtain an n(t + 1)-server ITDPF with domain [N ] and output group G, the framework [10] requires: (a) There is a function Conv : {0, 1, . . . , n − 1} × S1 × C1 → C2 such that for any x ∈ S1 , {gℓx = Conv(ℓ, x, ·)}n−1 ℓ=0 : C1 → C2 are n share conversion functions for R. (b) There is a commutative ring R with identity 1 such that G is a subgroup of the additive group of R, 1 ∈ G, and there is a surjective homomorphism ϕ : R → G. (c) There exist an R-module H, a function ψ : S1 → H, and a bilinear function Φ : H × C2 → R such that: for any α, x ∈ S1 , (c0 , . . . , cn−1 ) ← Share1 (α), and ! n−1 X ρ(α, x) = Φ ψ(α), Conv(ℓ, x, cℓ ) , (4)
C. Information-Theoretic DPF A t-private n-server information-theoretic DPF [2] allows one to secret-share a point function fα,β among n servers such that each server can compute an additive share of fα,β (x) ∈ G for any given input x ∈ [N ] but any t servers learn absolutely no information about the function. Definition 1 (Distributed point function). A t-private n-server DPF ((t, n)-DPF) Π = (Gen, {Evali }n−1 i=0 ) consists of n + 1 algorithms with the following syntax: (k0 , . . . , kn−1 ) ← Gen(1λ , fα,β ): Given a security parameter λ and a point function fα,β , the (randomized) key generation algorithm returns n secret keys k0 , . . . , kn−1 . • yi ← Evali (ki , x): Given a secret key ki and an input x ∈ [N ], the (deterministic) evaluation algorithm Evali (of server i) returns a group element yi ∈ G.
•
The scheme Π should satisfy the following requirements: •
Correctness. For any security parameter λ, any point function fα,β , any input x ∈ [N ], and any secret keys (k0 , . . . , kn−1 ) ← Gen(1λ , fα,β ), "n−1 # X Pr Evali (ki , x) = fα,β (x) = 1. (3) i=0
•
Security. Consider the following security experiment between a challenger and an adversary A that controls the j-th server for all j ∈ T (T ⊆ {0, 1, . . . , n−1}, |T | ≤ t): – Given the security parameter λ, A chooses two point functions f 0 = fα0 ,β0 , f 1 = fα1 ,β1 : [N ] → G and gives them to the challenger. – The challenger samples b ← {0, 1} uniformly, generates n secret keys (k0 , . . . , kn−1 ) ← Gen(1λ , f b ), and gives kT = {ki : i ∈ T } to A. – The adversary A outputs a guess b′ ← A(kT ). Let Adv(1λ , A, T ) = | Pr[b = b′ ]−1/2| be the advantage of A in guessing b in the experiment. For a circuit size bound M = M (λ) and an advantage bound ϵ = ϵ(λ), we say that Π is (M, ϵ)-secure if for all subset T ⊆ {0, . . . , n − 1} of cardinality ≤ t, and all non-uniform adversaries A of size M (λ), Adv(1λ , A, T ) ≤ ϵ(λ).
A (t, n)-DPF is called statistically ϵ-secure if it is (M, ϵ)secure for all M , and perfectly secure if it is statistically 0secure. Both kinds of DPFs are called information-theoretic DPFs (ITDPFs) [2]. To prove that a (t, n)-DPF is an ITDPF, it suffices to show that the joint distribution of any t secret keys are independent of the underlying point function, i.e., if (k0 , . . . , kn−1 ) ← Gen(1λ , f ), then kT is independent of f for any subset T of cardinality ≤ t.
ℓ=0
there exists a ring element σ ∈ R that satisfies ϕ(ρ(α, x) · σ) = δα,x .
(5)
Given any point function fα,β : [N ] → G, the framework [10] generates k = n(t + 1) keys by first computing n shares (c0 , . . . , cn−1 ) ← Share1 (α) of α under L1 , then additively sharing (σ · β) ◦ ψ(α) as the sum of t + 1 random module elements ω0 , ω1 , . . . , ωt ∈ H, i.e., ω0 + ω1 + · · · + ωt = (σ · β) ◦ ψ(α),
(6)
where ◦ is the scalar multiplication between ring elements and module elements, and finally setting the i-th key as ki = (ωj , cℓ )
(7)
for all i = jn + ℓ, where 0 ≤ j ≤ t and 0 ≤ ℓ ≤ n − 1. Given the key ki = (ωj , cℓ ) and any input x ∈ [N ], the i-th server’s evaluation algorithm simply outputs yi = ϕ(Φ(ωj , Conv(ℓ, x, cℓ ))).
(8)
E. GKS Derivative-based PIR A (1-private) k-server PIR scheme allows one to retrieve any element λα of a database λ = (λ1 , . . . , λN ) from k servers, where each server has a copy of λ, without revealing α ∈ [N ] to each individual server. Recently, Ghasemi et al. [7] presented the state-of-the-art 1-private PIR by improving the schemes of [3], [5], [6], which are all based on S-matching families and S-decoding polynomials. Definition 2 (S-matching family). For any integers m, h, N > 0 and any set S ⊆ Zm with 0 ∈ S, an S-matching family of N size N in Zhm is a pair (U = {ui }N i=1 , V = {vi }i=1 ) of subsets h of Zm that satisfies the following properties: • ui · vi = 0 for all i ∈ [N ]; and • ui · vj ∈ S \ {0} for all i ̸= j. Definition 3 (S-decoding polynomial). For any integer m > 0, any set S ⊆ Zm with 0 ∈ S, any prime q such that m|(q−1) and a primitive m-th root of unity γ ∈ Fq , an S-decoding polynomial is a polynomial P (X) ∈ Fq [X] such that • P (1) = 1; and s • P (γ ) = 0 for all s ∈ S \ {0}. For any integer m = p1 · · · pr that is a product of r ≥ 2 distinct primes, Grolmusz’s set systems [9] gave an Sm matching family of size N = exp(O((log h)r /(log log h)r−1 ))
(9)
in Zhm , where Sm is the canonical set of m and defined as Sm = {s ∈ Zm : s mod pi ∈ {0, 1}, ∀i ∈ [r]}.
(10)
With these families and a trivial construction of S-decoding polynomials, Efremenko [6] constructed a (1, 2r )-PIR of subpolynomial communication complexity exp(O(νr (N ))). In [6], the database λ is encoded as an h-variate polynomial Gλ (z) =
N X
h λj zuj : Hm → Fq ;
(11)
Definition 4 (0-interpolation property with multiplicity e). Let S ⊆ N with 0 ∈ S. A set B ⊆ Fq has the 0-interpolation property with multiplicity e for S if there exists a linear map E : (Feq )B → Fq such that E(R(<e) |B )P= R(0) for any s polynomial R(Z) of the form R(Z) = s∈S cs Z , where (<e) R |B denotes the vector of the evaluations of the i-th Hasse derivatives of R at B for all i < e. Let F be a finite field of characteristic p such that m|(|F|−1) and let Hm ⊆ F be the order-m subgroup of F∗ . Ghasemi et al. [7] showed that if 0 ∈ SM and SM ⊆ φ(Sm ×{0, 1, . . . , e−1}) for the Chinese Remainder Isomorphism φ : Zm × Zp → ZM , then any 0-interpolating set B ⊆ Hm with multiplicity 1 for Sm must be a 0-interpolating set with multiplicity e for SM . Based on this property, Ghasemi et al. [7] obtained a 1-private nr -server PIR of communication complexity 2O(νr+1 (N )) for any r ≥ 1, where nr is defined by Eq. (2). III. O UR DPF C ONSTRUCTION This section presents our new (1, 2nr )-ITDPF with shorter keys of size 2O(νr+1 (N )) . The proposed construction is based on the LKZ framework [10] and consists of two steps. The first of these steps extracts the required share conversions out of the GKS derivative-based PIR [7] and consists of our main technical contribution; and the second step converts the resulting share conversions to the proposed ITDPF, using the idea of [10]. A. From GKS Derivative-based PIR to Share Conversion Let m = p1 · · · pr be the product of r ≥ 2 distinct primes and let M = mp for a prime p such that gcd(m, p) = 1. Let F be a finite field of size pτ such that m | (|F| − 1). Let Hm be the order-m subgroup of F∗ . Let Sm ⊆ Zm and SM ⊆ ZM be the canonical sets of m and M , respectively. By Theorem 1.4 of [9], there is an SM -matching family (U = {ui }N i=1 , V = h {vi }N ) in Z for properly chosen h. By Theorem 4.1 of i=1 M [3], there is an Sm -decoding polynomial over F with nr terms for the nr in (2), i.e., there is a 0-interpolating set B = {b0 , b1 , . . . , bnr −1 } ⊆ Hm
j=1
over Hm ⊆ F∗q , the order-m subgroup of F∗q for a prime power q that satisfies m|(q −1), each server is queried with a specific point C(bℓ ) on a random multiplicative line C(Z) = w ⊙Z vα h in Hm and responds with an evaluation of the function g(Z) = Gλ (w ⊙ Z vα )
terms than the sparsest Sm -decoding polynomial, where M = mp for a prime p such that gcd(m, p) = 1. A main technical contribution of [7] is the study of the 0-interpolation property with multiplicity.
(12)
at bℓ , and finally λα = g(0) is recovered by interpolating g(Z). While subsequent works [3], [5] significantly reduced the number of servers required by [6], the recent work [7] further reduced this number by asking each server to provide not only evaluations of Gλ but also its Hasse derivatives, which allow [7] to use an SM -matching family to construct the polynomial in (11) but an SM -decoding polynomial that contains no more
(13)
with multiplicity 1 for Sm . Note that SM ⊆ φ(Sm × {0, 1}), B must be a 0-interpolating set with multiplicity 2 for SM . Choosing SSSs. Let fα,β : [N ] → Zp be a point function with output group Zp . The proposed share conversion chooses an SSS (L1 , S1 ) = ((Share1 , Rec1 ), S1 ) with share space C1 and an SSS (L2 , S2 ) with share space C2 such that S1 = [N ],
C1 = Fh+1 ,
S2 = C2 = Fh+1
(14)
For α ∈ S1 , Share1 (α) generates n shares c0 , c1 , . . . , cnr −1 ∈ C1 by mapping α to the vector vα ∈ V, randomly choosing a h vector w ∈ Hm and finally setting cℓ = (w ⊙ bvℓ α , bℓ ), ℓ = 0, 1, · · · , nr − 1.
(15)
The SSS L1 is 1-private because the first h entries of any share cℓ are truly random and independent of α. However, given any two shares cℓ1 and cℓ2 , (bℓ1 /bℓ2 )vα can be easily extracted by dividing the first h entries of both shares and then give full information about vα (and so α), because both bℓ1 and bℓ2 are public. The SSS L2 is simply an additive SSS over S2 .
As F is a field of characteristic p, (Z − bℓ )p |(Z M − 1) for all ℓ ∈ {0, . . . , nr − 1}. It follows that D̃x and Dx agree at each bℓ not only in their evaluations, but also in their first (p − 1) derivatives. In particular,
Constructing Conv. For every ℓ ∈ {0, 1, . . . , nr −1}, we need to construct a function that enables the ℓth server to transform its share cℓ into a component that eventually contributes to the reconstruction of the point function fα,β . Given the share cℓ and any input x ∈ S1 , the local share conversion function Conv(ℓ, x, cℓ ) is designed in four steps as follows.
Based on (23) and (24), the problem of recovering D̃x (0) can be reduced to that of computing the evaluations and first-order derivatives of Dx (Z) at all points in B.
1) Defining the core polynomial Dx (Z): We begin by associating a specific univariate polynomial Dx (Z) =
N X
fj,1 (x) · wuj Z vα ·uj
(16)
over the finite field F with the input x. In fact, if we denote λx = (f1,1 (x), . . . , fN,1 (x)), then the core polynomial Dx (Z) can be obtained by restricting the function Fx (z) := Gλx (z) =
N X
fj,1 (x)zuj
(17)
j=1
defined by Eq. (11) to the multiplicative line C(Z) = w ⊙ Z vα .
(18)
Note that the polynomial D̃x (Z) = Dx (Z) mod (Z M − 1) admits a sparse representation of the form X D̃x (Z) = fα,1 (x) · wuα + ks Z s , (19) s∈SM \{0}
due to the the properties of SM -matching family, where X ks = fj,1 (x) · wuj (20) j∈[N ]:vα ·uj =s
for all s ∈ SM \ {0}. The reduced form D̃x (Z) allows one to compute fα,1 (x) as fα,1 (x) = w−uα · D̃x (0)
(21)
and thus reduce the problem of computing of fα,1 (x) to that of recovering D̃x (0). 2) Applying 0-interpolation property with multiplicity: Recall that the set B in Eq. (13) is a 0-interpolating set with multiplicity 2 for SM and guarantees a linear map E : (F2 )B → F
(22)
such that the constant term D̃x (0) can be recovered from the evaluations and first-order derivatives of D̃x (Z) at all points in B, i.e. there exist constants {aℓ,k : 0 ≤ ℓ < nr , k = 0, 1} such that nX 1 r −1 X ℓ=0 k=0
3) Computing derivatives via chain rule: While Dx (bℓ ) can (1) be easily computed by each server, Dx (bℓ ) must be recovered from the Hasse derivatives of a multivariate polynomial. Recall that Dx (Z) = Fx (C(Z)), we must have Dx(1) (Z) = ⟨∇Fx (C(bℓ )), C (1) (bℓ )⟩
(25)
where for all bℓ ∈ B, ∇Fx (C(bℓ )) = (∂1 Fx (z), . . . , ∂h Fx (z))|z=C(bℓ )
j=1
D̃x (0) =
D̃x (bℓ ) = Dx (bℓ ), D̃x(1) (bℓ ) = Dx(1) (bℓ ), 0 ≤ ℓ < nr . (24)
aℓ,k · D̃x(k) (bℓ ).
(23)
C
(1)
(bℓ ) = b−1 ℓ C(bℓ ) ⊙ vα .
(26) (27)
(1)
Thus, for all bℓ ∈ B, to compute the derivative Dx (bℓ ), it suffices for the client to learn ∇Fx (C(bℓ ) from a server. 4) Embedding the linear map coefficient: Recall that the linear map E in Eq. (22) ensures the recovery of D̃x (0) from the values in Eq. (24), with coefficients {aℓ,k : 0 ≤ ℓ < nr , k = 0, 1} from Eq. (23). Given that cℓ = (b−1 ℓ C(bℓ ), bℓ ), our design of Conv is finally completed by embedding the recovery coefficients into Eq. (26) (which are required by Eq. (25)) and given by C(bℓ ) ⊙ ∇Fx (C(bℓ )) . (28) Conv(ℓ, x, cℓ ) = aℓ,0 Dx (bℓ ), aℓ,1 bℓ Given (28), the binary relation R in our DPF can be described h , x ∈ [N ], and the cℓ ’s as follows. For s1 = α ∈ S1 , w ∈ Hm in Eq. (15), the secret s2 ∈ S2 such that (s1 , s2 ) ∈ R is the sum of the nr converted shares in Eq. (28): s2 (w, α, x) =
nX r −1
Conv(ℓ, x, cℓ ).
(29)
ℓ=0
B. From Share Conversion to DPF So far the (1, nr )-TSSS (L1 , S1 ) (Eq. (14), (15)) and the additive SSS (L2 , S2 ) (Eq. (14), (29)) we have chosen in Section III-A and the new share conversion function Conv (Eq. (28)) we have constructed in Section III-A have been confirmed to satisfy the property (a) required by the LKZ framework (see Section II-D). To complete the DPF construction, we need to choose a ring R, an R-modulo H and three functions ϕ, ψ, Φ such that (b) and (c) are also satisfied. Choosing (R, ϕ). Note that F = Fpτ is a field of characteristic p. There exists a monic irreducible polynomial ζ(X) ∈ Zp [X] of degree τ such that F ∼ = Zp [X]/(ζ(X)). Then every field element y ∈ F has the form y = y0 + y1 X + · · · + yτ −1 X τ −1 . We choose R = F and choose ϕ : R → G such that ϕ(y) = y0 ,
∀y ∈ F.
(30)
It is trivial to verify that (R, ϕ) is a surjective homomorphism and the property (b) required by LKZ is satisfied. Choosing (H, ψ, Φ). To meet the requirement (c), we choose the R-modulo H = Fh+1 , choose ψ : S1 → H such that ψ(α) = (1, vα ),
∀ α ∈ S1 ,
(31)
and choose the bilinear function Φ : H × C2 → R such that Φ(h, c) = ⟨h, c⟩, ∀ h ∈ H, c ∈ C2 .
(32)
Then for any α, x ∈ S1 , (c0 , c1 , . . . , cnr −1 ) ← Share1 (α), the equations (29), (31) and (32) jointly imply that the ρ(α, x) in Eq. (4) has the following form ρ(α, x) = ⟨(1, vα ), s2 (w, α, x)⟩
(33)
By Eq. (23), (24), (25), (26), (27), (28), and (29), it is easy to see that ρ(α, x) = D̃x (0). Considering (21), we can easily satisfy (5) by further choosing σ = w−uα
(34)
completely determined by Eq. (15) (for cℓ ) and Eq. (35) (for ωj ). Since bℓ is a public parameter, the only component of cℓ that may be relevant to the point function fα,β is w ⊙ bvℓ α . This component is generated by a (1, nr )-TSSS and uniformly h distributed over the set Hm , as w is uniformly chosen from h Hm . On the other hand, ωj is an additive share of wβuα · ψ(α) and uniformly distributed over the set H. Considering that the sharing processes of cℓ and ωj are independent of each other, h the key ki is uniformly distributed over the set Hm × H and thus gives no information about fα,β , i.e., the proposed DPF is perfectly secure. Key size. Referring to Fig. 1, every secret key ki = (ωj , cℓ ) h+1 consists of an element of H = Fh+1 and an element of Hm and thus has size O(h log p), where h is an integer such that there is an SM matching family of size N . Since M = mp is the product of r + 1 distinct primes, by [9], we may choose h = 2c2 (r)·νr+1 (N ) , where c2 (r) is the larger one between p and the (r + 1)th smallest prime. Hence, the key size of the proposed DPF is O(2c2 (r)·νr+1 (N ) · log p).
and thus eventually meet the requirement (c).
D. Comparisons
The (1, 2nr )-ITDPF. Finally, by applying the transformation from Section II-D we get a perfectly secure (1, 2nr )-ITDPF (Fig. 1) with output group Zp , where nr is defined by (2). h Gen(fα,β ). Given α ∈ [N ] and β ∈ Zp , choose w ← Hm vα and set cℓ = (w⊙bℓ , bℓ ) for 0 ≤ ℓ < nr . Choose ω0 , ω1 ← H uniformly subject to
Table I give detailed comparisons between the (1, 2nr )ITDPF proposed by this work and the perfectly secure (t, n)ITDPFs for the same output group Zp prior to this work. Compared with the constructions in Thm. 7 of [10], Thm. 8 of [10], and Thm. 10 of [10], our ITDPFs achieve a key size that is asymptotically smaller as a function of N , the domain size of the point function. Compared with the construction in Thm. 1 of [2], our key size is not worse.
ω0 + ω1 = (w−uα · β) · ψ(α).
IV. C ONCLUSIONS
(35)
r −1 Output 2nr keys {ki }2n , where ki = (ωj , cℓ ) for every i=0
i = nr j + ℓ (0 ≤ j ≤ 1, 0 ≤ ℓ < nr ). Evali (ki , x). Given ki = (ωj , cℓ ) and x ∈ [N ], output C(bℓ ) ϕ ⟨ωj , (aℓ,0 D(bℓ )(x), aℓ,1 ⊙ ∇F (C(bℓ )))⟩ bℓ Fig. 1. Our (1, 2nr )-ITDPF
C. Analysis Correctness. Within the LKZ Framework it suffices to verify (a), (b) and (c) are all satisfied by the proposed constructions. While (a) and (b) have be confirmed, we focus on Eq. (5), i.e., ϕ(ρ(α, x) · σ) = δα,x , which is true because nX r −1 ϕ(ρ(α, x) · σ) = ϕ w−uα (1, vα ), Conv(ℓ, x, cℓ ) ℓ=0
Pnr −1 aℓ,0 Dx (bℓ ) + vα (aℓ,1 C(bℓ ) ⊙ ∇Fx (C(bℓ ))) ℓ=0 bℓ =ϕ wuα nX 1 r −1 X = ϕ w−uα aℓ,k Dx(k) (bℓ ) = δα,x . ℓ=0 k=0
Security. For any α ∈ [N ], β ∈ Zp and i = jnr + ℓ, the i-th DPF secret key ki = (ωj , cℓ ) for the point function fα,β is
In this paper we proposed a novel share conversion based on the state-of-the-art 1-private nr -server private information retrieval (PIR) of Ghasemi, Kopparty, and Sudan (STOC 2025) and gave a perfectly secure (1, 2nr )-ITDPF with output group G = Zp by using the LKZ framework, where p can be any prime. Compared with the best existing perfectly secure ITDPFs for the same output group, the proposed ITDPF is more efficient with asymptotically shorter secret keys. As a restriction, the proposed construction is only applicable to a prime-order output group Zp . We can partially remove this restriction on output groups by extending the proposed construction to any output group G that is isomorphic to Zp1 × Zp2 × · · · × Zpk , the direct product of k prime-order output groups, in a straightforward way. It is left for future work to extend the proposed construction to arbitrary output groups. As another restriction, the proposed construction gives 1private DPFs only, because the PIR underlying our construction is 1-private. Note that Barkol et al. [13] has a generic method of transforming any (1, k)-PIR to a (t, k t )-PIR. By applying this method to the PIR of GKS, the privacy of our ITDPF may be boosted, at the price of an exponential increase in the number of servers to (2nr )t , which however is inefficient. It is also an interesting future work to extend the proposed construction or even the LKZ framework to support stronger privacy requirements.
R EFERENCES [1] A. Beimel, Y. Ishai, E. Kushilevitz, I. Orlov, “Share conversion and private information retrieval,” in Proc. IEEE Conference on Computational Complexity (CCC), 2012, pp. 258–268. [2] E. Boyle, N. Gilboa, Y. Ishai, V. I. Kolobov, “Information-theoretic distributed point functions,” in Proc. 3rd Conference on InformationTheoretic Cryptography (ITC), ser. Leibniz International Proceedings in Informatics (LIPIcs), vol. 230, 2022, pp. 1–14. [3] Y. M. Chee, T. Feng, S. Ling, H. Wang, L. F. Zhang, “Query-efficient locally decodable codes of subexponential length,” Computational Complexity, vol. 22, no. 1, pp. 159–189, 2013. [4] B. Chor, O. Goldreich, E. Kushilevitz, M. Sudan, “Private information retrieval,” in Proc. IEEE Symposium on Foundations of Computer Science (FOCS), 1995, pp. 41–50. [5] Z. Dvir, S. Gopi, “2-server PIR with sub-polynomial communication,” in Proc. ACM Symposium on Theory of Computing (STOC), 2015, pp. 577–584. [6] K. Efremenko, “3-query locally decodable codes of subexponential length,” in Proc. ACM Symposium on Theory of Computing (STOC), 2009, pp. 39–44. [7] F. Ghasemi, S. Kopparty, M. Sudan, “Improved PIR Schemes using Matching Vectors and Derivatives,” in Proc. ACM Symposium on Theory of Computing (STOC), 2025, pp. 1648–1656. [8] N. Gilboa, Y. Ishai, “Distributed point functions and their applications,” in Proc. International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), 2014, LNCS, vol. 8441, pp. 640–658. [9] V. Grolmusz, “Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs,” Combinatorica, vol. 20, no. 1, pp. 71–86, 2000. [10] J. Li, P. Ke, L.F. Zhang, “Efficient information-theoretic distributed point functions with general output groups,” Designs, Codes, and Cryptography, vol. 93, no. 5, pp. 1501–1530, 2025. [11] L.F. Zhang, “A unified framework for constructing informationtheoretic private information retrieval,” Pragmatic Cybersecurity, 1(1):3, 2026. [12] P. Ke, L.F. Zhang, H. Wang, et al., “Efficient DPF-based errordetecting information-theoretic private information retrieval over rings,” Cybersecurity, 9:149, 2026. [13] O. Barkol, Y. Ishai, E. Weinreb, “On locally decodable codes, selfcorrectable codes, and t-private PIR,” Algorithmica, vol. 58, no. 4, pp. 831–859, 2010.