Context Free Grammar for the Generation of a One Time Authentication Identity

摘要

An authentication protocol was proposed in [11] for the generation of one time authentication identity, which can be used as one time passwords, generation of disposal credit card numbers. The proposed protocol was designed using a context free grammar and was in the learning theory domain. The protocol required that the context free grammar used for the authentication procedure be difficult to learn. The paper discusses the relationship between the learning theory and the number theory. Then based upon the experimental limitations to learn a context free grammar, we present an algorithm for the generation of context free grammar which is difficult to learn. There exists no theoretical study which states given a set of strings from a language L, how difficult it is to generate another string which belongs to the same language. Experiments were conducted to determine this empirically. A context free grammar from the proposed algorithm was used to generate the string.