Thread by @grittygrease

I’ll be tweeting about some post-quantum crypto things as the come up this week in this thread.

LEDAkem is a code-based crypto primitive for key encapsulation based on quasi-cyclic low-density parity-check codes (QC-LDPC). Large-ish keys (7KB+), slow (100ms+), but compact private keys, only simple binary field math and based on NP-complete problem. ledacrypt.org

Learning Parity with Noise (LPN) is a problem used in code-based crypto. A new algorithm to decode linear codes with many errors was introduced that reduces the security level of some LPN schemes. Key idea is the use of the nearest neighbor search. eprint.iacr.org/2017/1139.pdf

ParQ is a new coding-based cryptography primitive based on quasi-cyclic moderate density parity-check (QC-MDPC) codes suitable for repeated use. This was developed during research on existing QC-MDPC schemes in which the authors found a timing attack. eprint.iacr.org/2018/256.pdf

Niederreiter (1986) is a variant of McEllice (the original code-based cryptosystem). Goppa codes are family of error-correcting codes. Niederreiter is secure when used with the binary Goppa code. This was implemented in FPGAs using optimized merge sort. eprint.iacr.org/2017/1180.pdf

Each of these fields of cryptography its own set of trapdoor functions with cool names. Multivariate Quadradic crypto has Matsumoto-Imai Scheme A (MIA), Hidden Field Equations (HFE), Unbalanced Oil
and Vinegar (UOV), and Stepwise Triangular System (STS). pdfs.semanticscholar.org/5b2d/cf1c2f5d3…

MQ crypto is also an active field. The AJPS Mersenne-based
Cryptosystem from last year (based on NTRU with Mersenne numbers(!)) has been weakened the classical and the quantum setting using a meet-in-the middle attack and locality-sensitive hashing. homepages.cwi.nl/~rdewolf/publ/…

Meet-in-the middle is an attack that reduces the cost of a brute force attack at the cost of storage. It's why 3DES was introduced instead of 2DES. en.wikipedia.org/wiki/Meet-in-t…

Locality-sensitive hashing is a way of hashing high-dimensional data (think vectors) such that the output is clustered similarly based on some distance metric. A shadow is a locality-sensitive hash of an object. en.wikipedia.org/wiki/Locality-…

Some researchers implemented the Joux-Vitse Crossbred algorithm (lots of linear algebra) to attack MQ systems on GPUs. Really cool diagrams here. eprint.iacr.org/2017/1181.pdf

Indeterminate Equation Cryptosystem (IEC) from 2017, is also now broken. The cryptanalysts adapted an attack by Craig Gentry (the fully homomorphic crypto guy) from 2001 attack against NTRU-Composite. Foiled by the use of composite numbers again!
eprint.iacr.org/2017/1224

This algorithm is also called Giophantus. It can be considered a special case of Module Learning With Errors (similar to Ring-LWE). Gentry’s attack was nicknamed “origami” because it involves something akin to folding. The new attack cracks keys in under a day.

We're also learning more about elliptic curves. Joost Renes introduced new efficient formulas for 2-isogenies between Montgomery curves. This can be used to do Supersingular Isogeny Diffie-Hellman (SIDH) without expensive square root operations. eprint.iacr.org/2017/1198.pdf

Future work: this can also apply to Tate normal form curves (a generalization of Montgomery curves where the point at infinity is order n instead of 2). It also may be possible for this to apply to Edwards curves by combining this with eprint.iacr.org/2011/430.pdf

With recent results (eprint.iacr.org/2018/313.pdf) and key compression, safe SIDH/SIKE keys can be as small as 200B. Compression is expensive, but is getting faster. You need to compute bilinear pairings and discrete logs (not too expensive due to MOV attack). eprint.iacr.org/2017/1143.pdf

MOV is cool. Supersingular curves have the same number of points as elements in the base field, so you can solve DL on the curve by solving DL on the underlying field (cheap as factoring) using pairings. The badness of supersingular curves in DL crypto helps make SIDH PQ-safe.

These latest compression enhancements make use of something called Elligator 2, which is a way to map points on the curve to random-looking strings and back. However this only works on curves with a point of order 2 (sorry NIST curves). elligator.cr.yp.to/elligator-2013…

It also introduces a faster point tripling algorithm 5M+6S vs (6M+5S), an underrated enhancement.

There are also interesting quantum-resistant versions of "fancy" privacy-preserving crypto including ring signatures, which are used to provide some measure of anonymity for CryptoNote-based cryptocurrencies like Monero and group messaging protocols. eprint.iacr.org/2017/1154.pdf

Group signatures are similar to ring signatures but they permit anonymity revocation. You can build a quantum-safe group signature using Hash-based signatures, which is 70s crypto using only Merkle trees and hash functions. eprint.iacr.org/2018/274.pdf

That’s it for today. Follow @PQCryptoConf for more!

So the team at Microsoft would like us to know that they’re working on a quantum computer with qubits that last for multiple seconds before decohereing. Single-bit quantum computers for sale by the end of the year. microsoft.com/en-us/research…

Using it requires superconducting materials chilled to near absolute zero and a way to actually interact with and manipulate the quantum bits without freezing our classical computers. It’s safe to say we’re still years away from a quantum computer able to factor non-trivial RSA.

Simple Remote Password (SRP) is a protocol to authenticate remotely using a Password Augmented Key Exchange (PAKE) protocol. Square Rainbow Plus (also SRP) is a (now-broken) multivariate encryption scheme based on multiple layers of "oil and vinegar," a flavorful Rainbow.

It's not clear if you can create PAKEs from an SRP-inspired protocol like HFERP. Expect it to take at least a minute to log in with SRP using an SRP-based PAKE if it did exist. Linking to the PQCrypto copy of this paper (these will all expire in a months) link.springer.com/chapter/10.100….

I missed the Lattice-based Cryptography session, but the talks looked interesting. Lattice schemes are promising, but when you first learn about how they work it sounds a bit like nonsense. Learning with errors sounds like an autocorrect algorithm, not a hard crypto problem.

Identity-based cryptography (IBE) is a higher-order version of public key crypto. It admits encryption that scales to a large number of participants without a pairwise setup. In the classical crypto world, efficient implementations of IBE often need elliptic curve pairings.

There is now a new proposal for efficient IBE based on the combination of two lattice features defined earlier this decade, ABB (2010) and the Peikert and Micciancio trapdoor (2012). link.springer.com/content/pdf/10…

Again, this also depends on the Learning With Errors problem, which is so important to cryptography and computer science in general that Oded Regev was awarded the Gödel prize in 2018 for his 2005 discovery of it. eatcs.org/index.php/comp…

Lattice-based crypto is an active area and may end up being a NIST finalist for a quantum-safe key agreement protocol. A variant called New Hope has been tested in production by Google Chrome and the key large key size was found to be "ok" security.googleblog.com/2016/07/experi…

As mentioned earlier, hash-based signatures is another promising arena. The main drawback of most of hash-based schemes is that private keys can only be used a finite number of times. This violates many assumptions implicit in how digital signatures are currently used.

SPHINCS is a framework for doing hash-based signatures in a stateless manner. However, hash-based signatures should be used with caution, as demonstrated by this recent fault attack: eprint.iacr.org/2018/102.pdf

Hash-based signatures don't depend on many of the mathematical properties used by other constructions, only the one-wayness of the hash function. This gives more confidence that they will resist attacks compared to, say, lattice or isogeny-based crypto.

Hash functions are something we are still learning more about. One of the main properties of a cryptographic hash function is that it should be computationally infeasible to find two inputs that have the same output. Just last year, a collision was found in SHA-1.

Recently, Keccac was chosen as SHA-3, though there are still questions about its parameter choices. Still, Keccac team is actively working on new applications of the sponge construction, the underlying primitive. Farfalle, for example. keccak.team/farfalle.html

Against a quantum adversary, the sponge construction may not provide all the same security properties that it currently does. eprint.iacr.org/2017/771.pdf

In any case, the performance of SPHINCS has been analyzed with various hash functions, including SHA-256 and Keccac, on different Intel and AMD platforms. Looking forward to ARM results. The signatures are large and slow to compute, but quick to verify. eprint.iacr.org/2017/898.pdf

And I just realized I've been spelling Keccak wrong. Oh well, at least it's hard to use wrong in protocols, unlike SHA-2.

Whoa! CSIDH to be published in a week. Diffie-Hellman style key exchange based on class group action on isogeny volcanoes using supersingular curves over prime fields. No Fujisaki-Okamoto for public keys validation so static-static possible! 256B keys for 128bit, <50ms poc code.

The NIST PQC Standardization Conference kicks off with @hashbreaker describing post-quantum RSA. 1 TB keys. It has a legitimate security analysis and actually works (they implemented it). This was a brilliant troll. cr.yp.to/papers/pqrsa-2…

Next is David Jao on Supersingular Isogeny Key Encapsulation (SIKE) based on SIDH. The only competition entrant from the newest family of quantum-safe (hopefully) algorithms: isogeny-based cryptography. First mentioned in 1996 by Couveignes. sike.org