A generic private information retrieval scheme with parallel multi-exponentiations on multicore processors

Topcuoğlu, Cem and Kaya, Kamer and Savaş, Erkay (2018) A generic private information retrieval scheme with parallel multi-exponentiations on multicore processors. Concurrency and Computation: Practice and Experience (SI), 30 (21). ISSN 1532-0626 (Print) 1532-0634 (Online)

Full text not available from this repository. (Request a copy)


Private Information Retrieval (PIR) enables the data owners to share and/or retrieve data on remote repositories without leaking any information as to which a data item is requested. Although it is always possible to download the entire dataset, this is clearly a waste of bandwidth. A fundamental approach in the literature for PIR is exploiting homomorphic cryptosystems. In these approaches, not one but many modular exponentiations need to be computed and multiplied to obtain the desired result. This multi‐exponentiation operation can be implemented by exponentiating the bases to their corresponding exponents one‐by‐one. However, when the operation is considered as a whole, it can be performed in a more efficient way. Although individual exponentiations are pleasingly parallelizable, the combined multi‐exponentiation requires a careful parallel implementation. In this work, we propose a generic tensor‐based PIR scheme and efficient and novel techniques to parallelize multi‐exponentiations on multicore processors with perfect load balance. The experimental results show that our load balancing techniques make a parallel multi‐exponentiation up to %27 faster when the size of the bases and the exponents are 4096 bits and the number of threads is 16.
Item Type: Article
Uncontrolled Keywords: multicore processors; multi-exponentiation; parallel algorithms; private information retrieval
Subjects: Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 21 Aug 2019 22:04
Last Modified: 31 Jul 2023 15:51
URI: https://research.sabanciuniv.edu/id/eprint/37392

Actions (login required)

View Item
View Item