XTR+:: A provable security public key cryptosystem

The XTR is a very effective public key cryptosystem based on 3rd order LFSR, sequence. But it has parameter corresponding problem and it neglects the Provable Security property and the blind signature scheme. For overcoming these problems in this paper, the XTR is extended with 4-th order LFSR sequence to from a new public key cryptosystem called XTR+. An algorithm for computing the trace elements is proposed, which only depends on a 2 x 2 recursive matrix instead of 4 x 4 so that the running time of the algorithm is much shorter than the algorithm for XTR which depends on a 3 x 3 recursive matrix. Over XTR+ the provable IND-CCA2 secure encryption/decrypt ion protocol, the provable secure digital signature, the provable secure blind signature protocol and zero-knowledge proof protocol are established. Compared with the traditional methods such as ECC, XTR+ is more simple in cipherkey and parameter select ions and has more randomcity and faster algorithms. Under the same security requirements, the XTR+ can greatly reduce the overheads in parameter storage and communication and be suitable for bigger plaintext and ciphertext spaces.