Computation on encoded-and-encrypted values

A cryptographic device (110,112) for performing an encrypted computation on a set of one or more encoded-and-encrypted values, wherein:

• a value is encoded-and-encrypted as encryptions of multiple respective subvalues, wherein a subvalue has a corresponding message modulus and carry-message modulus larger than the message modulus;
• a value is encoded-and-encrypted without carry by non-carry subvalues smaller than the corresponding message moduli;
• and
• a value is encoded-and-encrypted with carry by at least one with-carry subvalue larger than or equal to the corresponding message modulus,
• wherein the device (110,112) comprises:
• a storage (140) for storing the one or more encoded-and-encrypted values;
• a processor subsystem (130) configured to apply an encrypted operation to at least an input value encoded-and-encrypted with carry to obtain an output value encoded-and-encrypted with carry;
• and to apply an encrypted carry-reduction to the output value encoded-and-encrypted with carry to obtain a further encoding-and-encryption of the output value in which at least one with-carry subvalue is reduced to a non-carry subvalue.