Discussion: (nextgen) post-quantum cryptography resistant to hypothetical quantum NP solver?
Jarek Duda
Dear All,
I have worked on ANS coding also with simultaneous encryption, and recently joined this mailing list especially to propose discussion as in the title.
There is a general focus on quantum computers potentially endangering current asymmetric encryption through e.g. Shor algorithm. However, physics might allow also for more powerful e.g. 2WQC (two-way quantum computers: https://arxiv.org/pdf/2308.13522 ) in theory being able to attack NP problems (more difficult than Shor).
While it might never happen, maybe it is worth to start thinking of next generation pqc designed to be resistant also to such possibilities – assuming existence of powerful but imperfect quantum NP solver.
In theory a perfect NP solver could also break symmetric cryptography. Specifically, brute force attacks testing succeeding keys need some classifier if the key is right (e.g. statistical test if decoded prefix is a noise) – we could use such classifier as verifier of NP problem.
One protection direction could be trying to go toward more difficult but still practical PSPACE, e.g. try to build cryptography on some https://en.wikipedia.org/wiki/PSPACE-complete problem, e.g. make M2M authentication as a game (?)
Another direction is exploiting rather unavoidable imperfections – like being able to maintain quantum entanglement for a limited time. For this purpose I was thinking of initialized encryption (originally for ANS) – requiring some initial calculations, like transformation of the key into much larger decoding tables, enforced to require e.g. ~1ms of calculations. It would protect from brute force attacks (additional ~1ms per tested key), and potential quantum attacks – until being able to maintain quantum entanglement of keys for a longer time.
Any thoughts, articles on such potential next generation pqc, e.g. PSPACE-based?
With best
regards,
Jarek Duda
--
dr Jarosław Duda
Institute of Computer Science and Computer Mathematics,
agiellonian University, Cracow, Poland
http://th.if.uj.edu.pl/~dudaj/
Bas Westerbaan
--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/2dd45994-c571-409b-8e87-864fe70d20adn%40list.nist.gov.
Jarek Duda
Two-way computers for electronic (or microfluid) chip are quite
common: controlled from both directions by both pushing into and
pulling from - using e.g. battery acting as a pump for electrons.
There are many quantum computer technologies, if for any of them we would be able to analogous realize "two-way", indeed attacking NP would be only one of consequences - postBQP with postselection replaced with physical constraints.
As state preparation allows to influence the initial state, "doing the same but reversed" (CPT symmetry analog), we should be able to influence the final state - e.g. pull-push, negative-positive (radiation) pressure, stimulated emission-absorption.
For photonic quantum computers usually laser pulse is used as
state preparation - of positive radiation pressure, realizing
impulse of negative radiation pressure we should be able to
analogously influence the final state.
https://scholar.google.pl/scholar?q=negative+radiation+pressure
https://scholar.google.pl/scholar?q=optical+pulling
E.g. ring laser ( https://en.wikipedia.org/wiki/Ring_laser )
should act as such "pump for photons" - it can have unidirectional
photon trajectories, from CPT symmetry perspective trajectories
would be reversed - creating positive radiation pressure toward
minus time, what means negative toward plus time like below.
-- dr Jarosław Duda Institute of Computer Science and Computer Mathematics, Jagiellonian University, Cracow, Poland http://th.if.uj.edu.pl/~dudaj/
Jarek Duda
Dear All,
Wolfram Quantum Framework can already simulate such nextgen 2WQC in theory being able to attack NP problems: https://community.wolfram.com/groups/-/m/t/3157512
Maybe we should start thinking of resistant nextgen pqc ...
Best,
Jarek Duda
--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/2dd45994-c571-409b-8e87-864fe70d20adn%40list.nist.gov.
-- dr Jarosław Duda Institute of Computer Science and Computer Mathematics, Jagiellonian University, Cracow, Poland http://th.if.uj.edu.pl/~dudaj/