Encrypt External Hard Drive for Mac and Linux
The easiest way to handle this situation is to buy a drive that uses OS-agnostic hardware encryption, then format it with a format which is readable by both OS X and Linux. Since both Time Machine and Ubuntu are referenced, you may want to install hfsprogs in order to enable Ubuntu to read OS X's HFS+, then format the drive itself as HFS+:

http://packages.ubuntu.com/trusty/otherosfs/hfsprogs