This paper develops a concatenated coding scheme with polynomial computational complexity for covert communication over Binary Symmetric Channels (BSCs) and binary-input Discrete Memoryless Channels (DMCs). Our setting is as follows — a transmitter Alice wishes to potentially reliably transmit a message to a receiver Bob, while ensuring that the transmission taking place is covert with respect to a warden Willie (who hears Alice’s transmission over another independent channel). Prior works showed that Alice can reliably and covertly transmit $\mathcal {O}(\sqrt {{n}})$ message bits over n channel uses, but one drawback is that the computational complexity of the codes designed scales as $2^{\Theta (\sqrt {{n}})}$ . In this work we provide a capacity-achiveing coding scheme with provable guarantees on both reliability and covertness, and its computational complexity grows polynomially in the blocklength n .