We propose a new authentication algorithm for small internet of things (IoT) devices without key distribution and secure servers. Encrypted private data are stored on the cloud server in the registration step and compared with incoming encrypted data without decryption in the verification step. We call a set of encryptions that can verify two encrypted data items without decryption a verifiable encryption (VE). In this paper, we define VE, and claim that several cryptosystems belong to the VE class. Moreover, we introduce an authentication algorithm based on VE, and show an example of the algorithm and discuss its performance and security. As the algorithm neither shares any secret keys nor decrypts, its computation time becomes very small.