BALANCED KEY ESCROW                                    

                            Lance J. Hoffman


      Institute for Computer and Telecommunications Systems Policy

                School of Engineering and Applied Science

                    The George Washington University

                         Washington, D. C. 20052


                             August 4, 1995





               This paper presents a framework for key escrow encryption

          that satisfies most law enforcement and civil liberties concerns.   It

          provides users considerable autonomy in deciding how and with

          whom information will be escrowed.  It relies on no specific

          technological solution but will accommodate all of them, whether

          implemented in hardware, software, firmware, or paper!  Depending

          on the specific system, it may provide real-time emergency access to

          information when requested by authorized entities.  Users, not

          governments, bear the costs of the scheme. 


                               BALANCED KEY ESCROW

                               Lance J. Hoffman




                    In this paper we present a framework that

               removes the debate about who should be able to read

               encrypted messages from the technological domain

               and pushes it back where it belongs -- into the political

               and legal arena.  We thus hope to move the discussion

               past the current stalemate among government, private

               sector, and civil liberties interests.  Any technological

               solution and any cryptographic algorithm can be used

               within the framework.  Specifically, DES [NBS 1977],

               RSA [Rivest 1978], PGP [Garfinkel 1994,

               Zimmermann 1995], Skipjack [Brickell 1993], and

               Commercial Key Escrow [Walker 1995] can all be

               supported by this framework.


               Clipper: Flawed First Steps


                    A system which is both readable by law

               enforcement authorities under certain circumstances

               and otherwise capable of very strong encryption has

               been a recent goal of the United States government. 

               The Clipper chip's objectives  were to  protect

               American telephone communications against

               industrial espionage and other compromises while at

               the same time maintaining the existing capability of

               law enforcement and national security agencies to

               eavesdrop, with a court order, on suspect


                    Details of this initiative appear in numerous

               places [Denning 1994,  Brickell 1993, Levy 1994]. 

                Clipper will never gain widespread public acceptance

               since there are too many people who don't trust a

               scheme with only government escrow agents,

               especially when there are currently  over 15 escrowed

               encryption products or proposals [Denning 1995],

               many of which show promise of being more general,

               less expensive, and/or more politically acceptable to

               non-U. S. governments.  In addition, there are almost

               900 encryption products available in 33 countries

               around the world.  Detailed lists of these are as close

               as the nearest bookstore [Hoffman 1995] and are

               available on-line via the World Wide Web at



               Key Escrow - What Is Possible Now


                    Key escrow systems can provide escrowed

               encryption that is more sensitive to the balance

               between the citizen and government than the flawed

               Clipper initiative.  If  society decides that one does not

               always have a right to private communications, then

               when escrow is mandatory the key can be broken up

               and the various parts stored with escrow agents who

               are available around the clock.  Some of these agents

               would be trusted by the user and some by the

               government; ideally, most or all would be trusted by

               both.  Operational requirements could be specified by

               Congress [HR5199 1994], the private sector, an

               international standards organization, or some

               combination of these.

                    A solution is available, described below, that

               protects against  rogues, rogue governments, and

               rogue cartels of escrow agents.  It allows the cost of

               encryption and the escrow agencies to be borne by

               users  rather than the government. Persons might  still

               communicate over private networks (e.g., within an

               organization) without using key escrow, but might be

               required to  use escrowed encryption for some 

               applications (e.g., some communications with financial

               institutions or the government).

                    While some [Ellison 1995a] might disagree,

               this paper assumes that there is no absolute right to 

               encrypted  communication (just like there is no

               absolute right to some types of speech, e.g. shouting

               "Fire!" in a crowded theater) and that under certain

               limited circumstances authorized entities (for example,

               government authorities) may have the right to surveill

               communications and/or data.  The framework

               described below allows escrow of both

               communications and data storage and presents an

               improved framework for deterring rogue

               eavesdroppers, rogue governments, rogue escrow

               agents, and even rogue users.   While we are aware of

               the dangers of  "excessive balance" as described by

               Marc Rotenberg [Rotenberg 1995], we believe that

               under some circumstances (e.g., prevention of [an

               unacceptable amount of] [computer-assisted]

               terrorism), mandatory key escrow may be appropriate.


               Possible Paradigms


                    One possible paradigm for escrow schemes

               which are appropriate here might be the conditions

               proposed by the U. S. Council on International

               Business [USCouncil 1994a], which stated that if a

               key escrow system is used, it must meet the following



                    -     a government may not be sole holder

                                        of the entire key except at the

                                        discretion of the user

                    -    the key escrow agent is responsible for

                                        making keys available to lawfully

                                        authorized entities when provided with

                                        proper, written legal authorizations;

                                        [there is a need for international

                                        cooperation when appropriate]

                    -    the process for obtaining and using

                                        keys for wiretapping must be auditable

                    -    keys obtained by law enforcement

                                        must be ued for a specified, limited

                                        time frame

                    -    the owner may also obtain the keys

                                        from the escrow agent.


                    Another possible paradigm [Perritt 1995]

               contains the following criteria:


                    -    no limitation on encryption technique

                    -    both authenticaiton and secrecy uses


                    -    no performance degradation due to

                                        key escrow scheme

                    -    private key escrow must not be costly

                    -    users can choose their own escrow


                    -    escrow agents must be legally liable to

                                        follow the rules

                    -    to access escrowed keys, government

                                        must demonstrate to a neutral party

                                        other than the escrow agent itself

                                        probable cause and no other feasible

                                        means of access to the information

                    -    government access must not

                                        compromise further use of the system

                    -    secure and ultimately public logs of

                                        government accesses must be provided

                    -    export barriers must be eliminated and

                                        there should be no limitations on

                                        where keys can be escrowed

                    -    governments outside the United States

                                        should abide by search and seizure

                                        rules (see "Note on 'exporting' the

                                        Fourth Amendment" in [Perritt 1995])

                    -    system should prohibit government

                                        "fronts" and voluntary disclosure by

                                        escrow agents

                    -    system must include fora for resolving

                                        disputes over its operation


                    Key escrow under the framework described

               below provides an appropriate balancing of all the

               interests involved, and is compatible with each of these

               paradigms, and allows governments and private parties

               to hold keys with a mix determined by each country

               for data [it considers] under its jurisdiction.  We thus

               name it "Balanced Key Escrow."


               BALANCED KEY ESCROW


                    We propose that future escrow schemes all be

               balanced.  With any balanced key escrow (BKE)

               scheme, there can be many possible escrow agents. 

               Not all (or even any) need be government agencies.  

               There are several other possible escrow agents such as

               financial institutions, law offices, and corporate

               records storage facilities with a history of safeguarding

               confidential data. We acknowledge that (some)

               governments (and other entities) may  (attempt to)

               restrict who can be an escrow agent, either to

               government entities only or to organizations licensed

               by the government.  This paper does not propose such


                    The scheme below pertains explicitly to both

               messages being transmitted and messages being

               stored.  We recognize the argument [Walker 1995]

               that only messages being stored are valuable enough

               to users that they will have an interest in using one or

               more key escrow agents, and that messages being

               transmitted, if lost, are not "retrieved" but rather

               retransmitted.  However, for a completely general

               solution, we treat both cases. 

                    The [sender] user/owner  of the encrypted

               [message] data selects n (n>1) escrow agents out of

               the (large) set of available ones and deposits some of

               its key(s) with each one, using an appropriate

               technological scheme for key splitting.  A certain mix

               of escrow key holders might be required, for example

               one each from the federal government, a civil liberties

               organization, an organization outside the user's local

               geographical area, a financial institution, and an

               encryption services provider.   If the data is a message

               being sent across a communications medium, the

               sender also, of course,  provides the key (s) to its

               intended recipient(s).  If an authorized entity  (such as

               a government) wishes to decrypt the [message] data,

               it must request a key portion from each of the n

               escrow agents, presenting them with a court order or

               other suitable authorization. After duly authenticating

               the authorized entity and logging this transaction, the

               escrow agent will reveal its portion of the key to the

               authorized entity.  As soon as k out of n keys are

               recovered, it is possible for the authorized entity  to

               obtain the entire key and thus decipher the [message]

               data.  With some underlying systems (e.g., [Balenson

               1994]), this could happen in real time or "near real

               time."  We note that k and n might be uniform or

               might vary by application.

                    This solution protects against  rogues

               (interlopers) because in almost all cases when (say) the

               government (as authorized entity) requests keys from

               the n escrow agents, it will get n keys (if the escrow

               agents are honest) and can read the [message] data. 

               Even if it only gets k keys (k < n), it will still be able to

               read the [message] data.  In this case, there may be

               serious problems as to why the n-k agents are not

               providing the appropriate keys, and the government

               (which may not be the same as the authorized entity)

               may wish to look into this.  If less than k of the n keys

               are surrendered, then we have a clear case of

               (electronic) civil disobedience; this is the protection

               against rogue governments.  Indeed, with BKE there

               is not necessarily any escrow agent under the direct

               control of a government.  

                    There may be rogue escrow agents as well.  

               For example, if  k agents were laxly policed and

               decided to conspire against the system, or if one large

               corporation controlled k supposedly independent

               escrow agents,  this could render the whole scheme

               useless to the authorized entities.  They might, for

               example, collude to withhold their key portion from

               appropriate authorized entities or to put together their

               portions of the key and distribute or sell it to  persons

               not otherwise authorized.  There is some work already

               done (outside computer science) in detecting and/or

               preventing this type of behavior [Lipsky 1991].  

                     Finally, rogue users may  attempt to hide a

               "shadow key" in their escrowed key, and then use the

               shadow key instead of the escrowed key to circumvent

               the key escrow function.   This problem can be

               overcome by requiring that the user's keys be

               generated jointly by the user and key escrow agents

               [Kilian 1994].

                    The technological ideas behind BKE are not

               new.  Indeed, they have been the topic of discussion

               and refinement for several years [Benaloh 1986,

               Chaum 1988, Goldreich 1987, Micali 1994, Rabin

               1989, Shamir 1979].  What is new is that to address a

               knotty social problem, we have packaged together a

               number of elements -- 


                         Many key escrow agents for the user

                                        to choose from

                         requiring only k out of n cooperating


                         costs paid by the user

                         government playing a relatively small

                                        operational role


               -- and given this combination a label, Balanced Key





                    Using BKE allows one to focus more clearly

               on the important policy issues, separating them from

               the technological ones.  Major unresolved policy

               issues include several touched upon here.


               Mandatory Key Escrow


                    For a  certain possibly large subset of

               communications, such as those on the developing

               Global Information Infrastructure (GII), some would

               argue that  an escrowed key system should be

               required.  Some persons would trust government

               escrow agents more than those in the private sector. 

               Others would not, likening this to [Orwell 1984]

               arriving just a few years late.  Insisting that any

               required system be balanced mitigates the problems (of

               trust) so evident in the Clipper experience.


                Jurisdictional problems


                    Jurisdiction may also be an issue here, as it is

               often are in cyberspace [Johnson 1993, Hardy 1995]. 

               Significant problems may arise when escrow agents

               are situated  in several countries.  Presumably, they 

               would have to be allowed by their local authorities

               (who might have their  own restrictions on who can be

               an escrow agent).  If an emergency or investigation in

               Country A triggers a need for the (key) data from

               Country B, C, ..., there should be some agreement

               covering the responsibilities of the escrow holders in

               each country, and the authorized entity (in Country A) 

               should be able to assemble portions of the key from

               each country.  Given the current patchwork scheme

               of export and use controls [Bernstein 1994] which

               varies from country to country a great deal [Chandler

               1994], cooperation might be difficult.  Facilitating

               laws or treaties are needed, similar to judicial

               assistance treaties already in place.  But problems

               related to these may suggest that model agreements

               for private contractual arrangements, including search-

               and-seizure commitments, compliance monitoring,

               suretyship, and arbitration provisions may be more

               suitable [Perritt 1995, Johnson 1993].   




                    Liability is another issue to be dealt with

               [Baum 1994].  As another of its requirements,

               [USCouncil 1994a] states that "Key escrow agents,

               including any government agent, will be liable for

               theft, loss, or improper disclosure of keys, and any

               legislation necessary to implement or confirm such

               liability should be adopted.  Parties utilizing key

               escrow by contract with their escrow agents may

               obtain stronger or weaker assurances of the agent's

               liability, for example through the posting of bonds." 

               Another report [USCouncil 1994b] identifed specific

               liability concerns [OTA 1995]:


                    -    uncertainty about whether the U. S.

                                        government might authorize strict

                                        government liability for

                                        misappropriation of keys

                    -    the degree of care underlying design of

                                        Skipjack, EES, and Capstone (given

                                        the government's still-unresolved

                                        degree, if any, of liability

                    -    confusion concerning whether the

                                        government intends to disclaim all

                                        liabilty in connection with the EES and

                                        Capstone initiatives

                    -    uncertainties about the liability of

                                        nongovernmental parties such as chip

                                        manufacturers, vendors, and their

                                        employees for misconduct or





                    There are costs associated with the use of

               escrow agents.   But escrow agents might actually be

               profit-making entities,  competing on price, reliability, 

               security,  user-friendliness, or other features. For

               example, a software manufacturer  could provide its

               own escrow agency service  and build its availability

               (for a fee) into all new software releases.  Companies

               that have traditionally been in the escrow business

               (e.g., banks) might want to do this to expand their

               customer base and entice their clients into more on-

               line transactions, moving them slowly away from

               brick-and-mortar branches with relatively high

               transaction  costs.


               Legality of Superencryption


                    Escrow is not completely effective as a law

               enforcement tool unless superencryption is illegal. 

               The possibility of criminalizing encryption to which the

               government does not effectively hold the keys has

               been referred to obliquely by high government officials

               in the United States.  Indeed, there are already

               constraints on intracountry encryption in  France

               [Chandler 1994] and Russia [Yeltsin 1995].  This

               raises very important and difficult legal questions

               related to free speech and civil liberties [Froomkin

               1995].  Does one have free speech if one is compelled

               to utter the key?


               FUTURE WORK


                    The time has come to determine appropriate k

               and n, and appropriate operating rules for and mixes of

               escrow agents.  In addition, a serious public discussion

               of the following questions is necessary:  


                     1)  Does key escrow

                                        fundamentally change the

                                        social contract between

                                        citizens and their government?


                    2)   "How will we ... develop and

                                        maintain the balance among

                                        traditional 'national security'

                                        (and law enforcement)

                                        objectives and other aspects of

                                        the public interest, such as

                                        economic vitality, civil

                                        liberties, and open



                    3)   "What are the costs of government

                                        efforts to control cryptography and

                                        who will bear them?" [OTA 1995] 


                    4)   If society decides to mandate some

                                        form of encryption key escrow, which

                                        solution is the most desirable?


               One hopes that future work on this topic, including the 

               forthcoming National Academy of Sciences report 

               (expected in early 1996) will address these issues.




                    Several people have offered helpful comments

               on earlier versions of this paper.  I want to specifically

               thank Dorothy Denning, Carl Ellison, Ken

               Mendelsohn, Doug Miller, Ray Pickholtz, Marc

               Rotenberg, and Pamela Samuelson.   Responsibility for

               the ideas in the paper and the way I expressed them

               remain solely my own.




                      [Balenson 1994]   Balenson, D., Ellison C.,

                                                       Lipner, S., and Walker, S., "A

                                                       New Approach to Software

                                                       Key Escrow Encryption",

                                                       Trusted Information Systems,

                                                       Glenwood, Md., 1994

                                                       (reprinted in [Hoffman 1995]).


               [Baum 1994]         Baum, M. S., Federal

                                                  Certification Authority

                                                  Liability and Policy: Law and

                                                  Policy of Certificate-Based

                                                  Public Key and Digital

                                                  Signatures, NIST-GCR-94-

                                                  654, NTIS Document No.

                                                  PB94-191-202 (Springfield,

                                                  VA, National Technical

                                                  Information Service), 1994.


               [Benaloh 1986] Benaloh, J., "Secret Sharing

                                             Homomorphisms: Keeping

                                             Shares of a Secret Secret",

                                             Advances in Cryptography--

                                             Proceedings of Crypto '86,

                                             Springer-Verlag, 1986.


               [Bernstein 1994]    Bernstein, David S.,

                                                  "Encryption's International

                                                  Labyrinth", Infosecurity News,

                                                  January/February 1994

                                                  (reprinted in [Hoffman 1995]).


               [Beth 1994]         Beth, T. et al, "Clipper Repair

                                                  Kit - Towards Acceptable Key

                                                  Escrow Systems", Proc. 2nd

                                                  ACM Conf. on

                                                  Communication and Computer

                                                  Security, 1994.


               [Brickell 1993]     SKIPJACK Review: Interim

                                                  Report, July 28, 1993.  Posted

                                                  to the sci.crypt newsgroup on

                                                  August 1, 1993 by Dorothy



               [Chandler 1994]     Chandler, J., et al, Review and

                                                  Identification of Foreign Laws

                                                  and  Regulations, and Case

                                                  Laws pertaining to the use of

                                                  Commercial Encryption

                                                  Products for Voice and Data

                                                  Communications, January

                                                  1994, Martin Marietta report

                                                  no. K/DSRD/SUB/93-

                                                  RF105/2 (reprinted in [EPIC



               [Chaum 1988]   Chaum, D., C. Crepeau, and I.

                                             Damgard, Multi-Party

                                             Unconditionally Secure

                                             Protocols, in Proceedings of

                                             the 20th ACM Symposium of

                                             Theory of Computing,

                                             Association for Computing

                                             Machinery, New York, 1988,

                                             pp. 11-19.


               [Denning 1994] Denning, D. E., "The U. S.

                                             Key Escrow Encryption

                                             Technology", Computer


                                             Butterworth-Heinemann Ltd.,

                                             Linacre House, Jordan Hill,

                                             Oxford, OX2 8DP, UK, July

                                             1994, Vol. 17, No. 7

                                             (reprinted in [Hoffman 1995]).


               [Denning 1995] Denning, D. E. and Branstad,

                                             D. K., "A Taxonomy for Key

                                             Escrow Encryption Systems",

                                             January 23, 1995, to appear in

                                             Communications of the ACM.


               [Ellison 1995a]     Ellison, C., "Attempt vs.

                                                  Succeed", at


                                                  /html/avss.html, 1995.


               [Ellison 1995b]     Ellison, C., private

                                                  communication, June 27, 1995.


               [EPIC 1995]         1995 EPIC Cryptography and

                                                  Privacy Sourcebook,

                                                  Electronic Policy Information

                                                  Center, June 1995


               [Froomkin 1995]     Froomkin, A. Michael, "The

                                                  Metaphor is the Key:

                                                  Cryptography, the Clipper

                                                  Chip, and the Constitution",

                                                  143 University of

                                                  Pennsylvania Law Review 709

                                                  (1995) (an earlier version was

                                                  reprinted in part in [Hoffman



               [Garfinkel 1994]    Garfinkel, S., Pretty Good

                                                  Privacy, O'Reilly and

                                                  Associates, Sebastopol, CA,

                                                  December 1994.


               [Goldreich 1987]    Goldreich, O., S. Micali, and

                                                  A. Wigderson, How to Play

                                                  ANY Mental Game or A

                                                  Completeness Theorem for

                                                  Protocols with an Honest

                                                  Majority, Proc. 19th Annual

                                                  ACM Symposium. of Theory of

                                                  Computing, Association for

                                                  Computing Machinery, new

                                                  York, 1987, pp. 218-229.


               [Hardy 1955]        Hardy, T., "The Proper Legal

                                                  Regime for 'Cyberspace'",

                                                  University of Pittsburgh Law

                                                  Review 55, 4 (1995), pp. 993-



               [Hoffman 1995] Hoffman, Lance J. (Ed.),

                                             Building in Big Brother,

                                             Springer-Verlag, New York,

                                             NY, March 1995, pp. 489-506.


               [HR5199 1994]  H. R. 5199, 103rd Congress,

                                             2nd Session, "Encryption

                                             Standards and Procedures Act

                                             of 1994" (reprinted in

                                             [Hoffman 1995]).


               [Johnson 1993] Johnson, D. R. and K. A.

                                             Marks, "Mapping Electronic

                                             Data Communications onto

                                             Existing Legal Metaphors:

                                             Should We Let Our

                                             Conscience (and Our

                                             Contracts) Be Our Guide?",

                                             Villanova Law Review 38

                                             (1993), p 487ff.


               [Kilian 1994]       Kilian, J. and Leighton, T.,

                                                  Failsafe Key Escrow,

                                                  MIT/LCS/TR-636, Laboratory

                                                  for Computer Science,

                                                  Massachusetts Institute of

                                                  Technology, Cambridge, MA,

                                                  August 1994.


               [Levy 1994]         Levy, Steven, "The

                                                  Cypherpunks vs. Uncle Sam",

                                                  The New York Times

                                                  Magazine, June 12, 1994

                                                  (reprinted in [Hoffman 1995]).


               [Lipsky 1991]       Lipsky, A. B., "Deterring

                                                  Cartel Behavoir: Harmonizing

                                                  and Disharmonizing Problems

                                                  and Solutions, Antitrust Law

                                                  Journal 60, 2 (1991), 563-570.


               [Micali 1994]       Micali, S. and Ray Sidney, "A

                                                  Resilient Clipper-Like Key

                                                  Escrow System", MIT

                                                  Laboratory for Computer

                                                  Science, 8 November 1994.


               [NBS 1977]          National Bureau of Standards,

                                                  Data Encryption Standard,

                                                  Federal Information

                                                  Processing Standards

                                                  Publication 81, Government

                                                  Printing Office, Washington,

                                                  D. C., 1977.


               [OTA 1995]          U. S. Congress, Office of

                                                  Technology Assessment, Issue

                                                  Update on Information

                                                  Security and Privacy in

                                                  Network Environments, OTA-

                                                  BP-ITC-147, Washington, D.

                                                  C., U. S. Government Printing

                                                  Office, June 1995.


               [Orwell 1984]       Orwell, G., 1984, Penguin

                                                  Group, New York, 1984.


               [Perritt 1995]      Perritt, H. H., Jr., "Guidelines

                                                  for Private Key Escrow",

                                                  Electronic Frontier Foundation

                                                  draft, March 26, 1995.


               [Rabin 1989]        Rabin, T. and M. Ben-Or,

                                                  Verifiable Secret Sharing and

                                                  Multiparty Protocols with

                                                  Honest Majority, Proc. 21st

                                                  ACM Symposium of Theory of

                                                  Computing, Association for

                                                  Computing Machinery, New

                                                  York, 1989, pp. 73-85.


               [Rivest 1978]       Rivest, R. L., A. Shamir, and

                                                  L. Adleman, A method for

                                                  obtaining digital signatures and

                                                  public-key cryptosystems,

                                                  Communications of the ACM

                                                  21 (2): 120-126, February



               [Rotenberg 1995]    Rotenberg, M., Informal oral

                                                  remarks at the 1995 Privacy

                                                  and Cryptography Conference

                                                  sponsored by the Electronic

                                                  Privacy Information Center,

                                                  Washington, D. C., June 5,



               [Shamir 1979]       Shamir, A., How to Share a

                                                  Secret, Communications of the

                                                  ACM 22 (11): 612-613,

                                                  November 1979.


               [USCouncil 1994a]   U. S. Council for International

                                                  Business, Statement on

                                                  Business Requirements for

                                                  Encryption, October 10, 1994,

                                                  1212 Avenue of the Americas,

                                                  New York, N. Y.


               [USCouncil 1994b]   U. S. Council for International

                                                  Business, Statement on

                                                  Liability Issues and the U. S.

                                                  Administration's Encryption

                                                  Initiatives, November 2, 1994,

                                                  1212 Avenue of the Americas,

                                                  New York, N. Y.


               [Walker 1995]  Walker, S. T. et al.,

                                             Commercial Key Escrow:

                                             Something for Everyone, Now

                                             and for the Future, Report No.

                                             541, Trusted Information

                                             Systems, Glenwood, Md.,

                                             January 3, 1995.


               [Yeltsin 1995]      Edict #334 (April 3, 1995) of

                                                  the President of the Russian

                                                  Federation on measures to

                                                  observe legality in the area of

                                                  development, production,

                                                  implementation and operation

                                                  of encryption facilities, as well

                                                  as provision of services in the

                                                  area of data encryption,

                                                  Rossiyskaya Gazeta 68, April

                                                  6, 1995.


               [Zimmermann 1995]   Zimmermann, Philip R., The

                                                  Official PGP User's Guide,

                                                  MIT Press, Cambridge, MA,