A visual zero-knowledge proof of identity is a new and simple cryptographic scheme for identity verification based on the concept of non-expansion visual cryptography. This paper presents an improved algorithm based on the visual zero-knowledge proof of identity scheme in order to enhance the security issue. The security of the improved algorithm is based on the 3-SAT NP-hard problem while the security of old algorithm was based on the difficulty of solving random Boolean OR operations. In addition, the improved visual zero-knowledge proof of identity scheme is also efficient in generating shares without repeating the steps as was happening in the old scheme in order to avoid getting full black shares. The improvement was made based on Yang's non-expansion (probabilistic) visual cryptography method and Boolean operations.