The search functionality is under construction.

The search functionality is under construction.

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*(log^{2} *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

Atsunori ICHIKAWA

NTT Social Informatics Laboratories

Wakaha OGATA

Tokyo Institute of Technology

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Atsunori ICHIKAWA, Wakaha OGATA, "Perfectly Secure Oblivious Priority Queue" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 3, pp. 272-280, March 2023, doi: 10.1587/transfun.2022CIP0019.

Abstract: 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*(log^{2} *N*), which is larger than that of the best known statistically secure OPQ but is the same as the known perfectly secure scheme.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022CIP0019/_p

Copy

@ARTICLE{e106-a_3_272,

author={Atsunori ICHIKAWA, Wakaha OGATA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Perfectly Secure Oblivious Priority Queue},

year={2023},

volume={E106-A},

number={3},

pages={272-280},

abstract={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*(log^{2} *N*), which is larger than that of the best known statistically secure OPQ but is the same as the known perfectly secure scheme.},

keywords={},

doi={10.1587/transfun.2022CIP0019},

ISSN={1745-1337},

month={March},}

Copy

TY - JOUR

TI - Perfectly Secure Oblivious Priority Queue

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 272

EP - 280

AU - Atsunori ICHIKAWA

AU - Wakaha OGATA

PY - 2023

DO - 10.1587/transfun.2022CIP0019

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E106-A

IS - 3

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - March 2023

AB - 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*(log^{2} *N*), which is larger than that of the best known statistically secure OPQ but is the same as the known perfectly secure scheme.

ER -