« previous | Tuesday, April 2, 2013 | next »
Provably Good Hash Function
Why do we care about hash functions?
- Vital for signatures (sign a message digest instead of the whole message)
- message padding
- Error-checking
Chaum, Van Hiejst, Pfitzman, 1992:
Following construction is strongly-collision-resistant, assuming discrete log is hard:
- Find large prime
with
also prime.
- in practice, pick
and then check if
is prime
- easy via Prime Number Theorem and assumption of randomness of primes: for 100-digit number, there are approx.
primes in
.
- Pick 2 (distinct) generators
and
for 
is defined by
, where
are the base-
numbers of
- Converting from
digits to
digits.
- good
- "provably good"
- bad
- Too inefficient for practical applications
- Only halves the number of digits
- ugly
- In practice, a simpler (Ad-Hoc) construction is used: SHA-1
Proof
Proposition.
is (2) pre-image resistant and (3) strongly-collision-resistant.
Proof. Let's prove (3) first.
Assumptions:
- discrete logarithm is not computable in polynomial time.
- we can find
with
in polynomial time.
If we find such
and
, then we have
and
Now since
is a generator for
,
for some
we don't know.
In fact,
is the discrete log of
to the base
, mod
.
Therefore
This congruence has a solution for
iff
.
So what can that GCD be?
by construction, so
Also,
, so the GCD is either 1 or 2,
, or
.
and
are too big, so only 1 and 2 remain.
Solution can now be found in poly time: Just try solutions!
We've just found the discrete log!
Now if
then
and
. CONTRADICTION!
Therefore, if
is not strongly-collision-resistant, then the discrete logarithm must be easy!
(2) is easy to prove, but we'll get to that later.
Q.E.D.
Pseudo-Random Generators
"Something even more fundamental"
Polynomial Congruential
One of Simplest PRGs: Linear congruential:
This "smells" random, but is terribly insecure: If you can find 3 consecutive
s, then you can easily find
and
:
Linear system is solvable given
In fact, any polynomial congruential generators are insecure due to predictability.
Blum-Blum-Shub Random Bit Generator
More Sophisticated:
- Pick large primes
and
with
, let
, and pick a random [1]
Let seed be 
- </math>x_{n+1} = x_n^2 \pmod{n}</math> Return
be the last bit of
.
Theorem
Assume computing Jacobi symbol
is not doable in polynomial time. Then the BBS Bit Generator is indistinguishable from a truly random bit stream, by any polynomial time algorithm.
Note: In modern analysis, how much time do you wish to invest to prove randomness?
Random numbers have certain properties according to probability
Elliptic Curves
Elliptic Curve Cryptography (ECC) is already being used in smart cards in Europe as an extra layer of security.
Using RSA, high security implies huge keys and slow computation
ECC allows "high security" using 300-bit keys (maybe equiv 4000-bit RSA key)
Idea: work with a more general "group" than
or
. Instead, ECC uses points on a curve over a finite field.
- ↑ It's odd that we need to pick a random number for a random number generator...