The Blum–Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum–Goldwasser is a probabilistic, semantically secure cryptosystem with a constant-size ciphertext expansion. The encryption algorithm implements an XOR-based stream cipher using the Blum-Blum-Shub (BBS) pseudo-random number generator to generate the keystream. Decryption is accomplished by manipulating the final state of the BBS generator using the private key, in order to find the initial seed and reconstruct the keystream. The BG cryptosystem is semantically secure based on the assumed intractability of integer factorization; specifically, factoring a composite value where are large primes. BG has multiple advantages over earlier probabilistic encryption schemes such as the Goldwasser–Micali cryptosystem. First, its semantic security reduces solely to integer factorization, without requiring any additional assumptions (e.g., hardness of the quadratic residuosity problem or the RSA problem). Secondly, BG is efficient in terms of storage, inducing a constant-size ciphertext expansion regardless of message length. BG is also relatively efficient in terms of computation, and fares well even in comparison with cryptosystems such as RSA (depending on message length and exponent choices). However, BG is highly vulnerable to adaptive chosen ciphertext attacks (see below). Because encryption is performed using a probabilistic algorithm, a given plaintext may produce very different ciphertexts each time it is encrypted. This has significant advantages, as it prevents an adversary from recognizing intercepted messages by comparing them to a dictionary of known ciphertexts. Operation The Blum–Goldwasser cryptosystem consists of three algorithms: a probabilistic key generation algorithm which produces a public and a private key, a probabilistic encryption algorithm, and a deterministic decryption algorithm. Key generation The public and private keys are generated as follows: Choose two large distinct prime numbers and such that and . Compute . Then is the public key and the pair is the private key. Encryption A message is encrypted with the public key as follows: Compute the block size in bits, . Convert to a sequence of blocks , where each block is bits in length. Select a random integer . Compute . For from 1 to Compute . Compute the least significant bits of . Compute . Finally, compute . The encryption of the message is then all the values plus the final value: . Decryption An encrypted message can be decrypted with the private key as follows: Compute . Compute . Compute . Compute . Using the Extended