Senior Scientist, NTT Research
A New Approach for Computing Attribute Weighted Sums over Encrypted Data
A complex problem in functional encryption cryptography is calculations involving weighted sums, where the output of a function is an arbitrary weight. At the recent Upgrade 2020 NTT Research Summit, NTT Research Senior Scientist Hoeteck Wee gave a talk that spelled out an encryption scheme that tackles just that problem.
Dr. Wee, who is on leave as a CNRS Senior Researcher at ENS, Paris, gave a presentation of work he conducted jointly with Dr. Michel Abdalla, a CNRS Senior Researcher and ENS Adjunct Professor, and Dr. Junqing Gong, who worked on the project while he was a post-doctoral researcher at ENS. (Dr. Gong is now tenure-track faculty at East China Normal University.)
To illustrate how his work might be used in practice, he said to imagine a database of attribute value pairs, comprising xi, a public value, and zi, a private value. The xi value constitutes demographic and geographic attributes while zi is an opinion poll. The challenge lies in computing the average xi value over some subset of the database.
For example, say you want to find individuals over the age of 40 in the state of Wisconsin who watch Fox News, he said. This group could be represented by the predicate f to the public value xi. Now suppose you want to find the folks in group f who responded in a certain way to the poll, zi.
This is where things get interesting. Wee and his team look at the problem from the point of view of functional encryption, where the encryption input is a database and the output is a ciphertext. The key generation algorithm takes as input the function f and outputs a secret key. The decryption algorithm takes as an input the ciphertext and the secret key and outputs the actual weighted sum.
But there’s a problem with that scenario: it leaks too much information to be considered secure. So, he goes on to explore several scenarios for solving the problem, including introducing various randomizers, a decisional Diffie–Hellman (DDH) assumption, and partial sums embedded into the secret key. In the end, he lands on a solution that defines a functional encryption scheme for attribute-weighted sums that apply to a large class of programs.
One property of the solution is that key generation is independent of any central database, so it can generate secret keys without knowing, a priori, the size of the database. The solution also enables the same secret key to decrypt a database of any size, containing any number of entries.
For the full transcript of Hoetech Wee’s presentation, click here.
Watch Hoeteck Wee’s full presentation below or read the paper on which his talk was based.
Functional Encryption for Attribute Weighted Sums