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

arXiv:1906.04862 · IEEE Transactions on Parallel and Distributed Systems

A Comment on Privacy-Preserving Scalar Product Protocols as Proposed in “SPOC”

Thomas Schneider, Amos Treiber

Published Sep 3, 2019• 10 citations
arXivHTMLPDF

Abstract

Privacy-preserving scalar product (PPSP) protocols are an important building block for secure computation tasks in various applications. Lu et al. (TPDS'13) introduced a PPSP protocol that does not rely on cryptographic assumptions and that is used in a wide range of publications to date. In this comment paper, we show that Lu et al.'s protocol is insecure and should not be used. We describe specific attacks against it and, using impossibility results of Impagliazzo and Rudich (STOC'89), show that it is inherently insecure and cannot be fixed without relying on at least some cryptographic assumptions.

DOI
10.1109/tpds.2019.2939313

Related papers

Towards Empirical Aspects of Secure Scalar Product

I-Cheng Wang, Chih-Hao Shen, Tsan‐sheng Hsu +3 more

Privacy is ultimately important, and there is a fair amount of research about it. However, few empirical studies about the cost of privacy are conducted. In the area of secure multiparty computation, the scalar product has long been reckoned as one of the most promising building blocks in place of the classic logic gates. The reason is not only the scalar product complete, which is as good as logic gates, but also the scalar product is much more efficient than logic gates. As a result, we set to study the computation and communication resources needed for some of the most well-known and frequently referred secure scalar-product protocols, including the composite-residuosity, the invertible-matrix, the polynomial-sharing, and the commodity-based approaches. Besides the implementation remarks of these approaches, we analyze and compare their execution time, computation time, and random number consumption, which are the most concerned resources when talking about secure protocols. Moreover, Fairplay the benchmark approach implementing Yao's famous circuit evaluation protocol, is included in our experiments in order to demonstrate the potential for the scalar product to replace logic gates.

•Apr 1, 2008•12 citations

Relation of PPAtMP and scalar product protocol and their applications

Youwen Zhu, Liusheng Huang, Wei Yang

Scalar product protocol and privacy preserving add to multiply protocol (PPAtMP) are two significant basic secure multiparty computation protocols. In this paper, we claim that the two protocols are equivalent to each other and we can achieve one based on the other with the same communication and computation complexity. Then, we propose Secure Two-party Mean Protocol, Secure Shared x ln x Protocol and Secure Shared Generic Polynomial Protocol based on scalar product protocol and PPAtMP. Additionally, we analyze the correctness, security, communication overheads and computation complexity of each protocol proposed in this paper.

IEEE Symposium on Computers and Communications (ISCC)•Jun 1, 2010•8 citations

Scalar-product based secure two-party computation

Chih-Hao Shen, Justin Z. Zhan, Tsan‐sheng Hsu +2 more

Secure multiparty computation is a very important research topic in cryptography. The sub-problem of secure multiparty computation that has received special attention by researchers because of its close relation to many cryptographic tasks is secure two-party computation. This area of research is concerned with the question: ldquoCan two party computation be achieved more efficiently and under weaker security assumptions than general multiparty computation?rdquo Yaopsilas protocol provided security against passive adversaries, while Lindell and Pinkas proposed secure two party protocols that are secure against active adversaries. In this paper, we would like to propose a set of information theoretically secure protocols based on scalar product protocol. The detailed complexity analysis is also provided.

IEEE International Conference on Granular Computing (GrC)•Aug 1, 2008•10 citations

New Protocols for Secure Equality Test and Comparison

Geoffroy Couteau

Protocols for securely comparing private values are among the most fundamental building blocks of multiparty computation. introduced by Yao under the name millionaire’s problem, they have found numerous applications in a variety of privacy-preserving protocols; however, due to their inherent non-arithmetic structure, existing construction often remain an important bottleneck in large-scale secure protocols.

•Jan 1, 2016•2 citations

Research on Secure Scalar Product Protocol and Its' Application

Fen Xu, Shuai Zeng, Shoushan Luo +3 more

Secure scalar product protocol is an important fundamental protocol in secure multi-party computation. Serving as a basic building block for many other secure protocols, it is widely used in data mining, statistical analysis and scientific computation. Based on additive homomorphism public key cryptosystem, we develop a new secure scalar product protocol under semi-honest model with low communication complexity which is easy to implement and understanding. Furthermore, we firstly apply it to position relationship decision for privacy preserving space vectors.

International Conference on Computational Intelligence and Software Engineering (CiSE)•Sep 1, 2010•8 citations

Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions

Samuel Bouaziz--Ermann, Alex B. Grilo, Damien Vergnaud +1 more

There has been a recent interest in proposing quantum protocols whose security relies on weaker computational assumptions than their classical counterparts. Importantly to our work, it has been recently shown that public-key encryption (PKE) from one-way functions (OWF) is possible if we consider quantum public keys. Notice that we do not expect classical PKE from OWF given the impossibility results of Impagliazzo and Rudich (STOC'89). However, the distribution of quantum public keys is a challenging task. Therefore, the main question that motivates our work is if quantum PKE from OWF is possible if we have classical public keys. Such protocols are impossible if ciphertexts are also classical, given the impossibility result of Austrin et al.(CRYPTO'22) of quantum enhanced key-agreement (KA) with classical communication. In this paper, we focus on black-box separation for PKE with classical public key and quantum ciphertext from OWF under the polynomial compatibility conjecture, first introduced in Austrin et al.. More precisely, we show the separation when the decryption algorithm of the PKE does not query the OWF. We prove our result by extending the techniques of Austrin et al. and we show an attack for KA in an extended classical communication model where the last message in the protocol can be a quantum state.

IACR Communications in Cryptology•Apr 9, 2024•2 citations
Privacy-preserving scalar product (PPSP) protocols are an important building block for secure computation tasks in various applications. Lu et al. (TPDS'13) introduced a PPSP protocol that does not rely on cryptographic assumptions and that is used in a wide range of publications to date. In this comment paper, we show that Lu et al.'s protocol is insecure and should not be used. We describe specific attacks against it and, using impossibility results of Impagliazzo and Rudich (STOC'89), show that it is inherently insecure and cannot be fixed without relying on at least some cryptographic assumptions.
Privacy is ultimately important, and there is a fair amount of research about it. However, few empirical studies about the cost of privacy are conducted. In the area of secure multiparty computation, the scalar product has long been reckoned as one of the most promising building blocks in place of the classic logic gates. The reason is not only the scalar product complete, which is as good as logic gates, but also the scalar product is much more efficient than logic gates. As a result, we set to study the computation and communication resources needed for some of the most well-known and frequently referred secure scalar-product protocols, including the composite-residuosity, the invertible-matrix, the polynomial-sharing, and the commodity-based approaches. Besides the implementation remarks of these approaches, we analyze and compare their execution time, computation time, and random number consumption, which are the most concerned resources when talking about secure protocols. Moreover, Fairplay the benchmark approach implementing Yao's famous circuit evaluation protocol, is included in our experiments in order to demonstrate the potential for the scalar product to replace logic gates.
Scalar product protocol and privacy preserving add to multiply protocol (PPAtMP) are two significant basic secure multiparty computation protocols. In this paper, we claim that the two protocols are equivalent to each other and we can achieve one based on the other with the same communication and computation complexity. Then, we propose Secure Two-party Mean Protocol, Secure Shared x ln x Protocol and Secure Shared Generic Polynomial Protocol based on scalar product protocol and PPAtMP. Additionally, we analyze the correctness, security, communication overheads and computation complexity of each protocol proposed in this paper.
Secure multiparty computation is a very important research topic in cryptography. The sub-problem of secure multiparty computation that has received special attention by researchers because of its close relation to many cryptographic tasks is secure two-party computation. This area of research is concerned with the question: ldquoCan two party computation be achieved more efficiently and under weaker security assumptions than general multiparty computation?rdquo Yaopsilas protocol provided security against passive adversaries, while Lindell and Pinkas proposed secure two party protocols that are secure against active adversaries. In this paper, we would like to propose a set of information theoretically secure protocols based on scalar product protocol. The detailed complexity analysis is also provided.
Secure scalar product protocol is an important fundamental protocol in secure multi-party computation. Serving as a basic building block for many other secure protocols, it is widely used in data mining, statistical analysis and scientific computation. Based on additive homomorphism public key cryptosystem, we develop a new secure scalar product protocol under semi-honest model with low communication complexity which is easy to implement and understanding. Furthermore, we firstly apply it to position relationship decision for privacy preserving space vectors.
There has been a recent interest in proposing quantum protocols whose security relies on weaker computational assumptions than their classical counterparts. Importantly to our work, it has been recently shown that public-key encryption (PKE) from one-way functions (OWF) is possible if we consider quantum public keys. Notice that we do not expect classical PKE from OWF given the impossibility results of Impagliazzo and Rudich (STOC'89). However, the distribution of quantum public keys is a challenging task. Therefore, the main question that motivates our work is if quantum PKE from OWF is possible if we have classical public keys. Such protocols are impossible if ciphertexts are also classical, given the impossibility result of Austrin et al.(CRYPTO'22) of quantum enhanced key-agreement (KA) with classical communication. In this paper, we focus on black-box separation for PKE with classical public key and quantum ciphertext from OWF under the polynomial compatibility conjecture, first introduced in Austrin et al.. More precisely, we show the separation when the decryption algorithm of the PKE does not query the OWF. We prove our result by extending the techniques of Austrin et al. and we show an attack for KA in an extended classical communication model where the last message in the protocol can be a quantum state.