This paper presents two new proof-of-retrievability schemes that are both efficient and provably secure against arbitrary adversaries in the strongest model, as defined by Juels and Kaliski. The first scheme, based on BLS signatures, features a short client query and server response, allowing public verifiability. The second scheme, based on pseudorandom functions (PRFs), allows private verification but has an even shorter server response. Both schemes use homomorphic properties to aggregate a proof into a small authenticator value. The paper also provides a modular proof framework for the security of these schemes, demonstrating their correctness, extractability, and retrievability through cryptographic, combinatorial, and coding-theoretical techniques. The schemes are the first to achieve full security proofs against arbitrary adversaries in the Juels–Kaliski model.This paper presents two new proof-of-retrievability schemes that are both efficient and provably secure against arbitrary adversaries in the strongest model, as defined by Juels and Kaliski. The first scheme, based on BLS signatures, features a short client query and server response, allowing public verifiability. The second scheme, based on pseudorandom functions (PRFs), allows private verification but has an even shorter server response. Both schemes use homomorphic properties to aggregate a proof into a small authenticator value. The paper also provides a modular proof framework for the security of these schemes, demonstrating their correctness, extractability, and retrievability through cryptographic, combinatorial, and coding-theoretical techniques. The schemes are the first to achieve full security proofs against arbitrary adversaries in the Juels–Kaliski model.