Is this a valid real-time authentication scheme?

The scenario in Alice/Bob/Cindy terms:

Alice approaches someone she doesn't know, but thinks is Bob, and asks for some secret information. Bob doesn't know and doesn't trust Alice, but Alice says she knows Cindy.

To prove that, Bob calls Cindy, who does know Bob, and asks for half of an asymmetric key pair. Bob then challenges Alice to encrypt a "secret" message (it's not shouted to the world, but it is transmitted in plaintext; it should therefore be cryptographically unpredictable). Alice calls Cindy, who really does know Alice, and Cindy gives Alice the other half of the key pair, which Alice uses to encrypt the secret message. Alice gives Bob the encrypted message, along with a message that she wants Bob to encrypt. Bob decrypts his message, gets the right answer, and is now convinced that Alice knows Cindy and is therefore to be trusted with the secret info. He then encrypts the message Alice gave him with his key, sends it back to Alice, and Alice decrypts it with hers to prove that Bob also really does know Cindy and isn't just taking what Alice says for granted. This happens without Alice or Bob having to tell each other how they know Cindy, and without Cindy having to know what secret messages Bob and Alice exchanged using the key. After this, the keys and secret messages can be discarded, and secure communication for the transfer of the secret information can be negotiated.

An attacker, Denise, impersonating Alice, would have to convince Cindy that she is in fact Alice, by speaking in Alice's voice and knowing things only Alice and Cindy would know. Or, Denise would have to have an accomplice, Emily, who would impersonate Cindy when talking to Bob.

In the real world, this would be an easy way for two programs who have authenticated with a central service to prove they have done so, without any knowledge about how that was done required to be shared.

The question is, is this viable, or is there a fundamental weakness in the scheme?

-
Why so weird? Can't you simply have Cindy authenticate a statement "Alice has the following public key"? That authentication can either be a signature or a key-exchange+MAC. –  CodesInChaos Nov 19 '12 at 19:45
MACs can be spoofed, and long-term-use keys like in signatures can be cracked. The key pair in question here is used for a couple of seconds at most, it's near useless forever after, and the only thing it tests is that both Alice and Bob know Cindy well enough to get the two halves of the key pair, and thus that they should trust each other. The information actually encrypted with it would be plainly visible to any man in the middle, and as long as the information is highly unlikely to be repeated, that's just fine. –  KeithS Nov 19 '12 at 19:51
MAC=Message authentication code, not MAC address. So no spoof for you. –  CodesInChaos Nov 19 '12 at 19:55
Ah. got it. Well, this is still two-way; most clients don't have X.509 certificates, but you could use it to have two clients of the same secure server handshake and trust each other based on them both being authenticated by the server, with disposable proof of authentication between the two clients that does not involve exchanging the credentials or authentication results from their server auth. –  KeithS Nov 19 '12 at 19:57
I'm surprised no one has mentioned the word "Kerberos" here before now. $\hspace{1.5 in}$ –  Ricky Demer Nov 19 '12 at 22:43