Computer Science

We say that a function T is incremental if it satisfies the following property: Having once applied T to M, the time required to update the result upon modification of M is proportional to the amount of modification done to M. Suppose we have an incremental hash function H.

a. Discuss one application where this incremental hash H would be superior to a standard (non-incremental) hash function.

b. Suppose a message M can only be modified by appending more bits, that is, the modified message M’ is M’ = (M, X), for some X. Given a cryptographic hash function h, define an incremental cryptographic hash function H based on h.

Suppose that Sally (a server) needs access to a symmetric key for user Alice and another symmetric key for Bob and another symmetric key for Charlie. Then Sally could generate symmetric keys K_a±, K_B, and K_c and store these in a database. An alternative is key diversification, where Sally generates and stores a single key K_s– Then Sally generates the key K_A as needed by computing K_A = /i(Alice, K_s), with keys K_B and K_c generated in a similar manner. Give one significant advantage and one significant disadvantage of key diversification as compared to storing keys in a database.

Solution: