The Vehicular Cloud Computing (VCC) provides significant benefits (e.g., higher resource availability, and low communication latency) to vehicular applications. However, still there exists latency related issues with applications that require real-time response, and it is difficult to achieve when using VCC. Therefore, the use of fog computing that provides the next level service of cloud computing from the centre to edge networks is envisioned. Apart from low latency, fog computing also supports mobility, location-awareness, and real-time data handling, which enables ubiquitous connectivity between fog nodes and smart vehicles. However, there remain several security and privacy challenges while using fog computing in VANET applications. To address these challenges, we propose the design of an authenticated message-exchange scheme for fog-assisted VCC (called AME-VCC). The proposed scheme ensures mutual authentication along with anonymity, which enables accountable privacy. The correctness of the protocol and its security is proved in the random oracle model, which indicates that it is provably secure under any probabilistic polynomial time adversary. Moreover, the comparative study of computation cost is done to prove the claim of efficiency. The analysis of security and performance indicates that AME-VCC is computationally efficient protocol, and it ensures authenticated secure message exchange with anonymity and unlinkability.