Tag Info

Hot answers tagged

10

Do the post-quantum ciphers also automag/tically address the 1st problem? Not really, however to explore that in any detail, we need to explore what the 1st problem is. If $P=NP$ is proven true, what does that practically mean? Well, it might have absolutely no practical ramifications, or it might mean that virtually all known cryptographical systems ...


6

Current symmetric cryptography and hashes are actually believed to be reasonably secure against quantum computing. Quantum computers solve some problems much faster than the best known classical algorithms, but the best known quantum attack against AES is effectively "try all the keys." In a quantum computer, the time taken to solve a general search problem ...


6

The statement a 15360-bit RSA key is the equivalent to a 256-bit symmetric key does not take into account quantum algorithms. In fact, it is based on a specific computation model. It is just based on the fact that there exist sub-exponential algorithms for factoring and therefore you need longer keys than when using symmetric-key crypto where it is ...


5

Actually, most of the primitives that are currently believed to be secure FHE methods would appear to be quantum resistant; a partial list would include Craig Gentry's original scheme based on ideal lattices, BGV (based on ring-LWE), and this NTRU-based approach. All three are based on hard problems that are not susceptible to Shor's algorithm.


5

If you need security against quantum attacks, there aren't that many options. I would go for a lattice-based encryption like NTRU or something based on ring learning with errors. There are no "magic numbers" involved and the assumptions they are based on have been scrutinized by the academic community. NTRU has been around for a decade and has pretty good ...


5

First of all there does exist information theoretically secure message authentication codes suitable for use with a one time pad. An HMAC is not one of those information theoretically secure. As far as I recall the first article presenting such a construction is the 1981 article by Wegman and Carter: New hash functions and their use in authentication and ...


5

I believe that the conjugacy search problem is broken by probabilistic attacks (see chapter 7). I am not sure if this completely ends braid cryptography, however, since there are other difficult problems in braid groups that have not been studied extensively.


4

An old thread, but I thought it deserved an answer. Information-set decoding In short, the idea behind information-set decoding is to pick a sufficiently large set of error-free coordinates in a sent codeword such that the corresponding columns in the generator matrix form an invertible submatrix. Then, the information sequence can easily be obtained by ...


4

In order to answer this question, we need to understand the basis behind all of modern cryptography, which is computational hardness. Today, we believe that we know how to construct block ciphers that are secure, except for brute force search (or almost that secure). However, we don't really know this. We also think that factoring is hard, and so on. All of ...


3

The elliptic curve discrete logarithm—like integer factorization and the classic finite field discrete logarithm—is an instance of the abelian hidden subgroup problem. Any abelian (commutative) instance of the hidden subgroup problem can be efficiently solved in quantum computers with (variants of) the Shor algorithm; therefore all of the above problems ...


3

Yes, a stateless hashbased signature method called Sphincs was recently proposed. It works by having a moderately large Merkle tree (similar to what D.W. suggested), but instead of using Lamport or Winternitz one time signatures at the bottom, it uses a hash based few-time signature method; this allows an occasional collision at the very bottom of the tree. ...


3

The Supersingular Elliptic Curve Isogeny Key Exchange that you refer to was first published in 2011 by DeFeo, Jao, and Plut. It builds on but is quite distinct from earlier work by Rostovetsev and Stolbunov in 2006. As a Post Quantum/Quantum Safe replacement for Elliptic Curve Diffie-Hellman (ECDH) it has several good properties: The number of bits that ...


3

In this notation, $f^k(x)$ means "apply $f$ $k$ times in succession". For example, $f^3(x)$ is defined to be $f(f(f(x)))$. Because of this definition $f^a(f^b(x)) = f^{a+b}(x)$ holds trivially (even though we known nothing else about $f$), as the the left side means "do $f$ $b$ times, and then do it $a$ times", while the right means "do $f$ $a+b$ times". ...


3

Symmetric algorithms are secure post-quantum, only with less bits of security (usually about half). That means you only need to care about the authentication and key exchange parts of the cipher suite. Suites that don't use public key authentication or key exchange, i.e. preshared key suites, are post-quantum secure, but not useful in most usecases. There ...


3

Supersingular isogenies are a rather recent attempt at post quantum security. You will have a hard time finding an efficient and secure implementation, and even if you write one yourself, the algorithms have not yet seen that much cryptanalysis. (Although that's a subjective judgement call.) If post quantum security wasn't a concern, you could choose from ...


3

Essentially any IND-CPA-secure lattice-based cryptosystem offers additive homomorphism, up to a predetermined number of operations. I don't know of any IND-CCA1-secure post-quantum candidate that offers any homomorphic property, except Loftus-May-Smart-Vercauteren SAC'11, which is based on a nonstandard "knowledge of error" lattice assumption.


2

Does using a slow-hash on the output of an asymmetric key-exchange offer any more protection in a quantum-computing era? No. $\:$ A quantum attacker would simply find seed even if you didn't use "a slow-hash on" it. Is the algorithm (greatly) diminished, or completely broken? The algorithm will still be completely broken by quantum attacks. ...


2

Properly speaking, forward secrecy is a property of a protocol. The protocol is forward secret if compromise of the long term keys does not allow an attacker to decipher any past communications. (Occasionally a distinction is made between that and perfect forward secrecy, with the latter secure when the attacker also knows e.g. all other session keys.) You ...


2

If "it's a fact (not just theory) that quantum computing will break PKI in less then 10-20 years" then "we still use, advise PKI" because there is only a small amount of currently existing evidence for that fact. Specifically, there are known algorithms which can be used for PKI that are not known to be breakable by feasible quantum adversaries.


2

NTRU private polynomial $f$, as described in Section 9.2.1 of IEEE Std. 1363.1, is computed as $f = 1 + p \cdot F \mod q$, where $F$ is a ternary polynomial of degree $N-1$ with a specific number of coefficients equal to -1, 1, and 0, determined by parameter $d_F$ (i.e., $d_F$ coefficients equal to 1, $d_F$ coefficients equal to -1, and the rest are 0's). ...


2

This [Carter-Wegman] MAC is not, in general, secure in the quantum setting This is true; however we need to ask "what is this setting, and is it a realistic one?" This setting is one where the adversary can ask queries that are composed of a superposition of quantum states, and the oracle returns the superposition of the answers. In other words, the ...


2

Since the time you asked your question some new algorithms have shown great promise. The first set of algorithms are based on the Learning with Errors Problem in over polynomial rings. See http://www.cc.gatech.edu/~cpeikert/pubs/suite.pdf There is also an elliptic curve scheme based around supersingular elliptic curve isogenies. There's a Wikipedia ...


2

I am a little confused about why it is believed to be secure against quantum attacks, couldn't the hash function be attacked? Yes, the attacker could attack the hash function, for example, by trying to find a second preimage (and there are known Merkle Signature Schemes where we can show that forging a signature can be reduced to the second preimage ...


2

We recently discussed this question with some colleagues and this is what we came up with (no guarantees): Grovers algorithm only outputs a correct answer if it is feed with a input set such that the target function evaluates as 1 for a single input and as 0 otherwise. The algorithm then iterates a subroutine $\sqrt{N}$ times (where $N$ is the size of the ...


2

Sorry I will have to answer my own question. I received a mail from Luca De Feo a moment ago. "Nope, I discussed this at length with Jean-François Biasse, and we couldn't find a way to apply this kind of attack to SSIKE." I'll leave this question around for reference for the next person who wonders.


1

Found the answer: The $l$-torsion subgroup is isomorphic to a direct sum of two quotient groups: $E[l] \simeq \mathbb{Z}_n \oplus \mathbb{Z}_n$, hence the basis requires two points and the elements of $E[l]$ are represented by linear combinations of such a basis. [Reference: Elliptic Curves, Washington, section 3.1]


1

Take a look at this chapter (Introduction to post-quantum cryptography by Daniel J. Bernstein). It gives an excellent overview of what is known. (Bottom line, Grover's is the best known today and so this can be thwarted by taking 256 bit keys.)


1

The inventors of the Supersingular Isogeny Key Exchange, Defeo, Jao and Plut have posted some code on GITHUB at: https://github.com/defeo/ss-isogeny-software/ There is also a paper on implementation of this key exchange by some people from the University of Waterloo. Their paper is "Efficient Implementations of A Quantum-Resistant Key-Exchange Protocol on ...


1

Two approaches to Post Quantum Key Exchange that have acceptable bandwidth requirements are the NTRU/Ring-LWE lattice designs and the ECC Isogeny Key exchange you mention. Since the UK spy agency published an attack on a lattice based scheme they had designed, there has been an active discussion between Dan Bernstein and the Lattice Cryptographers over the ...


1

There is some software available for the isogeny key exchange. It was developed by one of the designers of the key exchange (DeFeo). It is available on GitHub her: https://github.com/defeo/ss-isogeny-software/ The key exchange was first published in late 2011 and its security has held up under analysis since then. A 2014 paper from Indocrypt supports ...



Only top voted, non community-wiki answers of a minimum length are eligible