Logarithmic NTRU-Based Certificateless Ring Signature in E-Voting Applications

In electronic voting systems, a large number of voters are often required to vote. It is also necessary to ensure the security of the voters and the fairness of the vote. The use of ring signatures is very suitable for e-voting systems because of their special anonymity. Among the many types of ring signatures, certificateless ring signature (CRS) stands out because it does not require certificates and avoids the need to completely trust the key generation center (KGC). In this paper, we propose a certificateless ring signature based on the special structure of the number theory research unit (NTRU) lattice, which utilizes the Merkle tree and seed tree to split commitments and integrate them again to generate signatures. At the same time, we embed the NTRU small integer solution (NTRU-SIS) problem and provide a detailed proof of security under the random oracle model (ROM). In efficiency, the Merkle tree makes the signature size logarithmically increase with the ring scale. In the era of big data explosion, this feature enables the proposed scheme to maintain a comparatively short signature size even when the number of ring members N is very large. When N=8, the signature size is 61.08 KB; when N increases to 512, the size is 65.02 KB. From the data, we can observe that the signature size grows slowly, by only 4 KB when N grows exponentially, which is much slower than ring signatures with linear growth.