Hard Instances With Hidden Solutions