[tor-dev] Quantum-safe Hybrid handshake for Tor

[Jeff Burdges]

On Sat, 2016-04-02 at 18:48 -0400, Jesse V wrote:
> I just wanted to resurrect this old thread to point out that
> supersingular isogeny key exchange (SIDH) is the isogeny scheme that
> that you're referring to. Using a clever compression algorithm, SIDH
> only needs to exchange 3072 bits (384 bytes) at a 128-bit quantum
> security level. This beats SPHINCS by a mile and unlike NTRUEncrypt,
> fits nicely into Tor's current cell size. I don't know about key
> sizes, though. If I recall correctly, SIDH's paper also references
> the "A quantum-safe circuit-extension handshake for Tor" paper that
> lead to this proposal.

I should read up on this compression business since I'd no idea they
were so small.  At first blush, these SIDH schemes must communicate
curve parameters of the curve the isogeny maps to and two curve points
to help the other party compute the isogeny on their prime's subgroup,
so maybe 3-4 times the size of a curve point, but the curve is far
larger than any used with normal ECDH too.  

Warning : The signature schemes based on SIDH work by introducing
another virtual party employing a third prime.  And another more recent
scheme needs two additional parties/primes!  A priori, this doubles or
triples the key materials size, although it's maybe not so bad in
practice.  Also, these signature scheme have some unusual properties. 

> Again, I have very little understanding of post-quantum crypto and
> I'm just starting to understand ECC, but after looking over
> https://en.wikipedia.org/wiki/Supersingular_isogeny_key_exchange 
> and skimming the SIDH paper, I'm rather impressed. SIDH doesn't
> seem to be patented, it's reasonably fast, it uses the smallest
> bandwidth, and it offers perfect forward secrecy. It seems to me
> that SIDH actually has more potential for making it into Tor than
> any other post-quantum cryptosystem.

It'll be years before anyone trusts SIDH because it's the youngest.  And
Ring-LWE has a much larger community doing optimizations, etc. 

I like SIDH myself.  I delved into it to see if it offered the blinding
operation needed for the Sphinx mixnet packet format.  It seemingly does
not.  And maybe no post-quantum system can do so. 

All these post-quantum public key systems work by burring the key
exchange inside a computation that usually goes nowhere, fails, etc.*
In SIDH, it's replacing the kernel of the isogeny, which one can move
between curves, with two curve points that let the other party evaluate
your isogeny on their subgroup.  As the isogenies themselves form only a
groupoid, algorithms like Shor observe almost exclusively a failed
product, so the QFT rarely yields anything. 

As usual, there are deep mathematical questions here like : Has one
really hidden the kernel by revealing only the isogeny on a special
subgroup?  Are there parameterizations of appropriate isogenies in ways
that make the QFT dangerous again?  

As an aside, there are new quantum query attacks on symmetric crypto
like AEZ in: http://arxiv.org/abs/1602.05973 
We believe a quantum query attack against symmetric crypto sounds
unrealistic of course: http://www.scottaaronson.com/blog/?p=2673 
A quantum query attack is completely realistic against a public key
system though, so one should expect renewed effort to break the
post-quantum systems by inventing new QFT techniques.


On Sun, 2016-04-03 at 06:52 +0000, Yawning Angel wrote:
> Your definition of "reasonably fast" doesn't match mine.  The number 
> for SIDH (key exchange, when the thread was going off on a tangent 
> about signatures) is ~200ms.  

What code were you running?  I think the existing SIDH implementations
should not be considered optimized.  Sage is even used in : 
https://github.com/defeo/ss-isogeny-software  
I've no idea about performance myself, but obviously the curves used in
SIDH are huge, and the operations are generic over curves.  And existing
signature schemes might be extra slow due to this virtual third or
fourth party.  I know folks like Luca De Feo have ideas for optimizing
operations that much be generic over curves though.  


Around signatures specifically, there are deterministically stateful
hashed based, or partially hash based, scheme that might still be
useful :  One might for example pre-compute a unique EdDSA key for each
consensus during the next several months and build the Merkle tree of
the public keys of their hashes.  Any given consensus entry is
vulnerable to a quantum attack immediately after the key gets used, but
not the whole Merkle tree of EdDSA keys.  A signature costs O(log m)
where m is the number of consensuses covered by a single key.  It's
maybe harder to attack such a scheme while keeping your quantum computer
secret. **

Jeff

*  I'd be dubious that any non-abelian "group-based" scheme would remain
post-quantum indefinitely specifically because they lack this "usually
just fails" property.  It's maybe related to the issues with blinding
operations an the difficulties in making signature schemes.

** I recently found a Merkle tree of encryption keys trick that enables
post-quantum secure refresh operation in Taler. 



-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160403/d52f631f/attachment.sig>