The paper, due to be presented at the ACM Conference on Computer and Communications Security next month, shows how sensitive medical information on patients could be pilfered using four different attacks.
Researchers discovered the sex, race, age and admission information, among other data, using real patient records from 200 U.S. hospitals.
In the light of increasing cyberattacks against the health care industry, the researchers recommended that the systems they studied "should not be used in the context of" electronic medical records.
They focused on encrypted relational databases based on the design of CryptDB, which allows SQL queries to be performed on scrambled data.
Databases of this design often use property-preserving encryption (PPE) schemes to allow searching. PPE schemes have been long known to leak non-trivial information, "but the extent to which these systems are vulnerable, however, has never been investigated," they wrote.
CryptDB-based systems are often used by organizations because few changes are required to the legacy database infrastructure and they run on encrypted data in "the same way as they would operate on plaintext data," according to the paper. Also, they're fast.
Encryption is seen as one of the best defenses against cyberattacks. If information was recovered, the attackers would need the decryption keys -- which are closely protected -- to read it.
But using encryption also means the data has be continually decrypted in order to be useful. Often, encrypted information is decrypted in a computer's memory, which is dangerous if cyberattackers can get access to that.
"When the encrypted database is operating in a steady-state where enough encryption layers have been peeled to permit the application to run its queries, our experimental results show that an alarming amount of sensitive information can be recovered," the researchers wrote.
One of their "cumulative" attacks discovered the "disease severity, mortality risk, age, length of stay, admission month and admission type of at least 80 percent of the patients for at least 95 percent of the largest 200 hospitals."
Although they focused on databases with electronic medical records, the attacks would likely be successful against human resource or accounting databases, as those systems often store the same kind of demographic data.
The health care industry has been hit hard by hackers. One of the largest U.S. health insurers, Anthem, reported a data breach in February that exposed information on upwards of 80 million people.
The stolen data was never publicly released. Security experts said forensic clues matched the methods used by a long-known China-based group nicknamed Deep Panda.
About a month later, health insurer Premera said customer data, including bank account and clinical data going back to 2002, may have been compromised in an attack, affecting 11 million people.