Say Alice publishes (i.e. all parties in the universe) a key or certificate $x$ and sends a secret $s$ to Bob. Bob then publishes some data $d$ (his identity or a message or smt.) and an authentication of the data using the secret, $auth = mac(d,s)$. Dave can now verify the authenticity of $d$, $verify(auth,x)$, and must not be able to extract substantial information about $s$, even when Bob reuses $s$ for different messages. Furthermore, Alice may produce many $(x_i,s_i)$ pairs and all parties have limited computing resources. Finally, the identities of all parties are known and private sidechannels are possible (so $s$ can safely be transmitted to Bob).

This can be implemented using public-key cryptography with $x$ being the public key and $s$ the private key. However, the (public key) algorithms I know of rely on large prime generation (or other costly operations), which I presume is too costly when in practice Alice produces lots of unused key pairs.

Is there a cheap solution to the scenario above?

(the title may be a bit off — if only I knew what I was looking for)


1 Answer 1


Public-key cryptography is not sufficiently computationally burdensome to where other approaches must be used for authentication protocols. Note though that what you describe is not actually public-key based. The verification of the MAC requires Dave and Bob to both have a shared key. Also, note that a random component must be included in some manner in all authentication protocols, else an attacker will be able to mount a man-in-the-middle attack and/or reuse the authentication string in the future. However, similar schemes that are based purely on public-key algorithms do exist, and are more commonly used. Either way, Alice is acting as a $TA$, verifying Bob's identity through some secondary channel and publishing a mechanism by which Dave can confirm that the owner of Bob's private signature algorithm (presumably Bob) is in fact Bob.

In this case, the computationally burdensome process, generating public-private key pairs, occurs not every time authentication takes place, but only when Bob asks Alice for a certificate. Also note that generating public-private key pairs is not particularly expensive, provided access to either an efficient cryptographically secure random number generator or a large pool of entropy, both of which are relatively easy to have.

Beyond that, public-key algorithms are designed so that the encryption and decryption processes can be computed efficiently. For instance, RSA and other Discrete Logarithm based problems have square-and-multiply or some variant. As such, the actual signing and verification step for Bob and Dave is quite simple and efficient, and there are a number of schemes which require only the limited computing power of say, smart cards.

  • $\begingroup$ Regarding "not every time authentication takes place, but only when Bob asks Alice for a certificate": the first part is correct, but the second I've tried to clarify a bit more in the edit. Alice is supposed to show a 'certificate' up front, agnostic of its uses later on. Also the identities of the parties are assumed to be known, so any secret information can be passed on a different channel without MITM attacks. $\endgroup$
    – Flumble
    Oct 25, 2014 at 18:15
  • $\begingroup$ Okay, sorry for misunderstanding. Either way however, the certificate generation step is the only one which is in any way expensive, and even then not so much, plus those are long lasting. The rest of the operation of the protocol is computation, for which every public-private key algorithm is designed to be efficient. $\endgroup$
    – sju
    Oct 25, 2014 at 21:07
  • $\begingroup$ Perhaps you could give an example of a time when you think there'd be an actor in the system with enough computational power to compute a MAC but not enough to do say, modular exponentiation. $\endgroup$
    – sju
    Oct 25, 2014 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.