Transcript RSA: 1977--1997 and beyond

CRYPTOGRAPHY:
STATE OF THE SCIENCE
ASIACRYPT 2003 invited talk
Adi Shamir
Computer Science Dept
The Weizmann Institute
Israel
Cryptography: major trends
Cryptography: major trends

From secret to public
Cryptography is central
Com&info
theory
Math&
stat
Comp
science
crypto
Policy
issues
Computers
and chips
Hi-tech
industry
Cryptography is fun
 Gets
lots of media attention
 Attracts hackers
 Is full of delightful ideas
 Serves as an excellent educational tool
Cryptography: major trends

From secret to public

From national to international
The geography of cryptography

Publicly started in the US
The geography of cryptography

Publicly started in the US

Followed by Europe
The geography of cryptography

Publicly started in the US

Followed by Europe

Is rapidly expanding in Asia
Cryptography: major trends

From secret to public

From national to international

From art to science
Cryptography as a scientific discipline
Is thriving as a scientific area of research:





Taught at most major universities
Attracts many excellent students
Discussed at many conferences
(>25 in the next 6 months!)
Published in hundreds of papers (e.g., EPRINT)
Major conferences have >500 attendees
(Major trade shows have >10,000 attendees)
Received the ultimate seal of approval from the
general CS community (the Turing award…)
Should we rename the field?


Cryptography means “secret writing”
The official naming of the field:
Cryptology = Cryptography + cryptanalysis
Should we rename the field?




Cryptography means “secret writing”
The official naming of the field:
Cryptology = Cryptography + cryptanalysis
These terms have problematic conotations
Many research subfields do not deal with the
encryption or decryption of secret information
Should we rename the field?


Cryptography means “secret writing”
The official naming of the field:
Cryptology = Cryptography + cryptanalysis

These terms have problematic conotations

Many research subfields do not deal with the
encryption or decryption of secret information

I propose to call the broader field
Adversity Theory = cryptology + other areas
Cryptography: major trends

From secret to public

From national to international

From art to science

From math to physics
Related scientific fields:
 OLD
COMBINATIONS:
 Probability and statistics
 Algebra
 Number Theory
Related scientific fields:
 OLD
COMBINATIONS:
 Probability and statistics
 Algebra
 Number Theory
 NEW
COMBINATIONS:
 Signal processing (in steg, fingerprinting)
 Electronics (in side channel attacks)
 Physics (in quantum computers and crypto)
Cryptography: major trends

From secret to public

From national to international

From art to science

From math to physics

From theory to practice
Cryptography unites Theory & practice


Practical theory:
- using abstract math tools in cryptanalysis
- proving the security of real protocols
-developing new cryptographic schemes
Theoretical practice:
- developing new notions of security, complexity,
logics, and randomness
- turning cryptography from art to science
New challenges in cryptography
 Payment
systems
 Cellular telephony
 Wi-Fi networks
 RFID tags
 DRM systems
Cryptography: major trends

From secret to public

From national to international

From art to science

From math to physics

From theory to practice

From political to legal issues
Cryptographic misconceptions



By policy makers: crypto is dangerous, but:
- weak crypto is not a solution
- controls can’t stop the inevitable
By researchers: A provably secure system is secure, but:
- proven false by indirect attacks
- can be based on false assumptions
- requires careful choice of parameters
By implementers: Cryptography solves everything, but:
- only basic ideas are successfully deployed
- only simple attacks are avoided
- bad crypto can provide a false sense of security
The three laws of security:
 Absolutely
secure systems do not exist
 To
halve your vulnerability, you have to
double your expenditure
 Cryptography
penetrated
is typically bypassed, not
Cryptography: A rapidly moving field
Cryptography: A rapidly moving field

75-80: Public key cryptography, basic schemes
Cryptography: A rapidly moving field

75-80: Public key cryptography, basic schemes

80-85: Theoretical foundations, new protocols
Cryptography: A rapidly moving field

75-80: Public key cryptography, basic schemes

80-85: Theoretical foundations, new protocols

85-90: Zero Knowledge, secure computation
Cryptography: A rapidly moving field

75-80: Public key cryptography, basic schemes

80-85: Theoretical foundations, new protocols

85-90: Zero Knowledge, secure computation

90-95: Diff&lin cryptanalysis, quantum comp
Cryptography: A rapidly moving field

75-80: Public key cryptography, basic schemes

80-85: Theoretical foundations, new protocols

85-90: Zero Knowledge, secure computation

90-95: Diff&lin cryptanalysis, quantum comp

95-00: Side channel attacks, elliptic curves
Cryptography: A rapidly moving field

75-80: Public key cryptography, basic schemes

80-85: Theoretical foundations, new protocols

85-90: Zero Knowledge, secure computation

90-95: Diff&lin cryptanalysis, quantum comp

95-00: Side channel attacks, elliptic curves

00-05: ???
The basic schemes: Major trends
The basic schemes: Major trends

Secret key cryptography: DES out, AES in
The basic schemes: Major trends


Secret key cryptography: DES out, AES in
Public key cryptography: RSA steady, EC improving,
faster schemes increasingly risky and less appealing.
Should not be used for long term security.
The basic schemes: Major trends



Secret key cryptography: DES out, AES in
Public key cryptography: RSA steady, EC improving,
faster schemes increasingly risky and less appealing.
Should not be used for long term security.
Quantum schemes: the wild card
Some of my controvertial positions:
Some of my controvertial positions:
When applied in practice:
Some of my controvertial positions:
When applied in practice:

Security should not be overdone
Some of my controvertial positions:
When applied in practice:

Security should not be overdone

Security should not be overexposed
Some of my controvertial positions:
When applied in practice:

Security should not be overdone

Security should not be overexposed

Security should not be underregulated
Some of my controvertial positions:
When applied in practice:

Security should not be overdone

Security should not be overexposed

Security should not be underregulated

Security should be guided by an ethical code
Some of my controvertial positions:
When applied in practice:

Security should not be overdone

Security should not be overexposed

Security should not be underregulated

Security should be guided by an ethical code

Security should be complemented by legal measures
Cryptographic status report
In each of the six major subareas I’ll
summarize:
 The
major achievements so far
 Strong and weak points, major challenges
 A 1-10 grade
Theory of cryptography




Well defined primitives & definitions of security
Well understood relationships between notions
Deep connections with randomness & complexity
Beautiful mathematical results

Highly developed theory
Excellent design tools
Challenge: reduce dependence on assumptions

Final grade: 9


Public key encryption and
signature schemes


RSA, DH, DSA
Based on modular arithmetic, EC, other ideas(?)

Vigorous cryptanalytic research
Excellent theory
Expanding applications
Challenges: Break a major scheme, make a new one

Final grade: 8



Secret key cryptography –
block ciphers


DES, AES, modes of operation
Differential and linear cryptanalysis

Good cryptanalytic tools
Reasonable choice of primitives
Many good schemes
Challenge: Connect strong theory with strong practice

Final grade: 7



Secret key cryptography –
stream ciphers


Linear feedback shift registers
Fast correlation attacks, algebraic attacks

Limited cryptanalytic tools
Narrow choice of primitives
Many insecure schemes
Challenge: Improve weak theory and weak practice

Final grade: 4



Theoretical Cryptographic protocols



Zero knowledge interactive proofs
Secure multiparty computations
Almost anything is doable and provable

Many gems
Theoretical protocols are too slow
Challenge: Make the strong theory practical

Final grade: 8


Practical Cryptographic protocols



Many ad-hoc ideas
Proofs in the random oracle model (ROM)
Rapidly expanding body of results

Lots of buggy protocols
Reasonable design primitives
Improving theory
Challenges: incorporate side channel attacks, ROM

Final grade: 5



Cryptographic predictions:






AES will remain secure for the forseeable future
Some PK schemes and key sizes will be
successfully attacked in the next few years
Crypto will be invisibly everywhere
Vulnerabilities will be visibly everywhere
Crypto research will remain vigorous, but only its
simplest ideas will become practically useful
Non-crypto security will remain a mess
Summary
 It
was a thrilling 25 year journey
 The
best is yet to come
 Thanks
to everyone!