We provide a new protocol for Validated Asynchronous Byzantine Agreement in the authenticated setting. Validated (multi-valued) Asynchronous Byzantine Agreement is a key building block in constructing Atomic Broadcast and fault-tolerant state machine replication in the asynchronous setting. Our protocol has optimal resilience of f<n/3 Byzantine failures and asymptotically optimal expected O(1) running time to reach agreement. Honest parties in our protocol send only an expected O(n ) messages where each message contains a value and a constant number of signatures. Hence our total expected communication is O(n ) words. The best previous result of Cachin et al. from 2001 solves Validated Byzantine Agreement with optimal resilience and O(1) expected time but with O(n^3) expected word communication . Our work addresses an open question of Cachin et al. from 2001 and improves the expected word communication from O(n^3) to asymptotically optimal O(n^2).