# Tag Info

7

As far as I understand, the HSP is a hard problem such that: some types of HSP (namely those operating in an abelian group) can (theoretically) be solved efficiently on a quantum computer (assuming one can be built); many types of public key cryptosystems can be reduced to the HSP: if you can solve the HSP you can break the key. In particular, integer ...

6

You can do key agreement with asymmetric encryption. Any asymmetric encryption algorithm (post-quantum or not) can be used for key agreement: just choose a random key and encrypt it. Password Authenticated Key Exchange looks harder, because it cannot be applied on just any key exchange or asymmetric encryption scheme. The IPAKE framework can be applied on ...

6

The huge key is definitely an issue. Another is the lack of standardization or recommendations. Should you use OAEP with McEliece, or some other padding? What parameters are actually secure? And so on. Part of the problem is that, while it has been around since the 70s, it was not considered particularly interesting until quite recently—so it probably ...

5

In short, the answer is yes, if the full 512 bit hash output length of Keccak[r=1088,c=512] is used, this provides security up to 2256 operations against Grover's quantum algorithm. Using Grover's algorithm, one can find a preimage of a n-bit hash function in time 2n/2 with a quantum computer. This is a generic attack in the sense that it applies to any ...

5

Wide adoption of an asymmetric encryption algorithm, or a digital signature algorithm, requires at least the following: There must exist a reasonably clear standard which unambiguously says where each byte goes. It must cover endianness and similar issues. PKCS#1 is such a standard, for RSA. The algorithm must provide reasonably good performance, in ...

5

Yes there are. The first publicly accessible McEliece implementation was this one from The Error Correcting Codes (ECC) Page, but it isn't particularly useful for reading, being quite obfuscated. There's INRIA's SECRET group implementation called HyMES that implements something quite similar. FlexiProvider (java library) contains quite a good amount of ...

4

Yes, HMAC with a sufficiently long key will survive Grover's algorithm. Grover's algorithm breaks a cryptosystem with a $n$-bit key using $2^{n/2}$ (quantum) steps of computation. Therefore, in practice, a 128-bit key is likely to survive Grover's algorithm, and a 160-bit key almost surely will. So, HMAC with a 160-bit key is safe against Grover's ...

4

A quantum computer solves the discrete logarithm problem for both finite fields and elliptic curves. Being able to efficiently calculate discrete logarithms implies being able to break Diffie-Hellman, so Diffie-Hellman on either of them is not secure against an adversary who owns a large quantum computer. There might be other groups in which DL problem is ...

4

For authenticated/mutually authenticated key exchange, you can use that piece of TLS. TLS requires public key encryption and a key derivation function for the key exchange (plus a signature algorithm for the PKI, if necessary). There are many post-quantum encryption functions and KDFs are typically based on hashes or MACs, which are also post-quantum. There ...

3

Answering myself... There is now a very analogous alternative to Diffie-Hellman in post-quantum cryptography: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies The research paper is very new, but if the results turn out to be secure, this is a very competitive key agreement scheme for post-quantum cryptography.

3

Grover's Algorithm would allow searching an unsorted database with N entries in $O(\sqrt{N})$ time rather than in the usual $O(N)$ time. For AES-256 it currently takes an average of $n/2$ guesses to break, i.e. $2^{255}$. However with quantum computing this can be done in $2^{128}$ time, which is very much faster. And on top of that that's only brute force ...

3

We looked into post-quantum digital signature schemes for the Tahoe-LAFS "100 Year Cryptography" project but I stopped looking at all but one of them when David-Sarah Hopwood observed that they all rely on a secure hash function to generate a message representative for the digital signature scheme to sign. Therefore, all of them (except for that one) are ...

3

In cryptography, you care not merely that some problem is hard but that hard instances are readily producible. Why don't people use NP-complete problems for cryptography, for example? An NP-complete problem would give you greater confidence asymptoticly speaking for two reasons : If any NP-complete problem were collapsed to P, then factoring becomes P ...

2

First, lets get some thing clear over here. The analysis of Grover's algorithm is asymptotic, so it is fairly unfair to perform something as concrete as the setting you have mentioned. Grover's algorithm gives you an asymptotic upper bound of $O(\sqrt{N})$ for searching in an unsorted array of size $N$ so I have trouble understanding how one can claim that ...

2

It depends on the application. If you are using the block cipher as a hash function or for a MAC (say in CBC-MAC fashion), then it very well could create problems. Preimage attacks would be much easier than they should. For normal encryption, however, there wouldn't be a problem since the key is not known to the attacker. As evidence of this, consider ...

2

My impression is that there is no production ready post quantum scheme ATM. NTRU seems to be decent (complete spec, reasonable parameter-sizes and performance), but I think it's patented. No idea about the licensing terms. But whatever scheme you choose, don't use it instead of a conventional scheme(RSA, DH, ECDH) but in addition to a conventional scheme. ...

2

Biclique cryptanalysis is the current best known attack on AES. It reduces the security of AES-256 from $2^{256}$ to $2^{254.4}$. Related key attacks are not practical attacks as they should never occur in the wild. they are symptomatic of a poor implementation, and contrary to the recommended use of AES. The best known theoretical attack is Grover's ...

2

The open source version of CyaSSL contains code that calls into the commercial NTRU library -- the library itself is missing of course. You might be able to make CyaSSL work with the open source NTRU implementation at https://github.com/tbuktu/libntru ; it's alpha level software though.

2

Well, that would work, but identification is not enough for SSL. You would need to make the PKE scheme one-way against CCA1 attacks. $\:$ (On the other hand, it wouldn't need any semantic security.) $\:$ Sending back H(S') would change the required security notion to one that's even farther from what's been studied. You could use a tag-based PKE scheme ...

1

If the school has graduate courses that interest you and you think you can do well in (i.e. for comprehensive exams), and there is a strong crypto research group there, I would recommend any school that satisfied these criteria. As you move through academics, it becomes more and more clear that the quality of your research is the most important, and it is ...

1

All mathematical groups can be used to perform an ElGamal encryption, so that is a first kind of math. That's where elliptic curves are useful: they have a group structure. If you find a group, you can build a cryptosystem out of it. However, as @poncho pointed out, different groups have different properties with regards to security. For instance, elliptic ...

1

Diffie-Hellman isn't necessary for key agreement; it's relatively rarely used in TLS, which is among the most widely used secure protocols. DH without authentication is trivially susceptible to a man in the middle, so practical systems have to have an authentication mechanism in place anyway. Once you have authentication via one of the mechanisms you ...

1

The hidden subgroup problem is very useful for developing an understanding of pairing-based non-interactive zero-knowledge proofs. You would need a suitable elliptic curve of large composite order in order to use the hidden subgroup problem securely so in practice, you probably wouldn't bother as the implementation would be very slow. However, the ...

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