Perfectly Secure Oblivious Priority Queue

摘要

An Oblivious Priority Queue (OPQ) is a cryptographicprimitive that enables a client to outsource its data to a dishonest server,and also to securely manage the data according to a priority queue algorithm.Though the first OPQ achieves perfect security, it supports only twooperations; Inserting an element and extracting the top-priority element,which are the minimal requirement for a priority queue. In addition, thisOPQ allows an adversary to observe operations in progress, which leaks theexact number of elements in the data structure. On the other hand, thereare many subsequent works for OPQs that implement additional operationsof a priority queue, hide the running operations, and improve efficiency.Though the recent works realize optimal efficiency, all of them achieve onlystatistical or computational security. Aiming to reconcile perfect securityof the first OPQ with all functions (including the operation hiding) supportedby recent OPQs, we construct a novel perfectly secure OPQ that cansimulate the following operations while hiding which one is in progress;Inserting an element, extracting the top-priority one, deleting an element,and modifying the priority of an element. The efficiency of our scheme isO(log~2 N), which is larger than that of the best known statistically secureOPQ but is the same as the known perfectly secure scheme.