Ensure forward secrecy of queries #12
Description
We want to protect against parties learning when a particular record was added to the database. In the p2p model, forward secrecy is obtained by changing the key for Party A whenever a new record is added to the table. A now raises all entries to this new key, and shuffles the table. Party B then has to download this new table to perform a query.
In the outsourced model, we can limit the amount of data being sent between Party A and the compute parties when new records are added. Instead of re-sending shares of every entry in the table, only shares of new entries have to be sent. The compute parties now pick a new key, and perform the protocol of #9 with just those new shares. In parallel, raise the old data to the multiplicative inverse of the old key (to remove it), then raise it again to the new key. Send this to the next compute party, who performs the same operation with its new key. Complete this for every compute party. The final compute party sends the entries back to the others, and they all shuffle this table. This refreshes the old data with a new set of keys.