Liang Feng Zhang

Lin Zhu, Wen Ming Li, Liang Feng Zhang

A $k$-query locally decodable code (LDC) $C$ allows one to encode any $n$-symbol message $x$ as a codeword $C(x)$ of $N$ symbols such that each symbol of $x$ can be recovered by looking at $k$ symbols of $C(x)$, even if a constant fraction of $C(x)$ have been corrupted. Currently, the best known LDCs are matching vector codes (MVCs). A modulus $m=p_1^{α_1}p_2^{α_2}\cdots p_r^{α_r}$ may result in an MVC with $k\leq 2^r$ and $N=\exp(\exp(O((\log n)^{1-1/r} (\log\log n)^{1/r})))$. The $m$ is {\em good} if it is possible to have $k<2^r$. The good numbers yield more efficient MVCs. Prior to this work, there are only {\em finitely many} good numbers. All of them were obtained via computer search and have the form $m=p_1p_2$. In this paper, we study good numbers of the form $m=p_1^{α_1}p_2^{α_2}$. We show that if $m=p_1^{α_1}p_2^{α_2}$ is good, then any multiple of $m$ of the form $p_1^{β_1}p_2^{β_2}$ must be good as well. Given a good number $m=p_1^{α_1}p_2^{α_2}$, we show an explicit method of obtaining smaller good numbers that have the same prime divisors. Our approach yields {\em infinitely many} new good numbers.

Yan He, Liang Feng Zhang

The problem of securely outsourcing computation to cloud servers has attracted a large amount of attention in recent years. The verifiable computation of Gennaro, Gentry, Parno (Crypto'10) allows a client to verify the server's computation of a function with substantially less time than performing the outsourced computation from scratch. In a multi-function model (Parno, Raykova, Vaikuntanathan; TCC'12) of verifiable computation, the process of encoding function and the process of preparing input are decoupled such that any client can freely submit a computation request on its input, without having to generate an encoding of the function in advance. In this paper, we propose a multi-matrix verifiable computation scheme that allows the secure outsourcing of the matrix functions over a finite field. Our scheme is outsourceable. When it is used to outsource $m$ linear functions, the scheme is roughly $m$ times faster and has less communication cost than the previously best known scheme by Fiore and Gennaro (CCS'12), both in the client-side computation and in the server-side computation. We also show the cost saving with detailed implementations.

Liang Feng Zhang

Outsourcing computation has gained significant popularity in recent years due to the prevalence of cloud computing. There are two main security concerns in outsourcing computation: how to guarantee the cloud server performs the computation correctly and how to keep the client's data secret. The {\em single-server verifiable computation} (SSVC) of Gennaro, Gentry and Parno (Crypto'10) enables a client to delegate the computation of a function $f$ on any input $x$ with both concerns highly relieved, but only results in {\em computationally secure} schemes that {\em lack practical efficiency}. While the SSVC schemes use a single server, in this paper we develop a {\em multi-server verifiable computation} (MSVC) model where the client shares both $f$ and $x$ among multiple servers, each server performs a set of computations on its shares, and finally the client reconstructs $f(x)$ from all servers' results. In this MSVC model we propose a generic construction for outsourcing computations of the form $F{\bf x}$, where $F$ is a matrix and $\bf x$ is a vector. Our generic construction achieves {\em information-theoretic security, input privacy} and {\em function privacy}. By optimizing the parameters, we obtain both a 3-server scheme,which uses the least number of servers, and a 4-server scheme, which incurs the least workload. By decomposing many polynomial computations as a two-stage computation, where the first-stage has the form $F{\bf x}$ and the second-stage is fast, and delegating the first-stage computation, we obtain MSVC schemes for these polynomials. We implement our MSVC schemes and show that they are among the most {\em practical} ones to date.

Xin Chen, Liang Feng Zhang

Homomorphic secret sharing (HSS) allows multiple input clients to secret-share their data among multiple servers such that each server is able to locally compute a function on its shares to obtain a partial result and all partial results enable the reconstruction of the function's value on the outsourced data by an output client. The existing HSS schemes for {\em high-degree} polynomials either {\em require a large number of servers} or {\em lack verifiability}, which is essential for ensuring the correctness of the outsourced computations. In this paper, we propose a two-server verifiable HSS (VHSS) model and construct a scheme that supports the computation of high-degree polynomials. The degree of the outsourced polynomials can be as high as a polynomial in the system's security parameter. Despite of using only 2 servers, our VHSS ensures that each single server learns no information about the outsourced data and no single server is able to persuade the client to output a wrong function value. Our VHSS is significantly more efficient. When computing degree-7 polynomials, our scheme could be 3-10 times faster than the previously best construction.

Liang Feng Zhang, Rehanehi Safavi-Naini

{\em Verifiable computation} (VC) allows a computationally weak client to outsource the evaluation of a function on many inputs to a powerful but untrusted server. The client invests a large amount of off-line computation and gives an encoding of its function to the server. The server returns both an evaluation of the function on the client's input and a proof such that the client can verify the evaluation using substantially less effort than doing the evaluation on its own. We consider how to privately outsource computations using {\em privacy preserving} VC schemes whose executions reveal no information on the client's input or function to the server. We construct VC schemes with {\em input privacy} for univariate polynomial evaluation and matrix multiplication and then extend them such that the {\em function privacy} is also achieved. Our tool is the recently developed {mutilinear maps}. The proposed VC schemes can be used in outsourcing {private information retrieval (PIR)}.

Yeow Meng Chee, Huaxiong Wang, Liang Feng Zhang

Extended private information retrieval (EPIR) was defined by \cite{BCPT07} at CANS'07 and generalized by \cite{BC09} at AFRICACRYPT'09. In the generalized setting, EPIR allows a user to evaluate a function on a database block such that the database can learn neither which function has been evaluated nor on which block the function has been evaluated and the user learns no more information on the database blocks except for the expected result. An EPIR protocol for evaluating polynomials over a finite field $L$ was proposed by Bringer and Chabanne in \cite{BC09}. We show that the protocol does not satisfy the correctness requirement as they have claimed. In particular, we show that it does not give the user the expected result with large probability if one of the coefficients of the polynomial to be evaluated is primitive in $L$ and the others belong to the prime subfield of $L$.