# How can the Schmidt–Samoa cryptosystem uniquely decrypt large messages?

Suppose I choose $p=7$ and $q=11$.

This gives a public key of $p^2·q = 539$.

However, decryption occurs using a modulus of $p·q=77$.

If a person chooses to encrypt $500$ using my public key, how do I recover this value if the decryption modulus is so much smaller?

Is this a limitation of the Schmidt-Samoa scheme?

Is there a maximum message size for this scheme? How can this size be securely provided to the user without leaking information about the private key?

When you take a look at the paper you can see, that it is actually defined as a key-encapsulation mechanism, meaning that you will never encrypt data, but only keys for a symmetric encryption scheme. (That is, short messages.)

Further in $\mathsf{TKEM.Key}(pk)$ the "key carrier" that will be encrypted is explicitely chosen from $\{0, 1,\ldots, 2^{rLen} - 1\}$ where $rLen = 2k − 2$. As $p$ and $q$ are both $k$-bit primes, $pq$ will always be greater then $2^{rLen} - 1$ and therefore the problem will not arise.

If you view the scheme as a public key encryption scheme, then the message space is simply $\{0, 1,\ldots, 2^{rLen} - 1\}$. You are not supposed to encrypt larger messages. (which is fine, because $k$ is a lot larger than in your example and you only want to encrypt short keys.)

In RSA, the plaintext and ciphertext spaces are the same $\mathbb{Z}_N$ where $N=pq$. This is not, however, true for all cryptosystems. Schmidt-Samoa is one example (Paillier is another). In Schmidt-Samoa $m\in\mathbb{Z}_{pq}$, while $c\in \mathbb{Z}_{N=p^2q}$.

So, if you pick $m=500$ but $500\not\in\mathbb{Z}_{pq}$, you are really encrypting $500\pmod{pq}$. A similar analogy in RSA would be if $N=143$ and you chose $m=500$. $m$ is not in the plaintext space, so you won't get the exact same $m$ from decryption.

Is this a limitation of the Schmidt-Samoa scheme?

Not really, you are asking the cryptosystem to do something it was never intended to do (i.e., encrypt a plaintext that is not in the plaintext space).

Is there a maximum message size for this scheme? How can this size be securely provided to the user without leaking information about the private key?

The maximum message size is determined by the plaintext space. One way to do it would be to tell the user a maximum number of bits for plaintext messages. For example if $p$ and $q$ are each $512$ bits, $p\cdot q$ would be approximately $1024$ bits, so tell the user not to encrypt anything bigger than $1000$ bits.

From @Maeher's comment:

The message space in the scheme is however limited to $\{0,1,\cdots,2^{2k-2}-1\}$, (where $p,q$ are $k$-bit primes),

• You cannot publish $pq$. $N=p^2q$, therefore $N/(pq)=p$. That would break the scheme. The message space in the scheme is however limited to $\{0, 1,\ldots, 2^{2k-2} - 1\}$ (where $p,q$ are $k$-bit primes), so that solves the problem. – Maeher Jun 15 '12 at 17:14
• @Maeher, good call. I'll update my post. – mikeazo Jun 15 '12 at 17:17