Cryptography Reference
In-Depth Information
arithmetic circuit over a finite field having more than
m
elements, and
a secret element
s
of the field is shared by selecting uniformly a polyno-
mial of degree
d
=
)having
a free-term equal to
s
, and handing each party the value of this poly-
nomial evaluated at a different (fixed) point (e.g., party
i
is given the
value at point
i
). Addition is emulated by (local) point-wise addition
of the (secret sharing) polynomials representing the two inputs (using
the fact that for polynomials
p
and
q
,andanyfieldelement
e
(and
in particular
e
=0
,
1
, ..., m
), it holds that
p
(
e
)+
q
(
e
)=(
p
+
q
)(
e
)).
The emulation of multiplication is more involved and requires interac-
tion (because the product of polynomials yields a polynomial of higher
degree, and thus the polynomial representing the output cannot be the
product of the polynomials representing the two inputs). Indeed, the
aim of the interaction is to turn the shares of the product polynomial
into shares of a degree
d
polynomial that has the same free-term as the
product polynomial (which is of degree 2
d
). This can be done using the
fact that the coecients of a polynomial are a linear combination of
its values at suciently many arguments (and the other way around),
and the fact that one can privately-compute any linear combination (of
secret values). For details see (25; 61).
(
m
−
1)
/
3
(resp., degree
d
=
(
m
−
1)
/
2
A passively-secure 1-out-of-
k
Oblivious Transfer.
Usingacol-
lection of enhanced trapdoor permutations,
D
α
}
α∈I
,
we outline a passively-secure implementation of the functionality of
Eq. (7.4). The implementation originates in (54) (and a full description
is provided in (67, Sec. 7.3.2)).
{
f
α
:
D
α
→
k
,the
receiver
has
Inputs
:
The
sender
has input (
σ
1
,σ
2
, ..., σ
k
)
∈{
0
,
1
}
input
i ∈{
1
,
2
, ..., k}
.
Step S1
:
The sender selects at random a permutation
f
α
along with a
corresponding trapdoor, denoted
t
, and sends the permutation
f
α
(i.e., its index
α
) to the receiver.
Step R1
:
The
receiver
uniformly
and
independently
selects
x
1
, ..., x
k
∈
D
α
,sets
y
i
=
f
α
(
x
i
)and
y
j
=
x
j
for every
j
=
i
, and sends (
y
1
,y
2
, ..., y
k
) to the sender.
