##### ##### # # # # ## #### #### # # ### # # # # # # # # # # # # #### #### ##### # # ###### # # # # # # # # # # # # # # # ### ##### ###### # # #### #### ##### # ###### # # ##### #### ##### #### #### #### # #### # # # # # # # # # # # # # # # ###### # # # # # # # # # # # #### # ##### # # # # # # # # # # # # # # # # # # # # # # # # # # # # #### # #### #### #### ###### #### 3.1 Identification. 3.1.1 Computer Logins 3.1.2 Zero Knowledge Proof of Identity. 3.1.3 Schnorr Identification scheme. 3.1.4 Where are we? 3.1.5 Identification using symmetric algorithms 3.2 Signatures. 3.2.1 Signatures with symmetric information. 3.2.2 Signatures from public key systems. 3.2.3 Applications of Public Key Signatures. 3.2.3 Fingerprinting. 3.3 Secret Sharing 3.3.1 How not to do it. 3.3.2 Shamir's Threshold Schema. 3.3.3 Verifiable Secret Splitting. In this class we shall see how the cryptographic algorithms can be exploited to design protocols for identification, signatures, and secret sharing. 3.1 Identification. ----------------------- Here are a few situations in which Bob wants to be sure that the person he is talking to is who (s)he claims to be. 1. Bob is a computer and somebody logs in on account alice. 2. Bob is an automated Teller Machine and somebody enters Alice's bank card. 3. Bob is the automatic door opener of Alices house. In the good old days, identification was on the basis of what we now call `biometric parameters'; this simply meeans that people knew each other face to face and recognized the shape, the voice, etc. With the advent of computers and their unpersonal means of getting input, these good old methods have become obsolete. 3.1.1 Computer Logins ----------------------- Login procedures introduced the concept of recognizing somebody by a special secret, referred to as a password. The idea here is that Alice is given or makes up a private secret and she is supposed to tell it to nobody. Consequently, if somebody is able to tell Bob the secret, it must be Alice. This idea, being in wide use since the sixties, leaks from all sides, but the confidence it has is enormous. Secrets can be guessed, overheard, stolen, bought, beaten out, and moreover, with modern computers it is sometimes possible to try all possibilities by brute force. Then we should realize that, once Oscar has obtained Alice's secret, he is able to impersonate her COMPLETELY and even change the password and exclude Alice from her access! In most situations, however, identification by secret is the only possibility we have, so let us try to make the best of it. We have to solve the question how Bob can recognize the secret; of course it is possible that he has a copy, but then Alice isn't the only one to know it from the start!! Moreover, besides from stealing the secret from Alice, Oscar can then also steal it from Bob. In the UNIX world this was solved by using a one-way function f, shared by all computers and all users. When Alice changes her password to aaa, the system actually stores a' = f(aaa). When somebody logs in as alice and enters a password ppp, f is applied and f(ppp) is compared to the stored value a'. This guarantees Alice gets in when she uses the right password, but it makes stealing the value a' from Bob's files useless, as f(a') is different from a', so Oscar won't get in entering a'. We see a system emerging with three components: SHARED part for all users, here the function f. SECRET part for Alice, here her password aaa. PUBLIC part for Alice, here a', used for recognizing aaa. The UNIX solution solves the identification problem while using PUBLIC password files. However, severe problems remain unsolved and this solution is not suited for large scale secure applications. One problem is that Oscar can overhear Alice typing her password, and then may misrepresent himself. Sheet 8-2 shows Oscar operating a remote terminal service, but he logs all passwords and uses them to hack systems. You think this is far fetched, but it isn't. The bottom of the sheet shows a popular passtime with the Dutch maffia. They make cigaret machines that operate on bank cards; but they copy all the bank cards and log the PINs entered. Without checking, they give you cigarets (for free!!) but these cigarets do not only make you sick and smell badly, but they make you poor as well. 3.1.2 Zero Knowledge Proof of Identity. ----------------------------------------- The problem seems inevitable; if Alice must show her identity by showing a secret password, then Bob will know it also after the procedure... But wait: who said Alice will show the secret? All we need is that Alice demonstrates that she KNOWS the secret, and this can be demonstrated in other ways than by revealing it. We have seen that some calculations are intractible, but become tractible when some crucial information is known. For example, extracting a square root modulo a composit is feasible only when knowing the factors. Consequently, Alice could prove her knowledge of the factors by extracting square roots, i.e., by solving small arithmetic exercises. But who is going to prepare the test exercises? Alice? Suppose Alice says well, I know the root of this random number y, and the solution is x. Bob will verify that indeed x^2 = y, but he is not impressed because Alice may not have chosen a random y at all, but instead a random x and y as its square!! In fact, anybody can come up with A NUMBER for which he knows the root. Bob? Alice is giving away very precious resources if she is going to squareroot numbers of Bob's choice for him. In no time Bob may know the factors of n. Or otherwise Bob may have a few numbers he'd like to have the root for, and Alice is not here to provide Bob with free computing power! The solution for this is that Alice produces exercises in PAIRs. The pairs will be related in such a way that knowing ONE solution is nothing special, but knowing TWO solutions is equivalent to knowing Alice's secret. After giving Bob the pair, Bob challenges Alice to solve either the first or second exercise. If Alice does not know the secret, she has at most one solution and must fail with 50% probability. If she does know the secret she can respond to Bob's challenge. Because Alice reveals only one solution, Bob is unable to fake he is Alice afterwards! We shall now study the identification scheme of Fiat, Feige, and Shamir in detail. In this system Alice does not demonstrate the ability to extract roots modulo n, but she demonstrates her knowledge of a single root. So, the information is as follows: SHARED a large composite number n. SECRET for Alice: a random number a. PUBLIC for Alice: the number b = a^2. I first remark that Oscar, seeing n and b, is unable to compute a because square roots mod n are intractible. Even if he bribes all other users (sharing n) he gains nothing, because all he can get from the others is a series of numbers and their squares, but he could have computed as many numbers with squares as he likes! So anybody who knows a root of b must be Alice; observe that there are actually four keys matching this lock. The identification procedure: Step 1. Alice chooses a random number r, computes s = r^2. She sends Bob s. The sending of s is a claim to know both root(s) and root(s.b); indeed, knowing these two implies knowing a because root(s.b) / root(s) = root(b) = a. Let us take a while to look where we stand. Because Oscar doesn't know a, he cannot produce a pair for which he knows both answers! It would be easy for him, though, to produce a pair (s, s.b) for which he can root the first number: He computes s as the square of a random number, exactly like Alice, and is able to hand over root(s) BUT NOT root(s.b). It is likewise easy to produce a pair for which he can solve root(s.b): take random r and s=r^2/b. Then you know root(s.b) (namely, it is r) but you don't know root(s). So knowing BOTH answers is what Alice distinguishes from Oscar, but she is not going to GIVE BOTH in order to show!! Step 2: Bob tosses a coin and sends Alice the random bit 0/1. 0 means I want to see root(s), 1 means I want to see root(s.b). Step 3: Alice sends the required answer y, either r or r.a. Step 4: Bob verifies the correctness of the answer. Understandibly, Oscar, not knowing a, has (only) 50% chance of successfully misrepresenting himself as Alice; his chances are reduced further because Alice and Bob play this game, say, 20 times. Oscar has one chance in a million to succeed the protocol. What information about Alice's secret is gained by Bob? If he chooses challenge 0, he receives in step 3 a random number of which he knows the square; nothing special, as he may square as many random numbers as he wants. If he chooses challenge 1, he receives in step one the square of a random r, and in step 3 r.a. But he can also produce as many pairs with this property as he likes: take random y. compute s = y^2/b. Define r = y/a (Bob doesn't know a!!) and observe that r is a random number, y = r.a, and s = r^2. So Bob doesn't need Alice to prepare such pairs. So Bob learns NO INFORMATION he couldn't have computed without Alice! The consequences are two-fold. 1. Bob, nor anybody who heard the conversation, can misrepresent as Alice. To summarize the line of reasoning needed to see this: a. Successfully completing the protocol is equivalent to knowing the secret a. b. It is not possible to compute the secret a without Alice. c. All information revealed by Alice in the protocol could be computed without Alice. 2. Bob believes that he is talking with Alice, but has NO MEANS TO PROVE IT later, for example if his customer Alice complains somebody has been in her files/house/bank account. 3.1.3 Schnorr Identification scheme. -------------------------------------- The system by Schnorr generalizes the binary challenge to an integer one, thus allowing a very small success chance for Oscar in a single iteration of the prrotocol. SHARED: a large prime p and a generator alpha of Zp*. SECRET: random number a SHARED: beta = alpha^a. Oscar cannot compute a by himself because this is an instance of the discrete log problem. When Alice wants to identify herself to Bob: Step 1. Alice chooses a random r and computes gamma = alpha^r. Send gamma to Bob, claiming to know log(gamma.beta^i). Step 2: Bob chooses random integer i and sends i to Alice. Step 3: Alice sends y = r+i.a Step 4: Bob verifies that alpha^y = gamma.beta^i. Lemma 1: If Alice and Bob play the protocol correctly, Alice succeeds. [] Lemma 2: Anybody who knows the correct answer for TWO possible responses, i1 and i2, knows a. Proof. Suppose one knows y1 s.t. alpha^y1 = gamma.beta^i1 and y2 s.t. alpha^y2 = gamma.beta^i2. Then alpha^{y1-y2} = beta^{i1-i2}, so alpha^{(y1-y2)/(i1-i2)} = beta, and we find a = (y1-y2)/(i1-i2). [] Lemma 3: Even without a it is feasible to produce a gamma with known solution for a given challenge i0. Proof: Take y random, gamma = alpha^y / beta^i0, define r = y - i0.a. r is random, because y is random. Now we have gamma = alpha^r and alpha^y = gamma.beta^i0. [] So Bob cannot `prove' afterwards that he spoke with Alice by saying: look, she sent me this gamma, and when I challenged her i0 she gave me this y. It is not a proof, because such a protocol log is easily generated without knowing a. Another interesting scheme is the Guillou-Quisquater scheme. The shared system parameter is a public RSA key pair (n,e). Again Alice has a secret a, and her public is b = a^e; so she identifies herself by showing knowledge of an e-th root of her public. EXERCISE: give the protocol for convincing Bob of this knowledge. This schema can be used without a password file: it is self- identifying. The RSA function is not really one-way, because somebody (system administrator) may have the key d and can compute the e-th root of the string `Alice' as her password. 3.1.4 Where are we? --------------------- Alice and Bob use the new break-through in identificattion, the Zero Knowledge Proof... so Oscar will be forced to apply the new breakthrough-attacks! CHESSMASTER OSCAR. Oscar, a chess novice, invites Karpov and Kasparov for a game and beats one (or plays two draws). Oscar is actually a man in the middle, just communicating moves between K & K rather than playing. His chess successes inspire Oscar a way to defeat the interactive identification schemes. THE MAFFIA ATTACK. While Alice is having French fries at Oscar's, his companion Olga shops for some diamonds at Bob's jewelry. When Alice wants to pay, Oscar gives Olga the signal to move to the cash register and claim she is Alice. Alice uses her bank card to pay for the fries and identifies with the absolutely secure interactive identification protocol. But Oscar's terminal actually transmits her numbers of step 1 to Olga, who presents them to Bob. Olga and Oscar communicate Bob's challenge back to Alice and her answer to Bob. After a few rounds, Bob is absolutely sure he does talk with Alice; actually he does, but only Alice is not in front of him! It will be a surprise for Alice to receive her next bank slip; well, she had the fries for free! EXERCISE. Alice claims to Bob that she knows the factors of a large public composite. How can she convince Bob of her knowledge without giving him any information about the factors? EXERCISE. Alice claims for a PUBLIC RSA key (n,e) to know the secret exponent d. Same question. 3.1.5 Identification using symmetric algorithms ------------------------------------------------- Alice and Bob are too stingy to buy RSA capable hardware but want to invest only in cheap DES hardware. They both know one secret number, and want to recognize each other on basis of this number. It is not good for Alice to reveal her number straightaway; WHY??? Would she happen to speak not to Bob but to a traitor Oscar, she would enable Oscar to impersonate himself as Alice against the real Bob. In this situation, Alice and Bob treat the number as a DES key k. Bob will be convinced he is speaking with Alice in this way: 1. Bob sends a random number x to Alice. 2. Alice computes y = Ek(x) and sends it to Bob. 3. Bob compares y to Ek(x) and believes the Lady is Real if the results coincide. Alice becomes convinced of Bob's identity in a similar way. There is no risk for Alice when trying to prove herself to an intruder (Oscar), because encrypting a string for Oscar does not reveal her key. (Of course, Oscar may try the cubic root attack by Hellman, but this is not feasible if we use triple DES.) 3.2 Signatures. ------------------- Alice may want to sign a document electronically; the signature under a document is a piece of information added to it, which will allow everybody to verify that Alice has seen the information and consents with it. What we require: 1. Only Alice can produce the signature. 2. Bob and others can verify the validity of the signature. Signatures on paper documents are bound to the content because of being printed on the same medium (the paper) but because information can be cut and pasted freely, the binding must be ensured in another way: the signature is computed as a function of the message. 3.2.1 Signatures with symmetric information. ---------------------------------------------- Assume Alice wants to sign a message for Bob, and Alice and Bob share a symmetric (DES, 3DES, or IDEA) key k. This is how Alice signs the message M (and encrypts it at the same time). 1. Alice encrypts M as S = Ek(M) and sends it to Bob. 2. Bob decrypts S with key k and finds a message M. Because nobody but Bob and Alice know k, Bob is convinced that M came from Alice. Every method based on symmetric information has this same disadvantage: every computation possible for Alice is also possible for Bob. So, though Bob is convinced that the message came from Alice, he is never able to convince anybody that he got M from Alice; indeed Alice can later claim Bob made the signed message himself. 3.2.2 Signatures from public key systems. ------------------------------------------- What we need is Alice to have a secret (she is the only one to be able to sign, so she must have a computational treasure of some kind) and the others to have a piece of information matching that secret. In other words, a secret/public key pair. Indeed, signatures can be made using the RSA functions. Suppose Alice has an RSA key pair (n,e) and secret d; Alice will sign M by `decrypting' it: The signature of Alice on M is the value S = M^d. To verify that S is a valid signature under M, Bob computes S^e and compares with M. (Actually, it is not necessary to send both M and S, it is sufficient to send S alone.) EXISTENTIAL FORGERY. Oscar may take a number S, compute M = S^e and send it to Bob; Indeed, S is the signature under M, and it appears Oscar has forged a signature. However, Oscar has hardly any control over M, and the `message' will essentially be a random number. These existential forgeries are rendered harmless if we require that every message contains, say, 80 zero bits in specified positions in the middle of the number. Oscar's odds of hitting on a valid M are 1 in 2^80. There are other signature schemes, for example based on the ElGamal public key system. This signature scheme is the basis of the American DSS, Digital Signature Standard. 3.2.3 Applications of Public Key Signatures. ---------------------------------------------- THE ORIGINAL SIGNATURE APPLICATION In 1979 a nuclear test ban agreement between USA and USSR (does anybody still remember this country) was signed, and the agreement allowed each party to place a seismographic probe on the other's territory for verification; see Sheet 9-1. Of course, each party wanted to be sure that 1. the data received from `our' probe was not tampered by the dirty Yanks/Commies. 2. The probe these capitalist pigs/red thieves installed on our land does not pass through anything other than the seismo data agreed in the treaty. Because of requirement 2, classical encryption does not do the job. So each probe was equipped with a secret RSA key, of which both parties knew the public part. This allows verification of both the content (by the party where the probe is located) and the authenticity (by the party owning the probe). CERTIFICATES: DIGITAL PASSPORT To communicate, you need he public key of your partner, but where do you get it from? Perhaps Alice wants to send a message to Bob, but Oscar counterfeited the data bases so that Alice will get Oscar's public key and think it is Bob's. Some trusted agent will provide Alice and Bob with a KEY CERTIFICATEE: a signed message of the form C(Alice) = ( ID(Alice), v, s) where ID(Alice) = the relevant data for Alice v = the public key of Alice S = Signature of trusted agency on (ID(Alice),v). Alice and Bob initiate the communication by exchanging their key certificates. Perhaps Oscar can disrupt the exchange and cause the communication to be unsuccessful, but there is no way for him to forge a key certificate with a key different from the one certified for Bob. SOFTWARE VALIDATION. Bob gets some software from Alice but wants to make sure he has the original version, not a copy that could be tampered by Oscar to include viruses, Trojan horses, or logic bombs. So Alice will sign the software, and Bob can check the signature any time he is going to execute the software. Even if Oscar manges to replace the files in Bob's computer, he may be able to replace the program by a dangerous one, and he might be physically able to replace the signature by a signature of his own making as well; but he is not able to compute a signature matching the new program. CONTRACT SIGNING. Alice and Bob want to sign a mutually binding contract: they both compute a signature for the document and give it to each other. 3.2.3 Fingerprinting. ----------------------- The last two applications pose a problem, namely that the program or contract could be too large to be signed in one computation; indeed, RSA numbers are 1024 (or 2048) bits long, not a magabyte. QUESTION: How should longer messages be signed? It is not good to chop the document in blocks and sign each block separately. This ensures integrety of each block, but the blocks could be swapped, or some blocks can be removed and combined with blocks from other documents. In this situation we make use of a CRYPTOGRAPHIC HASH FUNCTION, which is a function H: B* --> B^k (for some fixed k), that is, it maps arbitrary length bit strings to strings of a fixed length. Instead of the contract or program, Alice signs its hash; so to sign M: 1. F := H(M) 2. S := Sig(F) (ie, F^d in the RSA case) 3. Send (M,S). Of course it is now no longer sufficient to send only the signature, because M cannot be computed from its fingerprint F. To verify the signature S for M: 1. Compute F = H(M) 2. Check that S is valid for F (ie, that S^e = F in the RSA case) Fingerprining is used extensively in modern communications and causes no safety risk if it is used well. In theory, Oscar gets some extra possibilities for forgery. We shall assume that the signature algorithm is one such that it is not possible to forge a signature S under the hash F directly. Observe that, because B* is a lot larger than B^k, H is many-to-one, that is, for each k-bit string there are many messages with that string as the fingerprint. Attack 1: Direct forgery, based on existential forgery of a signature. Oscar takes random string S, and takes F = S^e; we have seen that this yields a valid signature under the usually useless string F. He now tries to find a message M with H(M) = F. If successful, he has forged Alice' signature under M. DEFINITION: H is one-way if, given F, it is infeasible to compute an M with H(M) = F. Attack 2: Indirect forgery: Oscar receives some (presumably innocent) message (M,S) from Alice, and will try to find another message M' satisfying H(M') = H(M). If he succeeds, he has his lucky day because (M',S) is a forgery. DEFINITION: H is weakly collision free if, given M, it is intractible to find an M' != M with H(M') = H(M). EXERCISE: Does one-way imply weakly collision free or is it the other way around? What is needed to make a hash function one way? If Oscar launches a brute force attack (trying many random strings until one with the right fingerprint is found) the expected amount of work is 2^k. Assuming we require at least 10^24 steps to be necessary for an attack, we find that a fingerprint should contain at least 80 bits. Attack 3: The birthday attack. Oscar finds two messages M1 and M2 with the same fingerprint F, such that Alice agrees with M1. She signs, giving Oscar an S that is also a valid signature for M2!! DEFINITION: H is strongly collision free if it is unfeasible to compute M1 and M2 with H(M1) = H(M2). According to the Birthday Theorem, if we randomly draw from a set with N members, we see a duplication after approximately sqrt(N) draws. So, if we require again that at least 10^24 steps are necessary for a forgery, it requires at least 160 bit fingerprints to be secure against birthday attacks. EXERCISE: Show that if H is strongly collision-free, then H is also weakly collision-free and one-way. A popular fingerprint function is MD4, crunching any amout of data (in blocks of 512 bits) into a 128 bit fingerprint. MD4 is fast, software implementations hash at 1.4MB/s speeds. 3.3 Secret Sharing ---------------------- Sometimes a secret is simply too valuable to be given to any single person. Examples: 1. We need at least three American Generals to agree in order to launch any nuclear missile. 2. At least two bank employees must be present in order to open the bank vault. (This protects the bank against malicious employees, and any single employee against pressure from criminals.) 3. Access to escrowed keys must be possible only if at least two administrative agencies agree. (Actually most governments don't care anything about your privacy, but without this rule the escrow system willl not be accepted by the public.) Our model has a dealer holding the secret, and giving each participant a share; distribution over w shares is a procedure with input a secret k (from set K) and output S1 ... Sw from a share set S. The secret should be implied by knowing enough shares, but not by knowing too few. 3.3.1 How not to do it. ------------------------- SECRET CUTTING The dealer cuts the bitstring in w pieces; like to share a 168b 3DES key over three employees, we give 56b to each. This gives in practice SOME additional safety over giving each employee the entire key, but it is not what we want because knowing a subset of the shares IS very informative about k. Indeed, bribing two employees reduces the number of possible keys from 2^168 to 2^56. We would prefer to have PERFECT Secret Sharing: 1. (Reconstruction.) Given t shares, the secret can be computed. 2. (Perfect Conceal.) For any combination of t-1 shares, and any k in K, there is a value for the t-th share such that the t shares combine into k. THEOREM: Perfect secret sharing has each share at least as large as the entire secret: |S| >= |K|. WHO GIVES THE PROOF?? Proof: Given t-1 shares, the reconstruction function can be seen as a function from the last share to K, which, by 2., is surjective. [] SECRET SPLITTING Perfect sharing is obtained with the following scheme. 1. Make random bit strings R1 ... Rt-1. 2. Make shares: S1 = k + R1 S2 = R1 + R2 .. ....... St = R{t-1} (Here + is bitwise XOR.) S1 looks more valuable because it is the only one computed from the secret! But it is not true, and reconstruction is entirely symmetric: k = S1 + S2 + ... + St THEOREM: The scheme is a perfect secret sharing system. Proof. When combining ALL t shares, all random strings are eliminated (each occurs in two shares) and only k remains. If only S1..S{i-1},S{i+1}..St are given, every value k is still possible, namely for the value Si = S1 + .. + S{i-1} + S{i+1} + .. + St + k . [] Secret Splitting isn't very flexible, because it is a t-out-of-t scheme: we definitely need ALL shares to find the secret back. 3.3.2 Shamir's Threshold Schema. ---------------------------------- A general t-out-of-w scheme can be based on polynomial interpolation in a finite field; see Sheet 10-1. To see how Shamir's method works, recall that through each three points in the plane there is a unique (second-order) function of the form y = p(x) = ax^2 + bx + c. The method hides the secret in such a function by taking a and b random and c = k (so that k=p(0) ). A share is a point on the curve, i.e., a pair (x,p(x)). To reconstruct k from three shares, recall that three points determine the curve, hence k. To see it is concealing, recall that any TWO points can be supplemented with (0,k) for any k, and we still have a curve through it! DEFINITION: A (t-1)-degree polynomial is a function of the form p(x) = a0 + a1.x + ... + a{t-1}.x^{t-1}. (We deviate a bit from the usual because we allow the leading coefficient to be 0.) THEOREM: For t points (x1,y1) ... (xt,yt) with all xi different, there is a UNIQUE (t-1) degree polynomial through these points. Phase 1: Dealing phase for secret k. 1. Set a0 = k and choose random a1 through a{t-1} from Zp. 2. p is the polynomial p(x) = a0 + a1.x + ... a{t-1}.x^{t-1}. 3. Make the shares as (xi,p(xi)) using different xi != 0. Phase 2: Reconstruction. 1. Collect t shares. 2. Compute p(0). To be more precise, we use Lagrange interpolation; let t points (xi,yi) be given and consider the function a(x) = SUM_{j} [ yj . PROD_{k!=j} (xk - x)/(xk - xj) ] Observe that - a is a t-1 degree ploynomial. - for each xi, a(xi) = yi. And these imply that a and p are the same function, so the secret is a(0): k = SUM_j [ yj . PROD_{k!=j} xk/(xk-xj) ] . EXERCISE: Prove that the scheme is perfectly concealing. EXERCISE: A secret must be shared among Czechs and Slovaks in such a way that: - two Czechs and two Slovaks are sufficient for reconstruction; - one Czech and arbitrarily many Slovaks, or one Slovak with arbitrarily many Czechs cannot reconstruct. 3.3.3 Verifiable Secret Splitting. ----------------------------------- The assumption that the dealer is fair is justified in the applications of the bank vault and the missile launcher. But what about governments not wishing their citizens to have real privacy? They want them to hand over the secret keys of their communication so that their communication can be tapped for the purpose of law enforcement. To make the introduced safety risks politically acceptable, we may think of schemes where the citizen will share his secret over several government agencies, such that the key is only revealed if all agencies hand over the share. But then the real criminal will hand in bad shares because it is not really in his interest that the police will be able to get hard evidence of a crime being planned: when the prosecutors combine the shares they will find out, but that is too late! Is it possible to verify the validity of the shares without combining them rightaway? Of course this requires that the secret itself is something recognisable (if you see the k you can see it is the real thing). Here is a splitting method to do just that. 1. Alice makes up and publishes a public RSA key (n,e). Alice requests permission from a Key Distribution Center to use this key and have a key certificate for it. 2. The KDC requires Alice to share her secret key d over five Key Escrow Centers (KECs) first. 3. Alice computes five numbers d1...d5 with sum d and sends one number to each KEC. 4. The KDC will check the validity of the five shares: 4a. KDC selects random r and sends it to each KEC. 4b. KEC i computes si = r^di and sends it to KDC. 4c. KDC multiplies the five numbers si and finds s = r^{d1+d2+d3+d4+d5}. 4d. KDC compares s^e to r and accepts if they are equal. 5. Alice gets a certificate for public key (n,e). Upon a justice warrant against Alice, the center will hand the shares to the police to allow Alice to be wiretapped. EXERCISE: Show how the five centers can cooperate to decrypt a single message for Alice without reconstructing the key. Generalizations of the method allow Verifyable Sharing (i.e., t-out-of-w KECs can reconstruct) as well.