Secure Queries on Encrypted Multi-writer Tables

Performing searches on encrypted data is a verycurrent and active area. Several efficient solutions have beenprovided for the single-writer scenario in which all sensitivedata originates with one party (the Data Owner) that encryptsit and uploads it to a public repository. Subsequently, theData Owner (or authorized clients, the Query Sources) perform queries on the encrypted data through a QueryProcessor which has direct access to the public repository. Motivated by the recent trend in pervasive data, we departfrom this model and consider a multi-writer scenario inwhich data originates with several and mutually untrustedparties. In this new scenario the Data Owner providespublic parameters so that each piece of the generated datastream can be put into an encrypted stream, moreover, the Data Owner keeps some related secret informationneeded to generate tokens so that different subscribers canaccess different subsets of the encrypted stream in clear. Weconsider the case in which each piece of the data streamconsists of a fixed number of cells, organized in columns, and the data owner can authorize subscribers to accessindividual data based on the content of the columns. Currentpublic-key functional encryption schemes provide a directand impractical implementation of this scenario. We thus propose a new public-key primitive, Amortized Or-thogonality Encryption or AOE, derived from Inner-ProductEncryption, that can be used to encrypt each piece ofdata stream so that ciphertexts have size proportional tothe un-encrypted data, moreover, encryption and decryptiontake time proportional to the number of columns. Previousschemes would give quadratic complexity. We provide aconstruction of AOE and prove its selective security understandard assumptions in a bilinear setting with prime ordergroup. Using AOE, we implement all the basic operations inour multi-writer scenario in one round of communication. Wedemonstrate the feasibility and effectiveness of our proposalby providing an implementation of our scenario in C++.