Question

Which of the following statements are true and which are false?

(a) Assume that we are implementing AES or a similar system on an RFID tag. When calculating the ASIC cost, one of the things we need to take into account is the key.

(b) Assume that we are implementing AES or a similar system on an RFID tag. When calculating the ASIC cost, one of the things we need to take into account is the internal state. (c) Assume that we are implementing AES or a similar system on an RFID tag. When calculating the ASIC cost, one of the things we need to take into account is the cryptographic signature.

(d) When studying how hard it is to break a cryptosystem, average-case complexity is more important than worst-case complexity.

(e) The function n −5 is negligible.

(f) The function 5−n is negligible.

(g) The function log n is negligible.

(h) The function n − log n is negligible.

Answer 1

(a) Assume that we are implementing AES or a similar system on an RFID tag. When calculating the ASIC cost, one of the things we need to take into account is the key.

This statement is True, ASIC cost depends on number of keys to search.

(b) Assume that we are implementing AES or a similar system on an RFID tag. When calculating the ASIC cost, one of the things we need to take into account is the internal state.

This statement is False. ASIC cost is not dependent on internal state.

(c) Assume that we are implementing AES or a similar system on an RFID tag. When calculating the ASIC cost, one of the things we need to take into account is the cryptographic signature.

I am not sure here.

(d) When studying how hard it is to break a cryptosystem, average-case complexity is more important than worst-case complexity.

This statement is false. Worst-case complexity is more important than average case complexity.

A   function is called negligible function if  for any positive integer c, there is an integer Nc assciated with integer c such that for any x > Nc

(e) The function n −5 is negligible.

False, because even for c = 1, we cannot find an integer Nc such that x - 5 < 1/x for x > Nc

(f) The function 5−n is negligible.

True, this function is negligible function because for any integer c, we can find Nc = 4 such that 5-x < for x > 4

(g) The function log n is negligible.

False, this function is not negligible function since it is monotonically increasing function.

(h) The function n − log n is negligible.

False this function is not negligible since its monotonically increasing function.