Just a few decades years ago, everyone's names and phones in the US were freely available to anyone with a phone book. Communications were done in the clear, either via letters (hardly tamper-proof), or via phone (that anyone with access could tap).
Did every American live in a "surveillance state" back then?
What could be tracked from phones back then compared to now is completely different. Phones are basically only called "phones" for historical reasons.
Bad analogy. A phone book tells you nothing about who you are talking to or what you are talking about over the phone. Most free countries don't let law enforcement read letters without a warrant. And even in authoritarian states the police couldn't wiretap everyone or read every letter. The volume was simply too massive for any manual operation.
Digitalization and now AI technology changes this drastically because it makes it drastically cheaper to record and flag human communications.