Transcript Elliptic Curves - University of Rochester

Manipulating
Encrypted
Data
You store your data in the cloud, encrypted of course.
You want to use the computing power
of the cloud to analyze your data.
But you want to keep the data encrypted.
Basic Question: Is it possible to compute with
encrypted data without first decrypting?
One Goal:
Design an encryption method EK and a decryption
method DK (K is the key) with the following property:
If f is some function (algorithm), then we can find
a function F, independent of K, such that
for every message m :
f(m) = DK( F(EK(m)))
This means that if we want to compute f(m),
we can encrypt m, then F is applied to the
encrypted message, then we decrypt.
This has been done, in theory, by Gentry (homomorphic encryption)
M=message
f=function
E=encryption
D=decryption
E(M)
F(E(M))
E
D
f
M
f(M)
Cheating the IRS
Search
About 1,330,000 results (0.28 seconds)
Cheating on Your Taxes
www.thecheatfactory.com/taxes.html
Read these tips to find some smart, under the radar, and legal ways
to cheat on your taxes. The IRS has been screwing you for long enough.
It's time to turn the …
Tax Fraud Penalties - Cheating On Taxes - Esquire
www.esquire.com/the-side/feature/tax-deductions-032009
Apr 18, 2011 – ... in on five ways to hypothetically bend the law
and cheat on your taxes. ... When the IRS comes a-knocking you're
guilty until you can prove ...
Cheating the IRS
Encrypt
Fhrah$5&&$$$$$123mNmErTIoppYtEQCCV9&T
Fhrah$5&&$$$$$123mNmErTIoppYtEQCCV9&T
Nxvs$%432MnUiiOPlTRttyR^%$^&IHKVGRYGKNjkjkJ
6T%%$3CvDrk$65IhkU%eksaggYGFMVKHFkhvyrkGKJk
HcjgkllJkknlkGKknljlJllniy89^y;jTYNffsd9u123npih;xkn;k
gihHIH:KH;khj;;J;J;LSJRKN;N;KNHJSJ;;l;vrjpsihtihlhlkjU
dhstuhgerkekfklxkgh;knklHOlkn^(*^&$&%$OIHpj45ihkh
gfklxkgh;knklHOlkn^(*&885^%$OIHpj45ihkh;d;knfae,npih;x
kn;kgihHIH:KH;khj;;J;J;LSJRKN;N;KNHJSJ;;l;vrjpsihtihlh
gkfdhstuhgerkekgeksaggYGFMVKHFkhvyrkGKJkg,
gfklxkgh;knklHOlkn^(*^&$&%$OIHTYVbnmT**7%nBBnnHtFr
……
……
DECRYPT
Cheating the IRS
Search
About 1,330,000 results (0.28 seconds)
Cheating on Your Taxes
www.thecheatfactory.com/taxes.html
Read these tips to find some smart, under the radar, and legal ways
to cheat on your taxes. The IRS has been screwing you for long enough.
It's time to turn the …
Tax Fraud Penalties - Cheating On Taxes - Esquire
www.esquire.com/the-side/feature/tax-deductions-032009
Apr 18, 2011 – ... in on five ways to hypothetically bend the law
and cheat on your taxes. ... When the IRS comes a-knocking you're
guilty until you can prove ...
Cheating hte IRS
Encrypt
h&&$%#@$123mNmrah$5ErTIoppYtEQMMYfr
h&&$%#@$123mNmrah$5ErTIoppYtEQMMYfr
W#$RrDqPlOiuYuIgn^Tpihk;k^%$^&IHKVGRYGKNjkjkJ
Fjklk$65IhkU%eksaggYGFMVKHFkhvyrkGKJkg,nvkvtbvv
HcjgkllJkknlkGKknljlJllniy89^y;jTYNffsd9u123npih;xkn;k
gihHIH:KH;khj;;J;J;LSJRKN;N;KNHJSJ;;l;vrjpsihtihlhgkf
dhstuhgerkekfklxkgh;knklHOlkn^(*^&$&%$OIHpj45ihkh
gfklxkgh;knklHOlkn^(*^&$&%$OIHpj45ihkh;d;knfae,npih;x
kn;kgihHIH:KH;khj;;J;J;LSJRKN;N;KNHJSJ;;l;vrjpsihtihlh
gkfdhstuhgerkekgeksaggYGFMVKHFkhvyrkGKJkg,
nvkvtbvvgfklxkgh;knklHOlkn^(*^&$&%$OIHTYVbnmTbCfT$#w
……
……
Cheating hte IRS
Search
About 1,330,000 results (0.28 seconds)
Did you mean cheating the IRS
Search instead for cheating hte IRS
Cheating on Your Taxes
www.thecheatfactory.com/taxes.html
Read these tips to find some smart, under the radar, and legal ways
to cheat on your taxes. The IRS has been screwing you for long enough.
It's time to turn the …
Tax Fraud Penalties - Cheating On Taxes - Esquire
www.esquire.com/the-side/feature/tax-deductions-032009
Apr 18, 2011 – ... in on five ways to hypothetically bend the law
and cheat on your taxes. ... When the IRS comes a-knocking you're
guilty until you can prove ...
Somewhat Homomorphic Encryption (SWHE)
This will allow several additions and subtractions
but only a few multiplications.
Secret key is a large odd integer p.
We want to encrypt a bit m, where m = 0 or 1.
Choose a random integer r (much smaller than p)
and another integer s and let the ciphertext be
c = m + 2r + ps
To decrypt (i.e., recover m), compute
m = c (mod p) (mod 2)
We can add ciphertexts:
c1 = m1 + 2r1 + ps1
c2 = m2 + 2r2 + ps2
Then c1 + c2 decrypts to m1 + m2
Products:
c1c2 = m1m2 + 2(m1r2+m2r1+r1r2) + p(- - - - - - )
This decrypts to m1m2 if r1r2 is not too big.
Think of this as the encryption of m1m2 plus some noise.
If we do too many multiplications, the noise increases enough
that decryption fails.
If we compute by a series of bit operations f1, f2, f3 :
E(M)
M
E(f1(M))+noise
f1(M)
E(f2f1(M))+NOISE
f2f1(M)
E(f3f2f1(M))+NOISE
f3f2f1(M)
Bootstrapping (Craig Gentry, 2008)
E(M)||E(K)
E(f(M))+noise||E(K)
M||K
E(E(f(M))+noise ||E(K))
f(M)||K
E(E(f(M))+noise ||E(K))
E(f(M)) + noise
D
E(f(M))+noise||E(K)
f(M)
The noise has been reduced, so we can continue.
Bootstrapping can sometimes change a
Somewhat Homomorphic system into
a Fully Homomorphic system.
Are Fully Homomorphic Sytems practical?
Not yet.
A similar idea that is practical is
Secure Multiparty Computation
But first, a digression . . .
You are the manager of a bank.
You want to allow your employees to open the safe.
Requirements:
1. One person alone cannot open the safe.
2. Any two people can open the safe.
Two
People
determine a
Secret
Two
Points
determine a
Line
The secret combination to the lock is
ab
cd
ef
For example, the combination could be
14
15
03
Let B = abcdef mod p
where p is prime.
Choose a random M
We now have a line
y = Mx + B (mod p)
For example, if the combination is
14 – 15 – 03,
then
B = 141503.
We could randomly choose
M = 3456789.
The line is
y = 141503 + 3456789 x
If there are 30 people, compute 30 points
on the line y = Mx + B :
(1, M+B),
(2, 2M+B),
(3, 3M+B),
.
.
.
(30, 30M+B)
Give each
person one
point.
Summary: Someone shares a secret B
by choosing a random integer m and forming
the linear function f(x) = B+mx.
f(1)=B+m is given to person 1
f(2)=B+2m is given to person 2
f(3)=B+3m is given to person 3
These numbers are their “shares” of the secret.
Any two people can determine B.
Arithmetic Operations on Secrets
We can add secrets:
P1, P2, P3 have shares of f(0) and of g(0).
P1 adds f(1) + g(1), P2 adds f(2) + g(2), P3 adds f(3) + g(3)
They now share f(0) + g(0)
Can We Multiply Secrets?
P1, P2, P3 share f(0) and share g(0).
They want to share f(0) g(0).
Problem: f(x) g(x) is a quadratic polynomial,
so it takes three values to reconstruct it:
f(0) g(0) = 3f(1)g(1) – 3 f(2)g(2) + f(3)g(3)
So all three can recover the secret.
But “Sharing” requires that
2 people can reconstruct the secret.
How to Share Products:
(Gennaro, Rabin, Rabin)
Person 1 shares f(1)g(1)
Person 2 shares f(2)g(2)
Person 3 shares f(3)g(3)
(i.e., gives shares to 1, 2, 3)
Each person computes
Shareprod =3(Share received from 1) – 3(Share from 2) + (Share from 3)
This is a share of f(0)g(0).
Why? The numbers Shareprod are the values at x=1, 2, 3 of
a linear function whose y-intercept is
3f(1)g(1) – 3f(2)g(2) + f(3)g(3) = f(0)g(0)
Bit operations
Let a and b be bits (0 or 1). Then
a
(
b = a + b – 2ab
denotes addition mod 2)
If P1, P2, P3 share a and b, then
they can share a b
Suppose
a = a0 + 2a1 + 4a2 + …
and
b = b0 + 2b1 + 4b2 + …
A bit of a + b can be calculated via bit operations
such as
and multiplication (“and”)
If the bits of a and b are shared, then the
value of this bit is shared
Is d < s ?
s and d are shared numbers between 0 and 2n
Nobody knows s and d but we want to
determine which is larger.
Key idea: d < s if and only if the n-th bit of 2n + d –s is 0
SUGAR BEETS
Participants:
1200 Danish farmers
Danisco : the (only) Danish sugar beet processor
Danish cryptographers
Parameters
There are 4000 possible prices : Price1 < Price2 < . . . < Price4000
Farmeri is willing to sell si,k sugar beets at Pricek
Let sk = s1k + s2,k + . . . + s1200,k
Then sk is the supply at Pricek : s1 < s2 < . . . < s4000
Let dk be the amount Danisco is willing to buy at Pricek
d1 > d2 > . . . > d4000
Problem: Find k so that sk = dk
Constraint: No one wants to reveal their strategy
Solution:
There are three participants:
1. The farmers’ union
2. Danisco
3. The Danish cryptography group
For each Pricek, the Farmeri chooses a linear function fik(x) = sik + aikx
and sends fik(1) to P1, fik(2) to P2, fik(3) to P3. That is, the farmer shares sik
P1 adds up the numbers it receives. Similarly for P2 and P3.
They now have shares of each supply number s1, . . . , s4000
For Pricek, Danisco chooses a linear function
gk(x) = dk + ckx
and gives gk(1) to P1, gk(2) to P2, gk(3) to P3
Therefore, d1, d2, . . . , d4000 are shared
The 3 Participants determine whether s2000 < d2000.
No: Is s1000 < d1000 ?
Etc.
Yes: Is s3000 < d3000 ?
Etc.
They determine k such that sk = dk.
The 3 participants together reveal each
farmer’s supply amount sk for this price
(and only for this price).
This concludes the auction.
Number theory Interlude:
Let p be a prime and assume that p = 3 (mod 4).
Let x be a square mod p and let
y = x(p+1)/4 (mod p).
Then y2 = x (mod p).
Example: Let p = 19. Let x = 17 = -2 (mod 19).
Compute x(19+1)/4 = (-2)5 = -32 = 6 (mod 19).
Check:
62 = 17 (mod 19)
Flipping a Coin without Knowing the Result
(Sharing a Random Bit)
P1 chooses a random number b1 and shares b1
P2 chooses a random number b2 and shares b2
P3 chooses a random number b3 and shares b3
Each person adds together the shares received.
Let b = b1 + b2 + b3
They now have shares of b (but they do not know b )
This means: there is a linear function f(x) = b + ax and
P1 knows f(1),
P2 knows f(2), P3 knows f(3)
Construct shared random bits b0, b1, . . . , bn+k
Share
R = b0 + 2b1 + . . . + 2n+kbn+k
Compute A = 2n+k+1 – R + 2n + d – s
= a0 + 2a1 + . . . + 2n+k+1an+k+1
A is originally shared, but it can revealed since s and d
are masked by R.
This allows us to compute the binary expansion of A.
Compute the shares of the nth bit of A + R
= 2n+k+1 + 2n + d – s
This can be done by a series of shared bit operations.
P1, P2, P3 together reveal this bit.
If the bit is 0 then s>d. If the bit is 1 then s < d.
Flipping a Coin without Knowing the Result
(Continued)
Recall: f(x) = b + ax and b = b1 + b2 + b3
P1 computes f(1)2 and tells P2 and P3 the result,
P2 computes f(2)2 and tells P1 and P3 the result,
P3 computes f(3)2 and tells P1 and P2 the result,
They compute 3f(1)2 – 3f(2)2 + f(3)2 = b2
They compute v = (b2) (p+1)/4 = +b or –b (mod p)
v-1 b = +1 or -1 (mod p)
The shares of b are v-1f(1), v-1f(2), v-1f(3)