This paper presents two new efficient and secure proof-of-retrievability (POR) schemes with short proofs and strong security guarantees. The first scheme uses BLS signatures and is secure in the random oracle model, allowing public verifiability. The second scheme uses pseudorandom functions (PRFs) and is secure in the standard model, allowing private verification. Both schemes rely on homomorphic properties to aggregate proofs into small authenticator values. The first scheme features a proof-of-retrievability protocol where the client's query and server's response are both extremely short (20 bytes and 40 bytes, respectively, at the 80-bit security level). The second scheme has an even shorter server response (20 bytes at the 80-bit security level) but requires a longer client query. Both schemes are proven secure in the strongest model, that of Juels and Kaliski. The paper also discusses the security model for POR schemes, emphasizing the need for soundness and extractability. It defines a formal security model where a scheme is secure if any adversary that convinces the verification algorithm that it is storing a file actually is storing that file. The paper provides a modular proof framework for the security of the schemes, using cryptographic, combinatorial, and coding-theoretical techniques. The paper introduces two constructions for POR schemes: one for private verification and one for public verification. The private verification scheme uses a PRF and a MAC, while the public verification scheme uses BLS signatures and a bilinear map. Both schemes are proven secure under appropriate cryptographic assumptions. The paper also discusses the trade-off between storage and communication overhead in POR schemes, and provides a method for compressing the request to reduce the size of the client's query. It also discusses the use of erasure codes and the importance of having a secure and efficient erasure code for practical applications. Finally, the paper compares its POR model to other models, such as Proof of Data Possession, and argues that the POR model is more suitable for practical data storage problems because it provides a successful audit guarantee that all the data can be extracted. The paper concludes that provable full retrievability is crucial for cryptographic storage systems.This paper presents two new efficient and secure proof-of-retrievability (POR) schemes with short proofs and strong security guarantees. The first scheme uses BLS signatures and is secure in the random oracle model, allowing public verifiability. The second scheme uses pseudorandom functions (PRFs) and is secure in the standard model, allowing private verification. Both schemes rely on homomorphic properties to aggregate proofs into small authenticator values. The first scheme features a proof-of-retrievability protocol where the client's query and server's response are both extremely short (20 bytes and 40 bytes, respectively, at the 80-bit security level). The second scheme has an even shorter server response (20 bytes at the 80-bit security level) but requires a longer client query. Both schemes are proven secure in the strongest model, that of Juels and Kaliski. The paper also discusses the security model for POR schemes, emphasizing the need for soundness and extractability. It defines a formal security model where a scheme is secure if any adversary that convinces the verification algorithm that it is storing a file actually is storing that file. The paper provides a modular proof framework for the security of the schemes, using cryptographic, combinatorial, and coding-theoretical techniques. The paper introduces two constructions for POR schemes: one for private verification and one for public verification. The private verification scheme uses a PRF and a MAC, while the public verification scheme uses BLS signatures and a bilinear map. Both schemes are proven secure under appropriate cryptographic assumptions. The paper also discusses the trade-off between storage and communication overhead in POR schemes, and provides a method for compressing the request to reduce the size of the client's query. It also discusses the use of erasure codes and the importance of having a secure and efficient erasure code for practical applications. Finally, the paper compares its POR model to other models, such as Proof of Data Possession, and argues that the POR model is more suitable for practical data storage problems because it provides a successful audit guarantee that all the data can be extracted. The paper concludes that provable full retrievability is crucial for cryptographic storage systems.