Security and Communication Networks

Security and efficiency analysis of the Hamming distance computation protocol based on oblivious transfer

Mehmet Sabır Kiraz, Ziya Alper Genç, Süleyman Kardaş

Published Aug 21, 2015• 8 citations

Abstract

Abstract Bringer et al. proposed two cryptographic protocols for the computation of Hamming distance. Their first scheme uses oblivious transfer and provides security in the semi‐honest model. The other scheme uses committed oblivious transfer and is claimed to provide full security in the malicious case. The proposed protocols have direct implications to biometric authentication schemes between a prover and a verifier where the verifier has biometric data of the users in plain form. In this paper, we show that their protocol is not actually fully secure against malicious adversaries. More precisely, our attack breaks the soundness property of their protocol where a malicious user can compute a Hamming distance, which is different from the actual value. For biometric authentication systems, this attack allows a malicious adversary to pass the authentication without knowledge of the honest user's input with at most O(n) complexity instead of O(2n), where n is the input length. We propose an enhanced version of their protocol where this attack is eliminated. The security of our modified protocol is proven using the simulation‐based paradigm. Furthermore, as for efficiency concerns, the modified protocol utilizes verifiable oblivious transfer, which does not require the commitments to outputs, which improves its efficiency significantly. Copyright © 2015 John Wiley & Sons, Ltd.

DOI: 10.1002/sec.1329

Related papers

Security and Efficiency Analysis of The Hamming Distance Computation Protocol Based On Oblivious Transfer.

Mehmet Sabır Kiraz, Ziya Alper Genç, Süleyman Kardaş

Bringer et al. proposed two cryptographic protocols for the computation of Hamming distance. Their first scheme uses oblivious transfer and provides security in the semi-honest model. The other scheme uses committed oblivious transfer and is claimed to provide full security in the malicious case. The proposed protocols have direct implications to biometric authentication schemes between a prover and a verifier where the verifier has biometric data of the users in plain form. In this paper, we show that their protocol is not actually fully secure against malicious adversaries. More precisely, our attack breaks the soundness property of their protocol where a malicious user can compute a Hamming distance, which is different from the actual value. For biometric authentication systems, this attack allows a malicious adversary to pass the authentication without knowledge of the honest user's input with at most O(n) complexity instead of O(2n), where n is the input length. We propose an enhanced version of their protocol where this attack is eliminated. The security of our modified protocol is proven using the simulation-based paradigm. Furthermore, as for efficiency concerns, the modified protocol utilizes verifiable oblivious transfer, which does not require the commitments to outputs, which improves its efficiency significantly.

Jan 1, 20140 citations

Commitment and Oblivious Transfer in the Bounded Storage Model With Errors

Rafael Dowsley, Felipe Gomes Lacerda, Anderson C. A. Nascimento

The bounded storage model restricts the memory of an adversary in a cryptographic protocol, rather than restricting its computational power, making information theoretically secure protocols feasible. We present the first protocols for commitment and oblivious transfer in the bounded storage model with errors, i.e., the model where the public random sources available to the two parties are not exactly the same, but instead are only required to have a small Hamming distance between themselves. Commitment and oblivious transfer protocols were known previously only for the error-free variant of the bounded storage model, which is harder to realize.

arXiv:1510.06623IEEE Transactions on Information TheoryJan 22, 20182 citations

Secure computation protocol of Chebyshev distance under the malicious model

Xin Liu, Weitong Chen, Lu Peng +5 more

Secure multi-party computation of Chebyshev distance represents a crucial method for confidential distance measurement, holding significant theoretical and practical implications. Especially within electronic archival management systems, secure computation of Chebyshev distance is employed for similarity measurement, classification, and clustering of sensitive archival information, thereby enhancing the security of sensitive archival queries and sharing. This paper proposes a secure protocol for computing Chebyshev distance under a semi-honest model, leveraging the additive homomorphic properties of the NTRU cryptosystem and a vector encoding method. This protocol transforms the confidential computation of Chebyshev distance into the inner product of confidential computation vectors, as demonstrated through the model paradigm validating its security under the semi-honest model. Addressing potential malicious participant scenarios, a secure protocol for computing Chebyshev distance under a malicious model is introduced, utilizing cryptographic tools such as digital commitments and mutual decryption methods. The security of this protocol under the malicious model is affirmed using the real/ideal model paradigm. Theoretical analysis and experimental simulations demonstrate the efficiency and practical applicability of the proposed schemes.

Scientific ReportsJul 24, 20249 citations

An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries.

Yehuda Lindell, Benny Pinkas B

Abstract. We show an efficient secure two-party protocol, based on Yao’s construction, which provides security against malicious adversaries. Yao’s original protocol is only secure in the presence of semi-honest adversaries. Security against malicious adversaries can be obtained by applying the compiler of Goldreich, Micali and Wigderson (the “GMW compiler”). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs. Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running O(1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao’s protocol does not yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security. Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party com-putation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a sta-tistical security parameter. These two reductions are comparable to Kilian’s reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit [18]. 1

Jan 1, 20080 citations

More Efficient Oblivious Transfer and Extensions for Faster Secure Computation.

Gilad Asharov, Yehuda Lindell, Thomas H. Schneider +1 more

Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure com-putation becomes more practical, the need for practical large scale oblivious transfer protocols is becoming more evident. Oblivious transfer extensions are protocols that enable a relatively small number of “base-OTs ” to be utilized to compute a very large number of OTs at low cost. In the semi-honest setting, Ishai et al. (CRYPTO 2003) presented an OT extension protocol for which the cost of each OT (beyond the base-OTs) is just a few hash function operations. In the malicious setting, Nielsen et al. (CRYPTO 2012) presented an efficient OT extension protocol for the setting of active adversaries, that is secure in the random oracle model. In this work, we present an OT extension protocol for the setting of malicious adversaries that is more efficient and uses less communication than previous works. In addition, our protocol can be proven secure in both the random oracle model, and in the standard model with a type of correlation robustness. Given the importance of OT in many secure computation protocols, increasing the efficiency of OT extensions is another important step forward to making secure

Jan 1, 20130 citations

Oblivious transfer in the bounded storage model with errors

Rafael Dowsley, Felipe Gomes Lacerda, Anderson C. A. Nascimento

In the bounded storage model the memory of the adversarial parties is restricted, instead of their computational power. This different restriction allows the construction of protocols with information-theoretical (instead of only computational) security. We present the first protocol for oblivious transfer in the bounded storage model with errors, i.e., where the public random sources available to the two parties are not exactly the same, but instead are only required to have a small Hamming distance between themselves, and the memory of the (adversarial) receiver is limited. Oblivious transfer protocols were known previously only for the error-free variant of the bounded storage model, which is harder to realize.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 20148 citations