## Analysis and Implementation of An Efficient Ring-LPN Based Commitment Scheme

Helger Lipmaa and Kateryna Pavlyk. Analysis and Implementation of An Efficient Ring-LPN Based Commitment Scheme. In David Naccache and Mike Reiter, editors, CANS 2015, volume ? of Lecture Notes in Computer Science, pages ?--?, Marrakesh, Morocco, December 8--12, 2015. Springer, Heidelberg.

File: [.pdf (491 KB)] pdf recommended.

Abstract:

We analyze an efficient parallelizable commitment scheme that is statistically binding and computationally hiding under a variant of the decisional Ring-LPN assumption, conjectured to be secure against quantum computers. It works over medium-size binary finite fields, with both commitment and verification being dominated by $38$ finite field multiplications. Such efficiency is achieved due to a precise analysis (that takes into account recent attacks against LPN) of underlying parameters. We report an initial parallel implementation by using the standard OpenCL library on three different platforms. On the AMD Radeon HD 7950 GPU, one can commit to $1024$-bit messages in $1$ bit per $104.7$ cycles. We consider the analysis (which results in concrete parameters that subsequent work can try to falsify) together with the implementation the two most important aspects of the current work..

Keywords: commitment schemes, GPU implementation, learning parity with noise, postquantum.

Authors:

Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa>gmail.com.