Jan 15 2025 43 mins
Private Information Retrieval (PIR) is a cryptographic primitive that enables a client to retrieve a record from a database hosted by one or more untrusted servers without revealing which record was accessed. It has a wide range of applications, including private web search, private DNS, lightweight cryptocurrency clients, and more. While many existing PIR protocols assume that servers are honest but curious, we explore the scenario where dishonest servers provide incorrect answers to mislead clients into retrieving the wrong results.We begin by presenting a unified classification of protocols that address incorrect server behavior, focusing on the lowest level of resistance—verifiability—which allows the client to detect if the retrieved file is incorrect. Despite this relaxed security notion, verifiability is sufficient for several practical applications, such as private media browsing.Later on, we propose a unified framework for polynomial PIR protocols, encompassing various existing protocols that optimize download rate or total communication cost. We introduce a method to transform a polynomial PIR into a verifiable one without increasing the number of servers. This is achieved by doubling the queries and linking the responses using a secret parameter held by the client. About the speaker: Stanislav Kruglik has been a Research Fellow at the School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, since April 2022. He earned a Ph.D. in the theoretical foundations of computer science from the Moscow Institute of Physics and Technology, Russia, in February 2022. He is an IEEE Senior Member and a recipient of the Simons Foundation Scholarship. With over 40 scientific publications, his work has appeared in top-tier venues, including IEEE Transactions on Information Forensics and Security and the European Symposium on Research in Computer Security. His research interests focus on information theory and its applications, particularly in data storage and security.