The introduction of digital medical images requires a legally binding digital signature that guarantees authenticity and integrity of the image. In real-time teleradiology services, the system is expected to respond very quickly however to verify the signature a considerable amount of time is spent to compute the hash value of the image since the image size might be huge (tens of megabytes). Motivating by this fact, in this paper we propose EVEREST, an efficient methodology for verification. The key observation we have made is that in the traditional verification the processor of the verifying machine is idle (I/O blocked) while the image is downloaded. In EVEREST, to improve the real-time efficiency the receiver can perform most of the hash computation while he is receiving the image itself. One other important advantage of our scheme is the communication efficiency since getting the entire image file is no longer necessary to detect the tampering.