Do we need symmetric cryptosystems?

Question

One question I had to answer in my crypto exam today was:

Do we need symmetric cryptosystems?

As it stands, that's probably a debatable question, so I'd like to reformulate this as:

Are there any situations where symmetric cryptosystems could not be replaced by asymmetric cryptosystems without serious downsides?

I'm not thinking of performance-related issues here; rather, I'm looking for things that would be impossible to achieve in an asymmetric-only model, or at least that would require prohibitively complex or costly implementations.

I would be interested to hear of any answer, since my teacher seemed to suggest that I was missing something, but he wouldn't say what (this was an oral examination).

---

Here's my personal thinking and answer:

I'd tend to say that symmetric crypto is not absolutely necessary, since:

• For two-party communication, using two asymmetric key pairs should be enough to make do without symmetric crypto.
• Generalizing to broadcasting or more-than-two-party communication, the sender would need to have keys for all recipients, but that should be sufficient.
• Signatures should be able to emulate MACs (with the requirement that every group member who would have shared the MAC key now needs to have every group member's public key)
• For encrypting data for personal use (single party), asymmetric encryption should be fine.

The only situation where I can think of difficulties is the distribution of public keys in the absence of a trusted party: in the contrived setting where Alice can securely send data to Bob, but Bob can't securely reply, Alice could transmit a symmetric key to use for subsequent exchanges, while in a fully asymmetric context Bob wouldn't be able to reliably send his public key to Alice. But this sounds like a somewhat contrived example, and I have no doubts that their are good ways of circumventing this (for example, Alice could generate a key pair for Bob, and send it to him).

Other weaknesses that I could think of were encryption & decryption speeds, and resistance to an hypothetical quantum computer, since current symmetric systems just need a doubling of the key length to maintain security, while asymmetric systems based on factoring would be brought to their knees. But then again we have lattice-based cryptography, so that's not a definitive reason why symmetric systems are needed.

Answer 1

Yes, we need symmetric cryptosystems, for many reasons; to give three of these:

1. We need a hash function to make most asymmetric cryptosystems secure (e.g. we simply do not have a secure signature system based on RSA without a hash), and current hash functions are (or are built from) symmetric cryptosystems.
2. All asymmetric encryption cryptosystems are bound to output ciphertext larger than the plaintext, and there are situations where this is a major drawback (e.g. bulk disk encryption).
3. The best asymmetric encryption cryptosystems we have around are some orders of magnitude slower/more energy-hungry than state-of-the-art symmetric ones; it turns out this worsens, badly, if we want to minimize the ciphertext expansion ratio by using huge parameters.

Note: Point 1 has the appearance of being sufficient to prove my assertion, but it is debatable to a degree: perhaps in this question we want the big picture only, and disregard the symmetric internals of all existing asymmetric cryptosystems; and/or perhaps we could devise asymmetric-based hashes (though these would be symmetric cryptosystems in disguise).
Also: we could live with 2, if there was not 3, which in the end is the real killer.

Answer 2

Scroll to the end for tl;dr.

Regarding your contrived example: Alice doesn't have Bob's keypair, but sends a message in such a way that only Bob can read it, eg. puts it in a dead-drop. So she takes out her pen and writes

Hey Bob, could you sign and send me $X$ along with your public key? Here's mine: $P_A$
Signed, Alice

Bob has no way of knowing if the message is indeed from Alice, or from his ex, Mallory, who wants to see if he has cheated her with the aforementioned. He asks a common friend, Charlie, to verify Alice's key. Now Charlie is a good kid but he always seemed a bit too eager to hang out with Mallory and Bob has this nagging feeling that the two may be working together. He decides to ask others as well and get a consensus.

Thus the web of trust is born, and so far we have conceptually no need for symmetric crypto or trusted servers.

Our two protagonists start texting each other right away but find the delay of asymmetric operations quite annoying. Alice's inbox beeps with a new message. She runs the decryptor and goes to make a cup of tea - she has enough time to make two. Her thought go back to her first message to Bob and suddenly remembers there's a random generator on her machine - the same one she used to generate $X$. The idea starts forming in her head, runs some calculations and says to Bob

If we generate the same stream and simply $\mbox{XOR}$ with it the letters we wanna send we'll be orders of magnitude faster! That's so zen!

She puts Aretha Franklin on the cassette player, fires up the new editor she got from that weird Stallman guy and puts together a basic C solution. By the time she's compiling, Bob starts to read her message.

---

I got a bit carried away there but the point is symmetric crypto is much faster and much simpler to implement in software and hardware, like your credit card. And yes, performance is a serious downside.