Secure Games with Polynomial Expression

Aggelos Kiayias, Moti Yung

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We present the first private information retrieval (PIR) scheme which is both, deterministically correct and has poly-logarithmic communication complexity. Our PIR protocol is symmetrically secure, and improves by a few orders of magnitude the known probabilistically correct poly-logarithmic scheme. This result is achieved as an application of our methodology which introduces a broad family of games, called Secure Games with Polynomial Expressions (SGPEs), that involve two interacting players: Alice and Bob. The objective of these games is the secure “interactive computation” of the value of a polynomial expression which is made up of polynomials and field elements that both players distributedly contribute to the game. The players wish to keep some or all the data (field elements and polynomials) they contribute to the game, secret and independently secure. We show that any SGPE can be played much more efficiently than by using generic methods, and so that no party reveals more than what it intends to. Besides the above mentioned PIR application, we present additional applications such as the “lists’ intersection predicate” which is useful for secure conduct of e-commerce procedures, such as negotiation methods known as “settlement escrows” in the legal/ economics/ business literature.
Original languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication28th International Colloquium, ICALP 2001 Crete, Greece, July 8--12, 2001 Proceedings
EditorsFernando Orejas, Paul G. Spirakis, Jan van Leeuwen
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages12
ISBN (Electronic)978-3-540-48224-6
ISBN (Print)978-3-540-42287-7
Publication statusPublished - 2001

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'Secure Games with Polynomial Expression'. Together they form a unique fingerprint.

Cite this