Insights on Environmental Security and Ingenuity
O
n
E
n
v
i
r
o
n
m
e
n
t
a
l
S
e
c
u
r
i
t
y
A
t
r
i
b
u
t
e
t
o
R
a
n
C
a
n
e
t
t
i
o
n
h
i
s
6
0
t
h
B
-
d
a
y
Oded Goldreich
Weizmann Institute of Science
What is ingenuity?
Ingenuity is discovering something that, in retrospect, is self-evident.
Q: Why do idiots think the opposite?
That is, why do they confuse the
a posteriori
appeal of the discovery,
which is reflected in its becoming fully-internalized to the level of
becoming invisible (or self-evident) once understood,
with the
a priori
evasiveness of and opposition to the discovery?
A: Because they are idiots!
T
h
e
t
e
r
m
“
e
n
v
i
r
o
n
m
e
n
t
a
l
s
e
c
u
r
i
t
y
”
w
a
s
n
o
t
i
n
v
e
n
t
e
d
f
o
r
t
h
e
c
u
r
r
e
n
t
o
c
c
a
s
i
o
n
FN92 reads: The term used in [51]
is
Universal Composability
, but
we believe that a reasonable
sense of “universal
composability” is only a corollary
of the suggested definition.
FoC, Vol 2, 2004
.
Secure MPC (stand-alone)
For every (feasible) real-
model adversary that
attacks the protocol, there
exists a (feasible) ideal-
model adversary that
attacks the functionality
and obtains (essentially)
the same effect.
Hence, perceived weaknesses
of the protocol are actually due
to the functionality; that is, the
protocol itself has no additional
weaknesses.
Environmental Security
Environmental Security
Pivotal idea: Provide the adversaries with an oracle
that performs an
arbitrary
polynomial-time
computation.
Balances considerations (or a priori critiques):
•
An oracle will allow the adversary to break any complexity-based cryptography.
•
What’s the point of giving oracle access to an efficient computation?
The point is that both adversaries are given the same oracle.
Plugging this in the real-vs-ideal simulation paradigm:
For every real model adversary A there exists an ideal model adversary B
such that,
for every efficient oracle Z
, whatever harm A can do in reality
when given oracle access to Z
, can be done by B in the ideal world
when
given oracle access to Z
.
Environ.-Security implies general concurrent composition
•
Suppose A attacks
t
concurrent executions of the protocol
П
, which
computes the functionality F in an environmentally-secure manner.
•
Decompose into a single-session adversary A’ and a coordinator A’’.
•
Let B’ be an ideal-model adversary that simulates A’ (wrt env.-sec.).
•
Replace the
t
copies of (A’,П) by
t
copies of (B’,F).
•
Hybrids: The
i
th
hybrid uses
i
copies of (A’,
П
) and
t-i
of (B’,F).
Indistinguishability of
i
-1
st
and
i
th
hybrids follows by considering the
environment that emulates
i-1
copies of (A’,
П
) and
t-i
copies of (B’,F),
where the
i
th
copy is the actual execution to be distinguished.
Digest: main message
I can stop here. The most important points were made.
•
Environmental security is ingenious and great.
•
The pivotal idea is to consider oracle access
to an
arbitrary
efficient computation
.
N.B.: A fixed (efficient oracle) machine (i.e.,
)
is given access
to an oracle that is universally quantified (i.e.,
) as efficient.
Lesson: The order
is important
also when both objects come from the same domain.
- “We know this!” [Alternation]
- So why forget it when doing modeling?
An Example: Auxiliary inputs (a precursor)
Def
: A strategy P is
auxiliary-input ZK
if for every efficient adversary A
interactive with P, there exists an efficient simulator S such that,
for every main input x
and
auxiliary input z
, it holds that
{(P,A(z)
)(x)}
x
,z
is computationally indistinguishable from {S(x,z
)}
x
,z
A bad simplification:
every poly-sized adversary {An
} interactive with P,
there exists a poly-sized simulator {Sn
} such that, for every input x, it holds that
{(P,An
)(x)}
x
is computationally indistinguishable from {Sn
(x)}
x
A
n
S
n
x
A
S
x,z
An Example: Leonid Levin’s proposal
Conjecture
(badly stated). Let f:
0,1
n
0,1
n
be a OWF,
and h be taken from a family of hashing functions
(from 2n bits to n bits, and description length m).
Then, F:
0,1
n+m
0,1
n+m
such that F(x,<h>)=(<h>,h(f(x),x))
is a OWF.
[The point being that F is “practically injective”.]
Counterexample:
Suppose h(yz)=h’(z) if f(z)=y and h’’(yz) otherwise.
Then h is a “good” hashing but F(x,<h>)=(<h’,h’’>,h’(x)) is easy to invert.
Conjecture
(better stated (+ replacing hashing by randomness extractor)).
F
f
:
0,1
n+m
0,1
n+m
such that F
f
(x,s)=(s,E
s
(f(x),x)) is a OWF.
f,h
F
F,E
f
T
h
e
t
e
r
m
“
e
n
v
i
r
o
n
m
e
n
t
a
l
s
e
c
u
r
i
t
y
”
w
a
s
n
o
t
i
n
v
e
n
t
e
d
f
o
r
t
h
e
c
u
r
r
e
n
t
o
c
c
a
s
i
o
n
FN92 reads: The term used in [51]
is
Universal Composability
, but
we believe that a reasonable
sense of “universal
composability” is only a corollary
of the suggested definition.
FoC, Vol 2, 2004
.
In this tribute to Ran Canetti, insights are shared on environmental security, ingenuity, and secure multi-party computation (MPC). The discussion delves into the essence of ingenuity, addressing why some may misunderstand discoveries. Furthermore, the concept of environmental security and its pivotal ideas are explored, highlighting the importance of adversaries in cryptographic protocols.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
On Environmental Security A tribute to Ran Ran Canetti Canetti on his 60thB-day Oded Goldreich Weizmann Institute of Science
What is ingenuity? Ingenuity is discovering something that, in retrospect, is self-evident. Q: Why do idiots think the opposite? That is, why do they confuse the a posteriori appeal of the discovery, which is reflected in its becoming fully-internalized to the level of becoming invisible (or self-evident) once understood, with the a priori evasiveness of and opposition to the discovery? A: Because they are idiots!
The term environmental security was not not invented for the current occasion FoC, Vol 2, 2004 . FN92 reads: The term used in [51] is Universal Composability, but we believe that a reasonable sense of universal composability is only a corollary of the suggested definition.
Secure MPC (stand-alone) For every (feasible) real- model adversary that attacks the protocol, there exists a (feasible) ideal- model adversary that attacks the functionality and obtains (essentially) the same effect. Hence, perceived weaknesses of the protocol are actually due to the functionality; that is, the protocol itself has no additional weaknesses.
Environmental Security Pivotal idea: Provide the adversaries with an oracle that performs an arbitrary polynomial-time computation. Balances considerations (or a priori critiques): An oracle will allow the adversary to break any complexity-based cryptography. What s the point of giving oracle access to an efficient computation? The point is that both adversaries are given the same oracle. Plugging this in the real-vs-ideal simulation paradigm: For every real model adversary A there exists an ideal model adversary B such that, for every efficient oracle Z, whatever harm A can do in reality when given oracle access to Z, can be done by B in the ideal world when given oracle access to Z.
Environ.-Security implies general concurrent composition Suppose A attacks t concurrent executions of the protocol , which computes the functionality F in an environmentally-secure manner. Decompose into a single-session adversary A and a coordinator A . Let B be an ideal-model adversary that simulates A (wrt env.-sec.). Replace the t copies of (A , ) by t copies of (B ,F). Hybrids: The ithhybrid uses i copies of (A , ) and t-i of (B ,F). Indistinguishability of i-1stand ithhybrids follows by considering the environment that emulates i-1 copies of (A , ) and t-i copies of (B ,F), where the ithcopy is the actual execution to be distinguished.
Digest: main message I can stop here. The most important points were made. Environmental security is ingenious and great. The pivotal idea is to consider oracle access to an arbitrary efficient computation. N.B.: A fixed (efficient oracle) machine (i.e., ) is given access to an oracle that is universally quantified (i.e., ) as efficient. Lesson: The order is important also when both objects come from the same domain. - We know this! [Alternation] - So why forget it when doing modeling?
An Example: Auxiliary inputs (a precursor) Def: A strategy P is auxiliary-input ZK if for every efficient adversary A interactive with P, there exists an efficient simulator S such that, for every main input x and auxiliary input z, it holds that {(P,A(z))(x)}x,zis computationally indistinguishable from {S(x,z)}x,z A S x,z A bad simplification: every poly-sized adversary {An} interactive with P, there exists a poly-sized simulator {Sn} such that, for every input x, it holds that {(P,An)(x)}xis computationally indistinguishable from {Sn(x)}x An Sn x
An Example: Leonid Levins proposal Conjecture (badly stated). Let f: 0,1 n 0,1 nbe a OWF, and h be taken from a family of hashing functions (from 2n bits to n bits, and description length m). Then, F: 0,1 n+m 0,1 n+msuch that F(x,<h>)=(<h>,h(f(x),x)) is a OWF. [The point being that F is practically injective .] Counterexample: Suppose h(yz)=h (z) if f(z)=y and h (yz) otherwise. Then h is a good hashing but F(x,<h>)=(<h ,h >,h (x)) is easy to invert. f,h F Conjecture (better stated (+ replacing hashing by randomness extractor)). Ff: 0,1 n+m 0,1 n+msuch that Ff(x,s)=(s,Es(f(x),x)) is a OWF. F,E f
The term environmental security was not not invented for the current occasion FoC, Vol 2, 2004 . FN92 reads: The term used in [51] is Universal Composability, but we believe that a reasonable sense of universal composability is only a corollary of the suggested definition.
