Flipping a Coin

Threshold SchemesEnd

Complexity and Cryptography
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
https://www-alg.ist.hokudai.ac.jp/∼thomas/COCRB/

Lecture 15: More Cryptographic Protocols

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone I
The coin flipping problem is the problem which initiated thewhole area (see M. Blum (1981)).

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone I
The coin flipping problem is the problem which initiated thewhole area (see M. Blum (1981)).
Blum described the scenario as follows. Suppose Alice and Bob
and are going to get a divorce. They already live in cities far
apart of each other and they don’t want to see each other again.
For deciding who will obtain the new car, they have agreed toflip a coin. Of course, they don’t like to make their choice, saychoosing head, and then hearing from the other end of thephone: “I am flipping the coin,. . . , the outcome is tail. I am sosorry for you.”Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone I
The coin flipping problem is the problem which initiated thewhole area (see M. Blum (1981)).
Blum described the scenario as follows. Suppose Alice and Bob
and are going to get a divorce. They already live in cities far
apart of each other and they don’t want to see each other again.
For deciding who will obtain the new car, they have agreed toflip a coin. Of course, they don’t like to make their choice, saychoosing head, and then hearing from the other end of thephone: “I am flipping the coin,. . . , the outcome is tail. I am sosorry for you.”So, we do not only have to realize the coin flip but also amethod for verifying its outcome by the other party.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone II

Question
How can we attack this problem?

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone II

Question
How can we attack this problem?

Let us have a look at the proposals made.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone II

Question
How can we attack this problem?

Let us have a look at the proposals made.
The first proposal was made by Blum and Micali.
Let X be a finite set of numbers containing as much evennumbers as odd ones, and let f : X → Y be a one-way function.
Furthermore, assume Alice and Bob have agreed to use f. Then,the following protocol is used.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone III
Proposal 1 (Blum/Micali)
Step 1: Alice chooses at random an element x ∈ X,
computes y = f(x) and sends y to Bob.
Step 2: Bob guesses whether or not x is even or odd andsends his guess to Alice.
Step 3: Alice tells Bob whether or not his guess was rightand proves her claim by sending x to Bob, too.
Step 4: Bob verifies Alice’s claim by computing f(x) andcomparing it to y.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone III
Proposal 1 (Blum/Micali)
Step 1: Alice chooses at random an element x ∈ X,
computes y = f(x) and sends y to Bob.
Step 2: Bob guesses whether or not x is even or odd andsends his guess to Alice.
Step 3: Alice tells Bob whether or not his guess was rightand proves her claim by sending x to Bob, too.
Step 4: Bob verifies Alice’s claim by computing f(x) andcomparing it to y.
At first glance, this protocol looks good. But we are alreadywarned. So, let us ask if a participant of this protocol can cheat.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone IV
We assume that f is indeed a one-way function. This is a goodplace to see why we have required one-way functions to be
injective. If not, there could be two numbers x and x 0 such thatx is even, x 0 is odd and f(x) = f(x 0 ).

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone IV
We assume that f is indeed a one-way function. This is a goodplace to see why we have required one-way functions to be
injective. If not, there could be two numbers x and x 0 such thatx is even, x 0 is odd and f(x) = f(x 0 ).
But still, the definition of one-way function does not imply that
we cannot compute that last bit of x. If we could, we alreadyhave to whole information needed.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone IV
We assume that f is indeed a one-way function. This is a goodplace to see why we have required one-way functions to be
injective. If not, there could be two numbers x and x 0 such thatx is even, x 0 is odd and f(x) = f(x 0 ).
But still, the definition of one-way function does not imply that
we cannot compute that last bit of x. If we could, we alreadyhave to whole information needed.
This is a subtle point. So, we cannot prove anything about the
protocol above.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone IV
We assume that f is indeed a one-way function. This is a goodplace to see why we have required one-way functions to be
injective. If not, there could be two numbers x and x 0 such thatx is even, x 0 is odd and f(x) = f(x 0 ).
But still, the definition of one-way function does not imply that
we cannot compute that last bit of x. If we could, we alreadyhave to whole information needed.
This is a subtle point. So, we cannot prove anything about the
protocol above.
Therefore, Blum (1981) proposed the following more advanced
Protocol CF for flipping a coin per telephone.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone V
Protocol CF
Step 1: Alice chooses two huge primes p and q sends their productn = pq to Bob.
Step 2: Bob chooses randomly a number s from {1, . . . , b n2 c}.
Furthermore, he computes z = s2 mod n and sends z to Alice.
Step 3: Alice computes the four discrete roots ±x and ±y of z modulo n.
Let x 0 be the smaller number of x mod n and −x mod n andlet y 0 be defined analogously.
Step 4: Alice looks for the smallest bit position i in which x 0 and y 0
differ. Then she guesses one of these numbers and communicatesher guess to Bob by telling him: “The ith bit of your number
is 0” and “The ith bit of your number is 1,” respectively.
Step 5: Bob tells Alice whether or not her guess was correct (if it wascorrect, she wins).
Step 6: Bob sends his number s to Alice.
Step 7: Alice tells Bob the factorization of n.
Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold Schemes

End

Example 1
Here we keep p and q small for being able to follow thecomputations.
(1) Alice chooses p = 5 and q = 13, and sends 65.
(2) Bob chooses 21, computes 51 ≡ 212 mod 65, and sends 51.
(3) Alice computes ±21 and ±31, chooses x 0 = 21 = 10101 andy 0 = 31 = 11111.
(4) She guesses “The ith bit of your number is 1.”(5) Bob tells her that she is wrong.
(6) Bob sends 21 to Alice.
(7) Alice sends 5 and 13 to Bob.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone VI

This protocol looks more complex than the previous one. It isalso not obvious whether or not it is correct and fair. Thus, wehave do to the following.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone VI

This protocol looks more complex than the previous one. It isalso not obvious whether or not it is correct and fair. Thus, wehave do to the following.
1

Analyze the Protocol CF carefully.

2

Check whether or not it is fair and secure.

3

Finding out whether or not it can be executed efficiently.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone VI

This protocol looks more complex than the previous one. It isalso not obvious whether or not it is correct and fair. Thus, wehave do to the following.
1

Analyze the Protocol CF carefully.

2

Check whether or not it is fair and secure.

3

Finding out whether or not it can be executed efficiently.

If Alice is making her guess randomly and if Bob is choosing
his number s indeed randomly from the set {1, . . . , b n2 c}, thenthe probability that Alice wins is clearly 1/2.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone VII

Furthermore, it is not a good idea for Bob not to choose his
number randomly (provided the protocol is executed
repeatedly), since a certain preference for some numbers would
offer Alice a possibility to possibly increase her chance of
winning.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone VII

Furthermore, it is not a good idea for Bob not to choose his
number randomly (provided the protocol is executed
repeatedly), since a certain preference for some numbers would
offer Alice a possibility to possibly increase her chance of
winning.
So, the most important question we have to study right here iswhether or not Bob can possibly cheat, if he is changing s after
having sent z to Alice.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone VII

Furthermore, it is not a good idea for Bob not to choose his
number randomly (provided the protocol is executed
repeatedly), since a certain preference for some numbers would
offer Alice a possibility to possibly increase her chance of
winning.
So, the most important question we have to study right here iswhether or not Bob can possibly cheat, if he is changing s after
having sent z to Alice.
In order to avoid being detected as cheater, Bob should possess
x 0 as well as y 0 .

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone VIII
Taking into account that(x 0 )2 ≡ z mod n(y 0 )2 ≡ z mod n , we get(x 0 )2 − (y 0 )2 ≡ 0 mod n .
Furthermore, we have x 0 . y 0 mod n. This clearly implies
x 0 − y 0 . 0 mod n. Additionally, it is not hard to see that we
also have x 0 + y 0 . 0 mod n. Thus, putting it all together we
directly arrive at(x 0 )2 − (y 0 )2 ≡ (x 0 − y 0 )(x 0 + y 0 ) ≡ 0 mod n .

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone VIII
Taking into account that(x 0 )2 ≡ z mod n(y 0 )2 ≡ z mod n , we get(x 0 )2 − (y 0 )2 ≡ 0 mod n .
Furthermore, we have x 0 . y 0 mod n. This clearly implies
x 0 − y 0 . 0 mod n. Additionally, it is not hard to see that we
also have x 0 + y 0 . 0 mod n. Thus, putting it all together we
directly arrive at(x 0 )2 − (y 0 )2 ≡ (x 0 − y 0 )(x 0 + y 0 ) ≡ 0 mod n .
This is possible if and only if
gcd(n, x 0 + y 0 ) = p or
gcd(n, x 0 + y 0 ) = q .
Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone IX
Thus, if Bob is able to cheat he is able to factorize n, too.
Therefore, the security of our second protocol is based on the
difficulty to factorize. We summarize our knowledge by thefollowing theorem.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone IX
Thus, if Bob is able to cheat he is able to factorize n, too.
Therefore, the security of our second protocol is based on the
difficulty to factorize. We summarize our knowledge by thefollowing theorem.
Theorem 1
The Protocol CF is secure provided factoring is difficult.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone IX
Thus, if Bob is able to cheat he is able to factorize n, too.
Therefore, the security of our second protocol is based on the
difficulty to factorize. We summarize our knowledge by thefollowing theorem.
Theorem 1
The Protocol CF is secure provided factoring is difficult.
We have elaborated this point here in some more detail, since italso shows why Alice is sending just one bit in Step 4 and not x 0
or y 0 .
So, it remains to show that the protocol can be executed
efficiently.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone X
Since Alice is knowing the factorization of n, it suffices to argue
that Alice can efficiently compute discrete square roots modulo
a prime. Again, we refer to Lecture 5, where we studied
Berlekamp’s (1970) procedure for taking discrete square roots
modulo a prime. This algorithm is a Las Vegas method and has
an expected running time that is polynomially bounded in thelength of the input a and the modulus p.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone X
Since Alice is knowing the factorization of n, it suffices to argue
that Alice can efficiently compute discrete square roots modulo
a prime. Again, we refer to Lecture 5, where we studied
Berlekamp’s (1970) procedure for taking discrete square roots
modulo a prime. This algorithm is a Las Vegas method and has
an expected running time that is polynomially bounded in thelength of the input a and the modulus p.
So, the whole Protocol CF relies on the assumption thatfactoring is difficult.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Flipping a Coin per Telephone X
Since Alice is knowing the factorization of n, it suffices to argue
that Alice can efficiently compute discrete square roots modulo
a prime. Again, we refer to Lecture 5, where we studied
Berlekamp’s (1970) procedure for taking discrete square roots
modulo a prime. This algorithm is a Las Vegas method and has
an expected running time that is polynomially bounded in thelength of the input a and the modulus p.
So, the whole Protocol CF relies on the assumption thatfactoring is difficult.
Next, we look at another problem of high practical relevance,i.e., how to share a secret.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes I

The problem we want to consider goes back to Liu (1968) who
stated it as follows.
Eleven scientists are working on a secret project. They wish
to lock up the documents in a cabinet so that the cabinet canbe opened if and only if six or more of the scientists arepresent. What is the smallest number of keys to the locks
each scientists must carry?

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes I

The problem we want to consider goes back to Liu (1968) who
stated it as follows.
Eleven scientists are working on a secret project. They wish
to lock up the documents in a cabinet so that the cabinet canbe opened if and only if six or more of the scientists arepresent. What is the smallest number of keys to the locks
each scientists must carry?
Shamir (1979) showed that the smallest solution comprises 462
locks at all and 252 keys per scientist.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes II
Let us assume that all keys and all locks have numbers printed
on them. The locks are numbered by pairwise different
numbers, and without loss of generality we shall assume thatthey are numbered ` = 1, . . . , n.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes II
Let us assume that all keys and all locks have numbers printed
on them. The locks are numbered by pairwise different
numbers, and without loss of generality we shall assume thatthey are numbered ` = 1, . . . , n.
A key with number ` can open the lock with number m if andonly if ` = m.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes II
Let us assume that all keys and all locks have numbers printed
on them. The locks are numbered by pairwise different
numbers, and without loss of generality we shall assume thatthey are numbered ` = 1, . . . , n.
A key with number ` can open the lock with number m if andonly if ` = m.
Now, one can show:
Claim 1. The smallest number of locks needed issmallest number of keys needed is n−1
k−1 .

Complexity and Cryptography

n
k−1



and thec Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes II
Let us assume that all keys and all locks have numbers printed
on them. The locks are numbered by pairwise different
numbers, and without loss of generality we shall assume thatthey are numbered ` = 1, . . . , n.
A key with number ` can open the lock with number m if andonly if ` = m.
Now, one can show:
Claim 1. The smallest number of locks needed issmallest number of keys needed is n−1
k−1 .

n
k−1



and theThe proof can be found in the script.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes III
Furthermore, it should be mentioned that n
k becomes
maximal for k = n/2, if n is even, and for k = (n + 1)/2, if k isnodd. Moreover, n/2= O(4n/2 ), and thus it grows
exponentially in n.
Thus, a (k, n) threshold scheme, for being practically applicable,
has to give up the intuitive appealing idea of locks and keys.
Instead, we shall look for different possibilities to share a secret.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes III
Furthermore, it should be mentioned that n
k becomes
maximal for k = n/2, if n is even, and for k = (n + 1)/2, if k isnodd. Moreover, n/2= O(4n/2 ), and thus it grows
exponentially in n.
Thus, a (k, n) threshold scheme, for being practically applicable,
has to give up the intuitive appealing idea of locks and keys.
Instead, we shall look for different possibilities to share a secret.
For doing this, let us first give the general definition of a sharedsecret and of a (k, n) threshold scheme given by Shamir (1978).
Assume we have n persons P1 , . . . , Pn and a secret datum D
which we want to divide into n pieces D1 , D2 , . . . , Dn .

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes IV
Definition 2
We say that n participants k-divide a secret, where 1 < k 6 nprovided the following 3 conditions are satisifed.
(1) Each participant Pi possesses an information Di which is
not known to any other participant Pj , i , j for
j ∈ {1, . . . , n}.
(2) The knowledge of any k or more of the D1 , D2 , . . . , Dnpieces allows us to compute the whole datum D easily,(3) the knowledge of any k − 1 or fewer D1 , D2 , . . . , Dn pieces
leaves D completely undetermined.
A set {D1 , . . . , Dn } satisfying (2) and (3) is said to be a (k, n)
threshold scheme.
Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes V
The pieces Di of information are referred to as a share. The
example at the beginning of this chapter provides at least
evidence that (k, n) threshold schemes can be realized.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes V
The pieces Di of information are referred to as a share. The
example at the beginning of this chapter provides at least
evidence that (k, n) threshold schemes can be realized.
However, while the idea of using locks is intuitively appealing
we still have to outline how to simulate them by appropriately
chosen problems that meet the wanted complexity theoretic
requirements in Items (2) and (3). Furthermore, we aim to finda simulation such that the the number of simulated “locks”
does no longer grow exponentially.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes V
The pieces Di of information are referred to as a share. The
example at the beginning of this chapter provides at least
evidence that (k, n) threshold schemes can be realized.
However, while the idea of using locks is intuitively appealing
we still have to outline how to simulate them by appropriately
chosen problems that meet the wanted complexity theoretic
requirements in Items (2) and (3). Furthermore, we aim to finda simulation such that the the number of simulated “locks”
does no longer grow exponentially.
The following construction is based on Mignotte’s thresholdsequences.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes VI
A sequence m1 < · · · < mn of pairwise relatively prime andpositive numbers is said to be a (k, n) threshold sequence if
m1 · m2 · · · · · mk > mn · mn−1 · · · · · mn−k+2Complexity and Cryptography(A)c Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes VI
A sequence m1 < · · · < mn of pairwise relatively prime andpositive numbers is said to be a (k, n) threshold sequence if
m1 · m2 · · · · · mk > mn · mn−1 · · · · · mn−k+2(A)

Now, suppose, we have a (k, n) threshold sequence. We set
M = m1 · m2 · · · · · mk , andN = mn · mn−1 · · · · · mn−k+2 .
The secret is then any number D satisfying N 6 D 6 M. Now,
the pieces for each participant are defined by
Di = D mod mi ,that is, Pi obtains Di and nothing else, i = 1, . . . , n.
Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes VII
Thus, Condition (1) of Definition 2 is fulfilled by construction.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes VII
Thus, Condition (1) of Definition 2 is fulfilled by construction.
Claim 1. Condition (2) is satisfied.
Proof. Let Di1 , . . . , Dik be any subset of k elements from{D1 , . . . , Dn }. By the Chinese remainder theorem, the systemi ∈ {i1 , . . . , ik }b modulo Qk mi .
has a uniquely determined solution D
j=1
jx ≡ DiComplexity and Cryptography

mod mi ,c Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes VII
Thus, Condition (1) of Definition 2 is fulfilled by construction.
Claim 1. Condition (2) is satisfied.
Proof. Let Di1 , . . . , Dik be any subset of k elements from{D1 , . . . , Dn }. By the Chinese remainder theorem, the systemi ∈ {i1 , . . . , ik }b modulo Qk mi .
has a uniquely determined solution D
j=1
j
By the definition of a (k, n) threshold sequence and the choiceof D we obtainkY
D 6 M = m1 · m2 · · · · · mk 6
mij .
x ≡ Dimod mi ,j=1

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes VII
Thus, Condition (1) of Definition 2 is fulfilled by construction.
Claim 1. Condition (2) is satisfied.
Proof. Let Di1 , . . . , Dik be any subset of k elements from{D1 , . . . , Dn }. By the Chinese remainder theorem, the systemi ∈ {i1 , . . . , ik }b modulo Qk mi .
has a uniquely determined solution D
j=1
j
By the definition of a (k, n) threshold sequence and the choiceof D we obtainkY
D 6 M = m1 · m2 · · · · · mk 6
mij .
x ≡ Dimod mi ,j=1

b ≡ Di ≡ D mod mi for all i ∈ {i1 , . . . , ik }, we see that
Since Dany k participants of the secret sharing scheme can compute thesecret datum D. This proves (2).
Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes VIII
Claim 2. Condition (3) is satisfied.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes VIII
Claim 2. Condition (3) is satisfied.
Proof. Let {Di1 , . . . , Dik−1 } be any subset of k − 1 elements from{D1 , . . . , Dn }. Again, we may apply the Chinese remainder
theorem, and obtainb = ei · Di + · · · + ei · Di
D
mod
1
1
k−1
k−1

k−1
Y

mij

(1)

j=1

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes VIII
Claim 2. Condition (3) is satisfied.
Proof. Let {Di1 , . . . , Dik−1 } be any subset of k − 1 elements from{D1 , . . . , Dn }. Again, we may apply the Chinese remainder
theorem, and obtainb = ei · Di + · · · + ei · Di
D
mod
1
1
k−1
k−1

k−1
Y

mij

(1)

j=1

Obviously, (1) is the congruence containing all information wehave. Nevertheless, (1) leaves many possibilities for D.
Therefore, we continue by estimating the number ofpossibilities.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes IX
The biggest product of k − 1 numbers chosen from {m1 , . . . , mn }is N. The smallest product of k numbers chosen from
{m1 , . . . , mn } is M.
b mod mi for all i ∈ {i1 , . . . , ik−1 }, we also haveSince D ≡ D
b mod
D≡D

k−1
Y

mij ,

j=1

(remember that the numbers mi , i ∈ {1, . . . , n} are relatively
b differ by a multiple of Qk−1 mi .
prime), i.e., D and D
j=1
jConsequently, one can try all
b+
D=D

k−1
Y
j=1

Complexity and Cryptography

mij ,

b +2·
D=D

k−1
Y

mij , . . . ,j=1
c Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes X

This gives a lower bound of
M−N−1Nmany possibilities. Of course, the true value of D can be only
determined, if one has an oracle for testing these possibilities.
For example, it is well imaginable that one has only 3 trials totest D (like passwords).

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes X

This gives a lower bound of
M−N−1Nmany possibilities. Of course, the true value of D can be only
determined, if one has an oracle for testing these possibilities.
For example, it is well imaginable that one has only 3 trials totest D (like passwords).
Thus, it remains to show that one can always choose (k, n)
threshold sequences in a way such that (M − N − 1)/N is large.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes XI
Let π(x) be the number of all primes less than or equal to x.
The prime number theorem is telling us thatx
5 x
< π(x) < ·ln x
4 ln xfor all x > 114 ,i.e., there is constant c such that
π(x) 6 c ·Complexity and Cryptography

x
.
log x

c Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes XI
Let π(x) be the number of all primes less than or equal to x.
The prime number theorem is telling us thatx
5 x
< π(x) < ·ln x
4 ln xfor all x > 114 ,i.e., there is constant c such that
π(x) 6 c ·

x
.
log x

Now, let π(n, α) be the number of all primes in the interval(pαn , pn ), where pn is the n-th prime number and α ∈ (0, 1).
Then, we can show the following lemma.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes XII
Lemma 1
Let n ∈ N with n > 2. For every k with 2 6 k 6 n there arearbitrarily big numbers y such thatk2 − 1>n.
π y,k2Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes XII
Lemma 1
Let n ∈ N with n > 2. For every k with 2 6 k 6 n there arearbitrarily big numbers y such thatk2 − 1>n.
π y,k2
Before proving the lemma, we show how to get the desired
result from it.
2
We choose y such that π(y, kk−1
2 ) > n. That is, in the interval(k2 −1)/k2(py, py ]

there are at least n prime numbers. Let m1 , . . . , mn be the first nprimes in this interval.
Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes XIII
Claim. m1 , . . . , mn form a (k, n) threshold sequence.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes XIII
Claim. m1 , . . . , mn form a (k, n) threshold sequence.
The condition m1 < m2 < · · · < mn is obvious. Moreover,
M=

k
Y

mi >

mk
1

 k2 −1 k
2
> pyk

i=1
(k+1)(k−1)
k= py> pk−1y> mn · mn−1 · · · · · mn−k+2 = N ,where the last inequality holds, since mn 6 py and thusmk−1
6 pk−1ny . This proves the claim.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes XIV
Finally, we obtain
k2 −1

k−1
py k − pk−1
M−N
y
k
>
=
p
−1.
y
N
pk−1
y

Consequently, one can start with a lower bound B for(M − N − 1)/N. Then one searches for pz such thatk−1

pz k − 1 > B .
By the lemma above, then there exists a y > z such that one canform the wanted (k, n)-threshold sequence from m1 , . . . , mn .

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes XV
Finally, we have to show Lemma 1 above.
Let k, n be arbitrarily fixed, and let α ∈ (0, 1). By the prime
number theorem we know that pm = O(m log m). Hence,ααpαm = O(m (log m) ). Furthermore,
π(m, α) = π(pm ) − π(pαm) .
We choose c1 such that π(pm ) > c1 m and c2 such thatπ(pαm ) 6 c2 ·= c2 ·

Complexity and Cryptographymα (log m)αmα (log m)α6c·2log(mα (log m)α )log mαmα (log m)α.
α · log mc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes XV
Finally, we have to show Lemma 1 above.
Let k, n be arbitrarily fixed, and let α ∈ (0, 1). By the prime
number theorem we know that pm = O(m log m). Hence,ααpαm = O(m (log m) ). Furthermore,
π(m, α) = π(pm ) − π(pαm) .
We choose c1 such that π(pm ) > c1 m and c2 such thatπ(pαm ) 6 c2 ·= c2 ·mα (log m)αmα (log m)α6c·2log(mα (log m)α )log mαmα (log m)α.
α · log mThus, we obtain:
Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes XVI
m log mmα (log m)α− c2 ·log m
α · log mm log m mα (log m)α
c
−
log m
α · log mmα (log m)αc
m log m −
log m
α


c · m log m
1
1−
log m
α · m1−α (log m)1−α1
c·m 1−
α · m1−α (log m)1−α|{z}π(m, α) = π(pm ) − π(pαm ) > c1 ·
>
=
=
=

=:X

The expression X converges to 1 as m tends to infinity.
Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes XVIIConsequently, for all sufficiently large values of m we see thatπ(m, α) > n.
Thus, setting α = (k2 − 1)/k2 , the lemma follows.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Threshold Schemes XVIIConsequently, for all sufficiently large values of m we see thatπ(m, α) > n.
Thus, setting α = (k2 − 1)/k2 , the lemma follows.
So, for threshold schemes we were able to prove a verysatisfactory result.

Complexity and Cryptographyc Thomas Zeugmann

Flipping a Coin

Threshold SchemesEnd

Thank you!

Complexity and Cryptographyc Thomas Zeugmann