[tor-dev] [proposal] Post-Quantum Secure Hybrid Handshake Based on NewHope

William Whyte wwhyte at securityinnovation.com
Fri May 13 14:59:40 UTC 2016

Hi all,

> 3. The only implementation that mitigates decryption failures completely,
killing information leaks to adversaries.

This is clearly a nice-to-have feature, but it comes with a tradeoff. To
remove decryption failures you need to increase the parameter q, but this
affects size (and so performance) in two ways: first, the key and
ciphertext are arrays of integers mod q, so obviously increasing log_2(q)
increases key and ciphertext size; but second, increasing q makes lattice
reduction attacks more effective, so it means that you need to increase the
dimension parameter N as well to get the same level of lattice security.
Conversely, it's not difficult to calculate upper bounds on decryption
failure probabilities, so it's straightforward to find a q that gives less
than 2^-k chance of a decryption failure. There's no particular need for a
decryption failure probability that's less than the security of the other
parts of the cryptosystem.

Just wanted to explain why the standardized NTRUEncrypt parameter sets
(from https://github.com/NTRUOpenSourceProject/ntru-crypto) are chosen the
way they are, i.e. to have nonzero decryption failure probability. We could
have chosen larger q and N but didn't think the tradeoff is worth it.
Obviously the other point of view is legitimate too.



On Thu, May 12, 2016 at 9:51 PM, <bancfc at openmailbox.org> wrote:

> Some great developments in lattice-based crypto. DJB just released a paper
> on NTRU Prime:
> 1. Competitively fast compared to the leading lattice-based cryptosystems
> including New Hope.
> 2. Safer implementation of NTRU that avoids vulnerable ring structures and
> runs in constant-time.
> 3. The only implemntation that mitigates decryption failures completely,
> killing information leaks to adversaries.
> 4. Includes some handy advice for "transitional cryptography" - mixing and
> matching classical signature schemes with PQ public-keys.
> https://ntruprime.cr.yp.to/ntruprime-20160511.pdf
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160513/6f345449/attachment.html>

More information about the tor-dev mailing list