Yes, secure handshaking via PKI is a well known and already solved problem. However, as mentioned in the post you originally replied to: "Anti-competition legislation in Europe dictates that the manufacturer cannot stand in the way of the transfer of secret keys." Keys, here, referring to the private half of a public/private keypair.

This means that a manufacturer can't be the exclusive source of resetting a key much in the same way that Verisign isn't the exclusive source of SSL certificates. Due to the anti-competition legislation, you should be able to take your vehicle to any local garage and have it fully serviced whether for a tune-up or to get a key reset. And if a local garage can be employed to reset your key because they have access to the private key required to sign the key request, thieves can do it just as easily.