Further research on public-key cryptosystems based on third-order recurrence sequence

Abstract

Properties of third-order recurrence sequences were investigated and a new variant of the GH public-key cryptosystem, which was further improved to be a probabilistic public-key cryptosystem, was proposed. Then security analysis of the proposed scheme was provided and it was proved that the one-wayness of the proposed scheme is equivalent to partial discrete logarithm and its semantic security is equivalent to decisional Diffie-Hellman problem in ring extension. Finally, efficiency analysis of the proposed scheme was provided, and that these two encryption schemes need to transfer 2log N and 4log N bits data respectively.

Keywords

public-key cryptosystem, third-order linear recurrence sequence, (trapdoor) discrete logarithm, integer factorization