One Self-delegation Scheme and the Knowledge Complexity of Problems
一个自授权系统及问题的知识复杂性

A solution to the problem of self-delegation using the identification-authentication-signature scheme based on the graph isomorphism problem is proposed in this paper. The major difference from the traditional solutions is that it is based on the graph isomorphism rather than computing numeric theory problem, though they all leak out secret information little by little. The knowledge complexity of problems, the including knowledge complexity, the practical knowledge complexity, and the computing knowledge complexity are also defined. In the authors' opinion, these definitions should be used as the upper bound of knowledge complexity of protocols.