Information theoretically secure oblivious polynomial evaluation: Model, bounds, and constructions

Goichiro Hanaoka; Hideki Imai; Joern Mueller-Quade; Anderson C.A. Nascimento; Akira Otsuka; Andreas Winter

doi:10.1007/978-3-540-27800-9_6

Information theoretically secure oblivious polynomial evaluation: Model, bounds, and constructions

Goichiro Hanaoka, Hideki Imai, Joern Mueller-Quade, Anderson C.A. Nascimento, Akira Otsuka, Andreas Winter

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

8 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Huaxiong Wang, Josef Pieprzyk, Vijay Varadharajan
Publisher	Springer Verlag
Pages	62-73
Number of pages	12
ISBN (Print)	9783540223795
DOIs	https://doi.org/10.1007/978-3-540-27800-9_6
State	Published - 2004
Externally published	Yes

Publication series

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

Access to Document

10.1007/978-3-540-27800-9_6

Cite this

Hanaoka, G., Imai, H., Mueller-Quade, J., Nascimento, A. C. A., Otsuka, A., & Winter, A. (2004). Information theoretically secure oblivious polynomial evaluation: Model, bounds, and constructions. In H. Wang, J. Pieprzyk, & V. Varadharajan (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 62-73). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3108). Springer Verlag. https://doi.org/10.1007/978-3-540-27800-9_6

Hanaoka, Goichiro ; Imai, Hideki ; Mueller-Quade, Joern et al. / Information theoretically secure oblivious polynomial evaluation : Model, bounds, and constructions. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Huaxiong Wang ; Josef Pieprzyk ; Vijay Varadharajan. Springer Verlag, 2004. pp. 62-73 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{b69c7635216745858bfc1dfc83b52806,

title = "Information theoretically secure oblivious polynomial evaluation: Model, bounds, and constructions",

abstract = "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.",

author = "Goichiro Hanaoka and Hideki Imai and Joern Mueller-Quade and Nascimento, {Anderson C.A.} and Akira Otsuka and Andreas Winter",

year = "2004",

doi = "10.1007/978-3-540-27800-9_6",

language = "English",

isbn = "9783540223795",

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

publisher = "Springer Verlag",

pages = "62--73",

editor = "Huaxiong Wang and Josef Pieprzyk and Vijay Varadharajan",

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

}

Hanaoka, G, Imai, H, Mueller-Quade, J, Nascimento, ACA, Otsuka, A & Winter, A 2004, Information theoretically secure oblivious polynomial evaluation: Model, bounds, and constructions. in H Wang, J Pieprzyk & V Varadharajan (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3108, Springer Verlag, pp. 62-73. https://doi.org/10.1007/978-3-540-27800-9_6

Information theoretically secure oblivious polynomial evaluation: Model, bounds, and constructions. / Hanaoka, Goichiro; Imai, Hideki; Mueller-Quade, Joern et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Huaxiong Wang; Josef Pieprzyk; Vijay Varadharajan. Springer Verlag, 2004. p. 62-73 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3108).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - Information theoretically secure oblivious polynomial evaluation

T2 - Model, bounds, and constructions

AU - Hanaoka, Goichiro

AU - Imai, Hideki

AU - Mueller-Quade, Joern

AU - Nascimento, Anderson C.A.

AU - Otsuka, Akira

AU - Winter, Andreas

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

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

U2 - 10.1007/978-3-540-27800-9_6

DO - 10.1007/978-3-540-27800-9_6

M3 - Chapter

AN - SCOPUS:35048831490

SN - 9783540223795

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

SP - 62

EP - 73

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

A2 - Wang, Huaxiong

A2 - Pieprzyk, Josef

A2 - Varadharajan, Vijay

PB - Springer Verlag

ER -

Hanaoka G, Imai H, Mueller-Quade J, Nascimento ACA, Otsuka A, Winter A. Information theoretically secure oblivious polynomial evaluation: Model, bounds, and constructions. In Wang H, Pieprzyk J, Varadharajan V, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 62-73. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-27800-9_6

Information theoretically secure oblivious polynomial evaluation: Model, bounds, and constructions

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this