Thoughts on PQC

[Robert J. Hansen]

> My understanding (based on the "heffalumps" paper) is that past PQC 
> systems have had nasty tendencies to unravel under conventional 
> computing.  You have looked at this much more than I have.  Have we 
> finally found problems that are reliably hard for both quantum and 
> conventional computing?

I have no idea.

What I have heard from the mathematicians I trust is there is good 
reason to believe the learning-with-errors problem in lattice 
cryptography is Just Plain Hard. I have no reason to disbelieve them. 
The discovery of learning-with-errors problems earned Oded Regev a Gödel 
prize (theoretical computer science's version of a Nobel; comparable to 
a Turing award). The underlying math appears to be, as you ask, reliably 
hard for both quantum and conventional computing.

But the complexity is mind-boggling. You need a strong undergraduate 
math degree just to understand the language used in the NIST 
publications defining Kyber and Dilithium.

Complex algorithms overwhelmingly tend to be fragile ones.

> How does its performance compare to existing TRNGs?  (Presumably a 
> random quantum circuit would produce random output... or is my ignorance 
> showing and most of them just produce zero or some constant not 
> characteristic of the circuit?)

Quantum random circuits can be thought of as the quantum computing 
analogue of a mathematical random matrix. A matrix is a structured 
collection of numbers: for instance, the simple set of linear equations

	3x + y  = 4
	2x - 3y = 7

... can be expressed as the mathematical matrix

	+-     -+
	| 3 1 4 |
	| 2 3 7 |
	+-     -+

... and then you can do things like Gauss-Jordan elimination to solve 
the matrix, etc. Hey, x = 19/11 and y = -13/11. See that? We did 
something with our matrix. We put it to use.

Well, what if instead of the coefficients of linear equations we put in 
probabilities instead? Instead of "2" in the lower-left corner we put 
something like "60%"? Now we have a matrix that incorporates 
nondeterminism -- randomness -- a random matrix.

Now if instead of "60%" you allow probabilities to be negative as well 
as positive, and to even represent complex numbers, suddenly you're now 
plugging quantum mechanical probability distributions into this 
fantastically useful mathematical tool. And that's the final evolution 
of random matrices.

A good first approximation of "what's a quantum random circuit?" is, "a 
random matrix implemented on a quantum computer." That's all.

My frustration with Google's paper about "look at us! We demonstrated 
quantum supremacy by creating a random quantum circuit and sampling it!" 
is, okay, great, they might have demonstrated a fantastic capability, 
but _what did they do with it_? What was the overall _effect_ of this?

-------------- next part --------------
A non-text attachment was scrubbed...
Name: OpenPGP_signature.asc
Type: application/pgp-signature
Size: 236 bytes
Desc: OpenPGP digital signature
URL: <https://lists.gnupg.org/pipermail/gnupg-users/attachments/20260414/7d241f4f/attachment-0001.sig>