Six out of 10 Britons polled have objected to a European directive to store electronic communications details, which came into force in the UK this month.
The poll by PoliticsHome for Metro, the London morning free newspaper, found that 60% of 1,247 Britons polled did not want details of the time, location and parties to e-mails, internet and phone calls to be recorded to help the fight against terrorism and serious organised crime.
Less than a quarter approved of the measure, which the government estimates will cost taxpayers £45.7m to implement.
Although the legislation covers all "communications service providers", Computer Weekly has learned that not all internet service providers are expected to collect the data.
This raises questions over the completeness and therefore effectiveness of the government's measures.
Some 58% of those polled felt the information would get into the wrong hands. More six out of 10 felt the government already knew too much about them. Only 10% were reassured by the fact that companies rather than government stored the data, and only 15% believed the data were stored securely.
Nearly four out of 10 thought most criminals already knew how to avoid being tracked, so retaining the data would be ineffective.
Some 56% agreed with the statement, "Give me my privacy back: this has gone too far. They can't secure it, they
are collecting more and more, and I do not want to live in a big brother state."
One third agreed with the statement: "The state should have access to data about its people for security purposes - as long as it is not abused, I think the current levels, including these proposals, are about right."