what is security?

a system is secure iff it meets its security goals.

a security goal is either a safety or liveness goal
(as opposed to, eg, an efficiency goal).

a safety goal is of the form,
something bad cannot happen.
eg
1) only user x can access the account of x
2) no 3 users can combine their information
to learn anything nontrivial about x
3) if the protocol tells us to believe that x
was sent from y, then x really was sent from y

a liveness goal is of the form,
something good can happen.
eg
1) user x can access the account of x
2) all 3 users can find out f(x)
3) if x sends y, then the protocol will tell
us to believe that x was sent from y

there are no concrete definitions of safety and liveness
since we cannot a priori make exact the notions
of "something", "good", "bad", "can", "cannot".
these are up to us for each specific application.
"something" depends on our desires.
"good" vs "bad" depends on our perspective.
"can" vs "cannot" depends on our threat model.

an analogous notion is that an algorithm cannot be
declared "correct" until it is specified just what
the algorithm is supposed to do.

successive refinements

some goals are unrealistic.  for example
1) x and only x can access the account of x.

probably the only way to achive this is to kill
every person on the planet but x.
a much more realistic goal would be
1) x can access the account of x with probability 1 and
with minimal effort;
for anyone else, to access the account of x with probability
greater than epsilon requires an amount of effort exceeding
y using any attack in the set z.

effort could be quantified as some function of
money, time, space, willingness to commit sinful deeds.
eg
we might say that an attacker could gain unauthorized access
to the account of x with probability > 1/2^n if he
is willing to buy a $1M computer, let it run some specific
attack for 30 years, sleep with the sys admin, shoot the
security guard, leap over the infrared beams, etc.

typically one does not design a single system but rather
a parameterized family of systems.
for that matter, the goals themselves should be parameterized.
eg
1) for the system parameterized by n,
an attacker needs >2^n effort to succeed
with probability >1/2^n; by contrast,
x needs effort n to gain access.

if the system is designed well,
the effort lower bound for the attacker grows much faster than n
while the effort upper bound for x grows much more slowly.

our goals are still slightly unrealistic.
the problem is that as stated, we cannot prove that
any reasonable system is secure unless our threat
model is very weak, such as including only a finite
number of attacks.  we need to weaken our demands to the point
where we can prove something useful.

to do this, we will typically use reductions from other
security systems that are believed to be strong.
we will state our goals as,
if an attacker can defeat our system with probability >epsilon
and with effort <y, then he can also defeat
system z with probability >f(epsilon) and with effort <g(y).

if f(epsilon) is not too much smaller than epsilon
and if g(y) is not too much larger than y, then
we should feel some confidence that our system is
not much weaker than z.

next, we need to know from which systems we should reduce.
typically these will be systems that have stood up against
the scrutiny and assault of many intelligent people for a long time.
the reasoning here is,
if they couldn't break the system, probably no one else
will either.
this is not proof of unbreakability, but it is (strictly!)
more comforting than nothing.