Master’s Thesis Presentation • Cryptography, Security, and Privacy (CrySP) • Equality Operators for Constant-weight Codewords, with Applications in (Keyword) PIR

Please note: This master’s thesis presentation will be given online.

Rasoul Akhavan Mahdavi, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Florian Kerschbaum

Equality checks are at the heart of many tasks in secure computation such as PIR and PSI. However, equality checks are computationally expensive and are avoided in these tasks due to the computational overhead. This overhead is partly due to the high multiplicative depth of circuits such as the equality circuit. In this work, we propose constant-weight equality operators, which compare constant-weight codewords using a circuit that has a multiplicative depth that depends solely on the Hamming weight of the constant-weight code, not the size of the operands.

Private Information Retrieval (PIR) is one task where equality operations are a solution but avoided due to the high computational cost. In a PIR protocol, a user wishes to query a database without revealing which element is queried to the server. In this thesis, we also detail an architecture for private information retrieval which was previously assumed to be impractical. At the heart of this architecture is the constant-weight equality operator. Our experiments show how constant-weight equality operators outperform existing equality operators and can be used for practical purposes. We also conduct experiments to show the practicality of PIR using our approach and our results show how constant-weight PIR outperforms existing work in aspects of scale such as large domain sizes and large responses.

To join this master’s thesis presentation on BigBlueButton, please go to https://bbb.crysp.org/b/ras-h3f-qjw.