Share Conversion and Private Information Retrieval
by Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Ilan Orlov
Oded's comments
This paper presents a framework for the construction of
(constant-server) PIRs and (constant-query) LDCs,
which greatly abstracts and generalizes all known constructions
(including the relatively recent breakthrough of Sergei Yekhanin
and Klim Efremenko).
This framework clarifies some aspects of these mysterious
constructions, and also provides better quantitative results.
Unfortunately, the impressive conceptualization is not coupled
with a clear exposition, but hopefully this will be improved
in future versions. Let me try to provide a high-level descrption
of the framework, which consists of a relatively large number
of (appealing) steps. Notions that will feature below, but will
intensionally remain undefined include "MPC for a function class",
XSS (for various X's), and "C-share-conversion" (for a relation $C$).
-
Constructing $k$-PIR of c-complexity $c(n)$
reduces to constructing $k$-server MPC of complexity $c(n)$ for
a function class $F$ of VC at least $n$. [See Thm IV.3 in the paper]
Thus, we need a class of high VC and a k-server MPC for it.
The first is presented in step (2), and the second in step (3),
although in applying this framework the design starts in step (3).
-
For $m$ a product of two primes $p_1
[For sake of elegancy, the class $F(R,h)$ is defined for any ring $R$.
I intensionally avoid defining this class here.]
-
For two rings $R$ (indeed, we shall take $R=Z_m$) and $R'$,
and any integer $h$, the construction of a $k$-server MPC
of complexity $h \cdot s(R)$ for the class of functions $F(R,h)$,
reduces to
(i) the construction of a $k$-LSS scheme over $R$ that uses shares
of length $s(R)$, and (ii) a $C_S$-share-conversion of the scheme in (i)
to a $k$-ASS over $R'$, where LSS (resp., ASS) denote Linear
(resp., Additive) Secret Sharing schemes. [Thm IV.2]
[Indeed, I suggest to replace the pharse "share-conversion of $k$-SS
over $R$ to $k$-SS' over $R'$ wrt $C$" by "$C$-share-conversion of $k$-SS
over $R$ to $k$-SS' over $R'$". The belated "wrt" is bad...]
-
Re (3i): An $k$-LSS with $s(R)=O(1)$ always exists [not stated...]
Re (3ii): For $m$ a product of two primes, there exist
a $C$-coversions from a 3-ASS over $Z_m$ to a 3-LSS over $Z_p^b$,
for various $(m,p,b)$ triples including $m=6$ and $p=b=2$. [Thm III.5]
[The relation $C$ used depends on a set $S_m$,
and constructing this share-conversion requires using non-standard SS.
In contrast, Klim uses a $C_m$-share-conversion of $Z_{m}$ to $Z_2^t$,
for $m=2^t-1$, and so he has $m=511 = 2^9-1 = 73 * 7$.
Therefore, Klim has 2*73 as the constant in the exponent,
whereas you have $2 * 3 = 6$. The fact that your $R'=Z_2^2$
is smaller is much less significant.]
In summary,the contributions of this work are three-fold:
(a) generalizing and abstracting the foregoing four-step plan,
and specifically the roles of VC, SS, share-conversion, and MPC in it;
(b) Finding share-conversions from much smaller rings $R=Z_m$; and
(c) obtaining negative results on share conversion.
The original abstract
See proceedings of Complexity 2012;
a full version may be posted on ECCC soon.
Back to
list of Oded's choices.