I don't think lying to the government is automatically illegal (ymmv, ianal, probably varies with jurisdiction). They are generally pretty explicit about the contexts in which lying is illegal (certain signed forms, being under oath etc) which would imply that lying is at least not illegal in other cases.

This is not, by the way, a strictly government related concern. If you lie on a credit card application (and are caught), you're going to have a bad time. But the signed bit of the application is usually completely different from where you're asked to set up "security questions".