Cryptography Reference
In-Depth Information
we often make the implicit assumption that telepathy does not exist or does not work
(otherwise, encrypting data does not make a lot of sense). Similarly, we assume that
randomness exists (otherwise, secret keys cannot exist in principle). Other assump-
tions are less obvious. As mentioned earlier, we often work with intractability as-
sumptions when we prove the security of a cryptographic system. These intractabil-
ity assumptions are often related to a specific adversary and assumptions about his
or her capabilities and computational power. For example, if we assume that an
adversary is an illiterate (i.e., he or she cannot read and write), then it is fairly trivial
to come up with a secure encryption system.
2
More realistic assumptions are related
to the computing power, available time, and available memory. Last but not least,
we often make assumptions about the correct behavior of system entities and human
users. These assumptions are particularly difficult to make, and many cryptographic
security protocols can be broken if an adversary does not play by the rules. These
considerations must also be taken into account when one tries to work with formal
methods.
According to [1], all assumptions that are made implicitly and explicitly must
be taken into account and considered with care when one considers cryptography
and security proofs. It is particularly important to note
•
That every security proof for a cryptographic system is only relative to certain
assumptions;
•
That assumptions should be made explicit;
•
That assumptions should always be as weak as possible.
A major future goal for cryptographic research is to reduce the necessary
assumptions to a set of realistic assumptions, while preserving the practicality of
the systems. This is particularly true for computational intractability assumptions.
After a talk I gave on Internet security,
3
I was asked whether the fact that
almost nothing in cryptography can be proven in a mathematically strong and
absolute sense wasn't potentially dangerous and worrisome. I had to answer in the
affirmative and confess that the current types of reasoning about the security of
cryptographic systems are not satisfactory but simply the best we currently have
at hand. We would like to see absolute proofs for the security of cryptographic
systems (instead of proofs that are relative to specific computational intractability
assumptions). Similarly, we would like to have functions that can be shown to be
2
This is why the Caesar cipher mentioned in Sections 1.3 and 10.1.1 was secure. It was used in a
time when most people were illiterate.
3
The talk was entitled “Sicherheit im Internet” and was held on November 21, 1996, at the
Swiss Association for the Security of Information Services (CLUSIS) meeting on “Sicherheit und
Gefahren des Internet” in Z urich (Switzerland).
