In the halls of the dead, you can open a secret area and end up on a beach. There is a chest there but it is locked.
Is the key in that area, or somewhere later? Because I beat the first boss and I still can't find it anywhere in the area. I dug up the entire beach and found nothing.