Revision #1 Authors: Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry

Accepted on: 13th December 2006 00:00

Downloads: 1752

Keywords:

We investigate two-party cryptographic protocols, called cheat

sensitive protocols,

which guarantee that if one party cheats then the other has good

probability of detecting the

mistrustful party. We give quantum protocols for two basic cryptographic

primitives: bit

commitment and one-out-of-two oblivious transfer ($\binom{2}{1}$-OT),

and prove that they

are cheat sensitive. For the quantum bit commitment scheme we show that

if a cheating gives

$\varepsilon$ advantage i.e. information about the committed bit then

the committer can detect

the cheating with a probability $\Omega(\varepsilon^2)$; If the

committer cheats trying to change

his mind during the revealing phase then the probability of detecting

the cheating is greater

than some fixed constant $\lambda>0$. This improves the probabilities of

cheating detections shown

by Hardy and Kent [Phys.Rev.Lett.'04], as well as the scheme by

Aharonov et~al.~[Proc. STOC'00]

who presented a protocol that is sensitive against cheating by one

party, but not both parties

at the same time. Our cheat sensitive quantum $\binom{2}{1}$-OT protocol

guarantees that if

cheating gives any mistrustful party $\varepsilon$ advantage then the

other party can detect

the cheating with a probability $\Omega(\varepsilon^2)$.

The heart of the both cheat-sensitive protocols is a weakened version of

quantum

$\binom{2}{1}$-OT which we call {\em susceptible} quantum

$\binom{2}{1}$-OT. In this version,

similarly as in the standard definition, Alice has initially secret bits

$a_0,a_1$ and Bob

has a secret selection bit $i$ and if both parties are honest they solve

the $\binom{2}{1}$-OT

problem fulfilling the standard security requirements. However, if Alice

is dishonest and she

gains some information about the secret selection bit then the

probability that Bob computes

the correct value is proportionally small. Moreover, if Bob is dishonest

and he learns something

about both bits, then he is not able to gain full information about one

of them.

TR06-085 Authors: Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry

Publication: 19th July 2006 09:25

Downloads: 1185

Keywords:

It is well known that unconditionally secure bit commitment is impossible

even in the quantum world. In this paper a weak variant of quantum bit

commitment, introduced independently by Aharonov et al. and Hardy and Kent

is investigated. In this variant, the parties require some nonzero probability

of detecting a cheating, i.e. if Bob, who commits a bit $b$ to Alice,

changes his mind during the revealing phase then Alice detects the cheating

with a positive probability (we call this property binding); and if Alice

gains information about the committed bit before the revealing phase then

Bob discovers this with positive probability (sealing). In our paper we give

quantum bit commitment scheme that is simultaneously binding and sealing and

we show that if a cheating gives $\varepsilon$ advantage to a malicious Alice

then Bob can detect the cheating with a probability $\Omega(\varepsilon^2)$.

If Bob cheats then Alice's probability of detecting the cheating is greater

than some fixed constant $\lambda>0$. This improves the probabilities of

cheating detections shown by Hardy and Kent and the scheme by Aharonov et al.

who presented a protocol that is either binding or sealing, but not

simultaneously both.

To construct a cheat sensitive quantum bit commitment scheme we use a protocol

for a weak quantum one-out-of-two oblivious transfer ($\binom{2}{1}$-OT). In this

version, similarly as in the standard definition, Alice has initially secret bits

$a_0,a_1$ and Bob has a secret selection bit $i$ and if both parties are honest

they solve the $\binom{2}{1}$-OT problem fulfilling the standard security

requirements. However, if Alice is dishonest and she gains some information

about the secret selection bit then the probability that Bob computes the correct

value is proportionally small. Moreover, if Bob is dishonest and he learns something

about both bits, then he is not able to gain full information about one of them.