Crypto: why is(n't) the following indistinguishable from random?
I'm reading these notes, trying to understand why Regev encryption is circularly secure. They say (at the very end) that the following pair of values is indistinguishable from uniform:
(
a
′
−⌊
q
2
⌋
u
i
,<
a
′
,s>+e). (1)
where
q
q
is an integer,
a
′
a
and
s
s
are uniformly selected vectors, and
u
i
u
is the
i
th
i
standard basis vector.
e
e
is a small error term selected from a special distribution so that the pair
(
a
′
,<
a
′
,s>+e)
(
looks like it was selected from the uniform distribution - this is the learning with errors (LWE) assumption.
I can see why (1) would look uniform, however the original value they wanted to show was uniformly random was:
(a,<a,s>+e+
s
i
⌊
q
2
⌋). (2)
Where
s
i
s
is an element of
s
s
, the secret key, and
a
a
is another uniformly selected vector. In the notes they chose a' so that (2) = (1) and the claim follows. My question is, why was this necessary at all? Isn't
<a,s>+e
<
independent from
s
i
s
because of a? (Unless
s=0
s
). Can't one just argue directly that both sides of (2) look uniformly random and independent?
Many thanks for any help.
(
a
′
−⌊
q
2
⌋
u
i
,<
a
′
,s>+e). (1)
where
q
q
is an integer,
a
′
a
and
s
s
are uniformly selected vectors, and
u
i
u
is the
i
th
i
standard basis vector.
e
e
is a small error term selected from a special distribution so that the pair
(
a
′
,<
a
′
,s>+e)
(
looks like it was selected from the uniform distribution - this is the learning with errors (LWE) assumption.
I can see why (1) would look uniform, however the original value they wanted to show was uniformly random was:
(a,<a,s>+e+
s
i
⌊
q
2
⌋). (2)
Where
s
i
s
is an element of
s
s
, the secret key, and
a
a
is another uniformly selected vector. In the notes they chose a' so that (2) = (1) and the claim follows. My question is, why was this necessary at all? Isn't
<a,s>+e
<
independent from
s
i
s
because of a? (Unless
s=0
s
). Can't one just argue directly that both sides of (2) look uniformly random and independent?
Many thanks for any help.
Комментарии
Отправить комментарий