3 - Defining security

Question 1

Considerations when designing a secure algorithm (in relation to the hackers)

Answer 1

• What does the attacker know?
• What does it mean to break the system? Finding key, plaintext etc
• How much computing power does the attacker have?

Question 2

Computational Security

(If something is computationally secure then it is…)

Answer 2

Unfeasible to break the cipher
- Depends on the currently available algorithms and computing power

Question 3

Unconditional security

Answer 3

Impossible to break the cipher

Question 4

Possible mathematical definition of computational security

Answer 4

Provable security
- There is no efficient algorithm that can be used to succeed with reasonably high probability.
… Reasonably high might mean 1/(polynomial in n)

Question 5

polynomial time is efficient and exponential is…

Answer 5

Inefficient

Question 6

NP hard problem

Answer 6

No polynomial time algorithm exists and strongly believed to not exist

Question 7

If a known NP-complete problem reduces to breaking the cipher then

Answer 7

It is not expected that an efficient algorithm exists for breaking the cipher

Question 8

Unconditional security: potential precise definition.

(Explained in terms of ciphertext c and plaintext m)

Answer 8

Perfect secrecy/information-theoretic security

• Cipher text only attack
• Attacker has unlimited power

If, for ciphertext c, the probability that plaintext is m = the probability of plaintext being m without knowing c