Secure Computation in the Age of Information
Secure Computation
(Lecture 1)
Arpita Patra
Welcome to an exciting Journey
>>
Course Homepage:
http://drona.csa.iisc.ernet.in/~arpita/SecureComputation15.html
>> References:
1.
Secure Multiparty Computation and Secret Sharing - An Information
Theoretic Approach – by Ronald Cramer, Ivan Damgaard and Jesper
Buus Nielsen
2.
Efficient Two-party Protocols- Techniques and Constructions- by Carmit
Hazay and Yehuda Lindell
3.
Recent papers and a few lecture notes
Evaluation Policy
>> Tuned to ensure that you learn and you enjoy the learning!
Scribe (18%):
Every student will have to scribe 2/3 lectures
Chalk & Talk Seminar (14*2 + 4 = 32%):
Every student will make two
presentations (one in each half of the course) and write a small blog on one
of her/his friend’s seminar.
Project (25 + 35 = 60%):
Two projects (midterm and end-term)
>> theoretical or practical in nature
>> theoretical projects will involve answering deep and exciting theoretical
questions
>> practical projects will involve implementing and improving challenging
practical secure computation tasks
>> Both project topics may be same. Complete literature survey and decide
on an exciting problem by midterm. Make non-trivial theoretical progress/
implement the best solution in the second half.
We are in the age of Information!
Information Everywhere:
>
Individual:
Age, Salary, Bank Details (balance, netbaking login password),
Citizenship, Parents/family member details, Identity details (passport no.,
PAN card, Voter ID, AADHAR id ), Income Tax Details, Your vehicle details
(cycle, two wheeler, car), Medical data: diseases, biometric traits (face,
fingerprint, iris, speech), genome signature, minimum age of watching
porn/taking drug, Child adoption details
>
Profitable Organization (MS/IBM/TCS/Infosys):
List of employees and
their details, Profit, loss, turnover, salaries.
>
Educational Organization (IISc/IITs/IIITs/IISERs/NISERs/NITs)
:
List of employees and their details, students and their details, awards,
recognitions, scientific publications, products, dropouts, drug addicts,
suicides, sexual harassments,
We are in the age of Information!
>
Security Agencies (RAW/ IB/ CBI/NIA):
List of employees and details,
list of criminals and details, list of incidents and details
>
Country:
List of citizens and details, prime minister, presidents, MLA,
MPs, celebrities, under-privileged. Satellites / Nuclear weapons /
Submarines information
…….
>
Military Organizations (Army/Air Force/Navy):
List of soldiers, colonels
and details, list of operations and details, intercepted messages and details
>
Hospitals:
List of patients and their medical history and details. List of
doctors, nurses and their details
Secret Information
> Individual:
Age, Salary
, Bank Details (
balance
, netbaking login
password
),
Identity details (passport no., PAN card, Voter ID, AADHAR id ), Income
Tax Details, Your vehicle details (cycle, two wheeler, car), Medical data:
diseases, biometric traits (face, fingerprint, iris, speech), genome signature,
minimum age of watching porn/taking drug, Child adoption details
> Profitable Organization (MS/IBM/TCS/Infosys):
List of employees and
their details, Profit, loss, turnover, salaries.
> Educational Organization (IISc/IITs/IIITs/IISERs/NISERs/NITs):
List of employees and
their details
, students and
their details
, awards,
recognitions, scientific publications, products,
dropouts, drug addicts,
suicides, sexual harassments,
Secret Information
> Security Agencies (RAW/ IB/ CBI/NIA):
List of employees and details,
list of criminals and details, list of incidents and details,
list of intercepted
messages
> Country: List of citizens and details, prime minister, presidents, MLA, MPs,
celebrities, under-privileged.
Satellites / Nuclear weapons / Submarines
information
…….
> Military Organizations (Army/Air Force/Navy): List of soldiers, colonels
and details, list of operations
and details
,
intercepted messages and details
> Hospitals: List of patients and
their medical history and details
. List of
doctors, nurses and
their details
Secret Communication
We know how to solve (Encryption schemes)
>> Not trivial to achieve the goal
>> But the purpose is simple to state and well-understood
Privacy Preserving Information Processing
(Computation)
Many scenarios that:
>> A large amount of added value can be obtained by combining
confidential information from several sources and from this computing
some result that holds an interest for all parties
>> demands data privacy and computation on the data at the same
time!
Preventing Satellite Collision in Space
Preventing Satellite Collision in Space
Preventing Satellite Collision in Space
•
NASA tracks
7,000
space crafts and
21,000
objects in
space
•
Approximately
20,00,00,000
pairs
Preventing Satellite Collision in Space
•
The 1996 collision between the French Cerise military
reconnaissance satellite and debris from Ariane rocket
•
T
h
e
2
0
0
9
c
o
l
l
i
s
i
o
n
b
e
t
w
e
e
n
t
h
e
I
r
i
d
i
u
m
3
3
c
o
m
m
u
n
i
c
a
t
i
o
n
s
s
a
t
e
l
l
i
t
e
a
n
d
t
h
e
d
e
r
e
l
i
c
t
R
u
s
s
i
a
n
K
o
s
m
o
s
2
2
5
1
s
p
a
c
e
c
r
a
f
t
o
v
e
r
S
i
b
e
r
i
a
,
w
h
i
c
h
r
e
s
u
l
t
e
d
i
n
t
h
e
d
e
s
t
r
u
c
t
i
o
n
o
f
b
o
t
h
s
a
t
e
l
l
i
t
e
s
•
The
22 May 2013
collision between Ecuador's NEE-01 Pegaso and
Argentina's CubeBug-1, and the particles of a debris cloud left over
from the launch of Kosmos 1666
List of High-speed Collisions:
•
On
Jan. 22, 2013
, debris from the destroyed Chinese satellite
Fengyun 1C collided with a small Russian laser-ranging retro-
reflector satellite called BLITS ("Ball Lens in The Space").Preventing Satellite Collision in Space
•
NASA tracks
7,000
space crafts and
21,000
objects in
space
•
Approximately
20,00,00,000
pairs
•
High-accuracy positional information
is privy to operators
National secret
•
High-accuracy positional information
Preventing Satellite Collision in Space
To date, there have been no observed collisions
between natural satellites of any Solar System
planet or moon.
(Secure) Electronic Auction
•
Nothing
other than the winner and winning bid should be
revealed
(Secure) Electronic Auction
•
Hospitals
do not
want to
share
their patient records
(Privacy Preserving) Data Mining
•
But want to
data-mine
on
combined
data
•
They
do not
want to
share
their count of sexual abuse cases/ drug
addicted cases
(Privacy Preserving) Data Mining
•
But want to
data-mine
on
combined
data
>> Secure Set Intersection
>> Secure Bench-marking
>> Secure/private information retrieval….
Many more applications..
There is something common among all the problems.
…can we find an abstraction?
Secure (Multiparty) Computation (MPC)
–
>> n
parties P
1
,....,P
n
Do not trust each other
>> A common n-input function
f
>> P
i
has private input
x
i
Goals:
>>
Correctness:
Compute f(x
1
,x
2
,..x
n
)
>>
Privacy:
Nothing about the
inputs of the parties should be
leaked
MPC is the holy grail: Abstracts all
that we have seen so far and many
more
>> Refined Privacy:
Nothing more
than function output should be
revealed
>> Consider f(x
1
,x
2
) = x
1
AND x
2
MPC is easy if we could trust someone
Any task
y = f(x
1
,x
2
,x
3
,x
4
)
Can we Trust Someone?
Any task
y = f(x
1
,x
2
,x
3
,x
4
)
Some problem in the
solution..
>> Creates a single point failure
>> Why we are doing secure
computation? Because of the
lack of trust. How suddenly we
will get someone who is cent
percent trusted?
>> Trust is a very rare, volatile.
>> If there is trust in the world
MPC
But there will be dis-trust in the world..
Because..
>> Without darkness, one cannot know light
>> Without hatred, one cannot feel love
>> Without war, one cannot realize the price peace
>> Without noise, one cannot appreciate serenity
>> Without distrust, one cannot value trust
The contrasts are the hallmarks of the great Magician!!
So we have to solve MPC without a trusted party..
>> But looks impossible. How is it possible to
compute f(x
1
,x
2
,x
3
,x
4
) without
anyone knowing all the inputs. So do we have to really trust someone..
Looks like we are stuck. Does the journey of secure computation end here?
Secure Addition and Voting
y = f(x
1
,x
2
,..,x
n
) = x
1
+
x
2
+
…
+
x
n
x
2
x
3
x
n
x
1
…
P
1
P
2
P
n
P
3
y
y
y
y
Secret Sharing
S
e
c
r
e
t
s
Dealer
Provides a way for a party, say P
1
to spread information about a secret x
across all the parties so that together they hold full information about x, yet
individual (or subset of parties) has no information about x
Secret Sharing
S
e
c
r
e
t
s
Dealer
s
1
s
2
s
3
s
n
…
S
e
c
r
e
t
s
Dealer
v
1
v
2
v
3
v
n
…
Secret Sharing
S
e
c
r
e
t
s
Dealer
s
1
s
2
s
3
s
n
…
Secret Sharing
Secret Sharing Instantiation
Z
p
: {0,1….p-1}, p is a prime Theorem: F
p
= (Z
p
, + mod p (
+
), . mod p (
) ) is a field
Closure
Associativity
Identity: 0 and 1
Inverse: for every a there exist –a, a
-1
so that a
(-a) = 0 and
a
a
-1
= 1
Distributive: . mod p over + mod p
Secret Sharing Instantiation
s from F
p
S
\
s
1
S\
s
2
S\
s
3
S \
s
n
…
F
p
= (Z
p
,
+
,
) is a field
>> Choose random shares s
1
,..s
n
from F
p
s. t. s
1
+
…
+
s
n
= s
>>
S = {s
1
,.. s
n
}
>> Together all the parties know s (in fact any two parties know s)
>> Individual party has no information about s.
The probability of guessing s before secret sharing = the probability
of guessing s after secret sharing (does not depend on the computing
power of the parties)
Secure Addition y = x
1
+
x
2
+
x
3
(assume n=3
parties)
x
1
P
1
P
2
P
3
P
1
x
2
P
2
x
3
P
3
x
12
x
13
+
+
+
+
+
+
=
=
=
P
i
y = s
1
+
s
2
+
s
3
The same is done for all P
i
x
11
x
12
x
13
x
21
x
22
x
23
x
31
x
32
x
33
x
11
x
13
x
11
x
12
x
22
x
23
x
21
x
23
x
21
x
22
x
32
x
33
x
31
x
33
x
31
x
32
s
2
s
3
s
1
s
3
s
1
s
2
No party even with unbounded
power learns nothing more than y !
Primitives 1 (Secret Sharing
Schemes):
A magic primitive
and one of the fundamental
building blocks of MPC
Secure bit multiplication y = x
1
x
2
and Match-
making (assume n=2 parties)
x
1
P
1
P
2
P
1
x
2
P
2
x
12
Looks like we are stuck
x
11
x
12
x
21
x
22
x
11
x
22
x
21
y = x
1
x
2
=
(
x
11
+
x
12
)
(
x
21
+
x
22
)
= (
x
11
x
21
+
x
11
x
22
+ x
12
x
21
+
x
12
x
22
)
= x
12
x
22
= x
11
x
21
1-out-of-2 Oblivious Transfer
S
Message Transfer:
R
m
S
R
m
0
m
1
b
m
b
m
S does not know b
R does not know m
1-b
1-out-of-2
OT
m
0
m
1
b
m
b
Secure bit multiplication y = x
1
x
2
x
1
P
1
P
2
x
2
1-out-of-2
OT
0
x
1
x
2
x
1
x
2
1-out-of-2
OT
a
0
a
1
b
(1-b)
a
0
+ b
a
1
= a
b
Primitive 2 (Oblivious Transfer):
Another magic primitive and one of the
fundamental building blocks of MPC
Time to show Vishwaroop of MPC
Welcome to Secure Computation Lecture 1 by Arpita Patra. The course covers evaluation policies, projects, and references in the realm of secure computation. The content delves into the significance of information security across various sectors, emphasizing the importance of safeguarding sensitive data in the digital age.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Secure Computation (Lecture 1) Arpita Patra
Welcome to an exciting Journey >> Course Homepage: http://drona.csa.iisc.ernet.in/~arpita/SecureComputation15.html >> References: 1. Secure Multiparty Computation and Secret Sharing - An Information Theoretic Approach by Ronald Cramer, Ivan Damgaard and Jesper Buus Nielsen 2. Efficient Two-party Protocols- Techniques and Constructions- by Carmit Hazay and Yehuda Lindell 3. Recent papers and a few lecture notes
Evaluation Policy >> Tuned to ensure that you learn and you enjoy the learning! Scribe (18%): Every student will have to scribe 2/3 lectures Chalk & Talk Seminar (14*2 + 4 = 32%): Every student will make two presentations (one in each half of the course) and write a small blog on one of her/his friend s seminar. Project (25 + 35 = 60%): Two projects (midterm and end-term) >> theoretical or practical in nature >> theoretical projects will involve answering deep and exciting theoretical questions >> practical projects will involve implementing and improving challenging practical secure computation tasks >> Both project topics may be same. Complete literature survey and decide on an exciting problem by midterm. Make non-trivial theoretical progress/ implement the best solution in the second half.
We are in the age of Information! Information Everywhere: > Individual: Age, Salary, Bank Details (balance, netbaking login password), Citizenship, Parents/family member details, Identity details (passport no., PAN card, Voter ID, AADHAR id ), Income Tax Details, Your vehicle details (cycle, two wheeler, car), Medical data: diseases, biometric traits (face, fingerprint, iris, speech), genome signature, minimum age of watching porn/taking drug, Child adoption details > Profitable Organization (MS/IBM/TCS/Infosys): List of employees and their details, Profit, loss, turnover, salaries. > Educational Organization (IISc/IITs/IIITs/IISERs/NISERs/NITs): List of employees and their details, students and their details, awards, recognitions, scientific publications, products, dropouts, drug addicts, suicides, sexual harassments,
We are in the age of Information! > Hospitals: List of patients and their medical history and details. List of doctors, nurses and their details > Security Agencies (RAW/ IB/ CBI/NIA): List of employees and details, list of criminals and details, list of incidents and details > Military Organizations (Army/Air Force/Navy): List of soldiers, colonels and details, list of operations and details, intercepted messages and details > Country: List of citizens and details, prime minister, presidents, MLA, MPs, celebrities, under-privileged. Satellites / Nuclear weapons / Submarines information .
Secret Information > Individual: Age, Salary, Bank Details (balance, netbaking login password), Identity details (passport no., PAN card, Voter ID, AADHAR id ), Income Tax Details, Your vehicle details (cycle, two wheeler, car), Medical data: diseases, biometric traits (face, fingerprint, iris, speech), genome signature, minimum age of watching porn/taking drug, Child adoption details > Profitable Organization (MS/IBM/TCS/Infosys): List of employees and their details, Profit, loss, turnover, salaries. > Educational Organization (IISc/IITs/IIITs/IISERs/NISERs/NITs): List of employees and their details, students and their details, awards, recognitions, scientific publications, products, dropouts, drug addicts, suicides, sexual harassments,
Secret Information > Hospitals: List of patients and their medical history and details. List of doctors, nurses and their details > Security Agencies (RAW/ IB/ CBI/NIA): List of employees and details, list of criminals and details, list of incidents and details, list of intercepted messages > Military Organizations (Army/Air Force/Navy): List of soldiers, colonels and details, list of operations and details, intercepted messages and details > Country: List of citizens and details, prime minister, presidents, MLA, MPs, celebrities, under-privileged. Satellites / Nuclear weapons / Submarines information .
Secret Communication We know how to solve (Encryption schemes) >> Not trivial to achieve the goal >> But the purpose is simple to state and well-understood
Privacy Preserving Information Processing (Computation) Many scenarios that: >> demands data privacy and computation on the data at the same time! >> A large amount of added value can be obtained by combining confidential information from several sources and from this computing some result that holds an interest for all parties
Preventing Satellite Collision in Space NASA tracks 7,000 space crafts and 21,000 objects in space Approximately 20,00,00,000 pairs
Preventing Satellite Collision in Space List of High-speed Collisions: The 1996 collision between the French Cerise military reconnaissance satellite and debris from Ariane rocket The 2009 collision between the Iridium 33 communications satellite and the derelict Russian Kosmos 2251 spacecraft over Siberia, which resulted in the destruction of both satellites The 22 May 2013 collision between Ecuador's NEE-01 Pegaso and Argentina's CubeBug-1, and the particles of a debris cloud left over from the launch of Kosmos 1666 On Jan. 22, 2013, debris from the destroyed Chinese satellite Fengyun 1C collided with a small Russian laser-ranging retro- reflector satellite called BLITS ("Ball Lens in The Space").
Preventing Satellite Collision in Space NASA tracks 7,000 space crafts and 21,000 objects in space Approximately 20,00,00,000 pairs High-accuracy positional information High-accuracy positional information is privy to operators National secret
Preventing Satellite Collision in Space To date, there have been no observed collisions between natural satellites of any Solar System planet or moon.
(Secure) Electronic Auction Nothing other than the winner and winning bid should be revealed
(Privacy Preserving) Data Mining Hospitals do not want to share their patient records But want to data-mine on combined data
(Privacy Preserving) Data Mining They do not want to share their count of sexual abuse cases/ drug addicted cases But want to data-mine on combined data
Many more applications.. >> Secure Set Intersection >> Secure Bench-marking >> Secure/private information retrieval . There is something common among all the problems. can we find an abstraction?
Secure (Multiparty) Computation (MPC) MPC is the holy grail: Abstracts all that we have seen so far and many more >> n parties P1,....,Pn Do not trust each other >> Pi has private input xi >> A common n-input function f Goals: >> Correctness: Compute f(x1,x2,..xn) >> Privacy: Nothing about the inputs of the parties should be leaked >> Consider f(x1,x2) = x1 AND x2 >> Refined Privacy: Nothing more than function output should be revealed
MPC is easy if we could trust someone x1 x2 Any task x3 x4 y = f(x1,x2,x3,x4)
Can we Trust Someone? Some problem in the solution.. >> Creates a single point failure x1 x2 Any task >> Why we are doing secure computation? Because of the lack of trust. How suddenly we will get someone who is cent percent trusted? y y y y >> Trust is a very rare, volatile. x3 x4 >> If there is trust in the world y = f(x1,x2,x3,x4) MPC
But there will be dis-trust in the world.. Because.. >> Without darkness, one cannot know light >> Without hatred, one cannot feel love >> Without war, one cannot realize the price peace >> Without noise, one cannot appreciate serenity >> Without distrust, one cannot value trust The contrasts are the hallmarks of the great Magician!! So we have to solve MPC without a trusted party.. >> But looks impossible. How is it possible to compute f(x1,x2,x3,x4) without anyone knowing all the inputs. So do we have to really trust someone.. Looks like we are stuck. Does the journey of secure computation end here?
Secure Addition and Voting y = f(x1,x2,..,xn) = x1 + x2 + + xn x1 x2 x3 y xn y y y P3 Pn P1 P2
Secret Sharing Provides a way for a party, say P1 to spread information about a secret x across all the parties so that together they hold full information about x, yet individual (or subset of parties) has no information about x Dealer Secret s
Secret Sharing Dealer Secret s sn s1 s3 s2
Secret Sharing Dealer Secret s vn v1 v3 v2 Individual players have no information on s
Secret Sharing Dealer Secret s sn s1 s3 s2 Together all the parties know s Secret s
Secret Sharing Instantiation Zp : {0,1 .p-1}, p is a prime Theorem: Fp = (Zp , + mod p (+), . mod p ( ) ) is a field Closure Associativity Identity: 0 and 1 Inverse: for every a there exist a, a-1 so that a (-a) = 0 and a a-1 = 1 Distributive: . mod p over + mod p
Secret Sharing Instantiation >> Choose random shares s1,..sn from Fp s. t. s1 + + sn = s s from Fp >> S = {s1,.. sn } S\s2 S \ sn S\s1 S\s3 >> Together all the parties know s (in fact any two parties know s) >> Individual party has no information about s. The probability of guessing s before secret sharing = the probability of guessing s after secret sharing (does not depend on the computing power of the parties) Fp = (Zp , +, ) is a field
Secure Addition y = x1+x2+x3 (assume n=3 parties) P3 P1 P2 Primitives 1 (Secret Sharing Schemes): A magic primitive and one of the fundamental building blocks of MPC x3 x1 x2 x31 x32 x33 x11 x12 x13 x21 x22 x23 x22 x23 x32 x33 s2 s3 x12 x13 P1 + = + x21 x23 x31 x33 s1 s3 x11 x13 P2 + + Pi y = s1 +s2 +s3 = x21 x22 x31 x32 s1 s2 x11 x12 P3 + + = No party even with unbounded power learns nothing more than y ! The same is done for all Pi
Secure bit multiplication y = x1 x2 and Match- making (assume n=2 parties) P1 P2 y = x1 x2 =(x11 + x12 ) (x21 + x22 ) = (x11 x21 + x11 x22 + x12 x21 + x12 x22) x1 x2 x11 x12 x21 x22 P1 = x12 x22 x12 x22 = x11 x21 x11 P2 x21 Looks like we are stuck
1-out-of-2 Oblivious Transfer Message Transfer: S R m m m0 m1 b mb S R S does not know b R does not know m1-b b m0 1-out-of-2 OT m1 mb
Secure bit multiplication y = x1 x2 x2 0 P2 P1 1-out-of-2 OT x1 x1 x2 x2 x1 a0 b 1-out-of-2 OT a1 (1-b) a0 + b a1 = ab Primitive 2 (Oblivious Transfer): Another magic primitive and one of the fundamental building blocks of MPC
