Maritime communication, critical for global oceanic trade, faces challenges and opportunities with advancements in Information and Communication Technology (ICT). Traditional methods are susceptible to interception due to open channels, limited authentication, jamming, and other security risks. Securing vessel movements and locations in Internet of Vessels (IoV) is essential to prevent unauthorized data interception and tampering during transmission. We propose a ship authentication method using location-based secure keys to ensure the confidentiality of a vessel’s whereabouts. The proposed scheme’s robustness is validated through formal and informal security analyses, and formal verification using the Scyther automated verification tool, demonstrating its effectiveness against potential attacks in maritime networks. Comparative studies indicate that utilizing location-based keys maintains anonymity and untraceability without imposing significant computational or communication burdens. Experimental findings from comprehensive big data analytics and simulations using NS3 validate the scheme’s feasibility and performance.