Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Advanced ICT and Education (ICAICTE)

Unconditionally secure Oblivious Polynomial Evaluation protocol

Li Luyao, Duan Zongtao, Wang Qinglong, Jing Wang, Dai Ming

Published Jan 1, 2013• 2 citations
Publisher

Abstract

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.

DOI
10.2991/icaicte.2013.115

Related papers

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, 2012•2 citations

TinyOLE: Efficient Actively Secure Two-Party Computation from Oblivious Linear Function Evaluation

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, 2017•51 citations

Quantum linear polynomial evaluation based on XOR oblivious transfer compatible with classical partially homomorphic encryption

Li Zhi Yu, Xu, Jie, Fuqun Wang +1 more

XOR oblivious transfer is a universal cryptographic primitive that can be related to linear polynomial evaluation. We firstly introduce some bipartite quantum protocols for XOR oblivious transfer, which are not secure if one party cheats, and some of them can be combined with a classical XOR homomorphic encryption scheme for evaluation of linear polynomials modulo 2 with hybrid security. We then introduce a general protocol using modified versions of the XOR oblivious transfer protocols to evaluate linear polynomials modulo 2 with partial information-theoretic security. When combined with the ability to perform arbitrary quantum computation, this would lead to deterministic interactive two-party computation which is quite secure in the information-theoretic sense when the allowed set of inputs is large. For the task of classical function evaluation, although the quantum computation approach is still usable, we also discuss purely classical post-processing methods based on the proposed linear polynomial evaluation protocols.

arXiv:2305.11114•May 18, 2023•0 citations

TinyOLE: Efficient Actively Secure Two-Party Computation from Oblivious Linear Function Evaluation.

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. This asymptotically matches the best previous protocols, but our protocol at the same time obtains significantly smaller constants hidden by the big-O notation, yielding a highly practical protocol. Conceptually our techniques lift the techniques for basing practical actively secure 2PC of Boolean circuits on OT introduced under the name TinyOT by Nielsen, Nordholt, Orlandi and Burra at Crypto 2012 to the arithmetic setting. In doing so we develop several novel techniques for generating various flavours of OLE and combining these. We believe that the efficiency of our protocols, both in asymptotic and practical terms, establishes OLE and its variants as an important foundation for efficient actively secure 2PC.

•Jan 1, 2017•2 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, 2006•0 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, 1999•633 citations
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.
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.
XOR oblivious transfer is a universal cryptographic primitive that can be related to linear polynomial evaluation. We firstly introduce some bipartite quantum protocols for XOR oblivious transfer, which are not secure if one party cheats, and some of them can be combined with a classical XOR homomorphic encryption scheme for evaluation of linear polynomials modulo 2 with hybrid security. We then introduce a general protocol using modified versions of the XOR oblivious transfer protocols to evaluate linear polynomials modulo 2 with partial information-theoretic security. When combined with the ability to perform arbitrary quantum computation, this would lead to deterministic interactive two-party computation which is quite secure in the information-theoretic sense when the allowed set of inputs is large. For the task of classical function evaluation, although the quantum computation approach is still usable, we also discuss purely classical post-processing methods based on the proposed linear polynomial evaluation protocols.
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. This asymptotically matches the best previous protocols, but our protocol at the same time obtains significantly smaller constants hidden by the big-O notation, yielding a highly practical protocol. Conceptually our techniques lift the techniques for basing practical actively secure 2PC of Boolean circuits on OT introduced under the name TinyOT by Nielsen, Nordholt, Orlandi and Burra at Crypto 2012 to the arithmetic setting. In doing so we develop several novel techniques for generating various flavours of OLE and combining these. We believe that the efficiency of our protocols, both in asymptotic and practical terms, establishes OLE and its variants as an important foundation for efficient actively secure 2PC.
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.
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.