Physical unclonable functions (PUFs) exploit the intrinsic complexity and irreproducibility of physical systems to generate secret information. PUFs have the potential to provide fundamentally higher security than traditional cryptographic methods by preventing the cloning of identities and the extraction of secret keys. One unique and exciting opportunity is that of using the super-high information content (SHIC) capability of nanocrossbar architecture as well as the high resistance programming variation of resistive memories to develop a highly secure on-chip PUFs for extremely resource constrained devices characterized by limited power and area budgets such as passive Radio Frequency Identification (RFID) devices. We show how to implement PUF based on nano-scale memristive (resistive memory) devices (mrPUF). Our proposed architecture significantly increased the number of possible challenge-response pairs (CRPs), while also consuming relatively lesser power (around 70 uW). The presented approach can be used in other silicon-based PUFs as well.