Shamir Secret Sharing is very cool and fairly old. It introduces a tool that inspires many neat applications.

There is a lot of interesting work in privacy preserving databases as well.