Commutative Encryption Method Based on Hidden Logarithm Problem

A candidate for post-quantum commutative encryption algorithm is proposed, which is based on the hidden discrete logarithm problem defined in a new 6-dimensional finite non-commutative associative algebra. The properties of the algebra are investigated in detail and used in the design of the proposed commutative cipher. The formulas describing the set of p^2 different global right-sided units contained in the algebra and local left-sided units are derived. Homomorphisms of two different types are considered and used in the commutative cipher. The encrypted message is represented in the form of a locally invertible element T of the algebra and encryption procedure includes performing the exponentiation operation and homomorphism map followed by the left-sided multiplication by a randomly selected local right-sided unit. The introduced commutative cipher is secure to the known-plaintext attacks and has been used to develop the post-quantum no-key encryption protocol providing possibility to send securely a secret message via a public channel without using any pre-agreed key. The proposed commutative encryption algorithm is characterized in using the single-use keys that are selected at random directly during the encryption process.

Keywords

commutative encryption; probabilistic cipher; post-quantum cryptoscheme; no-key protocol; finite non-commutative algebra; associative algebra; global unit; right-sided unit.

References

Литература:
1. Song Y. Yan. Quantum Computational Number Theory. N.Y., Springer, 2015.
2. Song Y. Yan. Quantum Attacks on Public-Key Cryptosystems. N.Y., Springer, 2014.
3. Shor P.W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on Quantum Computer. SIAM Journal of Computing, 1997, vol. 26, pp. 1484-1509.
4. Moldovyan D.N. Non-Commutative Finite Groups as Primitive of Public-Key Cryptoschemes. Quasigroups and Related Systems, 2010, vol. 18, no. 2, pp. 165-176.
5. Kuzmin A.S., Markov V.T., Mikhalev A.A., Mikhalev A.V., Nechaev A.A. Cryptographic Algorithms on Groups and Algebras. Journal of Mathematical Sciences, 2017, vol. 223, no. 5, pp. 629-641.
6. Moldovyan D.N., Moldovyan N.A. Cryptoschemes over Hidden Conjugacy Search Problem and Attacks Using Homomorphisms. Quasigroups Related Systems, 2010, vol. 18, no. 2, pp. 177-186.
7. Moldovyan A.A., Moldovyan N.A. Post-Quantum Signature Algorithms Based on the Hidden Discrete Logarithm Problem. Computer Science Journal of Moldova, 2018, vol. 26, no. 3 (78), pp. 301-313.
8. Moldovyan N.A., Moldovyan A.A. Finite Non-Commutative Associative Algebras as Carriers of Hidden Discrete Logarithm Problem. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2019, vol. 12, no. 1, pp. 66-81.
9. Menezes A.J., Oorschot P.C., Vanstone S.A. Applied Cryptography. N.Y., London, CRC Press, 1996.
10. Hellman M.E., Pohlig S.C. Exponentiation Cryptographic Apparatus and Method. U.S. Patent no. 4,424,414, 3 January 1984.