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 ...
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 ...
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 ...
9
There is also a non cryptographic alternative. From their site :-
"IP and legal rights" suggests that they are IP savvy. They may be after a patent for an attack algorithm/appliance against symmetric ciphers. Much like Terahash appliances and cell phone interceptors. A patent award requires that the applicant:-
Demonstrate aesthetic design or ...
9
The webpage you referenced shows the First-, Second-, and Third-Prize winners of the Chinese national cryptographic algorithm design competition, which was held in Chengdu on July 22, 23. The goals were to support the construction of new network security systems and the 14th five-year plan of industry. The meeting hoped to promote a new era of industrial ...
7
It clearly reminds me of the Treadwell Stanton DuPont story. Just to add some numbers on the current state-of-the-arts methods on these topics :
the best quantum known attack on complete AES is using Grover (which is still $2^{138.8}$ in its 256-bit version, using 2k+ qubits). As far as I know, the best quantum attacks on reduced-rounds AES are barely ...
7
I am unaware of cryptography that is hard solely assuming that $P\neq NP$, so I believe you are misunderstanding something. I know the story best when it comes to lattices, so I'll discuss why lattices are solely "adjacent" to an $NP$-hard problem.
The story is rather simple, but also technical.
Let $\mathsf{LWE}[n, \sigma, q]$ be the average-case ...
6
Is it legit?
No, and you hit on the reason - the algorithm converts the message into a series of 16 values from 1 to 128, and then signs based only on that. That's a total of 112 bits; actually, it's somewhat worse than that, as the algorithm they use to convert the message hash into the series of 16 values will generate values that always sum (mod 128) to ...
6
Why are classical cryptanalysis methods -algebraic, mathematical attacks etc.- more effective on classical algorithms than post-quantum algorithms?
I feel that this is a little unfair on some excellent mathematical work. The recent developments in lattice algorithms such as saturation and sieving (see Alberecht et al "The General Sieve Kernel
and New ...
5
They don't need to be: isogeny-based cryptography has no connection to any NP-complete problems, as far as I am aware.
Generally you want the underlying mathematical problem to be hard, and you can't get "harder" than NP, since (to be very imprecise) the secret key of a public-key cryptosystem acts like a "witness" for any hard problem ...
5
Can anyone explain why?
That is because NIST specifically stated that stateful schemes were not allowed in the NIST postquantum competition, because they could not be implemented using the API that NIST has defined (which does not allow any state).
That would appear to be reasonable, as stateful hash based signature methods do need extra care to implement ...
5
There is only one paper I know of which explains a post-quantum key exchange algorithm in such a way that a beginner could understand it, and that is for SIDH (Supersingular Isogeny Diffie-Hellman key exchange). The paper is called Supersingular isogeny key exchange for beginners.
Abstract. This is an informal tutorial on the supersingular isogeny Diffie-...
5
I could not reproduce the exact bit complexities from the mentioned paper [1], the authors did not provide the source code. I'm posting my estimators for MMT and BJMM attacks here.
The conclusion that BJMM algorithm is worse than MMT is incorrect because MMT is a special case of BJMM. Briefly, BJMM is MMT with no representations of type $1 = 0+0 \bmod 2 $ ...
5
They must be using the $\|a\|-\|b\| \le \|a+b\|$ variant of the triangle inequality (see Wolfram MathWorld).
For those of you following along, this is all at the end of page 5. They start with the following fact:
$$
\bigl\| w + \lceil q/2 \rfloor \cdot m - \lceil q/2 \rfloor \cdot m' \bigr\|_\infty \le \lceil q/4 \rfloor.
$$
Apply the triangle inequality ...
5
NSA removed EC-256 and SHA-256 from CNSA recently--should we be alarmed by this?
No.
There is one overwhelming reason why, as stated in the document:
The cryptographic systems that NSA produces, certifies, and supports often have very long lifecycles. NSA has to produce requirements today for systems that will be used for many decades in the future, and ...
5
I noticed that almost all third party cryptanalysis papers consist of side-channel attacks.
Well, there certainly are papers examining the strength of these postquantum algorithms and the hardness of the hard problems they are based on - they may be a minority at this point.
Part of the issue is the publishability; at the moment, most of the cryptanalytic ...
5
…Public keys are derived from private keys using ECDSA … using secp256k1.
Not quite. The transformation of private key to public key is not using ECDSA. It's per the parameters of secp256k1, using an operation called point multiplication, and towards making the public/private key pair usable later for ECDSA.
This is a one-way function… until you take into ...
4
Out of curiosity, what is the current state of the art on the sampling over $D_{\mathbb{Z},\alpha q}$
This is a fairly involved question to answer. There are a number of competing ways to sample it, which you can roughly divide into:
Techniques that work for any probability distribution
Techniques that are specific to the discrete Gaussian
Table 1 of [...
4
I encourage you to read section 3.1 of Generalized Compact Knapsacks are Collision Resistant, where it is first defined.
The answers to your questions are:
I can find information for the factor in terms of vectors, but I don't understand it in terms of polynomials.
The idea behind the "Expansion Factor" way of defining a norm on $R = \mathbb{Z}[x]...
4
Lattice-based cryptography is based on the hardness of certain lattice problems (almost tautologically). The region marked "crypto" denotes the region of approximation factors $\gamma$ such that:
We know how to construct cryptographic primitives assuming the hardness of $\mathsf{SVP}_\gamma$
It is plausible that $\mathsf{SVP}_\gamma$ is hard (as ...
4
Can quantum computer find the period of any given function efficiently? Are there any requirements towards the function?
Well, the function has to be periodic; that is, we have, for some $c > 0$, $f(x) = f(x+c)$, for all $x$ [1].
For both factoring and discrete log, we have such a function; and we know how finding the period of that function will give us ...
4
There are a few limitations on the function that you may or may not consider obvious.
The image of the function $f$ has to be a finite set. The function $f$ has to be computable and the efficiency depends on how well $f$ can be implemented as a quantum circuit. Arguably, you also need some sort of bound on the period so that you know how big the quantum ...
4
To answer your first question: it's as simple as that. Restating what you wrote, it's enough to check that $l$ divides all the four generators: $l^2$, $l(π-1)$, $l(π+1)$ and $π^2-1$. It's obvious for the first three, and for the last one just recall that by definition $π^2 = -p$, and that CSIDH expliciticly forces $l|(p+1)$. This proves that $(l) ⊃ (l,π-1)(l,...
4
There are two key points that you are mentioning (one mentioned by Poncho in the comments --- I repeat here for exposition purposes).
The RLWE errors $e_i(x)$ are small, and
the secret $s(x)$ is consistent across all samples.
This gives a fairly simple way to verify that you have recovered the correct $s(x)$ --- split your set of samples in half, recover $...
4
Does Grover's algorithm (or any other applicable quantum algorithm) only apply to weakening the hash function itself or can it also search only plausible inputs (a-z, A-Z, 0-9 <=14 characters) to reduce the search space?
Grover's is a general search method - it doesn't know or care how the function is given interprets the input. If you give it a ...
4
Cryptanalysis with adversaries capable of submitting superpositions of inputs and interpreting superpositions of outputs does exist, but is still relatively new with relatively little work. The earliest example that I'm aware of Zhandry's work on quantum-secure pseudo-random functions. I don't think the term "quantum chosen message" was introduced ...
3
Not necessarily; this varies from signature scheme to signature scheme. In some lattice signature schemes (e.g. FALCON) it is important not to produce two signatures for the same private key and hash value. In the case of FALCON it is therefore specified that the message be randomly salted before hashing and signing (see section 2.2.2 of the FALCON ...
3
1024 and 768 refer to the dimension of the base "generator" matrix $A$, these numbers are multiples of 256, which is the size of the module ring.
If the terminology is a bit confusing so far, then let me explain a little:
$A$ is a component of the public key, it's computed from a random seed chosen during key generation. It's also used in signing ...
3
As there don't seem to be any PQC alternatives for Diffie-Hellman (DH / ECDH), DH must have been replaced by key encapsulation using an ephemeral key pair.
I don't believe that is correct; a postquantum Key Encapsulation Method (KEM) would appear to be the natural replacement for DH/ECDH within TLS. In the KEM, one side (the client) produces a KEM public ...
3
The hyperbole is jaw-dropping: Advanced Quantum Domination, in the link Mr. Bodewes shared.
Terra Quantum AG is a little low on self-doubt:
Terra Quantum is a deep tech pioneer, developing revolutionary quantum
applications to shape the technology of the future. Our international
team of experts brings together the best minds from science, academia
and ...
Only top voted, non community-wiki answers of a minimum length are eligible