Lightweight cipher using only 8-bit operations What is the most efficient (in cycles per byte) cryptographically secure symmetric cipher to implement using only 8-bit operations? Algorithms like TEA are great for embedded devices, but it is optimized for 32-bit operations. I am not looking for the most efficient implementation of an algorithm, but rather an algorithm which was designed with this in mind. The MCU in question is a 3.5 MHz Z80 with 16K RAM.

Looking this up, I found resources showing how to implement AES on 4-bit microcontrollers, and how to implement secure hashes on 8-bit microcontrollers, but neither of those answer my actual question.
I second Richie Frame's observation that AES is an excellent choice. I'd use AES-128 in CTR mode, which has the advantage that decryption is the same as encryption (thus is as fast, contrary to some other modes).

Update: SPECK, considered in this other answer, is good if compactness or speed per encryption for narrow block size are the choice criteria. SPECK-32 can be competitive with AES from the standpoint of cycles/byte on a Z80 (as asked in the question) because the state fits in registers. But I doubt SPECK-128 can be competitive with AES from the standpoint of cycles/byte on a Z80, because the  multi-bit rotation and large number of rounds are going to be show stoppers; and the state has to be in memory.

AES is good on 8-bit CPU (especially if a wide block is desired) because


It has a natural implementation with as the only data transformations: XOR between octets, and lookup of two 256-octet tables. Contrary to many modern ciphers, no word rotation is needed, which is extremely desirable in the context, in which that would be slow even when using assembly.
With an implementation (still natural) separating derivation of round subkeys from encryption itself, speed for large data will be hard to beat, thanks to the carefully crafted structure of AES.
Typical C compilers can generate fair code, and optimization is relatively easy.
With the precaution of locating the two 256-octet tables on page boundaries, a natural implementation on a CPU without data cache (such as the Z80) will typically exhibits no data timing dependency (but I have seen small caches, e.g. 16-octet, in the read path of Flash memory).


As illustration, here is reference code:

// ezAES: Public domain AES-128 encryption.
// C99-conformant. Well suited to 8-bit CPUs.
// CAUTION: vulnerable to fault attacks and side-channels, including
// Differential Power Analysis, and possibly data cache timing attack.

// Data types
typedef unsigned char octet_t;      // 8-bit octet
typedef octet_t ezAESblk_t[16];     // AES data block
typedef octet_t ezAESkey_t[16];     // key for AES-128
typedef octet_t ezAESsks_t[11*16];  // subkeys for AES-128

// Sbox for encryption, FIPS-197 figure 7
static const octet_t ezAESs[256] = {
    0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0,
    0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,
    0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,
    0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,
    0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73,0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,
    0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,
    0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,
    0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16
    };

// Tabulation of (x&lt;&lt;1)^((x&gt;&gt;7)*0x1B)
static const octet_t ezAESt[256] = {
    0x00,0x02,0x04,0x06,0x08,0x0a,0x0c,0x0e,0x10,0x12,0x14,0x16,0x18,0x1a,0x1c,0x1e,0x20,0x22,0x24,0x26,0x28,0x2a,0x2c,0x2e,0x30,0x32,0x34,0x36,0x38,0x3a,0x3c,0x3e,
    0x40,0x42,0x44,0x46,0x48,0x4a,0x4c,0x4e,0x50,0x52,0x54,0x56,0x58,0x5a,0x5c,0x5e,0x60,0x62,0x64,0x66,0x68,0x6a,0x6c,0x6e,0x70,0x72,0x74,0x76,0x78,0x7a,0x7c,0x7e,
    0x80,0x82,0x84,0x86,0x88,0x8a,0x8c,0x8e,0x90,0x92,0x94,0x96,0x98,0x9a,0x9c,0x9e,0xa0,0xa2,0xa4,0xa6,0xa8,0xaa,0xac,0xae,0xb0,0xb2,0xb4,0xb6,0xb8,0xba,0xbc,0xbe,
    0xc0,0xc2,0xc4,0xc6,0xc8,0xca,0xcc,0xce,0xd0,0xd2,0xd4,0xd6,0xd8,0xda,0xdc,0xde,0xe0,0xe2,0xe4,0xe6,0xe8,0xea,0xec,0xee,0xf0,0xf2,0xf4,0xf6,0xf8,0xfa,0xfc,0xfe,
    0x1b,0x19,0x1f,0x1d,0x13,0x11,0x17,0x15,0x0b,0x09,0x0f,0x0d,0x03,0x01,0x07,0x05,0x3b,0x39,0x3f,0x3d,0x33,0x31,0x37,0x35,0x2b,0x29,0x2f,0x2d,0x23,0x21,0x27,0x25,
    0x5b,0x59,0x5f,0x5d,0x53,0x51,0x57,0x55,0x4b,0x49,0x4f,0x4d,0x43,0x41,0x47,0x45,0x7b,0x79,0x7f,0x7d,0x73,0x71,0x77,0x75,0x6b,0x69,0x6f,0x6d,0x63,0x61,0x67,0x65,
    0x9b,0x99,0x9f,0x9d,0x93,0x91,0x97,0x95,0x8b,0x89,0x8f,0x8d,0x83,0x81,0x87,0x85,0xbb,0xb9,0xbf,0xbd,0xb3,0xb1,0xb7,0xb5,0xab,0xa9,0xaf,0xad,0xa3,0xa1,0xa7,0xa5,
    0xdb,0xd9,0xdf,0xdd,0xd3,0xd1,0xd7,0xd5,0xcb,0xc9,0xcf,0xcd,0xc3,0xc1,0xc7,0xc5,0xfb,0xf9,0xff,0xfd,0xf3,0xf1,0xf7,0xf5,0xeb,0xe9,0xef,0xed,0xe3,0xe1,0xe7,0xe5
    };

// Round constants
static const octet_t ezAESr[10] = {
    0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x1b,0x36
    };


// encrypt one block
void ezAESenc
    (
          ezAESblk_t    oC, // ciphertext output
    const ezAESblk_t    iP, // plaintext input
    const ezAESsks_t    iS  // round subkeys
    ) {
    ezAESblk_t vB;          // current state of the block
    ezAESblk_t vT;          // temporary
    octet_t vn;

    // first AddRoundKey
    vn = 16;
    do {
        --vn;
        vB[vn] = iP[vn] ^ iS[vn];
    } while( vn!=0 );

    // round loop, started 10 times; exits with break in the middle of the last round
    for( ; ; ) {

        // ShiftRows and SubBytes, performed 10 times
        vT[ 0] = ezAESs[vB[ 0]]; vT[ 1] = ezAESs[vB[ 5]]; vT[ 2] = ezAESs[vB[10]]; vT[ 3] = ezAESs[vB[15]];
        vT[ 4] = ezAESs[vB[ 4]]; vT[ 5] = ezAESs[vB[ 9]]; vT[ 6] = ezAESs[vB[14]]; vT[ 7] = ezAESs[vB[ 3]];
        vT[ 8] = ezAESs[vB[ 8]]; vT[ 9] = ezAESs[vB[13]]; vT[10] = ezAESs[vB[ 2]]; vT[11] = ezAESs[vB[ 7]];
        vT[12] = ezAESs[vB[12]]; vT[13] = ezAESs[vB[ 1]]; vT[14] = ezAESs[vB[ 6]]; vT[15] = ezAESs[vB[11]];

        if ( (vn += 16)==10*16 )
            break;

        // MixColumns and AddRoundKey, performed 9 times
#define EZAESMA(x) \
    vB[x+2] = vT[x+0]^vT[x+1];                  /* 1 1 0 0 */               \
    vB[x+3] = vT[x+2]^vT[x+3];                  /* 0 0 1 1 */               \
    vB[x+0] = ezAESt[vB[x+2]]^vT[x+1]^vB[x+3]   /* 2 3 1 1 */ ^iS[x+0+vn];  \
    vB[x+2] ^= ezAESt[vB[x+3]]^vT[x+3]          /* 1 1 2 3 */ ^iS[x+2+vn];  \
    vB[x+3] = vT[x+1]^vT[x+2];                  /* 0 1 1 0 */               \
    vT[x+3] ^= vT[x+0];                         /* 1 0 0 1 */               \
    vB[x+1] = ezAESt[vB[x+3]]^vT[x+2]^vT[x+3]   /* 1 2 3 1 */ ^iS[x+1+vn];  \
    vB[x+3] ^= ezAESt[vT[x+3]]^vT[x+0]          /* 3 1 1 2 */ ^iS[x+3+vn];
        EZAESMA( 0)
        EZAESMA( 4)
        EZAESMA( 8)
        EZAESMA(12)
#undef EZAESMA
        // here the content of vT is immaterial
        }

    // last AddRoundKey
    vn = 16;
    do  {
        --vn;
        oC[vn] = vT[vn] ^ iS[10*16+vn];
    } while( vn!=0 );
}

// prepare round subkeys
void ezAESkey (
          ezAESsks_t    oS, // round subkeys output
    const ezAESkey_t    iK  // key input
    ) {
    octet_t vj, vk;

    // first subkey is the key
    vj = 16;
    do {
        --vj;
        oS[vj] = iK[vj];
    }
    while ( vj!=0 );

     // for each 4-octet word of each 10 other subkeys
    vk = 0;
    do  {
        if( (vj&amp;15)==0 ) {
            oS[16+vj] = ezAESs[oS[13+vj]]^oS[  vj]^ezAESr[vk++];
            oS[17+vj] = ezAESs[oS[14+vj]]^oS[1+vj];
            oS[18+vj] = ezAESs[oS[15+vj]]^oS[2+vj];
            oS[19+vj] = ezAESs[oS[12+vj]]^oS[3+vj];
            }
        else {
            oS[16+vj] = oS[12+vj]^oS[  vj];
            oS[17+vj] = oS[13+vj]^oS[1+vj];
            oS[18+vj] = oS[14+vj]^oS[2+vj];
            oS[19+vj] = oS[15+vj]^oS[3+vj];
            }
    } while( ( vj += 4)!=10*16 );
}

// Minimal test and demo. Returns 0 for OK, 1 for error.
int ezAESchk(void) {
    // test values from FIPS-197 appendix C.1
    const ezAESkey_t key = {
        0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f
    };
    const ezAESblk_t plaintext = {
        0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff
    };
    const ezAESblk_t ciphertext = {
        0x69,0xc4,0xe0,0xd8,0x6a,0x7b,0x04,0x30,0xd8,0xcd,0xb7,0x80,0x70,0xb4,0xc5,0x5a
    };
    ezAESsks_t subkeys;
    ezAESblk_t result;
    octet_t j, r;

    // derive the round subkeys
    ezAESkey( subkeys, key );

    // encrypt
    ezAESenc( result, plaintext, subkeys );

    // compare result and known-good ciphertext
    for( j = r = 0; j&lt;16; ++j)
        r |= result[j] ^ ciphertext[j];

    return r!=0;    // 0 for OK, 1 for error
};