What would the Internet be like without public-key cryptography?

The functioning of the Internet as we know it nowadays depends very heavily on public-key cryptography, including several key root systems that depend on its asymmetric properties.

But what would it be like to not have that tool? Could a sufficiently advanced but less convenient private-key cryptography system still make up for what public-key cryptography does? Would the Internet still be able to function in roughly the way it currently does?

-
Do you allow hash signatures? You can create a digital signature scheme, using nothing apart from cryptographic hashes. – CodesInChaos Dec 21 '12 at 9:37

You can create a public key cryptosystem from any trapdoor function, and you need some form of trapdoor to design a public key cryptosystem. Do you mean "those trapdoor functions, which are currently USED in Internet standards"? The most prominent ones are discrete log of integers, factorization and discrete log in elliptic curves.

If so: Yes, it might be possible to set up new protocols, based on other hard problems, although I can just think of lattice problems atm (SVP,CVP,LWE,etc) and McEliece(based on linear codes). It is easy to use these instead of any factorization-based public key cryptosystem. However, the discrete log problem is a different matter: The group structure does not depend on a specific private key and several (pk,sk) key pairs can operate on the same group. This is required for several primitives, e.g. DH key exchange. I can't think of any hard problem with this, other than discrete log on integers and elliptic curves.

If you want to disallow all known public key cryptosystems (in the sense of all protocols based on trapdoor function)... it would be VERY different. While you could communicate over secure channels with symmetric key crypto, there is no way to exchange a key. If you want to use a key for symmetric encryption, both sides have to know it previously or send it plain.

In this case, some parts of the Internet still would work: You could store a secret key for every single party, with whom you interacted. Based on this key, you can set up a new secure connection again. Authentication might still work with hash functions, etc.

But assuming, you want to visit a website and interact over a secure channel: You have no known secret and have to agree on something. Whatever you send, the routers between you and the website will know. If you can trust ALL of them, you are okay. But any of them could just listen in your secret channel

To sum it up: If the Internet was based on trustworthy infrastructure (providers, exchange points, etc.), it would be similar. However, that would not be the Internet we have today. The current Internet would just not work.

-
I meant in the sense of disallowing all trapdoor functions. So your second explanation is the one I wanted. – Joe Z. Dec 22 '12 at 5:00
"The current internet" just needs secure key agreement, not necessarily trapdoor functions. $\:$ (Although I would count secure key agreement as "public-key cryptography".) $\;\;$ – Ricky Demer Dec 22 '12 at 10:34
How would you create a public-key cryptosystem from hashes? – Joe Z. Dec 25 '12 at 16:09