We introduce an information theoretical model for oblivious polynomial evaluation relying on predistributed data, and prove very general lower bounds on the size of the predistributed data, as well as the size of the communications in any (one-round) protocol. We then show that these bounds are tight by exhibiting a scheme for oblivious polynomial evaluation achieveing all the lower bounds simultaneously. We also present a natural generalisation to oblivious linear function evaluation.
|Translated title of the contribution||Information theoretically secure oblivious polynomial evaluation: Model, bounds, and constructions|
|Pages (from-to)||62 - 73|
|Journal||Lecture Notes in Computer Science|
|Publication status||Published - 2004|
Bibliographical notePublisher: Springer-Verlag Berlin
Other identifier: IDS Number: BAK11