Reversible data hiding over encrypted images (RDH-EI) technology is a viable solution for privacy-preserving cloud storage, as it enables the reversible embedding of additional data into images while maintaining image confidentiality. Since the data hiders, e.g., cloud servers, are willing to embed as much data as possible for storage, management, or other processing purposes, a large embedding capacity is desirable in an RDH-EI scheme. In this article, we introduce a novel bi-directional block encoding (BDBE) method, which, for the first time, encodes the distances of values in a binary sequence from both ends. This approach allows for encoding images with smaller sizes compared to traditional and state-of-the-art encoding methods. Leveraging the BDBE technique, we propose a high-capacity RDH-EI scheme. In this scheme, the content owner initially predicts the image pixels and then employs BDBE to encode the prediction errors, creating space for data embedding. The resulting encoded data are subsequently encrypted using a secure stream cipher, such as the Advanced Encryption Standard, before being transmitted to a data hider. The data hider can embed confidential information within the encrypted image for the purposes of storage, management, or other processing. Upon receiving the data, an authorized receiver can accurately recover the original image and the embedded data without any loss. Experimental results demonstrate that our RDH-EI scheme achieves a significantly larger embedding capacity compared to several state-of-the-art schemes.