Cryptology ePrint Archive: Report 2021/898

On Extremal Expanding Algebraic Graphs and post-quantum secure delivery of passwords, encryption maps and tools for multivariate digital signatures.

Vasyl Ustimenko

Abstract: Expanding graphs are known due to their remarkable applications to Computer Science. We are looking for their applications to Post Quantum Cryptography. One of them is postquantum analog of Diffie-Hellman protocol in the area of intersection of Noncommutative and Multivariate Cryptographies .This graph based protocol allows correspondents to elaborate collision cubic transformations of affine space Kn defined over finite commutative ring K. Security of this protocol rests on the complexity of decomposition problem of nonlinear polynomial map into given generators. We show that expanding graphs allow to use such output as a ‘’seed’’ for secure construction of infinite sequence of cubic transformation of affine spaces of increasing dimension. Correspondents can use the sequence of maps for extracting passwords for one time pads in alphabet K and other symmetric or asymmetric algorithms. We show that cubic polynomial maps of affine spaces of prescribed dimension can be used for transition of quadratic public keys of Multivariate Cryptography into the shadow of private areas.

Category / Keywords: cryptographic protocols / Extremal Graph Theory, Post Quantum Cryptography, Multivariate Cryptography, stable subgroups of affine Cremona group, Noncommutative Cryptography, key exchange protocols, random and pseudorandom sequences, digital signatures.

Date: received 30 Jun 2021

Contact author: vasyl at hektor umcs lublin pl

Available format(s): PDF | BibTeX Citation

Note: None.

Version: 20210701:065147 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]