Input-trees of finite automata and application to cryptanalysis

In this papert weights of output set and of input set for finiteautomata are discussed. For a weakly invertible finite automaton, we proye thatfor states with minimal output weight, the distribution of input sets is uniform.Then for a kind of compound finite automata, we give weights of output set and ofinput set explicitly, and a characterization of their input-trees. For finite automatonpublic key cryptosystems, of which automata in public keys belong to such a kind ofcompound finite automata, we evaluate search amounts of exhaust search algorithmsin average case and in worse case for both encryption and signature, and successfulprobabilities of stochastic search algorithms for both encryption and signature. Inaddition, a result on mutual invertibility of finite automata is also given.