Authors: Manuel Barbosa, Dario Catalano, Azam Soleimanian and Bogdan Warinschi
We construct functional encryption (FE) schemes for the orthogonality (OFE) relation where each ciphertext encrypts some vector x and each decryption key, associated to some vector y, allows to determineif x isorthogonalto y ornot. Motivated by compelling applications, we aim at schemes which are function hidding, i.e. y is not leaked.
Our main contribution are two such schemes, both rooted in existing constructions of FE for inner products (IPFE), i.e., where decryption keys reveal the inner product of x and y. The first construction builds upon the very efficient IPFE by Kim et al. (SCN 2018) but just like the original scheme its security holds in the generic group model (GGM). The second scheme builds on recent developments in the construction of efficient IPFE schemes in the standard model and extends the work of Wee (TCC 2017) in leveraging these results for the construction of FE for Boolean functions. Conceptually, both our constructions can be seen as further evidence that shutting down leakage from inner product values to only a single bit for the orthogonality relation can be done with little overhead, not only in the GGM, but also in the standard model.
We discuss potential applications of our constructions to secure data bases and provide efficiency benchmarks. Our implementation shows that the first scheme is extremely fast and ready to be deployed in practical applications.