A certificate revocation scheme based on Quadratic Residues problem

The revocation of certificates is very important to PKI. The sticking points that influence a certificate revocation scheme heavily are the traffic for distribution of certificate status, the time the CA spent to flush those status to directory, whether the access to directory comes on smoothly, whether there is a strict requirement on the security of the directory, and computation complexity of status verification. Following the analysis of the existing certificate revocation schemes, we propose a new certificate revocation scheme based the difficulty of resolving the Quadratic Residues problem. This new scheme is good at the traffic needed to distribution the status, the time to flush the status to the directory and also good at the smoothness of access of users to the directory, and requires nothing about the security of the directory. And then we show that this new scheme has lower computation complexity than that of OCSP, CRL and CRT.