We want to implement an Oblivious Min Heap. To do that, we will store the heap in an array, called, $A,$ in the most

obvious form. The $0^{th}$ index of the array is kept free. The first index stores the root. The $(2i{)}^{th}$ location stores the left

child of the node stored in the $i^{th}$ location. The right child is stored in location $2i+1.P_0$ and $P_1$ hold $A_0$ and $A_1($each

of size $n+1,$ i$.$e$.,$ it has $n$ elements; remember, the $0^{th}$ index is kept free$)$ respectively, such that $A_0+A_1=A.$ Of course,

the heap property is that: $A_0[i]+A_1[i]A_0[2i]+A_1[2i]$ and $A_0[i]+A_1[i]A_0[2i+1]+A_1[2i+1].$

In the first part we will write a protocol such that $P_0$ and $P_1$ can do an INSERT operation on this shared array

$($You can increase the size of $A_0$ and $A_1$ as new elements arrive$).P_0$ and $P_1$ get $M_0$ and $M_1$ respectively, such that

$M_0+M_1=M.$ In other words, the parties get additive shares of $M.$ Their goal is to insert $M$ in the secret shared

heap.

$($a$)$ In the first step, they both increase the size of the array by $1.$ What would $P_0$ and $P_1$ put in $A_0[n+2]$ and

$A_1[n+2]\mathrm{.}5$ marks

$($b$)$ After the first step, why is the heap property not necessarily satisfied? $5$ marks

$($c$)$ Suppose you have access to an oblivious comparisons black box, which has the following functionality: $P_0$

holds $(x_0,y_0)$ and $P_1$ holds $(x_1,y_1).$ After the end of the protocol, $P_0$ gets $c_0$ and $P_1$ gets $c_1.$ They have the

property that, if $c_0+c_1=1c_0+c_1=0P_0{P}_1{A}_0[1]A_1[1]A_0{A}_1{A}_0[1]A_1[1]P_0{P}_1$