WASHINGTON (CNN) -- President Bush said Thursday the government is "not mining or trolling through the personal lives of millions of innocent Americans" with a reported program to create a massive database of U.S. phone calls.

"The privacy of ordinary Americans is fiercely protected in all our activities," Bush said in a statement he read to reporters at the White House. "Our efforts are focused on links to al Qaeda and their known affiliates."

Bush's comments followed a USA Today report Thursday that telecommunications giants AT&T, BellSouth and Verizon have provided the National Security Agency with billions of records of domestic phone calls beginning shortly after the attacks of September 11, 2001.

The secretive electronic intelligence agency does not record or listen to the conversations but uses the data -- numbers, times and locations -- to look for patterns that might suggest terrorist activity, the newspaper reported.

Bush would neither confirm nor deny the program's existence, but he told reporters the government "does not listen to domestic phone calls without court approval."

Representatives of Verizon and AT&T declined to comment on what they called national security matters, but insisted they are acting in compliance with the law.

Political repercussions

Bush administration officials already have been under fire for allowing the NSA, without a court order, to monitor calls between people in the United States and people overseas suspected of having links to terrorists.

Lawmakers from both parties said Thursday's report raises new questions about the extent of the administration's surveillance efforts, and some warned it could complicate Bush's nomination of Gen. Michael Hayden, a former NSA director, to replace Porter Goss as head of the CIA.

Republican Sen. Arlen Specter of Pennsylvania, chairman of the Senate Judiciary Committee, said he would call phone company executives to testify about their involvement.

Specter has complained the administration has been reluctant to provide details of the previously known surveillance program since its disclosure in December.

"We will be calling in ATT, Verizon and BellSouth, as well as others, to see some of the underlying facts when we can't find out from the Department of Justice or other administration officials," he said.

According to the USA Today report, Qwest, a Denver, Colorado-based telecommunications company, refused to cooperate with the program. T-Mobile USA, a wireless operator based in Bellevue, Washington, later said it also does not participate, The Associated Press reported.

Senate Majority Leader Bill Frist, a Tennessee Republican, told reporters he "strongly" agrees with Bush and said, "We'll discuss whether hearings are necessary." Republican Sen. Trent Lott of Mississippi said Specter should back off his call for hearings.

"What are people worried about? What is the problem?" asked Lott, a former majority leader. "Are you doing something you're not supposed to?"

Hayden, now deputy national intelligence director, faces a Senate confirmation hearing for the CIA post May 18. Democratic Sen. Dianne Feinstein of California, a member of the Judiciary Committee, said Thursday's disclosure presented "a growing impediment" to his nomination.

"I happen to believe we are on our way to a major constitutional confrontation on Fourth Amendment guarantees of unreasonable search and seizure," said Feinstein, who had expressed no reservations about Hayden earlier this week.

White House spokeswoman Dana Perino said the Bush administration would continue to push Hayden's nomination "full steam ahead."

Hayden, who headed the NSA from March 1999 to April 2005 during the time when the surveillance program began, met Thursday with Sen. Mitch McConnell of Kentucky, the Republican whip, about his nomination.

"All I would want to say is that everything that NSA does is lawful and very carefully done, and that the appropriate members of Congress, the House and Senate, are briefed on all NSA activities," Hayden said after the meeting.

Leahy: 'Shame on us'

Sen. Patrick Leahy of Vermont, the ranking Democrat on the Judiciary Committee, blasted his colleagues for failing to demand answers from the administration.

"Shame on us for being so willing to rubber-stamp anything this administration does," he said. "The Republican-controlled Congress refuses to ask questions, so we have to pick up the paper to find out what is going on."

Republican Sen. Pat Roberts of Kansas, chairman of the Senate Intelligence Committee, said the government was not eavesdropping on the calls, and he said a subcommittee of seven senators had been briefed on the program.

"People should not be alarmed or surprised that intelligence analysts and law enforcement people use the business records or the telephone records of people -- not the content -- in regards to all sorts of things, whether you are a drug dealer, a child pornographer or a terrorist," Roberts said.

Republican Sen. Jon Kyl of Arizona said the debate is "nuts."

"We are in a war, and we've got to collect intelligence on the enemy, and you can't tell the enemy in advance how you are going to do it," Kyl said. "Discussing all of this in public leads to that."

But House Majority Leader John Boehner, a Ohio Republican, said he is "concerned" by the latest disclosure.

"I don't know enough about the details, except that I'm going to find out, because I am not sure why it would be necessary for us to keep and have that kind of information," he said. Hayden will "have a lot more explaining to do," he said.

The law covering surveillance

In a lawsuit privacy advocates brought last year against AT&T, a retired technician reported the company allowed the NSA to conduct what his lawyer called "vacuum cleaner surveillance" of e-mail messages and Internet traffic.

In court papers, Mark Klein said the spy agency was allowed to "split" fiber-optic cables, creating an exact copy of the data carried over those lines.

Critics have accused Bush of violating the Foreign Intelligence Surveillance Act with the program that intercepted calls between a person inside the United States and someone outside.

That 1978 law requires officials seeking to tap phone lines or collect phone records to get the approval of a special court set up to oversee intelligence issues.

The president has argued the congressional resolution that authorized military action after the 9/11 attacks, along with his authority as commander-in-chief of the military, gave him the power to initiate wiretaps without a court order.

The nine Democrats on the House Intelligence Committee issued a statement saying the program reported Thursday also appears to violate the 1978 law and shows that the Bush administration "cannot be trusted to police itself."

Investigation dropped

Four Democratic House members said Thursday they want more details from the Justice Department's Office of Professional Responsibility about the NSA's denial of security clearances to investigate the role of department attorneys in authorizing the agency's domestic surveillance program.

The Justice Department said Wednesday it had been denied security clearances and had dropped its investigation.

Reps. Maurice Hinchey of New York, Henry Waxman of California, John Lewis of Georgia and Lynn Woolsey of California asked a Justice Department official to tell them what "agencies or persons did your office seek out for clearance" and "who made the decision not to give you clearance."

The No. 2 Democrat in the Senate, Sen. Richard Durbin of Illinois, called the development "evidence of a cover-up."

"The fact ... that the Department of Justice has abandoned their own investigation of this administration's wrongdoing because there's been a refusal to give investigators security clearances is clear evidence of a cover-up within the administration."