Paper 2024/001

On short digital signatures with Eulerian transformations

Vasyl Ustimenko, Royal Holloway University of London

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.

Available format(s)
Publication info
Multivariate CryptographyDigital signaturesNoncommutative CryptographyEulerian transformationsProtocol based cryptosystemsPublic keys
Contact author(s)
Vasyl Ustymenko @ rhul ac uk
2024-01-05: approved
2024-01-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Vasyl Ustimenko},
      title = {On short digital signatures with Eulerian transformations},
      howpublished = {Cryptology ePrint Archive, Paper 2024/001},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.