Cryptology ePrint Archive: Report 2018/523

Reducing Complexity of Pairing Comparisons using Polynomial Evaluation

Adam Bobowski and Marcin Słowik

Abstract: We propose a new method for reducing complexity of the pairing comparisons based on polynomials. Thought the construction introduces uncertainty into (usually deterministic) checks, it is easily quantifiable and in most cases extremely small. The application to CL-LRSW signature verification under n messages and group order q allows to reduce the number of computed pairings from 4n down to just 4, while the introduced uncertainty is just (2n-1)/q.

Category / Keywords: foundations / elliptic curve cryptosystem, implementation, polynomials, bilinear maps

Date: received 28 May 2018, last revised 19 Nov 2018

Contact author: marcin slowik at pwr edu pl

Available format(s): PDF | BibTeX Citation

Note: Added funding source acknowledgement.

Version: 20181119:114354 (All versions of this report)

Short URL: ia.cr/2018/523


[ Cryptology ePrint archive ]