The complexity of developing algorithms for AEAD arises from the fact that when data is sent over the internet, it is broken down into packets that consist of a body and a header. The body is the information itself and has to be both encrypted and authenticated, while the header indicates the destination to which it has to be sent and only requires authentication.