ABSTRACTThe vector decomposition problem has been considered as a hard problem, which is applicable to cryptography. Okamoto and Takashima proposed various types of public key cryptographic schemes based on the VDP. In this paper, we study the cryptographic implications of Okamoto‐Takashima schemes with respect to the properties of public keys. In the public key cryptography, one public key is associated to a unique private key, and an action using the public key implicitly assumes that the corresponding private action can be done only with the corresponding private key. We formalize this security issue by introducing the notion of equivalent public keys. We show that equivalent public keys exist in the Okamoto‐Takashima basic signature scheme and the homomorphic encryption scheme. We present a strong key substitution attack to their basic signature. We suggest how to prevent equivalent public keys and strong key substitution attack in their signature scheme. We point out that there are cases with no efficient methods to prevent equivalent public keys in their encryption scheme. Copyright © 2013 John Wiley & Sons, Ltd.