Is the notion of authenticated-encryption something new?
Yes and no. The general idea to combine privacy+authenticity is folklore, and lots of attempts can be found in the security literature and in systems. Nobody was solving this problem correctly, but nobody in the cryptographic community was paying any attention. Bellare and I finally presented definitions for the goal in an ASIACRYPT 2000 paper, while the same definitions independently appeared in a EUROCRYPT 2000 paper by Katz and Yung. The ASIACRYPT 2000 paper by . Bellare and Namprempre looks at the notion in greater depth. It’s pretty common that a folklore cryptographic goal may fail to get a proper cryptographic treatment for a long time.
