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

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 Jan 1, 2014• 0 citations
Publisher

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.

DOI
10.1002/sec.1329/abstract

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ş

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.

Security and Communication Networks•Aug 21, 2015•8 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.06623•IEEE Transactions on Information Theory•Jan 22, 2018•2 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 Reports•Jul 24, 2024•9 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, 2013•0 citations

Black-Box Constructions of Protocols for Secure Computation.

Iftach Haitner, Yuval Ishai, Eyal Kushilevitz Z +2 more

In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor permutation) in a black-box way only. Until now, all known general constructions for this setting were inherently non-blackbox since they required the parties to prove zero-knowledge statements that are related to the computation of the underlying primitive. Our main technical result is a fully black-box reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semi-honest parties. As a corollary, we obtain the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which only make a black-box use of semi-honest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption. In order to construct this reduction we introduce a new notion of security called privacy in the presence of defensible adversaries. This notion states that if an adversary can produce (retroactively, after the protocol terminates) an input and random tape that make

•Jan 1, 2010•2 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, 2014•8 citations
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.
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.
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.
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.
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
In this paper, we study the question of whether or not it is possible to construct protocols for general secure computation in the setting of malicious adversaries and no honest majority that use the underlying primitive (e.g., enhanced trapdoor permutation) in a black-box way only. Until now, all known general constructions for this setting were inherently non-blackbox since they required the parties to prove zero-knowledge statements that are related to the computation of the underlying primitive. Our main technical result is a fully black-box reduction from oblivious transfer with security against malicious parties to oblivious transfer with security against semi-honest parties. As a corollary, we obtain the first constructions of general multiparty protocols (with security against malicious adversaries and without an honest majority) which only make a black-box use of semi-honest oblivious transfer, or alternatively a black-box use of lower-level primitives such as enhanced trapdoor permutations or homomorphic encryption. In order to construct this reduction we introduce a new notion of security called privacy in the presence of defensible adversaries. This notion states that if an adversary can produce (retroactively, after the protocol terminates) an input and random tape that make
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.