According to one embodiment of the invention, a plurality of IPsec packets belonging to a single IPsec tunnel are received. Different ones of the plurality of IPseck packets are distributed to different ones of a plurality of processing cores of a network element. At least some of those IPsec packets are processed in parallel and without taking a lock on a Security Association (SA) data structure storing a SA associated with the plurality of IPsec packets. The SA is atomically accessed and atomically updated.