What does ''latency'' really mean when a block cipher is partially unrolled? Typically，I think latency should mean the time from the first plaintext input to the first ciphertext output, when the block cipher is not totally unrolled (such as AES unrolled with 2 rounds).

If I use a pipeline to increase the throughput, the latency should relate to the amount of pipelined data. E.g. with AES unrolled with 2 rounds, and 100 group data to create the pipeline, then the latency must be larger than 500 cycles (except the time to calculate).

But in many papers, latency in this situation does not include this number, just the clock cycles of 10 rounds' critical path.

I do not understand why.

Also, what is the requirement of latency which limits the number of blocks which are pipelined?
When talking about a circuit (FPGA, ASIC...) implementing some encryption algorithm, the relevant measures are:


Bandwidth: how many input bytes can be processed per second.
Latency: how much time occurs between the moment an input byte (or block) is injected, and the corresponding output byte (or block) is obtained.
Circuit area, energy consumption...


AES (with 128-bit keys) is defined as using 10 successive rounds; the important point being that each round works over the output of the previous round. Thus, the ten rounds MUST be computed sequentially. However you implement it, the data block will have to go ten times through a circuit computing one round. Ten times through the same circuit, or five times through two copies of the circuit, or through ten distinct copies of the circuit: this does not matter here. The latency for an AES invocation is related to the number of rounds.

If you do a loop, with a single circuit for one round and some gates to reuse that circuit ten times, then you will have minimal total circuit area, but also lowest bandwidth, because you will have to wait for completion of the ten rounds before starting a new AES invocation. For instance, if processing one round takes one clock cycle, then you will have a latency of 10 cycles (it takes 10 cycles to get an encrypted block from the plaintext block), and a bandwidth of one block per 10 cycles. If you "unroll" the implementation with 10 copies of the "round" circuit, then latency will still be 10 cycles: when you inject one block, the corresponding output block will be available 10 cycles later. However, you can then inject one block per cycle: ten times the circuit area, but also ten times the bandwidth.

To sum up, loop unrolling and pipelining in a circuit does not change the latency, but the bandwidth.



All of the above is about doing "AES invocations", i.e. applying the AES algorithm on 16-byte blocks which are independent of each other. When encrypting a message (as a potentially very long sequence of bytes), you are using the AES through a block cipher mode of operation which can add its own constraints. For instance, if using CBC, then, by construction, you need the result of the encryption of one block before beginning the encryption of the next block (because you first XOR each block with the previous encrypted block). Therefore, even if you have a fully unrolled AES circuit with a latency of 10 cycles and a bandwidth of one block per cycle, you will not be able to encrypt more than one block every 10 cycles. Conversely, CTR mode allows for the full bandwidth of one block per cycle, because all the elementary encryptions in CTR can be done in parallel.

Here, I am not talking about the latency of the block cipher itself (AES), but the latency induced by its mode of operation.

If we go one step further and think about overall message processing: consider SSL/TLS. In SSL, data is encrypted as records where each record contains up to 16 kB of data, and has its own MAC. Upon receiving a record, an SSL implementation must first verify the MAC over the complete (decrypted) record before beginning to use the data (until the MAC is verified, the SSL implementation cannot assume that the data has not been altered). This means a much higher latency: between the time the first encrypted record byte is received and the time the corresponding plaintext byte is really available, the decryption and MAC processing of the whole record must occur.

This example shows that the notion of "latency" is flexible and occurs at many levels, so it is important to be clear about what we are talking. In the case of a block cipher like AES, the "latency" is about the minimum processing time for one block independently of other blocks. This translates to the latency for a "message" only insofar as the encryption mode and other protocol characteristics like a MAC do not add their own constraints.