Paper 2017/280
Amortization with Fewer Equations for Proving Knowledge of Small Secrets
Rafael del Pino and Vadim Lyubashevsky
Abstract
For a linear function $f$, a vector $\mathbf x$ with small coefficients, and a vector $y=f(\mathbf x)$, we would like to be able to give a zeroknowledge proof for the knowledge of an $\mathbf x'$ with small coefficients that satisfies $f(\mathbf x')=y$. This is a common scenario in latticebased cryptography, and there is currently no satisfactory solution for this problem. All known protocols are built via the repetition a basic protocol that only has constant ($1/2$ or $2/3$) soundness error. This implies that the communication complexity of the final protocol will be at least a factor of $k$ larger than that of the basic one, where $k$ is the security parameter. One can do better if one considers simultaneously proving the knowledge of many instances of the above linear equation. The protocol that has the smallest amortized communication complexity while achieving closetooptimal slack (i.e. the ratio between the coefficients in the secret and those that can be extracted from the proof) is due to Cramer et al. (Eurocrypt '17) which builds on an earlier work of Baum et al. (Crypto '16). The main downside of this protocol is that the amortization only kicks in when the number of equations is rather large  $4k^2$. This means that for $k=128$, it is only truly optimal when one has more than $2^{16}$ equations to prove. The aforementioned work of Cramer et al. also shows how to achieve a protocol requiring $o(k^2)$ samples, but it is only applicable for much larger values of $k$ and the number of required samples ends up being larger than $2^{16}$. The main result of our work is reducing the concrete minimal number of equations required for the amortization, while keeping the communication complexity almost unchanged. The cost of this is an increase in the running time of the zeroknowledge proof. More specifically, we show that one can decrease the required number of equations by a factor of $\Omega(\log^2{\alpha})$ at the cost of increasing the running time by a factor of $\Omega(\alpha)$. For example, increasing the running time by a factor of $8$ allows us to decrease the required number of samples from $66000$ to $4500$  a factor of $14$. As a side benefit, the slack of our protocol decreases by a factor of $\log{\alpha}$ as well. We also show that in the case that $f$ is a function over the polynomial ring $\mathbb Z[X]/(X^d+1)$ and we would like to give a proof of knowledge of an $\mathbf x'$ with small coefficients such that $f(\mathbf x')=2y$, then the number of samples needed for amortization is even lower. Without any tradeoffs in the running time, our algorithm requires around $2000$ samples, and for the same factor $8$ increase in the running time, the requirement goes down to $850$.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 zero knowledgeprotocolsproofs of knowledgeoneway functions
 Contact author(s)
 afe @ zurich ibm com
 History
 20170802: last of 2 revisions
 20170330: received
 See all versions
 Short URL
 https://ia.cr/2017/280
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/280, author = {Rafael del Pino and Vadim Lyubashevsky}, title = {Amortization with Fewer Equations for Proving Knowledge of Small Secrets}, howpublished = {Cryptology ePrint Archive, Paper 2017/280}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/280}}, url = {https://eprint.iacr.org/2017/280} }