Sharing a secret key between two physically separated nodes, Alice and Bob, is possible through the use of quantum key distribution (QKD) techniques. In the presence of an eavesdropper, Alices key may not be identical with Bobs key, due to the characteristics of a quantum channel. To obtain identical keys at Alice and Bob, we propose a block-based key verification protocol that relies on Newtons polynomial interpolation. As the nodes solely share random numbers and indices of the removed blocks, no information is revealed about the secret message, at a cost of higher computational complexity. The error propagation through the key verification process is prevented by the characteristics of the proposed approach.