This disclosure involves the notion of using physical objects to generate public key-based authenticators and, in particular, to use “everyday” physical objects to create a generator seed for a key generator that will use that seed to generate a key pair comprising a public key, and its associated private key. In a preferred approach, the physical object is used to create a digital representation (of the physical object) that, together with some uniqueness associated to the user, gives rise to a key generator seed value. Without knowledge of (a) the physical object itself, (b) how the physical object characteristic is converted (to a digital representation), and (c) the uniqueness value, an attacker cannot reproduce the key generator seed (or the key(s) generated from that seed).