Cryptographic Puzzles and Complex Systems
Rade Vuckovac
Rade.Vuckovac@griffithuni.edu.au
Abstract
A puzzle lies behind password authentication (PA) and blockchain proof of work (PoW). A cryptographic hash function is commonly used to implement them. The potential problem with secure hash functions is their complexity and rigidity. We explore the use of complex systems constructs such as a cellular automaton (CA) to provide puzzle functionality. The analysis shows that computational irreducibility and sensitivity to initial state phenomena are enough to create simple puzzle systems that can be used for PA and PoW. Moreover, we present puzzle schemata using CA and n-body problems.
Keywords: password authentication; proof of work; provable security
Cite this publication as:
R. Vuckovac, “Cryptographic Puzzles and Complex Systems,” Complex Systems, 30(3), 2021 pp. 375–390.
https://doi.org/10.25088/ComplexSystems.30.3.375
