Provided are apparatuses and methods of generating and verifying signature information for data authentication. A method of verifying signature information may involves receiving signature information with respect to a predetermined number of data segments from a transmitter, constructing a hash tree based on the signature information, and verifying a validity of the signature information, by verifying trapdoor hash values using a root hash value of the constructed hash tree.