Most SNS (Social Networking Service) and EC (Electronic Commerce) sites request and store customers' personal information. When we exchange these information through Internet, it is recommended to use encryption mechanism such as SSL or TLS. Even if we use SSL or TLS based on Public-key cryptosystem, secret information can be stolen by Man-in-the-middle attack (MITM). Currently, Certificate Authority (CA) guarantees the legitimacy of the Public-key. However, some CAs issue false certificates, and no one can guarantee the genuineness of the CAs themselves. This paper proposes Public-key decision protocol based on majority to against MITM. Proposed protocol require no CA, and it can detect substitution of Public-key. We implement prototype of proposed protocol on virtual network and show our protocol can select correct Public-key by simulations.