Can one implement AES on 4-bit microcontroller? It is possible to implement AES on 4-bit microcontroller? As far as I know, AES on 8-bit microcontroller are common especially for light weight application such as the RFID.

I have yet to come across AES been employed on 4-bit microcontroller, therefore I have been wondering whether such implementation is feasible.
Yes, AES could be implemented on a 4-bit micro-controller such as this EM6626, and that would not be rocket science or stupidly slow. This application note illustrates that all kind of 8-bit operations are simple, and table lookups are possible.

In fact, tables are not even indispensable if performance is non-critical; see this minimalist AES source code in C which has a compilation option to avoid any table.

The most serious issue is the amount of RAM required: current 128-bit subkey and 128-bit data will eat half of the total 512-bit RAM of the above device.

Also worrying is the security: I know no 4-bit micro-controller with any kind of security evaluation. Thus I would trust such an implementation only if it is operated in a secure environment, and with a key that vanishes from the device after use. That's an appropriate security model for an enciphering machine, but not a copy-protection dongle.