© 2017 Smart cities aim at developing new applica-tions and architectures to improve the quality of urban services. However, privacy and security are still two of the technical issues that remain unsolved. The reason is that traditional solutions such as Public Key Infrastructures (PKI) were created to ensure some security services such as non-repudiation and data integrity. PKI enable the use of digital certificates and public key cryptosystems and require the cooperation among multiple entities to verify the certificates validity and to maintain a certificate revocation list. Due to the latest development in quantum computing, PKI-based solutions will not be able to provide continuous data integrity and non-repudiation. In fact, the techniques used by today PKI-based solutions to sign docu-ments are not future-proof. To address these drawbacks, we propose an efficient, lightweight non-repudiation protocol for multiples entities that makes use of Merkle tree and of a Hash function that is future-proof. In contrast to PKI-based solutions, we demonstrate the efficiency of our proposed approach in terms of its low transmission and message overheads, and ability to maintain continuous data integrity and non-repudiation for smart cities’ applications and services.