We decided that verifiability is the big advantage over Elaine Shi's paper that uses ORAM and Merkle trees.
We decided that option 1 of Olivier’s last email is the best, i.e. to abandon the big commitment and commit to the list of neighbours.
We also had some discussion of how we prove that something (A) is not in the list of neighbours. Two options: a. Go through the list of committed neighbours and, for each one, prove blindly that the committed thing is not A. (e.g. by subtracting a commitment to A from it, and raising to a random value, and showing that the result is not zero.) b. Commit at the beginning to something describing adjacency in the list of neighbours, e.g. by alphabetical order. Then when you have to prove something isn’t there, prove that there are two adjacent elements on either side.
General discussion 13/12:
We decided that verifiability is the big advantage over Elaine Shi's paper that uses ORAM and Merkle trees.
We decided that option 1 of Olivier’s last email is the best, i.e. to abandon the big commitment and commit to the list of neighbours.
We also had some discussion of how we prove that something (A) is not in the list of neighbours. Two options: a. Go through the list of committed neighbours and, for each one, prove blindly that the committed thing is not A. (e.g. by subtracting a commitment to A from it, and raising to a random value, and showing that the result is not zero.) b. Commit at the beginning to something describing adjacency in the list of neighbours, e.g. by alphabetical order. Then when you have to prove something isn’t there, prove that there are two adjacent elements on either side.