This paper first introduces a binary-block embedding (BBE) method to embed secret data in a binary image. Using BBE, we propose an algorithm for reversible data hiding in encrypted images (BBE-RDHEI). It uses BBE to embed binary bits in lower bit-planes of the original image into its higher bit-planes such that the lower bit planes can be reserved for hiding secret data in subsequent processes. BBE-RDHEI employs a bit-level scrambling process after secret data embedding to spread embedded secret data to the entire marked encrypted image so that it can prevent secret data from loss. A security key design mechanism is proposed to enhance the security level of BBE-RDHEI. The processes of BBE-RDHEI are fully reversible. The secret data and original image can be reconstructed independently and separately. Experiments and comparisons show that BBE-RDHEI has an embedding rate nearly twice larger than the state-of-the-art algorithms, generates the marked decrypted images with high quality, and is able to withstand the brute-force, differential, noise and data loss attacks.