Digital Signature with Subliminal Channel
Lein Harn and Guang Gong
Department of Computer Networking
University of Missouri - Kansas City
Kansas City, MO 64110
TEL:(816)235-2367
FAX:(816)235-5159
Email:HARN@CSTP.UMKC.EDU
Abstract: A subliminal channel is a covert communication channel to send a message to the authorized receiver; but this message cannot be discovered by any unauthorized receiver. It can be a debating issue to discuss whether it is a good or a bad property for designing cryptosystems in which there are subliminal channels. This type of discussion is beyond the scope of our paper. But, there are some applications that can take advantage by hiding secret message in this subliminal channel. For example, the credit card provider can hide card holder's credit history and credit limit in a digital signature for issuing credit card. Simmons had found that ElGamal-type digital signature schemes, due to their low information rate, can be easily established a subliminal channel. Simmons had also found that in all broadband subliminal channels devised thus far the receiver needs to know the transmitter's secret signing key; but the subliminal channels that do not require the transmitter to entrust his secret key to the subliminal receiver are generally narrowband. Thus, this limits the practical usefulness of the subliminal channel. In this paper, we show how to construct a digital signature scheme with a broadband subliminal channel that does not require the subliminal receiver to share the transmitter's secret signing key. The subliminal channel can be constructed in either p-channel or q-channel, where p and q are two large primes as used in the RSA scheme. To any outsider, forging a legitimate signature requires to solve both the factoring problem and the discrete logarithm problem. In addition, we propose to implement the signature scheme based on the Lucas function in order to achieve great efficiency.
Key words: Digital signature, subliminal channel, covert channel.
I. Introduction
A subliminal channel is a covert communication channel that can be used to send a secret message to an authorized receiver; but the message cannot be discovered by any unauthorized receiver. It can be a debating issue to discuss whether it is a good or a bad property for designing cryptosystems in which there are subliminal channels. This discussion is beyond the scope of our paper. But, there are some applications that can take the advantage by hiding secret message in this subliminal channel. For example, the credit card provider can hide card holder's credit history and credit limit in the subliminal channel for issuing digital signature of credit card. Simmons [1] had shown how to construct subliminal channels by using any signature scheme.
The security of ElGamal's signature scheme is based on solving the discrete logarithm problem. Assume that the ElGamal scheme requires b bits of security against forgery and a bits are used to communicate a signature. Since a>b, the a-b bits are potentially available for the subliminal communication. Simmons [2] had defined that if the subliminal channel uses all, or nearly all, of the a-b bits, it is said to be the broadband; otherwise it is said to be the narrowband.
The digital signature on a passport can be used by customs agents to authenticate the passport holder. The message in the subliminal channel can also tell customs agents that the passport holder is a known terrorist, smuggler, etc. The digital signature on a driver's license can be used by shop tellers to verify the bearer's identity. The message in the subliminal channel can also tell law enforcement agents the bearer's driving record, his traffic violations' history, etc. The digital signature on a credit card can be used by any commercial company to verify the customer's identity. The message in the subliminal channel can also tell verifiers that the customer's credit limit, payment history, etc. Thus, there are many potential applications can be benefited from the subliminal channel.
Simmons [3] had described several narrowband subliminal channels that do not require the subliminal receiver to share the transmitter's secret signing key. In Eurocrypt '93, Simmons [2] had also describe a broadband subliminal channel that requires the subliminal receiver to share the transmitter's secret signing key. This requirement will limit the practical usefulness of the subliminal channel. Due to this requirement, the customs agent requires to know the secret signing key of the passport agency, the law enforcement agent requires to know the secret signing key of the driver's license bureau, the shop teller requires to know the secret signing key of the credit card issuer. In other words, the subliminal receiver shares the same capability with the transmitter. In general, this requirement cannot be accepted by most applications. We should point out here that there are three entities with different knowledge in these applications. The signature signer knows all secrets. The subliminal receivers know partial secret to recover subliminal messages; but they cannot forge any signature. The outsiders know only the public key of the signer to verify any signature.
In this paper, we show how to construct a digital signature scheme with broadband subliminal channel that does not require the subliminal receiver to share the transmitter's secret signing key. The subliminal channel can be constructed in either p-channel or q-channel, where p and q are two large primes as used in the RSA scheme. To any outsider, forging a legitimate signature requires to solve both the factoring problem and the discrete logarithm problem. Thus, this signature scheme is more secure in comparing with most schemes that the security relies on just one cryptographic assumption. We will also discuss some variations of this scheme to improve the security as well as the efficiency.
II. Proposed Digital Signature Scheme with Broadband Subliminal Channel
We assume that there are two "disjoint" subliminal channels, p-channel and q-channel, in the signature scheme. We call them disjoint channels because we assume that each subliminal receiver can only belong to one of these two channels and receivers in these two channels do not exchange secrets with each other. The signature signer needs to select four large primes, 
, 
, 
and 
, where 
and 
, and two secret keys, 
and 
, where 
are even integers, for these two disjoint subliminal channels. The signer needs to compute 
and to select a public parameter 
with order 
operation. The public key used to verify any signature is 
which is the common solution that satisfies both equations 
and 
, where 
and 
. We denote 
as 
(i.e., CRT stands for the Chinese Remainder Theorem). The signer also needs to compute a secret signing key 
, where
and 
. We need to point out here since gcd(
)=2, by restricting 
be even integers can guarantee us that there are two solutions of 
. We can always select the smaller one as the secret signing key x. Since each subliminal receiver needs to know either p or q in order to discover the subliminal message, these two secret primes cannot be kept secret from subliminal receivers. We need to point out here that although each subliminal receiver knows how to factor n; but this information does not reveal to any outsider.
Secret key for the signer: 
.
Secret key for the p-channel receiver: 
.
Secret key for the q-channel receiver: 
.
Public key for outsider: 
.
Signature generation: For the sake of easy representation, we assume that signer wants to sign m, where m is the one-way hash result of a meaningful message. We assume that there are two subliminal messages, 
, where 
are even integers (i.e., the last bit is zero), needed to be hidden in p- and q- channels respectively. Signer needs to compute 
, 
and 
. Again, there are two solutions of 
and we can select the smaller solution as 
. Then the signer uses the Chinese Remainder Theorem to compute 
. The signer uses the secret signing key 
to solve the equation 
, where 
. The signature of m is (r, s).
Signature verification: The signature (r, s ) for m can be verified using the public key 
by checking whether 
Theorem:
If 
, then (r, s) is the valid signature for m.
Proof. Since the signature (r, s ) for m satisfies
,
we then have
,
and
.
Thus, we obtain
and
Since we have
, and 
, we can obtain the equality
. Q.E.D.
Message recovery in subliminal channels: p-channel receiver uses the secret key
to compute 
, where 
. Similarly, q-channel receiver uses the secret key 
to compute 
.
Discussion:
(a) For each subliminal channel receiver, since p- and q- channels are disjoint and thus each receiver knows either
, he needs to solve the discrete logarithm problem in order to obtain the other secret. In our signature scheme, the subliminal receiver does not have the same capability as the signer.
(b) For any outsider, in order to forge a signature, it needs to solve both the factoring and the discrete logarithm problems. Thus, this signature scheme is more secure in comparing with most schemes that the security relies on just one cryptographic assumption. The security of this proposed signature scheme can be found in [4].
(c) This proposed scheme can hide any message in subliminal channels. In addition, the message can be discovered by the subliminal receiver without computing any multiplication inverse. In [4], there is one other variation of ElGamal signature scheme,
which can provide the same result.
(d) In the above scheme we assume that p- and q- channels are disjoint. This assumption differentiates the capability between the signer and the subliminal receivers. If it is impossible to enforce this assumption in the practical application, we may just use a single subliminal channel to hide the secret message. Thus, it is impossible for subliminal receivers to obtain both secrets,
, of these two channels simultaneously. There is one alternative approach that can cause the subliminal receiver to have difficulty in forging any signature. Instead of using p- and q- channels, we create a new subliminal channel. We call it as the r-channel. The signer needs to select one more prime r. The size of this prime can be much smaller than either p or q. The secret key for the r-channel is 
. The public key for any signature is 
, where 
. The signer uses the same approach to hide message 
in the r-channel. Subliminal receiver needs to know the secret key 
to discover the message. Although this small prime r can be factored out easily from n, the other factoring problem is still based on the size of the product of two large primes p and q.. To any outsider or subliminal receiver, he has to solve both the factoring problem and the discrete logarithm problem in order to forge any signature.
III. Modified Lucas-Type Signature Scheme with Broadband Subliminal Channel
Recent advanced techniques imply that the computational difficulties of solving the factoring problem in
and solving the discrete logarithm in 
are almost the same. Thus, in order to maintain the minimum security level for the scheme proposed in section II, the size of the modulus p for the discrete logarithm problem should be determined first. Then, the size of modulus n for the factoring problem will be too large. McCurley [5] proposed the first cryptosystem based on these two assumptions. However, this design results in two disadvantages: (1) larger key size; and (2) longer computation time. Since the computational difficulty for solving the discrete logarithm in 
is much harder than that in 
[6], it is possible to reduce the difference between security levels if we build our scheme based on solving the discrete logarithm in 
and solving the factoring problem in 
. This approach can maintain the efficiency of the implementation. Since Lucas-type cryptosystems can incorporate the factoring problem in 
and the discrete logarithm problem in 
together in an efficient way, we suggest to modify the above signature scheme to base on the Lucas function.
A Lucas sequence can be represented as 
which elements are given by
in 
with 
,
, and 
. A Lucas sequence in 
is a 2nd-order linear recurring sequence over 
with the minimal polynomial 
and the initial state 
. Let
a and 
be two roots of the minimal polynomial f(x). Then 
.
Horster et al. [7] has proposed a Lucas-type signature scheme in 1995. As a result of their scheme, the signature generation (which requires one evaluation of Lucas function) and the signature verification (which requires three evaluations of a Lucas function) are slightly less efficient than that of the original ElGamal signature scheme over GF(p). For more information on the Lucas-type signature scheme, please see reference [7].
System setup: The signer selects four large primes,
, 
, 
and 
, where 
and 
, and computes n=pq. Then select an irreducible polynomial 
, where f(x) is an irreducible polynomial over 
and 
. Instead of using a as a public parameter, here, the signer publishes 
. The public key used to verify any signature is 
which is the common solution that satisfies both equations 
and 
, where 
and 
. In other words, we have 
and 
. The secret keys and public keys for the signer, subliminal receivers and outsiders are the same as in Section II.
Signature generation: We assume that there are two subliminal messages,
, needed to be hidden in p- and q- channels respectively. Signer needs to compute 
. Then signer uses the Chinese Remainder Theorem to compute 
and 
. The signer uses the secret key 
to solve the equation 
.
Signature verification: The signature (r, s ) for m can be verified using the public key
by checking whether 
mod n. The correctness of this verification can be easily checked according to Theorem 1 in [7].
Message recovery in subliminal channels: p-channel receiver uses the secret key 
to compute 
. Similarly, q-channel receiver uses the secret key 
to compute 
.
Discussion:
(a) The signature verification requires two evaluations of a Lucas function, which is one less than the scheme proposed in [7]. From reference [4], following signature generation also requires just two evaluations for the verification: 
(b) Breaking this system is computationally infeasible because it requires: (1) factoring n into two large primes, and (2) solving the discrete logarithm problem in two subgroups of 
and 
. For example, if we select two large primes, p and q, with 614 bits each, then their product is 1228-bit long. According to [6], the difficulty of solving the discrete logarithm problem in the subgroup of 
, with a 614-bit prime p, is equivalent to the difficulty of factoring a 1024-bit composite integer. Thus, in this proposed scheme, it is possible to reduce the difference between security levels for these two assumptions and to maintain the efficiency of the implementation.
IV. Conclusion
We have proposed a digital signature scheme with broadband subliminal channel. The unique feature of this proposed scheme is that the subliminal receiver does not require to share the sender's secret signing key. In other words, the sender does not need to completely trust the receiver. The security of this proposed scheme is based on two different assumptions. Since the signer shares only partial secret with the subliminal receiver, the subliminal receiver still has to solve one security problem in order to forge a signature. The efficiency of the basic scheme can be improved if we construct the proposed scheme on a Lucas function.
References
[1] G. J. Simmons, "A Secure Subliminal Channel (?),"Advances in Cryptology-Crypto '85, Lecture Notes in Computer Science, vol. 963, Springer-Verlag, pp. 33-41, Aug. 1985.
[2] G. J. Simmons, "Subliminal Communication is Easy using the DSA, "Pre-proceedings of Eurocrypt '93, Lofthus, Norway, May 1993.
[3] G. J. Simmons, "The Subliminal Channels in the U. S. Digital Signature Algorithm (DSA)," Proceedings of the 3rd Symposium on State and Progress of Research in Cryptography, Rome, Italy, Feb. 15-16, 1993.
[4] L. Harn and Y. Xu, "On the Design of Generalized ElGamal Type Digital Signature Schemes Based on the Discrete Logarithm", Electronics Letters, Vol. 30, No. 24, pp. 2025-2026, Nov. 1994.
[5] K. S. McCurley, "A Key Distribution System Equivalent to Factoring," Journal of Cryptology, Vol. 1, No. 2, pp. 95-106, 1988.
[6] D. Bleichenbacher, W. Bosma, A.K. Lenstra, "Some Remarks on Lucas-Based Cryptosystems," Advances in Cryptology-Crypto '95, Lecture Notes in Computer Science, vol. 963, Springer-Verlag, pp. 386-396, Aug. 1995.
[7] P. Horster, M. Michels and H. Petersen, "Digital Signature Schemes Based on Lucas Functions," Proceedings of the Communications and Multimedia Security Conference, IFIP TC-6 and TC-11, Graz, Austria, Sep. pp. 20-21, 1995.