In this work, we introduce a new technique that improves the above scheme, offering an acceleration factor up to 2.8, depending on the set of parameters.
Namely, we improve the unnatural geometric bound used in Bliss to a tighter and much more natural bound by using some extra degree of freedom: the ternary representations of binary challenges. Precisely, we efficiently choose a ternary representation that makes the result deterministically shorter than the expected length for a random challenges.
Our modified scheme Bliss-b is rather close to the original scheme, and both versions are compatible. The patch has been implemented on the Open-Source Software implementation of Bliss, and will be released under similar license.
Category / Keywords: public-key cryptography / Lattice Based Cryptgraphy, Signature, Bliss Date: received 22 Oct 2014 Contact author: lducas at eng ucsd edu Available format(s): PDF | BibTeX Citation Version: 20141022:230029 (All versions of this report) Short URL: ia.cr/2014/874 Discussion forum: Show discussion | Start new discussion