Computing inversions in finite fields based on cellular automata

Abstract

Over the past few years, there has been a sustaining interest in research of secure communication architectures and protocols based on asymmetric cryptographic techniques. However, it is showed that quantum computers can break most asymmetric cryptographic techniques and they will be insecure. In this paper, we focus on accelerating quantum-safe cryptography for communication systems by improving inversions in finite fields. Cellular Automaton (CA) is a discrete model in mathematics, physics, computer science and neural computing. It is a grid of cells with a finite number of states and it has been adopted and applied to many research and engineering fields, e.g., cryptography and neural computing. In addition, cellular automata can simulate many real-world systems, such as biological system, Vehicular Communication (VC) systems and neural networks. We propose a variant of Fermat’s theorem inversion based on cellular automaton. We implement inversions in finite fields on Application Specific Integrated Circuit (ASIC) and accelerate some quantum-safe signature schemes, which shows that they are efficient for constructing quantum-safe communications.