44
The onus is on the company to prove their claims, especially when they are extreme. There is also no financial motivation to not prove their claims. I can understand if they say that they want to keep their new "unbreakable algorithm" secret until they patent it, but what reason in the world would there be to not present a break? This is especially ...
43
It is a bit dubious to claim that hash functions "are not based on any hard problem": inverting a standard hash function, or finding a collision, is itself a very hard problem.
The point of a reduction is to gather the cryptanalytic effort on a smaller number of hypothesis. The fact that RSA-OAEP is CCA secure under the RSA assumption is not a ...
22
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 ...
22
Post-quantum crypto is a very young field and is still changing quite rapidly. If you just want a reading list to introduce you to the topics, I would recommend the March 2015 report released by the EU's PQCrypto Project, and the April 2016 report from NIST.
As of today, here's an (incomplete) list of candidate algorithms for post-quantum cryptography with ...
22
What makes a problem suitable for cryptography is slightly different than what makes a problem NP-hard.
What is required for cryptography is average-case hardness --- i.e., a randomly selected instance of a problem should be "hard" for an adversary to solve. However, random instances of some NP-hard problems (3SAT, e.g.) turn out to be easy with high ...
22
This depends on what kind of hash function you mean and what kind of security you want.
Poly1305 is an almost-universal hash family, which, when used with a uniform random key for a single message, has forgery probability for messages of $L$ bytes bounded by $8\lceil L/16\rceil/2^{106}$. This means that an adversary, given $(m, a)$ where $a = \operatorname{...
20
Is there any functional difference on how this process is conducted?
One likely difference is the intended end goal. The intended result of the AES process was to approve exactly one proposal, and that is what they did. In contrast, they are likely to approve at least two proposals (both for kem/public key encryption, and the signature side of things, so ...
19
How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer?
Like the answer you linked to shows, about $\log_2(N^2) = 2 \log_2(N)$ or just $2n$ where $n$ is the number of bits of the modulus $N$, i.e. the key size of RSA. So 4096 for 2048-bit RSA, double that for 4096-bit.
This paper (PDF) has an algorithm using ...
19
As mentioned in the comments, there is a serious flaw in the paper, and it has been withdrawn: see https://groups.google.com/forum/#!msg/cryptanalytic-algorithms/WNMuTfJuSRc/OtQMLRXgBwAJ and part (3) of http://www.scottaaronson.com/blog/?p=2996
17
With a 1024 qubit quantum computer you cannot break any of the algorithm you mentioned.
Current estimations for an impelmentation of Grover's algorithm for AES requires much more qubits. According to this paper by Grassl et al. the required number of qubits required for AES-256 is 6681, see the following extracted table:
I guess it's not unreasonable to ...
16
The authors themselves point out that this doesn't break lattice-based assumptions used in crypto. To quote:
Lattice problems have received enormous attention in recent years, mainly because of their algebraic structure has allowed constructions of cryptographic primitives, culminating in the Learning-with-Errors (LWE) encryption scheme due to Regev [...
15
Unless I misunderstood the definitions, an algorithm for the problem in Definition 1 (i.e. their main result) is in fact enough to attack decision-LWE if the noise is small. The fact that they need a promise that the point is always close to the lattice doesn't seem to be a problem.
A decision-LWE problem mod q, where samples are of dimension n and the ...
15
Yes, it is feasible. In fact, the NIST post-quantum submissions include a number of lattice-based cryptographic key exchange and signature protocols. As you can see from a summary of the different types of algorithms, lattice-based algorithms dominate the submissions. These include NTRU and its variants, R-LWE, and FALCON (designed in part by one of our ...
15
Edit 2021-02-10: covering now their latest press release
Red flags
While the details of their work/claims are yet to be published, this article is containing a lot of conspicuous statements.
Vinokur said in an interview that Terra Quantum’s team made the discovery after figuring out how to invert what’s called a “hash function,”
This would be a major ...
14
[source of information: my interpretation of multiple hallway chats I've had with DJB and Tanja Lange at conferences]
The actual NIST PQC submission was for two reasons:
A joke. Evidence1: DJB yelling from the back of the room "How much RAM does the NIST benchmarking machine have??" Dustin Moody replying "Dan, we're not benchmarking pqRSA!". Evidence2: DJB ...
14
Is this actually a viable method of key exchange?
No. An eavesdropper can find the integer $b$ chosen by Bob from $x$ (as sent by Alice) and $b'$ (as sent by Bob), and the equation $b'\,=\,b\,x\bmod 1$ (meaning $\exists d\in\mathbb Z,\ b'+d=b\,x$). The shared $k$ can then be determined from the $a'$ sent by Alice, just as Bob does.
If we take the numbers in ...
13
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 (...
13
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 can ...
13
What we traditionally call Elliptic Curve Cryptography (working in the group of points on an elliptic curve over a finite field) is vulnerable to an attack by a quantum computer running Shor's algorithm and is thus not considered a Quantum-Safe or Post Quantum Cryptographic algorithm.
However there is an true Post Quantum Key Exchange algorithm which uses ...
13
AES-256 is still considered the strongest (and is considered secure) as related key attacks are not particular to analysis with quantum computers.
Related key attacks could happen when AES is used within a construction such as a hash function, where the output of one round is used as a key for the next round.
As far as we know now, quantum computing won't ...
12
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.
12
Quantum computers don't attack the protocol, they attack the cryptographic primitives used in the protocol. You need to avoid primitives that can be broken by quantum computers.
Quantum computers don't break all computationally secure cryptography, so you don't have to resort to information theoretic algorithms (one-time-pad).
Symmetric encryption is ...
12
As noted by kodlu, you are basically asking about the existence of the whole field of quantum cryptography (which is different from post-quantum cryptography).
All the field was arguably started by Stephen Wiesner’s invention of Conjugate Coding in 1969, but which was rejected remained unpublished until 1983. He proposed a theoretical way to use quantum ...
12
It has been folklore (since at least 2010) that you can do what you propose, but less efficiently than the "key transport" method of any Ring-LWE based encryption scheme or KEM.
So here is what you can do: there is a public polynomial $a\in Z_q[X]/(X^n+1)$ that is shared by everyone. It needs to be uniformly random, so it can be set to XOF(1), where XOF is ...
12
It allows the security of the construction to be reduced to second-preimage-resistance, rather than collision-resistance. This is a significant distinction, since brute force against collision-resistance is $2^{n/2}$ while brute force against second-preimage-resistance is $2^n$. In short, this XOR trick allows signatures/keys in the scheme to be half as long ...
12
Since I'm not a cryptographer, I wanted to ask when quantum computers will be able to break the crypto algorithms used today and whether this breakthrough has significantly changed the predictions.
No, despite being on the front page of Nature, Google's result has no impact on cryptography for the foreseeable future.
The news about the (rather regrettable) ...
11
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 ...
11
They're actually sampling $5n$ elements from $\Psi_{16}$. Perhaps Protocol 2 on page 5 shows this most clearly, where $\textbf{s}, \textbf{e} \stackrel{\$}{\leftarrow} \Psi_{16}^n$ and $\textbf{s}', \textbf{e}', \textbf{e}'' \stackrel{\$}{\leftarrow} \Psi_{16}^n$ are sampled (on line 3 on Alice' side, and line 1 on Bob's).
This probably also answers part of ...
11
First, some definitions.
A public key encryption scheme (PKE) is a scheme with public and private keys, where we can encrypt a message using the public key and decrypt using the private key.
A key encapsulation method (KEM) is a scheme with public and private keys, where we can use the public key to create a ciphertext (encapsulation) containing a randomly ...
11
It's impossible to construct a strong asymmetric encryption algorithm that relies only on the security of a hash function:
We prove that every key exchange protocol in the random oracle model in which the honest users make at most n queries to the oracle can be broken by an adversary making O(n^2) queries to the oracle.
Boaz Barak, Mohammad Mahmoody-...
Only top voted, non community-wiki answers of a minimum length are eligible