Constant-Rank/title> </head> <body> <table> <tr> <td> <H4 ALIGN=CENTER> <FONT COLOR="#333333" SIZE=+1>Constant-Round Private Database Queries</FONT> </H4> </td> </tr> <tr> <td> We consider several private database query problems. The starting point of this work is the {\em element rank} problem: the server holds a database of $n$ integers, and the user an integer $q$; the user wishes to find out how many database records are smaller than $q$, without revealing $q$; nothing else about the database should be disclosed. We show a non-interactive communication-efficient solution to this problem. We then use it to solve more complex private database queries: range queries, range queries in plane and higher-dimensional generalizations of element rank. We also show an improved solution to the {\em $k^{th}$ ranked element} problem \cite{AMP04}, and a solution to {\em private keyword search} \cite{FIPR05} using weaker assumptions than those of \cite{FIPR05}. All our solutions assume semi-honest adversarial behaviour. </td></tr> <tr> <td> Files: [<a href = "const-rank.pdf"> pdf </a>][<a href = "Const-Rank.ppt"> ICALP07 talk </a>] </td></tr> </table> </body> </html>