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.
Attachment:
signature.asc
Description: This is a digitally signed message part
_______________________________________________ tor-dev mailing list tor-dev@xxxxxxxxxxxxxxxxxxxx https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev