Purdue CS 59000  Lecture notes (23 pages)
Previewing pages 1, 2, 22, 23 of 23 page document View the full content.Lecture notes
Previewing pages 1, 2, 22, 23 of actual document.
View the full content.View Full Document
Lecture notes
0 0 131 views
 Pages:
 23
 School:
 Purdue University
 Course:
 Cs 59000  Topics in Computer Sciences
Topics in Computer Sciences Documents

3 pages

25 pages

13 pages

2 pages

62 pages

Intrusion FaultTolerance using Threshold Cryptography
17 pages

47 pages

32 pages

Addressing privacy issues in CardSpace
7 pages

Ensuring Data Storage Security
25 pages

The Byzantine Generals Problem
22 pages

26 pages

42 pages

72 pages

28 pages

CLOUD COMPUTING FOR MOBILE USERS
6 pages

39 pages

97 pages

97 pages

56 pages

Improving the Scalability of Data Center Networks
8 pages

28 pages

A MobileCloud Collaborative Traffic Lights Detector for Blind Navigation
5 pages

24 pages

3 pages

A Berkeley View of Cloud Computing
15 pages

15 pages

6 pages

Exploring Information Leakage in ThirdParty Clouds
19 pages

28 pages

7 pages

Government Information Forecast
43 pages

26 pages

35 pages

Design Rationale behind the Identity Metasystem Architecture
11 pages

Effectively and Securely Using the Cloud Computing Paradigm
92 pages

30 pages

36 pages

31 pages

21 pages

A Measurement Based Admission Control Algorithm
18 pages

25 pages

Creating HIPAACompliant Medical Data Applications
8 pages

36 pages

40 pages

22 pages

25 pages

21 pages

15 pages

67 pages

23 pages

38 pages

28 pages

Athletes with Visual Impairments
13 pages

Byzantine Tolerant Group Communication Systems
15 pages

10 pages

Foundations of Software Testing
139 pages

14 pages

42 pages

25 pages

TESSA, a system to aid communication with deaf people
8 pages

25 pages

35 pages

38 pages

103 pages

25 pages

33 pages

22 pages

19 pages

Data Anonymization for Database Privacy
30 pages

31 pages

40 pages

27 pages

Association Rules, Sequential Associations
14 pages

15 pages

21 pages

29 pages

Adapting Distributed Realtime
20 pages

22 pages

15 pages

127 pages

34 pages

30 pages

Virtualized Cloud Infrastructure without the Virtualization
12 pages

3 pages
Sign up for free to view:
 This document and 3 million+ documents and flashcards
 High quality study guides, lecture notes, practice exams
 Course Packets handpicked by editors offering a comprehensive review of your courses
 Better Grades Guaranteed
Proactive Secret Sharing Or How to Cope With Perpetual Leakage Paper by Amir Herzberg Stanislaw Jarecki Hugo Krawczyk Moti Yung Presentation by David Zage What is Secret Sharing Basic Idea 2 2 threshold scheme Two friends find a map to buried treasure Who do we trust Neither each gets a share of the map Based on threshold cryptography Why Do We Need Proactive Sharing Secret sharing is a fundamental tool for protecting sensitive data How do we protect the data from gradual server break ins Renew data Not good for long lived data Renew the Secret Good Attacker must compromise k 1 servers in a time period instead of the entire life of the system System Assumptions System k 1 n threshold scheme Secure encryption and signatures exist Synchronized secure broadcasts over a common medium Data is actually destroyed when erased Mobile Adversary Byzantine corruption can occur at any time Adversary can corrupt no more than k out of n servers where k n 2 Adversary is connect to the communication medium but cannot interfere with communication Removing an Adversary from a Server Adversaries are removable through reboot procedures Honest servers always detect and remove misbehaving servers DOS attacks on the communication medium not taken into account further papers address this using asynchronous systems Definitions Semantically Secure Security is measured in terms of entropy and change The scheme is semantically secure if for any function k computable on the secret the difference in the probability of learning information between rounds is negligible Robust Scheme guarantees the correct reconstruction of the secret at any time Tolerates up to k Byzantine faults Cryptographic Tools Shamir s Secret Sharing Dealer chooses a function f of degree k over a finite field where f 0 secret Dealer calculates vi f i and secretly sends vi to the server i The secret can now be reconstructed with k 1 vi pieces and polynomial interpolation Cryptographic Tools Verifiable Secret Sharing g is an element of a the finite field the equation k was chosen from Values gfi are broadcast to every server before the secret share is broadcast When a server receives a secret share it checks i2 gxi g g g g f0 f1 i f2 fk ik If the equation holds the share is a valid share With VSS there is more information to attack Information can be learned from each of the gx What can be done Use a different scheme where extra information is already released ElGamal Signatures Place the secret X in an envelope Encode the secret in a longer bit string s Periodic Share Renewal Each server has a pair of public and private keys used for secure communication Assumption Attacker cannot modify the keys System initialization The secret is encoded using Shamir s secret sharing and securely distributed to all servers Time periods for renewal are set arbitrarily by system administrator Basic Share Renewal Protocol Each server Pi picks k random numbers from the finite field and creates a polynomial of degree k i z i1 z i 2 z ik z 1 2 k For all other servers Pj Pi secretly sends out i j to Pj Pi computes the new share by t 1 i x t 1 i x 1i 2i ni Pi updates its share and erases all other data Basic Share Renewal Protocol 2 Solves share renewal in the face of a passive adversary If all of the servers follow the protocol then the share renewal protocol is correct robust and is secret Each new round produces a valid set of secret shares Any k 1 servers can re create the secret at any time With k or less shares no information is learned Share Renewal Protocol in the Presence of Active Attackers Each server Pi picks k random numbers from the finite field and creates a polynomial of degree k i z i1 z i 2 z ik z 1 2 im k Each Pi also computes im g for each k Pi computes i j and broadcasts the set of s and signed with Pi s signature Share Renewal Protocol in the Presence of Active Attackers 2 Pi computes the new share by t 1 i x t 1 i x 1i 2i ni and checks the validity by computing j i i i2 ik g j1 j 2 jk If the messages are correct Pi broadcasts an accept message If not Pi broadcasts an accusation against the misbehaving server s Resolving Accusations If faulty server is recognized Do not use the polynomial broadcast by the server Reset the server to expel the adversary Three types of possible faults Incorrect message format Zero or greater than One correct message from a server Verifiability equations do not match 3rd type of fault requires extra effort to handle Resolving Accusations 2 If Pi accuses Pj of cheating Pj must defend itself If Pj sent a correct j i then it exposes this value and all servers can check with the values already published during the protocol If Pj defends itself then Pi marked as the fault server else Pj is marked The share renewal equation becomes t 1 i x t 1 i x ji j Bi Share Recovery Scheme Severs must make sure other servers have not had their keys compromised Otherwise an adversary could cause the secret to be lost by destroying n k keys Without recovery we loose security For practical schemes During reboot a server will loose it share and need recovery Detecting Corruption During initialization each server stores a the set of x jt t y j g for all the servers current shares During the secret share update this set of exponents is also updated in a similar fashion y t j y t 1 j g aj a Bi If during the update phase the value of the new x received and the one calculated do not match the server needs to have its share recovered Basic Share Recovery Protocol For every failed server r Every valid Pi picks a random k degree polynomial such that f r 0 Every Pi broadcasts f r Each Pi the creates a new share for r x i xi f i j D and send it to r R receives the shares and interpolates them to find its secret share xr Share Recovery Verifiability can be added using same technique as earlier Used to detect incorrect reconstructions Multiple shares can be recovered in parallel by treating each share as its on secret Total Protocol for Proactive Secret Sharing At the beginning of every time period Private Key Renewal protocol Do not have to assume attacker can not tamper with public private communication keys Share Recovery Protocol including lost shares detection Share Renewal Protocol Applications Proactively share decryption key for sensitive data Proactive function sharing built of Proactive secret sharing Proactive digital signatures Summary Semantically secure and robust proactive secret sharing scheme based on threshold cryptography and
View Full Document