Abstract
We study the problem of Oblivious Polynomial Evaluation (OPE). There are two parties, Alice who has a polynomial P, and Bob who has an input x. The goal is for Bob to compute P (x) in such way that Alice learns nothing about x and Bob learns only what can be inferred from P (x). Previously existing protocols are based on some intractability assumptions that have not been well studied [15][14], and these protocols are only applicable for polynomials over finite fields. In this paper, we propose efficient OPE protocols which are based on Oblivious Transfer only. Unlike that of [15], slight modifications to our protocols immediately give protocols to handle multi-variate polynomials and polynomials over floating-point numbers. Many important real-world applications deal with floating-point numbers, instead of integers or arbitrary finite fields, and our protocols have the advantage of operating directly on floating-point numbers, instead of going through finite field simulation as that of [14]. As an example, we give a protocol for the problem of Oblivious Neural Learning, where one party has a neural network and the other, with some training set, wants to train the neural network in an oblivious way.
Chapter PDF
Similar content being viewed by others
References
M. Bellare and S. Micali, Non-interactive oblivious transfer and applications, in: Proc. CRYPTO’ 89, Lecture Notes in Computer Science, Vol. 435 (Springer, 1990), pp. 547–557.
D. Boneh, Decision Diffie-Hellman problem, in: Proc. Algorithmic Number Theory 1998, Lecture Notes in Computer Science, Vol. 1423 (Springer, 1998), pp. 48–63.
D. Bleichenbacher and P. Nguyen, Noisy polynomial interpolation and noisy chinese remaindering, in: Proc. EUROCRYPT 2000, Lecture Notes in Computer Science, Vol. 1807 (Springer, 2000), pp. 53–69.
G. Brassard, D. Chaum, and C. Crepeau, Minimum disclosure proofs of knowledge, Journal of Computer and System Sciences 37(2), 1988, pp. 156–189.
G. Brassard, C. Crepeau, and J. M. Robert, Information theoretical reductions among disclosure problems, in: Proc. 27th Ann. IEEE Symp. Foundations of Computer Science, 1986, pp. 168–173.
D. Chaum, C. Crepeau, and I. Damgard, Multiparty unconditionally secure protocols (extended abstract), in: Proc. 20th Ann. ACM Symp. Theory of Computing, 1988, pp. 11–19.
U. Feige, J. Kilian, and M. Naor, A minimal model for secure computation, in: Proc. 26th Ann. ACM Symp. Theory of Computing, 1994, pp. 554–563.
Niv Gilboa, Two party RSA key generation, in: Proc. CRYPTO’ 99, Lecture Notes in Computer Science, Vol. 1666 (Springer, 1999), pp. 116–129.
O. Goldreich, S. Micali, and A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in: Proc. 19th Ann. ACM Symp. Theory of Computing, 1987, pp. 218–229.
J. Håstad, R. Impagliazzo, L. Levin, and M. Luby, Construction of a pseudorandom generator from any one-way function, SIAM Journal on Computing 28(4), 1999, pp. 1364–1396.
R. Impagliazzo and D. Zuckerman, How to recycle random bits, in: Proc. 30th Ann. IEEE Symp. Foundations of Computer Science, 1989, pp. 248–253.
Y. Ishai and E. Kushilevitz, Randomizing polynomials: a new representation with applications to round-efficient secure computaion, in: Proc. 41st Ann. IEEE Symp. Foundations of Computer Science, 2000, pp. 294–304.
J. Kilian, Founding cryptography on oblivious transfer, in: Proc. 20th Ann. ACM Symp. Theory of Computing, 1988, pp. 20–31.
Y. Lindell and B. Pinkas, Privacy preserving data mining, in: Proc. CRYPTO 2000, Lecture Notes in Computer Science, Vol. 1880(Springer, 2000), pp. 36–54.
M. Naor and B. Pinkas, Oblivious transfer and polynomial evaluation, in: Proc. 31st Ann. ACM Symp. Theory of Computing, 1999, pp. 245–254.
T. Sander, A. Young, and M. Yung, Non-interactive cryptocomputing for NC1, in: Proc. 40th Ann. IEEE Symp. Foundations of Computer Science, 1999, pp. 554–567.
A. C. Yao, How to generate and exchange secrets, in: Proc. 27th Ann. IEEE Symp. Foundations of Computer Science, 1986, pp. 162–167.
J. M. Zurada, Introduction to Artificial Neural Systems, PWS Publishing, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chang, YC., Lu, CJ. (2001). Oblivious Polynomial Evaluation and Oblivious Neural Learning. In: Boyd, C. (eds) Advances in Cryptology — ASIACRYPT 2001. ASIACRYPT 2001. Lecture Notes in Computer Science, vol 2248. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45682-1_22
Download citation
DOI: https://doi.org/10.1007/3-540-45682-1_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42987-6
Online ISBN: 978-3-540-45682-7
eBook Packages: Springer Book Archive