But Comey also rejected arguments by some computer scientists who say it's impossible to allow police access to encrypted data without also opening it up to hackers.
"I think Silicon Valley is full of folks [who] have built remarkable things that changed our lives," he said. "Maybe this is too hard, but given the stakes ... we've got to give it a shot."
While companies like Google and Apple were not included in the hearing, senators gave a mixed reaction to the testimonies of Yates and Comey. Some senators suggested it would be nearly impossible to prevent foreign tech vendors from offering encrypted communication products.
Senator Al Franken, a Minnesota Democrat, pressed Yates to provide statistics about the number of criminal cases affected by encrypted data.
Before creating new regulations, Congress needs to have a "clear understanding of the scope and the magnitude of law enforcement's security interests," Franken said.
Yates couldn't provide a number of cases affected, saying it was difficult because, in many cases, police don't seek a warrant when they know the information they want is encrypted. But Cyrus Vance Jr., district attorney in Manhattan, told senators his office has tried to pull data off 92 Apple phones running iOS 8 in the past six months, and on 74 of those devices, the data was encrypted.
Other senators were sympathetic to the encryption dilemma faced by law enforcement agencies. Senator John Cornyn, a Texas Republican, pressed Comey to tell lawmakers that U.S. residents will die if a solution wasn't found. Comey declined, saying he doesn't want to scare people. The FBI will do the best job it can with the crime-fighting tools it has, he said.
Still, Cornyn questioned companies that offer encryption without retaining some access to the data. "It strikes me as irresponsible, and perhaps worse, for a company to intentionally design a product in such a way that prevents them from complying with a lawful court order," he said.
Sign up for CIO Asia eNewsletters.