# Tag Info

12

Unless Keccak has structural weaknesses that I am not aware of, the answer is surprisingly neither 128 nor 256! Gilles Brassard, Peter Høyer and Alain Tapp describe a sort of quantum birthday attack in their paper "Quantum Cryptanalysis of Hash and Claw-Free Functions" that effectively works by creating a table of size $\sqrt[3]{2^b}$ (versus the ...

7

With any $n$ bit hash it is possible to: Find preimages with work $2^n$ on classical computers and $2^{n/2}$ using quantum computers Find collisions with work $2^{n/2}$ on classical computers and $2^{n/3}$ using quantum computers I want to emphasize that these are generic attacks that always work, no matter which concrete hashfunction is used. Grover's ...

6

I can't agree with bullet 3. of the question stating quantum computers are getting stronger with a good pace (82-qbit computer last year, 512-qbit computer this year), at least in a context of cryptanalysis. Even the marketing people praising the device alluded to do not pretend that it is of a kind useful for cryptanalysis: they state about it: The ...

6

This is highly insecure, for the same reason that ECB mode and simple substitution ciphers are. Every time you use the word the in your message, it will be encrypted the same way. The same goes for other, lower-frequency (but still fairly common) words -- like as or with or will (or any of hundreds of other examples). This is a humongous clue to ...

5

I'm not going to exactly answer your question, because I have no idea. I simply do not know how fast the quantum computer is that NSA is building in secret. However I could explain why people recommend 256-bit security in the face of quantum computing using some numbers. If you feel that $2^{128}$ is a comfortable security against bruteforcing, remember ...

5

"Frequency analysis of the output might help determine simple words in the ciphertext such as 'the' etc if that word is repeated and sent multiple times. This isn't necessarily a problem as it's only a simple word and doesn't convey much meaning to the message". If the word "the" doesn't convey much meaning, then why have you used that particular ...

4

This is a type of code book security. Code books can be very strong or very weak depending on operational security. If you never reuse a code book word even in a single message and the code words are genuinely random - this approach could work. Of course if you can't reuse code words and need perhaps 40 instances of THE and 30 instances BE to avoid ...

4

In the majority of multivariate cryptographic schemes (MQ) the encryption/signature function $E$ is a composition of secret affine invertible transformations $A,B$ and a nonlinear transformation $P$ (can be secret or public): $$E = B\circ P\circ A$$ $P$ is typically invertible, and the goal of the scheme is to make $E$ non-invertible even though it is ...

4

The problem is that the key is essentially random data and thus cannot be meaningfully compressed. Several variations of the McEliece cryptosystem have tried modifying it to produce public keys with special structure which are compressable. However, all such systems have been broken (as far as I know), and it seems that in most cases, adding special ...

4

McEliece NTRU Multivariate If you mean "syntactically public key" instead of "implies the existence of secure key agreement", then there is also hash-based signatures.

3

My understanding is that the attack only works against McEliece with algebraic geometry codes. The paper by Bernstein, Lange and Peters recommends parameters for McEliece with binary Goppa codes, so the attack does not apply against those parameters.

3

It would appear that (for example) Shamir's original threshold secret sharing scheme would meet the requirements of 'post-quantum' (that is, remain secure even if that attacker has access to a Quantum computer). Let us assume that the shares were generated using a truly random stream; in that case, someone with $N-1$ shares (where $N$ is the threshold) does ...

3

I am not quite sure why you are looking for the kind you have mentioned in your question. But good old Shamir's polynomial secret sharing over finite fields, look here, provides information theoretic secrecy, i.e., even a quantum computer will not help you to break the secrecy.

3

Your scheme would make a nice puzzle for amateur codebreakers. That's about the best that can be said for it. It does not meet the generally accepted standards for a modern encryption scheme; in particular, it is not semantically secure. In fact, the security of your scheme would be seriously compromised if an attacker obtained even a small amount of ...

3

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

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

You can build a gigantic, enormous tree that has capacity for up to $2^{80}$ one-time signatures (say). Then, each time you want to sign something, you randomly pick a 80-bit value and use that to select which of the $2^{80}$ subtrees to use to sign the message. As long as the number of messages you intend to sign is much less than $2^{40}$ messages, a ...

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

2

This scheme is very unsecure. In my humble opinion is like a complicated "translate your message into a unknown language". In my opinion it looks like an hashed version of the Windtalkers (WW2 native americans language used to encrypt messages). Your version add one more level: you have few languages (hash functions) to choose among.

2

Probably because they figured that using only one affine map might not be secure. Also, be warned that the Wikipedia article you are citing has serious problems. It is written as though there is a single scheme called "Multivariate Cryptography" with a specific form -- but that is wrong. In fact, multivariate cryptography refers to a class of schemes that ...

2

The Merkle tree signature scheme mainly assumes that the underlying hash function used is cryptographically secure. The pre-image and second preimage properties are especially important here as an attacker should not be able to : find preimage m such that h(m) = public key. (preimage resistance) Otherwise, the verifier may be able tricked into thinking ...

2

As D.W. notes, this works for the purpose in question. Actually, relying on number theoretic assumptions for the accumulators will give you no benefit as you have observed. However, here is a construction of accumulators from Nyberg in FSE'96, which does not rely on number theoretic or any computational assumptions. This is the paper of Nyberg and you may ...

2

Yes, they can be used for that purpose. The challenge in practice is exactly what you mentioned: if we're willing to trust number-theoretic assumptions, we usually don't need Lamport signatures. Nonetheless, they can be used in this way.

2

It seems they can be used for that purpose. I found this paper: "Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees" Niko Baric and Birgit Pfitzmann Eurocrypt '97, LNCS, Springer-Verlag, Berlin 1997.

2

Hash trees alone wont do that. But hash trees in combination with one time signatures (this is called the Merkle signature scheme). If you use hash based one time signatures such as Lamport-Diffie, then yes. Basically, the hash tree is used to "aggregate" $k$ public keys by representing the hash values of the public keys as leaves of the hash tree and ...

2

As you probably know the public key in McEliece is an $k \times n$ binary matrix, encoding a generator matrix for a randomly permuted Goppa code (i.e. $G_{\mathsf{pub}} = SGP$, where $S$ is any $k \times k$ invertible binary matrix, $G$ a $k \times n$ generator matrix for an $(n, k, t)$ binary Goppa code, and $P$ a $n \times n$ permutation matrix). ...

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

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

1

McEliece public keys need about 100 kByte to 1 MByte depending on the desired security level. 65 kB for 80 bits of security (too low, corresponds to 1024 bit RSA) 150 kB for 112 bits of security 220 kB for 128 bits of security 1000 kB for 256 bits of security The McBits paper contains the following table:

1

Firstly, I assume we are talking about classical computers Implementing a brute force attack on a RSA may not be the most sensible thing, unless of course the security parameter of your target system is small.. (160 bit numbers! ) Even then you may not want to implement a brute force here.. try using Fermat's Factoring or Pollards $\rho$ method. If you ...

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