1. Authentication by digital signature has always required CPUs

Digital counterfeiting is becoming a major social problem.

VuillaumeAlong with the growing use of digital tickets for admission to international sporting events, concerts, and all kinds of other events, the ease with which digital technology can be used to counterfeit these tickets has suddenly ballooned into a major social problem. The usual method of determining whether a digital ticket is real or fake is simply to read out and identify the serial number printed on the ticket. The problem is that it's very difficult with this method for the verifier—say, a ticket-taker at an admission gate—to detect a fake ticket even if the counterfeiter simply made a digital copy of an actual ticket (the originator's ID). A far more reliable method of distinguishing real from fake is authentication technology that uses an encryption algorithm in addition to the ID.

How do authentication schemes work?

VuillaumeIn ID identification, the originator simply sends the verifier the ID, but authentication involves the exchange of several messages between the originator and verifier in addition to sending the ID. First the originator sends a message which is the ID, followed by a message from the verifier to the originator—a challenge code—which is a randomly generated sequence of numbers that is only used once. The originator then sends a message in response to the challenge code that is impossible to counterfeit, thus thwarting the possibility of a replay attack.

Figure 1: Difference between identification and authentication

One technique for implementing this kind of scheme is a digital signature—authentication using a public key infrastructure (PKI). To illustrate how this works, consider this exchange between Alice (the originator) and Bob (the verifier). First Alice sends her public key along with a certificate backed by a trusted third party confirming that the public key is genuine to Bob. After verifying that the public key is legitimate, Bob sends a randomly generated challenge code to Alice that takes the form of a question. Alice then generates a digital signature using the challenge code and her own private key that answers Bob's question which she sends back to Bob as a response. Bob is able to confirm that the digital signature is legitimate using Alice's public key. This all works very well, but the cryptographic calculations require a CPU on both the originator and verifier ends. The need for a CPU is a basic assumption of conventional challenge-response authentication, but it is also a limiting factor for this type of authentication.

Figure 2: PKI based authentication