Cryptography Reference
In-Depth Information
Let
S
1
,...,S
m
be
m
servers.
Input
The sender
S
, contributes with
n
secrets
ω
1
,...,ω
n
∈
IK
The receiver
R
, chooses an index
σ ∈{
1
,...,n}
, and contributes with
n
private values
δ
σ
1
,...,δ
σn
∈{
0
,
1
}
R
receives
ω
σ
, while
S
receives nothing.
Output
Step
1
- Setup phase
1.
generates a vector
of
quasi-random polynomials
S
Ω
=(
F
1
,...,F
n
)
n
F
i
∈
IK
k−
1
[
X
]
, where the constant term of
F
i
is
ω
i
(
1
≤ i ≤ n
).
2.
S
transmits to the server
S
(
∈I
m
)thevector
Ω
=(
F
1
(
)
,...,F
n
(
))
.
Step
2
- Elaboration of the receiver's request
1.
R
chooses
σ ∈{
1
,...,n}
and
I
k
⊂I
m
.
2.
R
generates a vector
of
quasi-random polynomials
Φ
=(
Z
1
,...,Z
n
)
n
Z
i
∈
IK
k−
1
[
X
]
, where the constant term of
Z
i
is
δ
σi
.
3.
R
transmits to server
S
(
∈I
k
)thevector
Φ
=(
Z
1
(
)
,...,Z
n
(
))
.
Step
3
- Redistribution of the receiver's input
1. The contacted servers
S
(
∈I
k
) select a subset
I
2
k−
1
⊂I
m
of
2
k −
1
servers
such that
I
k
⊂I
2
k−
1
.
2. Each server
S
(
∈I
k
) generates two polynomial vectors:
(a)
Θ
1
=(
G
,
1
,...,G
,n
)
such that
is a quasi-random polynomial of
G
,i
IK
k−
1
[
X
]
with a null constant term,
Θ
2
=
u∈I
k
u
=
−u
×
Φ
,
and builds a vector
Ψ
=
Θ
1
+
Θ
2
of
n
polynomials.
3. The value
Ψ
j
is sent to the server
S
j
(
j ∈I
2
k−
1
).
4. Each server
S
j
, once it holds
k
values
(b)
X−u
(
∈I
k
), calculates
Φ
j
=
∈I
k
Ψ
j
,
as its shares from the receiver's input related to (
k
,
2
k −
1
)-threshold schemes.
Ψ
j
Step
4
- Computation of the requested secret
1. Each server
S
(
∈I
2
k−
1
) calculates the scalar product
λ
=
Ω
Φ
, which is its
share of the requested secret,
Ω
0
Φ
0
, related to a polynomial of degree
2
k −
2
.
So, the collaborating set of at least
2
k −
1
servers involved in the computation
of
Ω
0
Φ
0
, redistributes its shares using a (
k
,
k
)-threshold scheme.
2.
S
(
∈I
2
k−
1
) generates two polynomials:
(a)
H
1
, a quasi-random polynomial of
IK
k−
1
[
X
]
with a null constant term,
(b)
H
2
=
L
×λ
,where
L
is the truncated Lagrange basis polynomial
L
mod
X
k
,where
L
=
j∈I
2
k−
1
j
=
i
X−j
−j
,
and builds a polynomial
H
=
H
1
+
H
2
.Thevalue
H
j
is sent to the server
S
j
(
j ∈I
k
).
3. A server
S
j
, once it holds
2
k −
1
values
H
j
(
∈I
2
k−
1
), calculates the new share
μ
j
=
∈I
2
k−
1
H
j
.
Step
5
- Oblivious transfer of the requested secret
1.
S
j
(
j ∈I
k
) sends
μ
j
to
R
.
2.
R
interpolates a polynomial
μ
of degree at most
k−
1
, and calculates
ω
σ
=
μ
(0)
.
Fig. 1.
Asecure(
k
,
m
)-DOT-
1
protocol
Search WWH ::
Custom Search