Problem 1: Oblivious RAM
Consider the following strawman of an Oblivious RAM scheme.
Assume that all blocks are encrypted. Whenever I read/write a block, I always perform
a reencryption of the block regardless of whether the block is being updated.
1) I randomly permute all blocks before storing them on the server.
Suppose block i will be stored at position pi(i) on the server, where
pi is a random permutation.
I store the permutation pi
locally to remember where each block is.
Whenever I
need to read and write a block i, I look up my position map
to obtain pi(i), and I read/write the
position pi(i) on the server.
Why is this scheme insecure?
2) I try to make the above scheme a bit more secure.
When I need to read/write block i, I look up my position map to find pi(i).
In addition to reading/writing position pi(i) on the server, I also choose
k other locations to read and write, to mask my true block of intent.
Is this a secure Oblivious RAM scheme? Why or why not?
Problem 2: Secure Two-Party, Multi-Party Computation
1) Describe at a high level what is secure two-party, multi-party computation, and what
security/privacy property it offers.
2) What do you think are the most compelling 1-2 applications for secure two-party/multi-party computation?
Problem 3: Secure Multi-Party Coin Flip
My friend Chris and I go out to dinner.
We decide to flip a random coin to decide who will pay.
If it is heads, Chris will pay. Otherwise I will pay.
I don't trust Chris's coin because his coin may be biased towards tails, since he
wants me to pay.
Similarly, Chris does not trust my coin either.
1) How can we have a secure coin flipping protocol so both Chris and I will be happy?
2) Now my friends Chris, Sri, and I go out to dinner. We decide to flip a three-way
coin to decide who pays.
I don't trust my friends --- they may even be colluding with each other.
Similarly, Chris does not trust Sri or me. Sri does not trust Chris or me.
What is a secure coin flipping protocol that will make the three of us happy?
3) What about the case for N parties?