Pico without public keys

Pico is a user authentication system that does not require
remembering secrets. It is based on a personal handheld token that holds
the user’s credentials and that is unlocked by a “personal aura” generated
by digital accessories worn by the owner. The token, acting as prover,
engages in a public-key-based authentication protocol with the verifier.
What would happen to Pico if success of the mythical quantum computer
meant secure public key primitives were no longer available, or if for
other reasons such as energy consumption we preferred not to deploy
them? More generally, what would happen under those circumstances
to user authentication on the web, which relies heavily on public key
cryptography through HTTPS/TLS?
Although the symmetric-key-vs-public-key debate dates back to the 1990s,
we note that the problematic aspects of public key deployment that were
identified back then are still ubiquitous today. In particular, although
public key cryptography is widely deployed on the web, revocation still
doesn’t work.
We discuss ways of providing desirable properties of public-key-based
user authentication systems using symmetric-key primitives and tamperevident
tokens. In particular, we present a protocol through which a
compromise of the user credentials file at one website does not require
users to change their credentials at that website or any other.
We also note that the current prototype of Pico, when working in compatibility
mode through the Pico Lens (i.e. with websites that are unaware
of the Pico protocols), doesn’t actually use public key cryptography,
other than that implicit in TLS. With minor tweaks we adopt this as the
native mode for Pico, dropping public key cryptography and achieving
much greater deployability without any noteworthy loss in security.