Abstract
An authentication code consists of a collection of encoding rules associating states of an information source with messages that are to be used to communicate the state to a designated receiver. In order for a collection of encoding rules to be useful as an authentication code there must also exist one or more probability distributions on the rules which, if used by the receiver and transmitter (the insiders) to choose secretly the encoding rule they use, will result in the receiver being able to (probably) detect fraudulent messages sent by an outsider or modifications by him of legitimate messages.
Authentication codes that permit arbitration are codes that in addition to protecting the insiders from deception by outsiders, also protect against some forms of insider deception. This is accomplished by making it possible for an arbiter to resolve (again in probability) certain disputes between the transmitter and receiver: the transmitter disavowing a message that he actually sent or the receiver claiming to have received a message that the transmitter did not send.
An infinite class of authentication codes that permit arbitration is constructed and some bounds on the probability of a deception going undetected are proven. These codes are shown to be unconditionally secure, i.e., it is shown that the probability of a deception either going undetected or else of being unjustly attributed to an innocent party is independent of the computing capability or investment that a would-be cheater is willing to make.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
T.Beth, D.Jungnickel, and H.Lenz, Design Theory, Bibliographisches Inst., Zurich, 1985.
E. F.Brickell, A Few Results in Message Authentication (15th Southeastern Conference on Combinatorics, Graph Theory and Computing, Baton Rouge, LA, March 5–8, 1984), Congressus Numerantium, Vol. 43, 1984, pp. 141–154.
E. F.Brickell and D. R.Stinson, Authentication Codes with Multiple Arbiters (Eurocrypt '88, Davos, Switzerland, May 25–27, 1988), in Advances in Cryptology, ed. by Christoph G.Günther, Springer-Verlag, Berlin, 1988, pp. 51–55.
R. H.Bruck, Finite Nets, I: Numerical Invariants, Canadian Journal of Mathematics, Vol. 3, 1951, pp. 94–107.
R. H.Bruck, Finite Nets, II: Uniqueness and Embedding, Pacific Journal of Mathematics, Vol. 13, 1963, pp. 421–457.
M. De Soete, Some Constructions for Authentication—Secrecy Codes (Eurocrypt '88, Davos, Switzerland, May 25–27, 1988), in Advances in Cryptology, ed. by Christoph G.Günther, Springer-Verlag, Berlin, 1988, pp. 57–75.
T. ElGamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Transactions on Information Theory, Vol. 31, No. 4, 1985, pp. 469–472.
E. N.Gilbert, F. J.MacWilliams, and N. J. A.Sloane, Codes Which Detect Deception, The Bell System Technical Journal, Vol. 53, No. 3, March 1974, pp. 405–424.
S.Goldwasser, S.Micali, and R. L.Rivest, A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, SIAM Journal on Computing, Vol. 17, No. 2, 1988, pp. 281–308.
M.HallJr., Combinatorial Theory, second edition, Wiley, New York, 1986.
C. L. Henderson and A. M. Fine, Motion, Intrusion and Tamper Detection for Surveillance and Containment, Report SAND79-0792, Sandia National Laboratories, March 1980; also published by the International Safeguards Project Office for the International Atomic Energy Agency (IAEA) as ISPO Report No. 91, 1980.
J. L.Massey, Cryptography—A Selective Survey (International Tirrenia Workshop on Digital Communications, Tirrenia, Italy, Sept. 1–6, 1985), Alta Frequenza, Vol. LV, No. 1, 1986, pp. 4–11.
P. D. Merrillat, Secure Stand-alone Positive Personnel Identity Verification System (SSA-PPIV), Technical Report SAND79-0070, Sandia National Laboratories, March 1979.
J.-J.Quisquater and J.-P.Delescaille, How Easy Is Collision Search? Application to DES (Eurocrypt '89, Houthalen, Belgium, April 11–13, 1989, updated version Crypto '89, Santa Barbara, CA, August 20–24, 1989), in Advances in Cryptology, ed. by G.Brassard, Springer-Verlag, Berlin, 1990, pp. 419–424.
M. O. Rabin, Digitized Signatures and Public-key Functions as Intractable as Factorization, Technical Report LCS/TR-212, M.I.T. Laboratories for Computer Science, 1979.
R.Rivest, A.Shamir, and L.Adleman, A Method for Obtaining Digital Signatures and Public Key Cryptosystems, Communications of the ACM, Vol. 21, No. 2, 1978, pp. 120–126.
P. Schoebi, Perfect Authentication Systems for Data Sources with Arbitrary Statistics, Presented at Eurocrypt '86, Linköping, Sweden, May 20–22,1986.
G. J.Simmons, A Game Theory Model of Digital Message Authentication (11th Annual Conference on Numerical Mathematics and Computing, Winnipeg, Oct. 1–3, 1981), Congressus Numerantium, Vol. 34, 1982, pp. 413–424.
G. J.Simmons, A System for Verifying User Identity and Authorization at the Point-of-Sale or Access, Cryptologia, Vol. 8, No. 1, 1984, pp. 1–21.
G. J.Simmons, Message Authentication: A Game on Hypergraphs (15th Southeastern Conference on Combinatorics, Graph Theory and Computing, Baton Rouge, LA March 5–8,1984), Congressus Numerantium, Vol. 45 1984, pp. 161–192.
G. J.Simmons, Authentication Theory/Coding Theory (Crypto '84, Santa Barbara, CA, August 19–22,1984), in Advances in Cryptology, ed. by R.Blakley, Springer-Verlag, Berlin, 1984, pp. 411–431.
G. J.Simmons, Authentication Codes that Permit Arbitration (18th Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton, FL, Feb. 23–27, 1987), Congressus Numerantium, Vol. 59, 1987, pp. 275–290.
G. J.Simmons, Message Authentication with Arbitration of Transmitter/Receiver Disputes (Eurocrypt '87, Amsterdam, April, 13–15,1987), in Advances in Cryptology, ed. by D.Chaum and W. L.Price, Springer-Verlag, Berlin, 1988, pp. 151–165.
G. J.Simmons, A Natural Taxonomy for Digital Information Authentication Schemes (Crypto '87, Santa Barbara, CA, Aug. 16–20, 1987), in Advances in Cryptology, ed. by CarlPomerance, Springer-Verlag, Berlin, 1988, pp. 269–288.
G. J.Simmons, A Protocol To Provide Verifiable Proof of Identity and Unforgeable Certified Receipts, IEEE Journal of Selected Areas in Communications (Special Issue on Secure Communications), Vol. 7, No. 4, 1989, pp. 435–447.
D. R.Stinson, Some Constructions and Bounds for Authentication Codes (Crypto '86, Santa Barbara, CA. Aug. 12–15,1986), in Advances in Cryptology, ed. by A. M.Odlyzko, Springer-Verlag, Berlin, 1987, pp. 418–425; also in Journal of Cryptology, Vol. 1, No. 1, 1988, pp. 37–51.
D. R.Stinson, A Construction for Authentication Secrecy Codes from Certain Combinatorial Designs, (Crypto '87, Santa Barbara, CA, Aug. 16–20,1985), in Advances in Cryptology, ed. by CarlPomerance, Springer-Verlag, Berlin, 1988, pp. 355–366; also in Journal of Cryptology, Vol. 1, No. 2, 1988, pp. 119–127.
H. C.Williams, A Modification of the RSA Public-Key Encryption Procedure, IEEE Transactions on Information Theory, Vol. 26, No. 6, 1980, pp. 726–729.
Author information
Authors and Affiliations
Additional information
This work was performed at the Sandia National Laboratories and was supported by the U.S. Department of Energy under Contract No. DE-AC04-76DP00789.
Rights and permissions
About this article
Cite this article
Simmons, G.J. A cartesian product construction for unconditionally secure authentication codes that permit arbitration. J. Cryptology 2, 77–104 (1990). https://doi.org/10.1007/BF00204449
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00204449