Automata and Language Theory

In the cryptosystem discussed in the preceding section the underlying problem belongs to the theory of formal languages. Cryptanalysis and legal decryption amount to parsing the cryptotext in a certain fashion. Parsing will be essentially easier if the secret trapdoor is known. We have discussed this cryptosystem in some length, since quite a number of details are known about it. The cryptosystems presented in this section are based also on language theory and related areas. However, our discussion will now be more sketchy and brief. All details needed from the underlying areas will not be explained. Indeed, such an explanation is not necessary-for the overview.

Quite many of the proposed public-key cryptosystems apply an idea that could be called encryption by coloring. A color is associated to each plaintext letter. Since we again assume that plaintexts are bit sequences, we use only two colors white (bit 0) and black (bit 1). The public encryption key provides a method of generating arbitrarily many elements colored white, as well as arbitrarily many elements colored black. In the cryptosystems discussed here the elements are words. Bits are encrypted as words colored correspondingly. Of course, for differ­ent occurrences of the bit 0 (resp. 1), different words colored white (resp. black) should be chosen. In an ideal situation it is an intractable problem to decide the color of a given word, whereas the knowledge of the trapdoor makes such a decision easy. Clearly, the public encryption key always gives a decision method that may be of unmanageable complexity: generate words of both colors by turns until you meet the one appearing in the cryptotext.

All public-key cryptosystems based on encryption by coloring tend to increase word length unacceptably much. The number of words possible for the encryption of each bit has to be large, preferably potentially infinite. Otherwise, a cryptanalyst can generate all encryptions in advance and use a table look-up in order to encrypt. This leads to the somewhat paradoxical situation that to increase security one has to increase the expected ratio between cryptotext length and plaintext length.

A typical public-key cryptosystem based on the idea of encryption by coloring applies the word problem for finitely presented groups, that is, groups with finitely many generators {a_l5. . ., a_m} and finitely many defining relations

(*) w_t = X, i=\,...,n,

where X is the identity of the group and each w_t is a word over the alphabet {a,, af. . ., a_m, a^¹}. Two words x and y over this alphabet are termed equivalent iff there is a finite sequence of words

x = x₀, Xj, . . ., x, = y

such that, for j = 0,. . ., t — 1, x_{J +}, results from Xj by introducing or eliminating an occurrence of w_t, Wj~¹, zz~¹ or z~^lz, where 1 < i < n and z is an arbitrary word. The word problem for a finitely presented group consists of deciding of an arbitrary word whether or not it is equivalent to the identity X. (Clearly, x and y are equivalent iff xy~^l is equivalent to X) There are specific groups with an un- decidable word problem.

Such a group G is used as a basis for a public-key cryptosystem in the following way. Assume that G is determined by (*). The defining relations (*), as well as two nonequivalent words y₀ and y_{, are publicized as the encryption key. The encryp­tion of a bit i is an arbitrary word equivalent to y_t. Thus, to encrypt the bit 0, the sender applies the transformation rules determined by (*) in an arbitrary fashion to y₀. This can, of course, be done already in advance: the sender generates a large number of encryptions of both bits and keeps them in a safe deposit box until proper need arises.

The decryption leads, at least in principle, to the word problem: one has to decide whether a word is equivalent to y₀ or . The encryption method guarantees that each word under consideration is equivalent to exactly one of y₀ and y_l.

The secret trapdoor consists of additional defining relations such that the word problem will be easy for the resulting group G' but the words y₀ and y_l are still nonequivalent. Thus, G' has the same generators as G but, in addition to (*), some other defining relations. One may always choose y₀ and y_l as two generators of G, provided the new defining relations do not identify these generators. The new defining relations may, for instance, introduce some commutativity in order to make the word problem of G' easy.

The applicability of the cryptosystem depends on the choice of the defining relations. In particular, the additional relations constituting the trapdoor are essential from the point of view of security. It is important to notice that it is not necessary for the cryptanalyst to find the additional relations actually used by the cryptosystem designer. Any relations such that the resulting group G" will have an easy word problem and the two public words y₀ and y_l are nonequivalent will do. This means that the cryptosystem designer has to be very careful in inserting the trapdoor.

For instance, if G has two generators a and b which are also used as the two public words, then the introduction of the additional defining relation bab~*a~² = / induces commutativity in the form ba = a²b. Depending on the other relations, this might make the word problem essentially easier.

Similar cryptosystems can be constructed using defining relations in connection with algebraic structures other than groups. No specific results, such as the complexity of cryptanalysis by preprocessing (that is, cryptanalytic setup is encryption key only) are known.

The following public-key cryptosystem is based on hiding regular languages. As for systems based on iterated morphisms, cryptanalysis by preprocessing is provably /VP-complete. (Observe the contrast to the basic knapsack system.) The system uses also dummy letters, as well as encryption by coloring. Some basics of automata theory are needed. They will not be explained here; the reader is referred to [Sal]. The language generated by a grammar G (resp. accepted by an automaton A) is denoted by L(G) (resp. L{A)).

We present first a simplified version of the cryptosystem. Choose two arbitrary grammars G₀ and with the same terminal alphabet Z, as well as a finite deterministic automaton A₀ over the same alphabet Z. Make all final states of A₀ into nonfinal, and vice versa. Denote the resulting automaton by A_x. Thus, the languages L(A₀) and L(A_X) are complements of each other. Construct grammars G\ such that

L(G'i) = L(G,) n HA_t), for i = 0,1 .

The grammars GJ are easily obtained from G, and A_{ by the triple construction standard in language theory.

The grammars Go and G\ are now publicized as the encryption key. Encryption by coloring is used: the bit i is encrypted as an arbitrary word in L(G'i). The automata A_i are kept as the secret trapdoor. An eavesdropper has to decide membership in L(GJ), which is an undecidable problem in general. The legal receiver decrypts by solving the easy problem concerning whether the cryptotext is in L(A₀) or L(A,). System design guarantees that decryption is always unique.

We are now ready for the full version of the cryptosystem. In fact, the complex­ity results mentioned below deal with the full version.

We first define the morphic image of a grammar. Consider a grammar G, and let h be a morphism mapping each terminal letter of G into a letter (considered to be terminal) or the empty word, and each nonterminal letter of G into a letter (considered to be nonterminal). The morphic image h(G) of G consists of all productions h(a) h{(i), where a -> /? is a production in G. The start letter of h(G) equals the morphic image of the start letter of G. For grammars G, and G₂, the notation G_t s G₂ means that the set of productions of G, is a subset of the production set of G₂.

In the full version of the cryptosystem, A_t and G\ are defined as above. Let A be a much bigger alphabet than I, and let G'[ (i = 0, 1) be gammars with the terminal alphabet I and h a morphism such that

KG") c G; .

The pair (G'o, G'O constitutes the public encryption key. Also now encryption by coloring is used. As before, decryption will always be unique. To decrypt, the legal receiver applies the morphism h to one block of the cryptotext. If x is the resulting word, then the corresponding plaintext bit is 0 iff A₀ accepts x.

One can show that cryptanalysis by preprocessing is an /VP-complete problem in the following sense. Given (G'o, G'[\ it is (VP-complete to find (h, A₀) such that the former pair may result from the latter pair and the additional items G₀ and G, by the process described above. The other known public-key cryptosystems whose cryptanalysis by preprocessing is /VP-complete are the system considered in Example 2.2 and the system based on iterated morphisms. Of course, this property does not guarantee security: the result says nothing about the complexity of cryptanalysis in general.

The system based on hiding regular languages can be strengthened further by replacing the grammars G'o and G" with some equivalent grammars. Some specific method of generating equivalent grammars has to be considered. It is not clear whether this will constitute an essential strengthening.

Finally, some public-key cryptosystems based on automata theory will be briefly mentioned. A sequential machine M is a finite automaton provided with an output. Thus, M translates an input word into an output word of the same length. The inverse M ~¹ translates the output back to the input. Let k be a positive integer. The inverse M"¹(k) with delay k operates in the following fashion. Let y be M's output to the input word x. After receiving as its input the word yu, where u is an arbitrary word of length k, M~^l(k) produces the word wx as its output, where w is some word of length k. In the public-key cryptosystem, k and M~^x(k) are pub­licized as the encryption key, whereas M is kept as a secret trapdoor. To encrypt the plaintext y, one chooses an arbitrary word u of length k and applies M~ '(fe) to the word yu. To decrypt a c, the legal receiver ignores the first k letters of c and applies M to the remaining word. In general, it is difficult to compute M from k and M "¹ (k). No specific complexity estimates are known.

Cellular automata CA constitute a promising basis for public-key crypto­systems. The matter is not yet clearly understood. For instance, given a reversible two-dimensional cellular automaton, it is very difficult to find its inverse. In fact, there is no algorithm for finding the inverse within a time complexity bounded by a computable function. The public encryption key consists of a reversible cellular automaton CA and a natural number k. The plaintext is encoded as a configuration of CA and encrypted by applying CA k times to the configuration. The resulting configuration constitutes the cryptotext. The inverse CA ~¹ constitutes the secret trapdoor. The legal receiver applies CA ~¹ k times to the cryptotext.

Date: 2015-02-16; view: 669