PATH-SEARCH COLLATZ QUANTUM-RESISTANT ONE-WAY FUNCTIONS (PSC-QOWF): DESIGN, SECURITY AND EXPERIMENTAL EVALUATION
Authors: Andria Kelekhsaevi
Affiliation: Caucasus University
Category:
Keywords: Collatz conjecture; one-way functions; post-quantum cryptography; quantum resistance; Grover’s algorithm; parity sequence masking; combinatorial search; verifiable delay functions
ABSTRACT. In this paper, we present the Path-Search Collatz Quantum-Resistant One-Way Function (PSC-QOWF), a new cryptographic primitive based on the computational difficulty of recovering parity branch sequences in a salted Collatz-type iteration. Unlike previous Collatz-based cryptographic constructions, PSC-QOWF is designed from first principles to withstand both classical and quantum adversaries, and its inversion problem reduces to a well-defined unstructured search problem with a provable Ω(2^((T-m)/2)) lower bound in the quantum query model. Experimental results confirm the expected exponential growth in brute-force inversion cost, and security analysis shows that parameters can be selected to achieve post-quantum 128-bit security margins.
References:
Bennett, Charles H., Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. 1997. “Strengths and Weaknesses of Quantum Computing.” SIAM Journal on Computing 26 (5): 1510–1523. https://doi.org/10.1137/S0097539796300933
Bernstein, Daniel J., and Jeffrey C. Lagarias. 2016. “The 3x+1 Conjugacy Map.” Experimental Mathematics 25 (2): 185–196. https://doi.org/10.1080/10586458.2015.1062336
Biere, Armin, Marijn Heule, Hans van Maaren, and Toby Walsh, eds. 2009. Handbook of Satisfiability. IOS Press. https://doi.org/10.3233/978-1-58603-929-5-i
Grover, Lov K. 1996. “A Fast Quantum Mechanical Algorithm for Database Search.” In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212–219. https://doi.org/10.1145/237814.237866
Impagliazzo, Russell, Leonid A. Levin, and Michael Luby. 1989. “Pseudo-Random Generation from One-Way Functions.” In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 12–24. https://doi.org/10.1145/73007.73009
Lagarias, Jeffrey C. 1985. “The 3x+1 Problem and Its Generalizations.” American Mathematical Monthly 92 (1): 3–23. https://doi.org/10.2307/2322189
Ramesh, Suresh. 2025. “Proof-of-Collatz: A Blockchain Consensus Protocol.” International Research Journal of Modernization in Engineering, Technology and Science 7 (2). https://www.irjmets.com/uploadedfiles/paper//issue_2_february_2025/68269/final/fin_irjmets1740754525.pdf
Rompel, John. 1990. “One-Way Functions Are Necessary and Sufficient for Secure Signatures.” In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 387–394. https://doi.org/10.1145/100216.100264
Shah, Vishal, and Arun Kumar. 2021. “Pseudorandom Number Generation Using Collatz Conjecture.” International Journal of Advanced Computer Science and Applications 12 (5): 537–543. https://doi.org/10.14569/IJACSA.2021.0120565
Sinai, Yakov G. 2003. “Statistical (3x+1) Problem.” Communications on Pure and Applied Mathematics 56 (7): 1016–1028. https://doi.org/10.1002/cpa.10072
Smith, Alan. 2023. “On the Use of the Collatz Function in Hash Design.” Cryptology ePrint Archive, Report 2023/1234. https://eprint.iacr.org/2023/1234
Tao, Terence. 2019. “Almost All Collatz Orbits Attain Almost Bounded Values.” arXiv preprint arXiv:1909.03562. https://arxiv.org/abs/1909.03562
Vuckovac, Damir. 2018. “Collatz Sequence Based Hash Function.” arXiv preprint arXiv:1812.10941. https://arxiv.org/abs/1812.10941
Zhandry, Mark. 2012. “How to Construct Quantum Random Functions.” In 53rd Annual IEEE Symposium on Foundations of Computer Science, 679–687. https://doi.org/10.1109/FOCS.2012.37
Menu