Cryptosystems based on semi-distributive algebras

We propose a new cryptographic scheme of ElGamal type. The scheme is based on algebraic systems defined in the paper—semialgebras (Sect. 2). The main examples are semialgebras of polynomial mappings over a finite field K, and their factor-semialgebras. Given such a semialgebra R, one chooses an invertible element a ∈ R ^* of finite order r, and a random integer s. One chooses also a finite dimensional K-submodule V of R. The 4-tuple (R, V, a, b) where b = a ^s forms the public key for the cryptosystem, while r and s form the secret key. A plain text can be viewed as a sequence of elements of the field K. That sequence is divided into blocks of length dim(V) which, in turn, correspond to uniquely determined elements X _i of V. We propose three different methods (A, B, and C, see Definition 1.1) of encoding/decoding the sequence of X _i . The complexity of cracking the proposed cryptosystem is based on the Discrete Logarithm Problem for polynomial mappings (see Sect. 1.1). No methods of cracking the problem, except for the “brute force” (see Sect. 1.1) with Ω(r) time, are known so far.