ИСТИНА

Modern practically used public key cryptosystems, such as RSA, are based on number-theoretic problems, e.g. large number factorization, that are believed computationally hard. Nevertheless, in order to increase cryptosystem efficiency and/or security many attempts to build a public key cryptosystem on top of {NP}-complete or undecidable problems were made. There are number of requirements, apart from computational intractability of the underlying problem, that a cryptosystem should satisfy. First of all, one should describe a procedure for choosing a specific \emph{instance} of the problem, i.e. appropriate key generation, which in turn is a challenging task for combinatorial problems. This talk will discuss the possibility of development of a public key cryptosystem on top of \emph{language factorization}, more precisely, on \emph{rational subset membership} problem for finitely generated semigroup of regular languages, which is stated as follows. For a finite set of regular languages (semigroup generators) and a regular language in terms of generators, which represents the rational subset, one should decide whether or not a given regular language belongs to the rational subset. The ciphertext for single bit of a message is a finite automaton, which represents zero or one depending on its rational subset membership. The membership problem may be considered as a generalization of the finite power property of a regular language and the only known solution is based on PSAPCE-complete problem of testing limitedness of distance automata.