Analysis of possibility to use El Gamal algorithm with deterministic embedding for key encapsulation

Abstract

Suppose some parties, A and B, use some symmetrical encryption algorithm (for example, AES) to encrypt their messages from A to B and from B to A. They get their secret keys from some Trusted Authority (ТА). TA generates keys and then delivers them to correspondent users. The simplest and, may be, the optimal way to deliver the secret key to user A is to encrypt it (using some asymmetrical encryption algorithm) with A’s public key and then to send it to A via public channel. Such procedure is called “key encapsulation”.
Key encapsulation algorithms are widely used in the modern cryptography and represented in national and ISO/IEC standards of key encapsulations. Building the key encapsulation algorithm, which may be used as a national standard, is an actual problem nowadays. Ukrainian cryptographers are also working on such standard. Modified Elliptic Curve Integrated Encryption Scheme (ECIES), included in the ANSI X9.63, ISO/IEC 18033-2, IEEE 1363a and SECG SEC1 standards, was used in the project of national standard for key encryption.
In this article we propose some alternative encryption algorithm on elliptic curve which also may be used for this purpose.
Generally speaking we can use arbitrary asymmetric encryption algorithm for key encapsulation. One of the simplest and preferable algorithms is El Gamal encryption algorithm. To use this algorithm on elliptic curve, we need algorithms for embedding key into point on elliptic curve and for retrieving it back. Several lines of work in both the number theory and cryptography literature have considered the problem of deterministically mapping field element to point on elliptic curve. However, only probabilistic algorithms of such embedding existed until 2016, when deterministic algorithm for hash embedding was proposed. But key embedding is much more complicated procedure than hash embedding, because the correspondent mapping must be bijection.
In what follows we describe how this algorithm for key embedding can be built and then discuss the problems that appear if we want to use it in key encapsulation.