This paper presents a new algorithm to reduce significantly the computational cost of one of the best methods with self-recovery capabilities in the fragile watermarking literature. This is achieved by generating two sequences of reference bits associated to the 5 most significant bit-planes (MSBPs) of the image. The reference bits and some authentication bits are then allocated to the 3 least significant bit-planes (LSBPs) of the image. The receiver uses the authentication bits to localise altered pixel-blocks and then executes an iterative restoration mechanism to calculate the original value of the watermarked pixels. Experimental results demonstrate that the embedding method executes significantly faster compared to the state-of-the-art method while achieving a high restoration performance.