Paper 2024/001 Original: eprint.iacr.org/2024/001 ↗

On short digital signatures with Eulerian transformations

Abstract

Let n stands for the length of digital signatures with quadratic multivariate public rule in n variables. We construct postquantum secure procedure to sign O(n^t), t ≥1 digital documents with the signature of size n in time O(n^{3+t}). It allows to sign O(n^t), t <1 in time O(n^4). The procedure is defined in terms of Algebraic Cryptography. Its security rests on the semigroup based protocol of Noncommutative Cryptography referring to complexity of the decomposition of the collision element into composition into given generators. The protocol uses the semigroup of Eulerian transformations of variety (K*)^n where K* is a nontrivial multiplicative group of the finite commutative ring K. Its execution complexity is O(n^3). Additionally we use this protocol to define asymmetric cryptosystem with the space of plaintexts and ciphertexts (K*)^n which allows users to encrypt and decrypt O(n^t) documents of size n in time O(n^{3+[t]}) where [x] stands for the flow function from x. Finally we suggest protocol based cryptosystem working with plaintext space (K*)^n and the space of ciphertext K^n which allows decryption of O(n^t), t>1 documents of size n in time O(n^{t+3}), t>1. The multivariate encryption map has linear degree O(n) and density O(n^4). We discuss the idea of public key with Eulerian transformations which allows to sign O(n^t), t≥0 documents in time O(n^{t+2}). The idea of delivery and usage of several Eulerian and quadratic transformations is also discussed.