In one of our exams for a non security course, the professor asked for one key problem for public key cryptography and explain why is it a hard problem.

Several students claimed that the hard problem was establishing trust that a certain public key actually belongs to the person who claims that it is their public key.

I believe that the bigger problem is the cost associated with encrypting and decrypting the messages. Isn't that why we do a key exchange in TLS in the first place? To save cost for future messages?

Can someone please explain why establishing trust is the hard part? I believe that having certificate authorities pretty much fixes that problems for us.

  • 4
    I think you are using a different definition of "hard." Your definition of "hard" is "more expensive to compute," while your professor's definition of "hard" is "difficult to do well." Certificate authorities aren't that great because you have to rely on the integrity of a third party. So in a sense, this problem is so "hard" that it isn't entirely solved. The need for certificate authorities (and the whole public key infrastructure surrounding it) kind of sticks out like a sore thumb in public-key crypto implementations.
    – tlng05
    May 12 '18 at 18:19

Well, having key exchanges and similar hybrid combinations of symmetric and asymmetric crypto solves problem with slow public key cryptography.

On the other hand, while the Public Key Infrastructure (PKI) somewhat solves the problem of verifying public keys, it is very far from perfect. Just check all the problems with CAs that happened over the years. DigiNotar was entirely compromised, Symantec was recently distrusted because they did not verify client correctly, WoSign was distrusted because they backdated certificates, StartCom was distrusted because it was secretly bought by WoSign and did not disclose it as is required, etc.

The problem with slowness of asymmetric crypto is pretty much solved, while the PKI is a huge mess. While we are certainly making headway with things like CAA and Certificate Transparency being mandatory now, we have long way to go before this problem is sufficiently solved. It is also a lot more complicated to solve. There are so many technologies involved already and there will probably have to be more to get to a reasonable point. That is why this is considered a harder problem to solve.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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