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
(constantserver) PIRs and (constantquery) 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 highlevel 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 "Cshareconversion" (for a relation $C$).

Constructing $k$PIR of ccomplexity $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 kserver 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$shareconversion 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 "shareconversion of $k$SS
over $R$ to $k$SS' over $R'$ wrt $C$" by "$C$shareconversion 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 3ASS over $Z_m$ to a 3LSS 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 shareconversion requires using nonstandard SS.
In contrast, Klim uses a $C_m$shareconversion of $Z_{m}$ to $Z_2^t$,
for $m=2^t1$, and so he has $m=511 = 2^91 = 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 threefold:
(a) generalizing and abstracting the foregoing fourstep plan,
and specifically the roles of VC, SS, shareconversion, and MPC in it;
(b) Finding shareconversions 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.