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

Karina Paola Jiménez, Sandra Gómez-Canaval, Ricardo Villanueva-Polanco and Silvia Martín Suazo
Additional contact information
Karina Paola Jiménez: Facultad de Ingenierías, Universidad Simón Bolívar, Calle 58 No 55-132, Barranquilla 080001, Colombia
Sandra Gómez-Canaval: Departamento de Sistemas Informáticos, Universidad Politécnica de Madrid, Calle Alan Turing s/n, 28031 Madrid, Spain
Ricardo Villanueva-Polanco: Computer Science Department, Universidad del Norte, Barranquilla 080001, Colombia
Silvia Martín Suazo: Departamento de Sistemas Informáticos, Universidad Politécnica de Madrid, Calle Alan Turing s/n, 28031 Madrid, Spain

Mathematics, 2020, vol. 8, issue 12, 1-21

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 F 2 . This problem is demonstrated to be NP-hard, even with quadratic polynomials over the field F 2 , when the number of equations and the number of variables are of roughly the same size. The proposed solution runs in O ( n 2 ) 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; post-quantum blockchain (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/12/2160/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/12/2160/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:12:p:2160-:d:456745

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().