The search functionality is under construction.
The search functionality is under construction.

Perfectly Secure Oblivious Priority Queue

Atsunori ICHIKAWA, Wakaha OGATA

  • Full Text Views

    0

  • Cite this

Summary :

An Oblivious Priority Queue (OPQ) is a cryptographic primitive 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 two operations; Inserting an element and extracting the top-priority element, which are the minimal requirement for a priority queue. In addition, this OPQ allows an adversary to observe operations in progress, which leaks the exact number of elements in the data structure. On the other hand, there are many subsequent works for OPQs that implement additional operations of a priority queue, hide the running operations, and improve efficiency. Though the recent works realize optimal efficiency, all of them achieve only statistical or computational security. Aiming to reconcile perfect security of the first OPQ with all functions (including the operation hiding) supported by recent OPQs, we construct a novel perfectly secure OPQ that can simulate 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 is O(log2 N), which is larger than that of the best known statistically secure OPQ but is the same as the known perfectly secure scheme.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.3 pp.272-280
Publication Date
2023/03/01
Publicized
2022/08/23
Online ISSN
1745-1337
DOI
10.1587/transfun.2022CIP0019
Type of Manuscript
Special Section PAPER (Special Section on Cryptography and Information Security)
Category

Authors

Atsunori ICHIKAWA
  NTT Social Informatics Laboratories
Wakaha OGATA
  Tokyo Institute of Technology

Keyword