I live in the US, and there are many cases where lying is illegal, including perjury, libel, slander, fraud, filing a false police report, failing to disclose certain known facts during a sale, misrepresenting earnings of a corporation, and so on.
A fair point, and also true where I live. Let me modify my original statement: lying, at least where I live, is in most cases not illegal.