I've read that ancient Roman concrete was manufactured in a way that is seemingly lost to time. It's also practically impervious to the elements.

http://www.romanconcrete.com/docs/spillway/spillway.htm

If we want to find a way to build beneath the sea that's a good place to start.