Tag Info

14

Well, cryptographers have been contemplating a post-quantum world for some time now. Quantum computing, although in its infancy as far as real-life computers go, has been studied in a theoretical sense for a quite a while. Shor's algorithm was published 19 years ago; Grover's, 17 years ago. These are the two most-famous quantum algorithms, I think, but the ...

8

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

6

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

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

6

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

5

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

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

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

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

3

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

3

If he chooses $s$ at random, then the scheme will be stateless but will fail after using the same $s$ twice, which should happen after giving approximately $\:$$\Theta$$\big(\hspace{-0.05 in}$ $2^{H/2}$$\hspace{-0.01 in}\big)\:$ signatures. If he chooses $s$ by applying a PRF to $g(m)$, then the scheme will be deterministic and stateless, but can be ...

3

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

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

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

$w$ is a parameter that can be freely chosen, to maximize performance. Each element of the signature encodes $w$ bits of the message to be signed, so the larger $w$ is, the fewer elements you need to include in the signature. If you make $w$ large, then signatures can be shorter; however, the tradeoff is that key generation, signing, and verification run ...

2

The security of the LD scheme can be reduced to the one-wayness (aka preimage resistance) of the used hash function. The reduction is quite easy: Assume you want to invert the one-way function $f$ for image $y=f(x)$, given a forger for LD-OTS. Then you generate a valid LD key pair using $f$, sample a random position i in the key pair and a bit b and ...

2

Summary. The short answer is: Cryptography would be insecure. Any encryption you can do with a non-deterministic algorithm, can be broken (in approximately the same running time) by another non-deterministic algorithm. Non-determinism is extremely powerful. If you give everyone access to non-determinism, then secure encryption becomes impossible: the ...

2

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.

2

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

2

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

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

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.

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

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

1

As I already outlined in this answer, hash trees in combination with any one-time signature scheme gives the so called Merkle signature scheme. I assume there is some misunderstanding and therefore I sketch merkle signatures subsequently: The idea is to produce $n$ key pairs $(X_i,Y_i)$ of a one-time signature scheme and then to take the hash values ...

1

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

1

First, the passage you refer to is on page 55, 2nd paragraph. And it would also be great if you'd announce that figure 4.1 is actually in a different document ;-) took me quite a while to figure this out. Now to your question. So, I assume you understand the paragraph? You have to note that a round here corresponds to $2^{(i-1)h}$ "whole tree rounds". Now, ...

1

Adding more qubits does not increase the computation speed. A quantum computer with 4 qubits does not factorize faster than one with 2. The qubits are the "memory" of the quantum computer. More qubits mean you can factor bigger numbers. If I remember correctly, you need a superposition of $\Theta(N^2)$ terms, which means $\Theta(\log(N^2))$ qubits to factor ...

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

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