Networks of Picture Processors with Filtering Based on Evaluation Sets as Solvers for Cryptographic Puzzles Based on Random Multivariate Quadratic Equations

Abstract

Networks of picture processors is a massively distributed and parallel computational model inspired by the evolutionary cellular processes, which offers efficient solutions for NP-complete problems. This bio-inspired model computes two-dimensional strings (pictures) using simple rewriting rules (evolutionary operations). The functioning of this model mimics a community of cells (pictures) that are evolving according to these bio-operations via a selection process that filters valid surviving cells. In this paper, we propose an extension of this model that empowers it with a flexible method that selects the processed pictures based on a quantitative evaluation of its content. In order to show the versatility of this extension, we introduce a solver for a cryptographic proof-of-work based on the hardness of finding a solution to a set of random quadratic equations over the finite field F2. This problem is demonstrated to be NP-hard, even with quadratic polynomials over the field F2, when the number of equations and the number of variables are of roughly the same size. The proposed solution runs in O(n2) computational steps for any size (n,m) of the input pictures. In this context, this paper opens up a wide field of research that looks for theoretical and practical solutions of cryptographic problems via software/hardware implementations based on bio-inspired computational models.

Keywords

• bio-inspired computational model
• networks of picture processors
• combinatorial optimization problems
• massively parallel and distributed algorithms
• cryptographic proof-of-work
• multivariate quadratic equations