Cryptography Reference
In-Depth Information
Now, we give an upper-bounding SMT-PD protocol Π 1 as follows. The following
protocol is an adaptation of (3,2)-round SMT-PD protocol proposed in [18].
and R i ∈{ 0 , 1 }
m
1.
( S→R ):For i =1 ,...,n ,
S
randomly selects r i ∈{ 0 , 1 }
and sends the pair ( r i ,R i ) to
R
along wire i .
correctly receives a pair ( r i ,R i ) along wire i
2.
( S←R ):For i =1 ,...,n ,if
R
(i.e., r i ∈{ 0 , 1 }
and R i ∈{ 0 , 1 }
m ),
and computes T i = r i
R
selects h i H
h i ( R i ); otherwise, wire i is assumed corrupted .
R
then constructs an indicator bit
string B = b 1 b 2 ···
b n where b i =1if the wire i is corrupted and b i =0otherwise.
Finally,
sends ( B, ( H 1 ,...,H n )) over the public channel, where H i =( h i ,T i )
if b i =0;and H i
R
is empty, otherwise.
3.
( S→R ):
S
ignores the wires with b i =1.For i =1 ,...,n ,if b i =0,
S
computes
h i ( R i ) and checks T i = T i ;if T i = T i ,wire i is assumed consistent ;
otherwise, wire i is corrupted.
T i = r i
S
constructs an indicator bit string V = v 1 v 2 ···
v n ,
where v i =1if wire i is considered consistent; otherwise v i =0.
S
sends the pair
( V, C = M S ⊕{ v i =1
R i } ) along every consistent wire j .
R
receives ( V j ,C j )
( V ,C ) V
along wire j and set
V = { ( V j ,C j ) }
.
R
chooses some pair
as
follows.
- All the elements in
can be enumerated as ( U 1 ,D 1 ) ,..., ( U d ,D d ) according
to some order, where d = | V |
V
.
- Let d i be the number of indices j such that ( V j ,C j )=( U i ,D i ).
- If d i <n
t then reset d i =0.
- Choose ( V ,C )=( U k ,D k ) with probability d k / ( i d i ).
Finally,
recovers M R = C ⊕{ v i =1
R
R i }
and outputs it, where V = v 1 ···
v n .
Theorem 4. The protocol Π 1 is a (3 , 0 , 1) -round (0 ) -SMT-PD protocol, where
t
n +
n
t
· t · 2 .
δ ≤
n
Proof. Let
B = {
i : wire i is corrupted
}
and
G = {
i : wire i is consistent
}
.
First, we upper-bound the reliability parameter. If
can detect all corrupted wires with
( r i ,R i ) =( r i ,R i ) and ( V, C )=( V ,C ), then the protocol is perfectly reliable.
The probability of the event when
S
( V, C )=( V ,C )
t ) /n .We
consider that the reliability is always violated when ( V, C ) =( V ,C ). Hence in the
following we assume that ( V, C )=( V ,C ).
In the second round the wires with b i =1are detected as corrupted and are ignored
in the third round. Hence in the following we only consider wires with b i =0.Forwire
i , the wire is called bad if ( r i ,R i ) =( r i ,R i ) but r i
is at least
( n
h i ( R i )= r i
h ( R i ).Badwires
. Using Proposition 1 and noting that r i ,R i ,r i ,R i are fixed
before the second round and then h i is selected with uniform distribution, we have
are always included in
G
h i ( R i )= r i
h ( R i ) ( r i ,R i ) =( r i ,R i )]
Pr[wire i is bad]=Pr[ r i
h i ( R i )= r i
h ( R i ) | ( r i ,R i ) =( r i ,R i )] 2 ,
Pr[ r i
 
Search WWH ::




Custom Search