A
k
-th order Carmichael key scheme for shared encryption
Authors: Russell Selwyn 
Published: June 2007

A generalization of a digital multisignature key scheme
published by Desmedt and Frankel is presented, with increased
protection from line monitors and with a high degree of privacy of
message contents.

The Desmedt/Frankel paper at Crypto'91 [1] presented the
following shared encryption Carmichael scheme:

&bull; An RSA cryptosystem with modulus n and private key K
Priv.

&bull; Separate individual keys K
Priv<sub>i</sub> are generated by some unspecified
process with the sole requirement that &Sigma;K
Priv<sub>i</sub> &equiv; (K Priv - 1) mod
&lambda;(n), where &lambda;(.) is the Carmichael
function.

&bull; Individual signatures ("partial results") of a
message m are calculated as s<sub>i</sub> &equiv;
m<sup>K Priv<sub>i</sub></sup> mod n.

&bull; A "Combiner" produces the final signature S from the
partial results and the plain text message as S &equiv; m
IIs<sub>i</sub> mod n. The combiner is specified as
"not necessarily trusted".

Desmedt/Frankel specify that the message m is being signed, not
a message digest value derived from the message. The limitation is
apparently imposed to meet the requirement that it must be
impossible for the combiner to substitute a different message for a
given set of partial results. This requirement is met if the plain
text message rather a message digest is used in the calculations.
This requirement is practical only when the length of the message
is less than the length of the RSA modulus. Many users would
probably prefer to use the message digest rather than the message
as the basis for the signature, for example as specified in the RSA
Public Key Cryptographic Standards (PKCS) [2] and Internet Privacy
Enhanced Mail [4]. Using the PKCS minimum modulus size of 328 bits
and PKCS padding of a minimum of 11 octets limits the message size
to 30 bytes.

A wire tapper who intercepts the partial results sent to the
Combiner will not be able to forge a signature without knowing the
original message. The power of this feature depends entirely on the
secrecy applied to the message inside the enterprise. If the wire
tapper is able to intercept the partial values sent to the
Combiner, the wire tapper will presumably be able to intercept the
original message sent to the Combiner. The wire tapper will then
have sufficient information to produce a signature. Forgery is more
likely in the more practical case where a message digest is signed
rather than a short message. If a message digest were used, it is
possible (but computationally difficult) to substitute a different
message which has the same message digest as the original [3], and
therefore obtain a verifiable signature for a fraudulent message.
For the Desmedt/Frankel system to be secure, the message must be
limited to those with high security clearances.

Most enterprises limit access to sensitive plain text
information on a "need to know" basis. The Combiner in the
Desmedt/Frankel scheme does not need to know the contents of the
plain text messages to combine the partial values. Moreover, the
("not necessarily trusted") Combiner is not provided with any
confidential exponent, but certainly does have access to the plain
text message. Thus, the combiner may be considered as not
sufficiently trustworthy to be provided with an exponent, but
nevertheless does have access to the plain text document.
Management may regard this as a security anomaly and wish the
document to be unreadable by the Combiner. To meet this
requirement, we extend the Desmedt/Frankel key scheme into what we
can name a k-th order Carmichael key scheme for RSA:

&bull; An RSA cryptosystem with modulus n and private key K
Priv.

&bull; Individual keys K Priv<sub>i</sub> are
generated by some unspecified process with the sole specification
that &Sigma;K Priv<sub>i</sub> &equiv; (K Priv
- k) mod &lambda;(n), where &lambda;(.) is the Carmichael
function.

&bull; Individual signatures of a message m are calculated
as s<sub>i</sub> &equiv; m<sup>K
Privi</sup> mod n.

&bull; The combiner produces the final signature S as S
&equiv; m<sup>k</sup> IIs<sub>i</sub>
mod n.

Now the combiner is provided with m<sup>k</sup> mod
n rather than m, and the confidentiality of the document is
preserved. Using this terminology, the Desmedt/Frankel scheme is
classified as a first order Carmichael key scheme.