A Novel Unconditionally Secure Oblivious Polynomial Evaluation Protocol

H. Vanishree, Koshy George

Published Jan 1, 2009• 5 citations

Abstract

Abstract—Oblivious polynomial evaluation is a protocol involving two parties, a sender whose input is a polynomial P, and a receiver whose input is a value x. At the end of the protocol, the receiver learns P (x) and nothing more about P, while the sender remains oblivious of both x and P (x). It is used as a primitive in many applications including protocols for private comparison of data, for mutually authenticated key exchange based on (possibly weak) passwords, and for anonymous coupons. In this paper, we describe a novel unconditionally secure oblivious polynomial evaluation protocol. Keywords—Multi-Party Computation, Oblivious Transfer, Oblivious Polynomial Evaluation.

Related papers

Unconditionally secure Oblivious Polynomial Evaluation protocol

Li Luyao, Duan Zongtao, Wang Qinglong +2 more

Oblivious polynomial evaluation is a protocol involving two parties: a sender whose input is a polynomial and a receiver whose input is a value a .Most of existing Oblivious Polynomial Evaluation protocols were built based on some cryptographically intractable problems which made them a higher computation complexity.By using some random and hiding secure information in them, this paper presents an unconditionally secure oblivious polynomial evaluation protocol.It does not rely on any cryptographic assumption and involves only simple computation.Further, our protocol does not include any third party and is more practice.

International Conference on Advanced ICT and Education (ICAICTE)Jan 1, 20132 citations

Cryptanalysis on a novel unconditionally secure oblivious polynomial evaluation protocol.

Qinglong Wang, Li Xu

Vanishree et.al proposed a novel unconditionally oblivious polynomial evaluation protocol and they claimed that can fulfill both sender and receiver’s security. Here, this protocol is cryptanalyzed. We find that it has a fatal fault which cannot implement the receiver’s security at all and show the detail analyzing process. Keywords oblivious polynomial evaluation, oblivious transfer, multi-party computation

Jan 1, 20122 citations

Information-Theoretically Secure Oblivious Polynomial Evaluation in the Commodity-Based Model

Rafael Tonicelli, Anderson C. A. Nascimento, Rafael Dowsley +4 more

Abstract. Oblivious polynomial evaluation (OPE) consists of a two-party protocol where a sender inputs a polynomial p(x), and a receiver inputs a single value x0. At the end of the protocol, the sender learns nothing and the receiver learns p(x0). This paper deals with the problem of oblivious polynomial evaluation under an information-theoretic perspective, which is based on recent definitions of Unconditional Security developed by Crépeau et al. [11]. In this paper, we propose an information-theoretic model for oblivious polynomial evaluation relying on pre-distributed data, and prove very general lower bounds on the size of the pre-distributed data, as well as the size of the communications in any protocol. It is demonstrated that these bounds are tight by obtaining a round-optimal OPE protocol, which meets the lower bounds simultaneously. We present a natural generalization to OPE called oblivious linear functional evaluation.

Oct 28, 20134 citations

Oblivious transfer and polynomial evaluation

Moni Naor, Benny Pinkas B

We describe efficient constructions for two oblivious twoparty computation problems: l-out-of-N Oblivious Transfer &d 'Oblivious Poly&nial Evaluation.The oblivious polynomial evaluation protocol is based on a new intractability assumption which is closely related to noisy polynomial re construction.A direct corollary of the l-out-of-N OT protccol is an efficient transformation of any Private Information Retrieval (PIR) protocol to a Symmetric PIR (SPIR) prc-tow1 without increasing the number of databases.The new construction for l-out-of-N OT is highly efficient -it requires only log N executions of a l-out-of-2 OT protocol.We also present a construction for k-out-of-N OT which is more efficient than k repetitions of l-out-of-N OT.The efficiency of the new OT protocols makes them useful for a variety of applications.These include oblivious sampling which can be used to securely compare the sizes of web search engines, protocols for privately solving the list intersection problem and for mutually authenticated key exchange based on (possibly weak) passwords, and protocols for anonymity preserving web usage metering.

ACM Symposium on Theory of Computing (STOC)May 1, 1999635 citations

TinyOLE

Nico Döttling, Satrajit Ghosh, Jesper Buus Nielsen +2 more

We introduce a new approach to actively secure two-party computation based on so-called oblivious linear function evaluation (OLE), a natural generalisation of oblivious transfer (OT) and a special case of the notion of oblivious polynomial evaluation introduced by Naor and Pinkas at STOC 1999. OLE works over a finite field F. In an OLE the sender inputs two field elements a ƒ F and b ƒ F, and the receiver inputs a field element x ∈ F and learns only ƒx) = ax + b. Our protocol can evaluate an arithmetic circuit over a finite field F given black-box access to OLE for F. The protocol is unconditionally secure and consumes only a constant number of OLEs per multiplication gate. An OLE over a field F of size O(2κ) be implemented with communication O(κ). This gives a protocol with communication complexity O(C κ) for large enough fields, where C is an arithmetic circuit computing the desired function.

ACM SIGSAC Conference on Computer and Communications Security (CCS)Oct 27, 201749 citations

General Two-Party Oblivious Circuit Evaluation

Sufyan T. F. Al-Janabi

A two-party oblivious circuit evaluation (2P- OCE) protocol is a way for a party Alice owns a secret x and another party Bob owns a secret y to compute the value of an agreed upon function f(x,y), where f can be computed by a polynomial sized Boolean circuit. This is done in such a way that Alice learns nothing about y and Bob learns nothing about x, except for what can be inferred from one's private input and the public value of f(x,y). This paper presents a general, correct, fair, honest, and maximum privacy 2P-OCE protocol that is based on a set of reductions to more simple cryptographic primitives. The protocol uses the primitives of one-out-of-two oblivious transfer (1-2-OT) and bit commitment (BC) as black boxes. Consequently, the protocol may be implemented with or without computational assumptions, depending on the type of 1-2-OT and BC used by participants.

Dec 1, 20060 citations