Remote attestation mechanisms are well studied in the high-end computing environments; however, the same is not true for embedded devices – especially for smart cards. With ever changing landscape of smart card technology and advancements towards a true multi-application platform, verifying the current state of the smart card is significant to the overall security of such proposals. The initiatives proposed by GlobalPlatform Consumer Centric Model (GP-CCM) and User Centric Smart Card Ownership Model (UCOM) enables a user to download any application as she desire – depending upon the authorisation of the application provider. Before an application provider issues an application to a smart card, verifying the current state of the smart card is crucial to the security of the respective application. In this paper, we analyse the rationale behind the remote attestation mechanism for smart cards, and the fundamental features that such a mechanism should possess. We also study the applicability of Physical Unclonable Functions (PUFs) for the remote attestation mechanism and propose two algorithms to achieve the stated features of remote attestation. The proposed algorithms are implemented in a test environment to evaluate their performance.