As the “Internet communications infrastructure” develops to encircle smart devices, it is very much essential for designing suitable methods for secure communications with these smart devices, in the future Internet of Things (IoT) applications context. Due to wireless communication among the IoT smart devices and the gateway node (GWN), several security threats may arise in the IoT environment, including replay, man-in-the middle, impersonation, malicious devices deployment and physical devices capture attacks. In this article, to mitigate such security threats we design a new certificate-based device access control scheme in IoT environment which is not only secure against mentioned attacks, but it also preserves anonymity property. A detailed security analysis using the widely-accepted “Real-Or-Random (ROR)” model-based formal security analysis, informal security analysis, and also formal security verification based on the broadly-accepted “Automated Validation of Internet Security Protocols and Applications (AVISPA)” tool has been performed on the proposed scheme to show that it is secure against various known attacks. In addition, a comprehensive comparative analysis among the proposed scheme and other relevant schemes shows that a better trade-off among the security & functionality attributes, communication and computational costs is achieved for the proposed scheme as compared to other schemes.