Accelerating SWHE based PIRs using GPUs

Wei Dai; Yarkın Doröz; Berk Sunar

doi:10.1007/978-3-662-48051-9_12

Accelerating SWHE based PIRs using GPUs

Wei Dai, Yarkın Doröz, Berk Sunar

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Scopus citations

Abstract

In this work we focus on tailoring and optimizing the computational Private Information Retrieval (cPIR) scheme proposed in WAHC 2014 for efficient execution on graphics processing units (GPUs). Exploiting the mass parallelism in GPUs is a commonly used approach in speeding up cPIRs. Our goal is to eliminate the efficiency bottleneck of the Doröz et al. construction which would allow us to take advantage of its excellent bandwidth performance. To this end, we develop custom code to support polynomial ring operations and extend them to realize the evaluation functions in an optimized manner on high end GPUs. Specifically, we develop optimized CUDA code to support large degree/large coefficient polynomial arithmetic operations such as modular multiplication/reduction, and modulus switching. Moreover, we choose same prime numbers for both the CRT domain representation of the polynomials and for the modulus switching implementation of the somewhat homomorphic encryption scheme. This allows us to combine two arithmetic domains, which reduces the number of domain conversions and permits us to perform faster arithmetic. Our implementation achieves 14–34 times speedup for index comparison and 4–18 times speedup for data aggregation compared to a pure CPU software implementation.

Original language	English (US)
Title of host publication	Financial Cryptography and Data Security - FC 2015 International Workshops BITCOIN, WAHC, and Wearable, Revised Selected Papers
Editors	Nicolas Christin, Kurt Rohloff, Michael Brenner, Nicolas Christin, Michael Brenner, Benjamin Johnson, Benjamin Johnson, Kurt Rohloff
Publisher	Springer Verlag
Pages	160-171
Number of pages	12
ISBN (Print)	9783662480502, 9783662480502
DOIs	https://doi.org/10.1007/978-3-662-48051-9_12
State	Published - 2015
Externally published	Yes
Event	International Conference on Financial Cryptography and Data Security, FC 2015 2nd Workshop on Bitcoin Research BITCOIN 2015, 3rd Workshop on Encrypted Computing and Applied Homomorphic Cryptography, WAHC 2015, and 1st Workshop on Wearable Security and Privacy, Wearable 2015 - San Juan, Puerto Rico Duration: Jan 30 2015 → Jan 30 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8976
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	International Conference on Financial Cryptography and Data Security, FC 2015 2nd Workshop on Bitcoin Research BITCOIN 2015, 3rd Workshop on Encrypted Computing and Applied Homomorphic Cryptography, WAHC 2015, and 1st Workshop on Wearable Security and Privacy, Wearable 2015
Country/Territory	Puerto Rico
City	San Juan
Period	1/30/15 → 1/30/15

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Keywords

Homomorphic encryption
NTRU
Private information retrieval

Access to Document

10.1007/978-3-662-48051-9_12

Cite this

Dai, W., Doröz, Y., & Sunar, B. (2015). Accelerating SWHE based PIRs using GPUs. In N. Christin, K. Rohloff, M. Brenner, N. Christin, M. Brenner, B. Johnson, B. Johnson, & K. Rohloff (Eds.), Financial Cryptography and Data Security - FC 2015 International Workshops BITCOIN, WAHC, and Wearable, Revised Selected Papers (pp. 160-171). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8976). Springer Verlag. https://doi.org/10.1007/978-3-662-48051-9_12

Dai, Wei ; Doröz, Yarkın ; Sunar, Berk. / Accelerating SWHE based PIRs using GPUs. Financial Cryptography and Data Security - FC 2015 International Workshops BITCOIN, WAHC, and Wearable, Revised Selected Papers. editor / Nicolas Christin ; Kurt Rohloff ; Michael Brenner ; Nicolas Christin ; Michael Brenner ; Benjamin Johnson ; Benjamin Johnson ; Kurt Rohloff. Springer Verlag, 2015. pp. 160-171 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1ba6a62d12c14f0ca52986fda4167a40,

title = "Accelerating SWHE based PIRs using GPUs",

abstract = "In this work we focus on tailoring and optimizing the computational Private Information Retrieval (cPIR) scheme proposed in WAHC 2014 for efficient execution on graphics processing units (GPUs). Exploiting the mass parallelism in GPUs is a commonly used approach in speeding up cPIRs. Our goal is to eliminate the efficiency bottleneck of the Dor{\"o}z et al. construction which would allow us to take advantage of its excellent bandwidth performance. To this end, we develop custom code to support polynomial ring operations and extend them to realize the evaluation functions in an optimized manner on high end GPUs. Specifically, we develop optimized CUDA code to support large degree/large coefficient polynomial arithmetic operations such as modular multiplication/reduction, and modulus switching. Moreover, we choose same prime numbers for both the CRT domain representation of the polynomials and for the modulus switching implementation of the somewhat homomorphic encryption scheme. This allows us to combine two arithmetic domains, which reduces the number of domain conversions and permits us to perform faster arithmetic. Our implementation achieves 14–34 times speedup for index comparison and 4–18 times speedup for data aggregation compared to a pure CPU software implementation.",

keywords = "Homomorphic encryption, NTRU, Private information retrieval",

author = "Wei Dai and Yarkın Dor{\"o}z and Berk Sunar",

note = "Funding Information: Funding for this research was in part provided by the US National Science Foundation CNS Award #1319130. Publisher Copyright: {\textcopyright} International Financial Cryptography Association 2015.; International Conference on Financial Cryptography and Data Security, FC 2015 2nd Workshop on Bitcoin Research BITCOIN 2015, 3rd Workshop on Encrypted Computing and Applied Homomorphic Cryptography, WAHC 2015, and 1st Workshop on Wearable Security and Privacy, Wearable 2015 ; Conference date: 30-01-2015 Through 30-01-2015",

year = "2015",

doi = "10.1007/978-3-662-48051-9_12",

language = "English (US)",

isbn = "9783662480502",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "160--171",

editor = "Nicolas Christin and Kurt Rohloff and Michael Brenner and Nicolas Christin and Michael Brenner and Benjamin Johnson and Benjamin Johnson and Kurt Rohloff",

booktitle = "Financial Cryptography and Data Security - FC 2015 International Workshops BITCOIN, WAHC, and Wearable, Revised Selected Papers",

address = "Germany",

}

Dai, W, Doröz, Y & Sunar, B 2015, Accelerating SWHE based PIRs using GPUs. in N Christin, K Rohloff, M Brenner, N Christin, M Brenner, B Johnson, B Johnson & K Rohloff (eds), Financial Cryptography and Data Security - FC 2015 International Workshops BITCOIN, WAHC, and Wearable, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8976, Springer Verlag, pp. 160-171, International Conference on Financial Cryptography and Data Security, FC 2015 2nd Workshop on Bitcoin Research BITCOIN 2015, 3rd Workshop on Encrypted Computing and Applied Homomorphic Cryptography, WAHC 2015, and 1st Workshop on Wearable Security and Privacy, Wearable 2015, San Juan, Puerto Rico, 1/30/15. https://doi.org/10.1007/978-3-662-48051-9_12

Accelerating SWHE based PIRs using GPUs. / Dai, Wei; Doröz, Yarkın; Sunar, Berk.
Financial Cryptography and Data Security - FC 2015 International Workshops BITCOIN, WAHC, and Wearable, Revised Selected Papers. ed. / Nicolas Christin; Kurt Rohloff; Michael Brenner; Nicolas Christin; Michael Brenner; Benjamin Johnson; Benjamin Johnson; Kurt Rohloff. Springer Verlag, 2015. p. 160-171 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8976).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Accelerating SWHE based PIRs using GPUs

AU - Dai, Wei

AU - Doröz, Yarkın

AU - Sunar, Berk

N1 - Funding Information: Funding for this research was in part provided by the US National Science Foundation CNS Award #1319130. Publisher Copyright: © International Financial Cryptography Association 2015.

PY - 2015

Y1 - 2015

N2 - In this work we focus on tailoring and optimizing the computational Private Information Retrieval (cPIR) scheme proposed in WAHC 2014 for efficient execution on graphics processing units (GPUs). Exploiting the mass parallelism in GPUs is a commonly used approach in speeding up cPIRs. Our goal is to eliminate the efficiency bottleneck of the Doröz et al. construction which would allow us to take advantage of its excellent bandwidth performance. To this end, we develop custom code to support polynomial ring operations and extend them to realize the evaluation functions in an optimized manner on high end GPUs. Specifically, we develop optimized CUDA code to support large degree/large coefficient polynomial arithmetic operations such as modular multiplication/reduction, and modulus switching. Moreover, we choose same prime numbers for both the CRT domain representation of the polynomials and for the modulus switching implementation of the somewhat homomorphic encryption scheme. This allows us to combine two arithmetic domains, which reduces the number of domain conversions and permits us to perform faster arithmetic. Our implementation achieves 14–34 times speedup for index comparison and 4–18 times speedup for data aggregation compared to a pure CPU software implementation.

AB - In this work we focus on tailoring and optimizing the computational Private Information Retrieval (cPIR) scheme proposed in WAHC 2014 for efficient execution on graphics processing units (GPUs). Exploiting the mass parallelism in GPUs is a commonly used approach in speeding up cPIRs. Our goal is to eliminate the efficiency bottleneck of the Doröz et al. construction which would allow us to take advantage of its excellent bandwidth performance. To this end, we develop custom code to support polynomial ring operations and extend them to realize the evaluation functions in an optimized manner on high end GPUs. Specifically, we develop optimized CUDA code to support large degree/large coefficient polynomial arithmetic operations such as modular multiplication/reduction, and modulus switching. Moreover, we choose same prime numbers for both the CRT domain representation of the polynomials and for the modulus switching implementation of the somewhat homomorphic encryption scheme. This allows us to combine two arithmetic domains, which reduces the number of domain conversions and permits us to perform faster arithmetic. Our implementation achieves 14–34 times speedup for index comparison and 4–18 times speedup for data aggregation compared to a pure CPU software implementation.

KW - Homomorphic encryption

KW - NTRU

KW - Private information retrieval

UR - http://www.scopus.com/inward/record.url?scp=84950292014&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84950292014&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-48051-9_12

DO - 10.1007/978-3-662-48051-9_12

M3 - Conference contribution

AN - SCOPUS:84950292014

SN - 9783662480502

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 160

EP - 171

BT - Financial Cryptography and Data Security - FC 2015 International Workshops BITCOIN, WAHC, and Wearable, Revised Selected Papers

A2 - Christin, Nicolas

A2 - Rohloff, Kurt

A2 - Brenner, Michael

A2 - Christin, Nicolas

A2 - Brenner, Michael

A2 - Johnson, Benjamin

A2 - Rohloff, Kurt

PB - Springer Verlag

T2 - International Conference on Financial Cryptography and Data Security, FC 2015 2nd Workshop on Bitcoin Research BITCOIN 2015, 3rd Workshop on Encrypted Computing and Applied Homomorphic Cryptography, WAHC 2015, and 1st Workshop on Wearable Security and Privacy, Wearable 2015

Y2 - 30 January 2015 through 30 January 2015

ER -

Dai W, Doröz Y, Sunar B. Accelerating SWHE based PIRs using GPUs. In Christin N, Rohloff K, Brenner M, Christin N, Brenner M, Johnson B, Johnson B, Rohloff K, editors, Financial Cryptography and Data Security - FC 2015 International Workshops BITCOIN, WAHC, and Wearable, Revised Selected Papers. Springer Verlag. 2015. p. 160-171. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-48051-9_12

Accelerating SWHE based PIRs using GPUs

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this