Abstract: We describe matrixfree pivotal algorithms in the XTR⁺ system. The computation efficiency of the pivotal algorithms is obviously improved. Consequently, the computation efficiency of the provable INDCCA2 secure cryptosystem, the provable secure digital signature, the provable secure blind signature protocol and zeroknowledge proof protocol by means of XTR⁺ system is also improved greatly.

Key words: XTR⁺ public key system, trace function, LFSR sequence, Lucas sequence