Paper 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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 Multivariate CryptographyDigital signaturesNoncommutative CryptographyEulerian transformationsProtocol based cryptosystemsPublic keys
 Contact author(s)
 Vasyl Ustymenko @ rhul ac uk
 History
 20240105: approved
 20240101: received
 See all versions
 Short URL
 https://ia.cr/2024/001
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/001, author = {Vasyl Ustimenko}, title = {On short digital signatures with Eulerian transformations}, howpublished = {Cryptology ePrint Archive, Paper 2024/001}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/001}}, url = {https://eprint.iacr.org/2024/001} }