Modern cryptography is not only about protecting data from unauthorized access, but also about enabling computation on encrypted information. This idea, known as homomorphic encryption, allows specific operations to be performed directly on ciphertexts without revealing the underlying plaintext. Among the early milestones in this field, the Goldwasser–Micali cryptosystem stands out as a pioneering probabilistic encryption scheme with homomorphic properties over bitwise XOR. However, as practical applications evolved, the need for different types of homomorphic operations became apparent. In particular, supporting logical AND operations over encrypted data opens the door to a broader class of secure computations.
Addressing this gap, the Sander-Young-Yung (SYY) cryptosystem, introduced in 1999 by Tomas Sander from Berkeley, Adam Young and Moti Yung from Columbia, extends the ideas behind Goldwasser–Micali to achieve homomorphism with respect to bitwise AND instead of XOR. The security of the SYY cryptosystem, like its predecessor, is rooted in the hardness of the quadratic residuosity problem, a well-studied assumption in number theory and cryptography. This mathematical foundation ensures that, while encrypted data can be manipulated in controlled ways, recovering the original plaintext without the private key remains computationally infeasible. In this blog post, we will walk through the Sander–Young–Yung cryptosystem step by step, building an intuitive understanding of its design and then implementing it in Python. By the end, you will not only see how bitwise AND homomorphism is achieved, but also gain deeper insight into how classical number-theoretic assumptions power modern cryptographic constructions.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Sander-Young-Yung In Python
In this post, we will mostly focus on the math behind the cryptosystem and implement it from scratch. If you are interested in how to use the algorithm easy and fast instead of its mathematical foundation, then you may consider to use LightPHE.
LightPHE is a lightweight partially homomorphic encryption library for python. It wraps many partially homomorphic algorithms such as RSA, ElGamal, Exponential ElGamal, Elliptic Curve ElGamal, Paillier, Damgard-Jurik, Okamoto–Uchiyama, Benaloh, Naccache–Stern, Goldwasser–Micali, Boneh-Goh-Nissim. With LightPHE, you can build homomorphic crypto systems with a couple of lines of code, encrypt & decrypt your data and perform homomorphic operations such as homomorphic addition, homomorphic multiplication, homomorphic xor, regenerate cipher texts, multiplying your cipher text with a known plain constant according to the built algorithm.
# !pip install lightphe>=0.0.21 from lightphe import LightPHE # build the cryptosystem with randomly generated keys cs = LightPHE(algorithm_name="Sander-Young-Yung") # define plaintexts m1 = 17 m2 = 22 # encrypt c1 = cs.encrypt(plaintext=m1) c2 = cs.encrypt(plaintext=m2) # proof of decryption assert cs.decrypt(c1) == m1 assert cs.decrypt(c2) == m2 # homomorphic bitwise AND assert cs.decrypt(c1 & c2) == (m1 % modulo) & (m2 % modulo)
You may consider to watch the LightPHE demo video.
Homomorphic Encryption And Cloud
Homomorphic encryption enables computations on encrypted data without needing the private key. With the widespread adoption of cloud systems, homomorphic encryption has become increasingly popular. This technology allows us to store data in the cloud and leverage its processing power while keeping the private key secure. As a result, system design becomes both more cost-effective and secure. Watch this video to see how homomorphic encryption operates on both on-premises and cloud platforms.
Key Generation
In the Sander–Young–Yung cryptosystem, the key generation phase creates both the public and private keys. The process is probabilistic, meaning it may require multiple attempts before finding valid parameters.
We generate two large random primes p and q, they are roughly half of the total key size, they form the modulus n = p * q. This structure is similar to RSA and relies on the difficulty of factoring n.
p = sympy.randprime(2**512, 2**512) q = sympy.randprime(2**512, 2**512)
The parameter l defines part of the plaintext encoding range. This value becomes part of the public key.
l = random.randint(plaintext_limit, plaintext_limit + 100)
We compute the modulus n as the product of primes p and q. The security of the system depends on the hardness of factoring n.
n = p * q
We pick a random integer x in the multiplicative group modulo n.
x = random.randint(1, n - 1)
We require gcd(x, n) = 1. This ensures x is invertible modulo n.
if math.gcd(x, n) != 1:
continue
x must be a quadratic non-residue modulo both p and q. This structure is essential for the homomorphic AND property of the scheme.
if jacobi_symbol(x, p) != -1 or jacobi_symbol(x, q) != -1:
continue
Finally, (n, x, l) are public keys, and p and q are private keys.
In summary, key generation constructs:
- n = p × q (RSA-like modulus)
- x = special quadratic non-residue element
- l = plaintext range parameter
The security is based on quadratic residuosity, and the structure enables homomorphic AND operations over encrypted bits.
Encrypt
In the Sander–Young–Yung cryptosystem, encryption is more complex than standard schemes because each plaintext bit is expanded into a structured vector of ciphertext values. This structure is what enables homomorphic AND operations later.
Each encryption requires fresh randomness. This is critical for semantic security. We repeatedly sample a random integer r until gcd(r, n) = 1. This ensures that r is invertible modulo n, meaning it belongs to the multiplicative group Zn* (the set of all integers modulo n that are coprime with n).
def generate_random_key(self) -> int:
while True:
r = random.randint(0, n)
if math.gcd(r, n) == 1:
break
We convert the message into binary, and each bit will be encrypted separately.
m_binary = bin(plaintext)[2:] k = len(m_binary) for i in range(0, k): mi = int(m_binary[i])
We process the plaintext bit by bit. Each bit becomes a separate ciphertext vector.
For a bit equal to 1, encryption uses a zero vector encoding. The bit 1 is represented as a vector of all zeros in Z2l.
if mi == 1: vs = [0 for _ in range(l)]
In this case, we generate a fresh random value yi for each position and compute a quadratic residue modulo n:
yi = self.generate_random_key() ci = (yi * yi) % n ciphertext.append(ci)
Each ciphertext component is therefore of the form:
ci = yi^2 mod n
This means that every element encrypting bit 1 lies in the set of quadratic residues modulo n, which is an important structural property used in the security and homomorphic behavior of the scheme.
For a bit equal to 0, the encoding is different. Instead of using the zero vector, we randomly generate a non-zero binary vector vs in Z2l (the set of all binary vectors of length l, meaning all possible sequences of 0s and 1s with l elements). This ensures that at least one position contains a 1.
if mi == 0:
while True:
vs = []
for i in range(l):
vi = random.randint(0, 1)
vs.append(vi)
if sum(vs) > 0:
break
Once a valid non-zero vector is generated, each ciphertext component is constructed using both a random square and the public value x:
for i in range(l):
yi = self.generate_random_key()
ci = (yi * yi * pow(x, vs[i], n)) % n
ciphertext.append(ci)
This produces:
ci = yi^2 * x^vs[i] mod n
So each position behaves as follows:
If vs[i] = 0: ci = yi^2 mod n
If vs[i] = 1: ci = yi^2 * x mod n
This introduces the key cryptographic distinction between bit 0 and bit 1: the presence of the special value x, which is chosen to be a quadratic non-residue under specific constraints.
After processing all bits, the function returns a list of ciphertext vectors, where each vector corresponds to one plaintext bit:
At a high level, encryption works by:
- Expanding each bit into a vector of length l
- Encoding 1 using only quadratic residues
- Encoding 0 using a mixture of quadratic residues and the special element x
This structure is what later enables homomorphic evaluation of logical AND operations over encrypted data.
Decrypt
In the Sander–Young–Yung cryptosystem, decryption reverses the structured encoding used during encryption by exploiting knowledge of the secret factors p and q. The core idea is to recover each plaintext bit from the algebraic properties of quadratic residues using Jacobi symbol tests.
For each ciphertext vector, we reconstruct a binary vector vs by testing each component using the Jacobi symbol. This step uses the factorization of n = p * q, which is only known to the private key holder.
vs = []
for i in range(l):
if jacobi_symbol(ci[i], p) == 1 and jacobi_symbol(ci[i], q) == 1:
vi = 0
else:
vi = 1
vs.append(vi)
The intuition is:
- If an element behaves like a quadratic residue modulo both p and q, it is interpreted as 0
- Otherwise, it is interpreted as 1
This allows us to recover the hidden binary structure encoded during encryption.
Once the vector vs is reconstructed, we decide the plaintext bit based on whether it is the zero vector or not:
plaintext = 1 if sum(vs) == 0 else 0 plaintexts.append(plaintext)
So, if all entries are 0 → plaintext bit is 1. Otherwise, plaintext bit is 0.
Finally, we reconstruct the original binary message by concatenating all recovered bits and converting them back to an integer:
return int("".join(map(str, plaintexts)), 2)
At a high level, decryption works by:
- Using p and q to test quadratic residuosity via the Jacobi symbol
- Reconstructing the hidden binary vector for each ciphertext block
- Mapping the all-zero vector back to bit 1 and any non-zero vector to bit 0
- Reassembling the full binary plaintext from recovered bits
Homomorphic Features
One of the most powerful aspects of the Sander–Young–Yung cryptosystem is that it supports homomorphic AND operations, meaning we can compute logical AND directly on encrypted data without decrypting it first.
This property comes from the algebraic structure of the ciphertexts, where multiplication in the ciphertext space corresponds to logical operations on the underlying plaintext bits.
for c1, c2 in zip(ciphertext1, ciphertext2):
c1_and_c2 = [(c1[i] * c2[i]) % n for i in range(l)]
This step is crucial:
- Multiplication in the ciphertext space corresponds to combining encrypted structures
- The modulo n ensures the result stays within the correct algebraic group
At a high level, this function works because:
- Each ciphertext encodes a structured vector in Zn.
- The encoding distinguishes between 0 and 1 using quadratic residue properties and the special element x.
- Multiplying ciphertext components preserves and combines these structures in a way that reflects logical AND at the plaintext level
Summary
- The function performs component-wise multiplication of ciphertext vectors
- This operation is homomorphic with respect to logical AND
- It allows secure computation on encrypted bits without decryption
- The correctness relies on quadratic residuosity structure and the design of the encoding scheme
Re-Randomization
In the Sander–Young–Yung cryptosystem, re-randomization (also called re-encryption) is used to refresh ciphertexts without changing the underlying plaintext. This is an important security feature because it removes any structural traces from previous computations and ensures semantic security is preserved after homomorphic operations.
The key idea is that a ciphertext can be transformed into a new ciphertext that encrypts the same value, but looks completely different.
We iterate over each ciphertext vector. Each ci represents one encrypted plaintext bit encoded as a list of integers.
for ci in ciphertext:
For each ciphertext vector, we generate a fresh set of random values. Each component gets its own independent randomness.
r = [self.generate_random_key() for _ in range(l)]
These random values are sampled from Zn∗, ensuring they are invertible modulo n.
We then apply the re-randomization transformation. Each ciphertext component is multiplied by the square of a fresh random value:
ci_reencrypted = [
(ci[i] * r[i] * r[i]) % self.ciphertext_modulo for i in range(l)
]
This step is crucial:
- Each original ciphertext component ci[i] is “masked” by a fresh random square ri2.
Because squares preserve the quadratic residue structure, the underlying plaintext does not change. However, the resulting ciphertext becomes statistically independent from the previous one
Mathematically:
ci'[i] = ci[i] * ri2 mod n
Re-randomization ensures that:
- The ciphertext remains valid (decrypts to the same plaintext)
- But loses any link to previous encryptions or homomorphic operations
- The distribution of ciphertexts becomes fresh and indistinguishable from new encryptions
Summary
- Re-encryption multiplies each ciphertext component by a random square ri2
- This preserves correctness due to quadratic residue structure
- It significantly improves security by hiding computation history
- It is essential for maintaining semantic security after homomorphic operations
Conclusion
In this blog post, we explored the Sander–Young–Yung cryptosystem step by step, starting from key generation, moving through encryption and decryption, and finally covering its homomorphic AND functionality and re-randomization mechanism.
Unlike classical encryption schemes, SYY is designed not only to protect data but also to allow meaningful computation on encrypted values. This is achieved by carefully encoding bits using quadratic residues and non-residues modulo a composite number n = pq, whose security relies on the hardness of the quadratic residuosity problem.
We also saw how each plaintext bit is expanded into a structured vector in Z2l, enabling a clear separation between logical 0 and 1 in the encrypted domain. This structure is what makes homomorphic AND operations possible through simple component-wise multiplication in the ciphertext space.
Finally, re-randomization ensures that ciphertexts remain secure even after multiple transformations, by continuously refreshing them with fresh randomness while preserving the underlying plaintext.
Overall, the Sander–Young–Yung scheme is a beautiful example of how deep number-theoretic concepts can be used to construct cryptographic systems that support computation over encrypted data, bridging the gap between security and functionality.
Support this blog financially if you do like!
