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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Beaver, D.: Commodity-Based Cryptography (Extended Abstract). In: STOC 1997, pp. 446–455 (1997)
Blundo, C., Masucci, B., Stinson, D.R., Wei, R.: Constructions and Bounds for Unconditionally Secure Non-Interactive Commitment Schemes. Designs, Codes, and Cryptography, Special Issue in Honour of Ron Mullin 26(1-3), 97–110 (2002)
Hanaoka, G., Shikata, J., Zheng, Y., Imai, H.: Unconditionally Secure Digital Signature Schemes Admitting Transferability. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 130–142. Springer, Heidelberg (2000)
Matsumoto, T., Imai, H.: On the Key Predistribution Systems: A Practical Solution to the Key Distribution Problem. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 185–193. Springer, Heidelberg (1988)
Naor, M., Pinkas, B.: Oblivious transfer and polynomial evaluation. In: 31st STOC, pp. 245–254 (1999)
Rivest, R.L.: Unconditionally Secure Commitment and Oblivious Transfer Schemes Using Concealing Channels and a Trusted Initializer, Preprint available from http://theory.lcs.mit.edu/~rivest/Rivest-commitment.pdf
Chang, Y.-C., Lu, C.-J.: Oblivious Polynomial Evaluation and Oblivious Neural Learning. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 369–384. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
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: Wang, H., Pieprzyk, J., Varadharajan, V. (eds) Information Security and Privacy. ACISP 2004. Lecture Notes in Computer Science, vol 3108. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27800-9_6
Download citation
DOI: https://doi.org/10.1007/978-3-540-27800-9_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22379-5
Online ISBN: 978-3-540-27800-9
eBook Packages: Springer Book Archive