Sure it's possible, but the ATMEGA168 (on the diecimila at least) is only 16Mhz, so encrypting anything with a "modern" algorithm (AES, RSA) will take at least a few seconds, depending entirely on key length, rounds used, string to encrypt/decrypt, etc.
Plus the diecimila only has 512bytes of memory, which must include storage space for the variables used to decode the encrypted string (or encode the plaintext string), so you're going to be limited to probably 256 bytes at most (two SMS messages worth of text).
Plus you need storage space for the key, an means to input and output the messages and possibly the keys.
I'd recommend a more powerful device for doing cryptography personally, but you could easily use an arduino for Classical cryptography - Vigenere ciphers and Shift/Substitution ciphers for example. These require very little computation as they are character-based - they were essentially around just before computers could decode them.