A processor includes a memory encryption engine that provides replay and confidentiality protections to a memory region. The memory encryption engine performs low-overhead parallelized tree walks along a counter tree structure. The memory encryption engine upon receiving an incoming read request for the protected memory region, performs a dependency check operation to identify dependency between the incoming read request and an in-process request and to remove the dependency when the in-process request is a read request that is not currently suspended.