# Tag Info

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 ...

5

No, since finding $a$ allows offline checking of passwords. $\:$ No, although I can't back this part up.

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 ...

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

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

If you look at exact security, the height matters. The reason is that it defines the number of OTS key pairs and hence the possible number of one time signatures per MSS key pair. To forge a MSS signature, it is enough to generate a forgery for 1 out of $2^h$ OTS signatures. Hence you get a reduction in the bit security of $h$ bits.

3

Dinh, Moore, Russell have shown that the quantum algorithm (Quantum Fourier sampling) used to attack RSA and ElGamal does not work on McEliece-like crypto systems. (I think) this means, that there are no known algorithms on quantum computers that decrease the complexity of attacks on McEliece, and thus McEliece is just as safe post-quantum computers as it is ...

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 ...

2

That Wikipedia article is full of errors and false claims. Most importantly, FSB has not been proven to be as hard as an NP-complete problem. This is because the syndrome decoding problem is NP-hard in the worst case, but FSB uses random instances of the problem. Indeed, these random instances may be much easier to break than arbitrary instances. There is no ...

2

One algorithm that is especially suited to one-use key pars is lamport signatures. Like many (all?) other signature functions, lamport signatures first hash the message to get it down to a size that is more reasonable to sign. For this use case, if you are willing to have $n^{2}$-bit signatures and $2n^{2}$-bit keys (public and private), you can sign a ...

2

Choose some 128-bit hash function, such as RIPEMD-128, and a way of randomizing it, such as this. The private key is either 60 uniformly random 128-bit strings s00,s01,...,s58,s59 and a uniformly random short salt or a seed to regenerate those. $\:$ For each i in {00,01,...,58,59}, vi is the result of hashing si 19 times. $\:$ The public key is the ...

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

In general there is no reason to use tree hash modes for Merkle trees. The reason is that a Merkle tree itself is already some kind of tree hash mode. The important thing about this kind of mode is that it allows to compute the root node given the value of one leaf and one node per tree level. The possible ambiguity of hashes is not relevant for hash-based ...

1

The secret key blob consist of 1718 bytes where the first 1500 indicates the corresponding public key. The last 200 ish bytes store the encoded secret key. The secret key is a trinary polynomial with coefficients -1,0,1. So we only need to store the position of non-zero coefficients. The last couple of hundreds of bytes in the encoded secret key suggest ...

1

You can take a look at Dan Berstein's Curve25519. It's a non-NIST, non-NSA curve and he has his own adaptation of DSA that goes with it. However, I suppose it's possible to parallelize an attack on this, so it may not be resistant to quantum computing attacks. As for symmetric encryption, it's important to note that AES was developed by the international ...

1

Lets assume an adversary knows one LD signature for message $M$ as well as public key $pk$ and can generate a forgery for an arbitrary different message $M'$. Clearly, there exists at least one bit position where the messages differ, i.e. $M_i \neq M'_i$, as $M \neq M'$. So, for simplicity assume there is only one bit difference. Then the adversary can take ...

1

Why not use a stream cipher? The requirement for the generating function is not that it is a PRF but a PRG (which in many constructions is build out of a PRF). If you use the key stream of a stream cipher as output then this is a PRG.

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