##### ##### #
# # # ## #### #### # # ###
# # # # # # # #
# # # # #### #### #####
# # ###### # # # #
# # # # # # # # # # # ###
##### ###### # # #### #### ##### #
######
# # ##### #### ##### #### #### #### # ####
# # # # # # # # # # # # # # #
###### # # # # # # # # # # # ####
# ##### # # # # # # # # # #
# # # # # # # # # # # # # # #
# # # #### # #### #### #### ###### ####
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.