IEEE Access

Secure “Ratio” Computation and Efficient Protocol for General Secure Two-Party Comparison

Linming Gong, Shundong Li, Chunying Wu, Daoshun Wang

Published Jan 1, 2018• 5 citations

Abstract

Many privacy protections in distributed setting are based on secure comparison, according to which two distrusted users try to jointly determine whether a > b, a = b, or a1)/(kb + k1)), which implies the potential relationship (a > b, a = b, and a1, and b belong to the party who doesn't have the secret of the system. Based on this system, two distrusted users in distributed setting can learn whether a > b, a = b, or a <; b in one execution, without disclosing a and b to each other. Then, we develop two efficient protocols for secure comparison on integers and secure comparison on fractions, respectively. Our schemes, based on homomorphic encryption, are cryptographically secure. We prove that these protocols are secure using simulation paradigm. Our approaches can be used in many secure multi-party computation protocols that involve fractions, rational numbers, and integers. They can also be more convenient to solve some secure multiparty computational geometry problems that often involve ratio evaluation.

DOI: 10.1109/access.2018.2827025

Related papers

Secure multiparty computation of a comparison problem

Xin Liu, Shundong Li, Jian Liu +2 more

Private comparison is fundamental to secure multiparty computation. In this study, we propose novel protocols to privately determine [Formula: see text], or [Formula: see text] in one execution. First, a 0-1-vector encoding method is introduced to encode a number into a vector, and the Goldwasser-Micali encryption scheme is used to compare integers privately. Then, we propose a protocol by using a geometric method to compare rational numbers privately, and the protocol is information-theoretical secure. Using the simulation paradigm, we prove the privacy-preserving property of our protocols in the semi-honest model. The complexity analysis shows that our protocols are more efficient than previous solutions.

SpringerPlusSep 5, 20168 citations

Performance Comparison of Secure Comparison Protocols

Florian Kerschbaum, Debmalya Biswas, Sebastiaan J. A. de Hoogh

Secure multiparty computation (SMC) has gained tremendous importance with the growth of the Internet and e-commerce, where mutually untrusted parties need to jointly compute a function of their private inputs. However, SMC protocols usually have very high computational complexities, rendering them practically unusable. In this paper, we tackle the problem of comparing two input values in a secure distributed fashion. We propose efficient secure comparison protocols for both the homomorphic encryption and secret sharing schemes. We also give experimental results to show their practical relevance.

International Workshop on Database and Expert Systems Applications (DEXA)Aug 1, 200954 citations

A High Throughput BFV-Encryption-Based Secure Comparison Protocol

Tzu-Hsiang Kuo, Ja‐Ling Wu

Secure comparison is a fundamental problem in multiparty computation. There are two different parties, each holding an l-bit integer, denoted by a and b, respectively. The goal of secure comparison is to compute the order relationship between a and b, say (a>b)∈{0,1}, without revealing their inputs to any others. Since previous solutions based on homomorphic encryption need at least Ω(l) encryptions for each l-bit comparison, the total encryption time leads to a computational bottleneck for these protocols. This work presents a fast, semi-honest, secure comparison protocol based on the BFV encryption scheme. With its vector-like plaintext space, the number of required encryptions can be significantly reduced; actually, only six encryptions are needed for each comparison in our protocol. In other words, the proposed protocol can achieve the time complexity O˜(λ+l) for a given security parameter λ. As a result, 4096-bit integers can be securely compared within 12.08 ms, which is 280 times faster than the state-of-the-art homomorphic encryption-based secure comparison protocol. Furthermore, we can compare k pairs of l⋅k−1-bit integers with almost the same execution time as comparing l-bit integers and achieve higher throughput regardless of the compared integer size.

MathematicsMar 2, 20234 citations

On Protocol Security in the Cryptographic Model

Jesper Buus Nielsen, Jesper Buus Nielsen

It seems to be a generally acknowledged fact that you should never trust a computer and that you should trust the person operating the computer even less. This in particular becomes a problem when the party that you do not trust is one which is separated from you and is one on which you depend, e.g. because that party is the holder of some data or some capability that you need in order to operate correctly. How do you perform a given task involving interaction with other parties while allowing these parties a minimal influence on you and, if privacy is an issue, allowing them to learn as little about you as possible. This is the general problem of secure multiparty computation. The usual way of formalizing the problem is to say that a number of parties who do not trust each other wish to compute some function of their local inputs, while keeping their inputs as secret as possible and guaranteeing the correctness of the output. Both goals should be obtained even if some parties stop participating or some malevolent coalition of the parties start deviating arbitrarily from the agreed protocol. The task is further complicated by the fact that besides their mutual distrust, nor do the parties trust the channels by which they communicate. A general solution to the secure multiparty computation problem is a compiler which given any feasible function describes an efficient protocol which allows the parties to compute the function securely on their local inputs over an open network. Over the past twenty years the secure multiparty computation problem has been the subject of a large body of research, both research into the models of multiparty computation and research aimed at realizing general secure multiparty computation. The main approach to realizing secure multiparty computation has been based on verifiable secret sharing as computation, where each party holds a secret share of each input and during the execution computes secret shares of all intermediate values. This approach allows the parties to keep all inputs and intermediate values secret and to pool the shares of the output values to learn exactly these values. More recently an approach based on joint homomorphic encryption was introduced, allowing for an efficient realization of general multiparty computation secure against an eavesdropper. A joint encryption scheme is an encryption scheme where all parties can encrypt, but where it takes the participation of all parties to open an encryption. The computation then starts by all parties broadcasting encryptions of their inputs and progresses through computing encryptions of the intermediary values using the homomorphic properties of the encryption scheme. The encryptions of the outputs can then be jointly decrypted. In this dissertation we extend this approach by using threshold homomorphic encryption to provide full-fledged security against an active attacker which might control some of the parties and which might take over parties during the course of the protocol execution. As opposed to a joint encryption scheme a threshold encryption scheme only requires that a given number of the parties are operating correctly for decryption to be possible. In this dissertation we show that threshold homomorphic encryption allows to solve the secure general multiparty computation problem more efficiently than previous approaches to the problem. Starting from an open point-to-point network there is a long way to general secure multiparty computation. The dissertation contains contributions at several points along the way. In particular we investigate how to realize secure channels. We also show how threshold signature schemes can be used to efficiently realize a broadcast channel and how threshold cryptography can be used to provide the parties of the network with a source of shared randomness. All three tools are well-known to be extremely powerful resources in a network, and our principle contribution is to provide efficient realizations. The dissertation also contains contributions to the definitional part of the field of multiparty computation. Most significantly we augment the recent model of universally composable security with a formal notion of what it means for a protocol to only realize a given problem under a given restricted input-output behavior of the environment. This e.g. allows us to give the first specification of a universally composable zero-knowledge proof of membership which does not at the same time require the proof system to be a proof of knowledge.

Jan 1, 20039 citations

Efficient Protocols for the General Millionaires' Problem

Shundong Li, Yimin Guo, Sufang Zhou +2 more

Secure multiparty computation (SMC) is a research focusing in the international cryptographic community. The protocols used to address the millionaires' problem are the basic building blocks of most SMC protocols and their efficiency dominates that of many other SMC protocols. To the best of our knowledge, almost all protocols used to address the millionaires' problem are based on integers, which means that their applications are limited. In this study, we propose precise and efficient protocols for rational numbers based on additively homomorphic encryptions. One of our protocols is inspired by computational geometry and it reduces the millionaires problem to computing the area of a triangle formed by three private points. This approach can determine whether the relationship between two private inputs is greater than, equal to or less than, and it has a much lower computational complexity compared with existing methods. We proved that these protocols are secure using simulation paradigm. Our approaches can be used in many SMC protocols that involve rational numbers and integers, and they can also be used directly to solve some secure multiparty computational geometry problem in rational number field.

Chinese Journal of ElectronicsJul 1, 201710 citations

Protocols for secure multi-party private function evaluation

Feras Aljumah, Andrei Soeanu, Wen Ming Liu +1 more

Secure multi-party computation (SMC) allows multiple parties to jointly and securely compute a function while preserving the privacy of the involved parties. In this regard, homomorphic cryptosystems allow users to perform addition or multiplication operations on encrypted values without having to decrypt the input values. In this paper, we propose both a cryptographic and a non-cryptographic privacy-preserving protocols that allow one party to collaboratively compute a private polynomial function with at least two other parties using semantically secure cryptosystems. In this respect, the function to be evaluated is kept private to the party in question. In addition, we assume that there is no fully trusted party and that all parties are semi-honest. Moreover, we assume that there is no collusion between the different parties. We present the two protocols in question and report on the underlying performance through the presentation of our implementation results. The proposed protocols are relevant in many applications such as evidence sharing in multi-party forensic investigations, situation awareness through the secure sharing in distributed monitoring of plan execution, etc.

International Conference on Anti-Cyber Crimes (ICACC)Nov 1, 20151 citation