56 %
44 %
Information about SIA

Published on November 29, 2007

Author: Sarah


SIA: Secure Information Aggregation in Sensor Networks:  SIA: Secure Information Aggregation in Sensor Networks Bartosz Przydatek, Dawn Song, and Adrian perrig ACM SenSys 2003 November 9, 2004 Dept. Computer Science, KAIST Minsoo Kim Contents:  Contents 1. Introduction 2. Secure Information Aggregation 3. General Approach - Aggregate-Commit-Prove Framework 4. Secure Computing Protocols - Computing the Median - Computation of Min/Max - Counting Distinct Elements 5. Forward Secure Authentication 6. Discussion and Conclusion Introduction(1/2):  Large scale of Sensor Networks Aggregation is need To transmit all data from each sensor is inefficient Sensor nodes have limited resources (computation, storage, battery) Secure information aggregation is need To prevent stealthy attack which provides false aggregation results to user False aggregation result (Home server does not know!) Sensor nodes and aggregator can be corrupted Introduction(1/2) Secure Information Aggregation(SIA) mechanism is proposed Introduction(2/2):  Introduction(2/2) Aggregator (Base Station) - Min, Avg, Counting, etc Smart Sensor Node Smart Sensor Node Smart Sensor Node Smart Sensor Node Measured values Home Server(User) Problem Definition Smart Sensor Node Uncorrupted Sensor Corrupted Sensor Low communication cost Secure Information Aggregation(1/3):  Key setup and Communication model Key setup (Assumption) Home server and aggregator stores a master key KB and KA, respectively Sensor node stores shared keys MACKB(node ID) and MACKA(node ID), MAC : (Secure) Message Authentication Code Communication model (Assumption) Uncorrupted sensors form a connected component containing the aggregator Attack Model and Security Goals Attacker can corrupt at most a small fraction of all the sensors Attacker’s goal is to make the home server accept false aggregation results Security goal is to prevent stealthy attack Secure Information Aggregation(1/3) Secure Information Aggregation(2/3):  Efficiency vs. Accuracy Tradeoff Simple solution for stealthy attack Aggregator forwards to home sever all data and authentication information from each sensor Accurate, but inefficient Communicating just the result of a query(e.g. count, min/max, average) Very efficient, but not guarantee of correctness Relax the accuracy requirements and accept approximative results Difference between real result and approximation Some sensors may be corrupted and report wrong values When aggregtor uses sampling techniques, sampling techniques will be error Aggregator may be corrupted Secure Information Aggregation(2/3) Secure Information Aggregation(3/3):  Notation and Conventions n : the number of sensors (S1, …, Sn) A : aggregator B : home server ai : the values measured by the sensors totally ordered set, integers from [m]= {1,…,m} Secure Information Aggregation(3/3) General Approach (1/4):  General Approach (1/4) 1.Computation of the aggregation result (R) Aggregator (Base Station) Home Server(User) 2.Committing to the collected data and report back the aggregation result (v0,0 & R) 3.Proving the correctness of the result General Approach (2/4):  Aggregate-Commit-Prove framework This approach improves both security and efficiency Step 1 : Computation of the aggregation result Aggregator collects sensors’ data and computes aggregation result Aggregator can verify the authenticity of each sensors’ data using KA and MACKA(node ID) Step 2 : Committing to the collected data and report back the aggregation result Aggregator commits to the collected data Merkle hash-tree is used for committing to the data All data is placed at leaves of the tree Compute a binary has tree starting from the leaf nodes Internal node is computed as the hash value of the concatenation of two childs Root is called the commitment of the collected data General Approach (2/4) General Approach (3/4):  Step 3 : Proving the correctness of the result Aggregator communicates the aggregation result and the commitment to the server Interactive proof is used to prove the correctness of the result Home server checks that the committed data is a good representation Home server checks if the aggregator is cheating General Approach (3/4) General Approach (4/4):  Merkle hash-tree used to commit a set of values Cryptographic hash function v3,0 = H(m0), vi,j = H(vi+1,2j || vi+1,2j+1) (ex) Authentication of m5, aggregator sends m5 along with v3,4, v2,3, v1,0 v0,0 = H(v1,0 || H(H(v3,4 || H(m5) || v2,3)) General Approach (4/4) Secure Computing Protocol(1/8):  1.Computing the median Trivial solution Sending all measurements to home server Naive approach : Median by Random Sampling Aggregator Only forwards samples from the sensors without doing any processing Home server (1) Takes a random sample l (It is related with efficiency) (2) Computes the median of the sample as an approximation of the real median Sample of l out of n elements : l = O(1/2) Estimation range : n (Ex) n = 32,768(215),  = 0.01 Estimation range n  327, Sample number  10,000 Secure Computing Protocol(1/8) Efficient protocols to detect the aggregator cheating! Secure Computing Protocol(2/8):  New approach for Median (More efficient) Aggregator (1) Computes the median(amed) of the measured values from the sensors (2) Commits the measured values and the sequence of the values is sorted Home server performs interactive proof with aggregator (1) Verifies that the committed sequence is sorted Sort-Check-II spot checker Sample number : O(log n/) (2) Checks that amed is (close to) the median of committed sequence Median check program Sample number : O(1/) Total sample number : l = O(log n/) Estimation range : n (Ex) n = 32,768(215),  = 0.01 Estimation range n  327, Sample number  1,500 Secure Computing Protocol(2/8) Secure Computing Protocol(3/8):  Median Check Program Home server runs this program Secure Computing Protocol(3/8) Sensor Number Median computed by aggregator Estimation parameter Median Check Left half Check Right half Check Aggregator (Base Station) Home Server(User) n, amed,  aj Secure Computing Protocol(4/8):  2.Computation of Min/Max Secure min-discovery protocol Constructing protocol of aggregator + Checking protocol of Home server Constructing protocol (Minimum spanning tree construction) Construct a spanning tree, such that the root holds the minimum element Secure Computing Protocol(4/8) Initial State Min Rooted Tree Construction After the construction, all sensors have the same smallest value and form a tree rooted at the node is the owner of the smallest value Secure Computing Protocol(5/8):  Checking protocol Each node Si authenticate its final state (pi,vi,idi) from construction protocol, and send the authenticated state to the aggregator(A) A commits to the list of all nodes and their states, finds the root node, and reports the root node to home server Home server performs FindMin protocol Secure Computing Protocol(5/8) MinRootedTree Construction Consistency Check of the Constructed Tree Aggregator (Base Station) Home Server(User) n, root node,,  (pj,vj,idj) Secure Computing Protocol(6/8):  3.Counting Distinct Elements Method I : Counting Distinct Elements by Min-Computation Sensor node level processing (not aggregator) Random sample + Space-efficient estimation Random sample (Random selection of a node) (1) Home server picks random hash function h and sends it to aggregator (2) Aggregator broadcast h with sampling request (3) Each sensor computes hash value of its ID and current time interval (4) Whole network performs a MIN-discovery protocol Space-efficient estimation of the number of distinct elements in a stream (1) Pick random hash function h : [m] -> [0..1] (2) Keep the value v = mini=1 h(ai) (3) Estimated number of distinct elements ’ = 1/v Basic idea for improvement is to maintain t smallest values ’ = t/v Secure Computing Protocol(6/8) n Secure Computing Protocol(7/8):  Method II : Proving Bounds on the Number of Distinct Elements Aggregator level processing (More efficient than Method I) Approximation of lower & upper bounds Lower bound on the number of distinct elements Difference compared with Method I Method I is performed in sensor nodes, but Method II in Aggregator Home server has no means to check aggregator in evaluating hash function and reporting element Aggregator may report larger v compared with exact v => estimate ’ is smaller than  => Lower Bound Secure Computing Protocol(7/8) Space-efficient estimation Secure Computing Protocol(8/8):  Upper bound on the number of distinct elements Aggregator commits to the multi-set S of all the elements and subset S’ containing all distinct elements Aggregator reports ’= |S’| to home server Home server verifies aggreggtor’s claim by asking that all the distinct elements from S are present in S’ Ramdom sampling : home server request random element from S, and ask aggregator for an element with the same value present in S’ Secure Computing Protocol(8/8) Forward Secure Authentication:  What is forward secure authentication? Sensor is corrupted at a certain time, Attacker should not be able to alter the past data before the certain time Forward secure authentication mechanism Each sensor updates its key shared with home server at each time interval using one-way function Each sensor uses the updated key to compute MAC on sensing data Attacker in a later time is unable to compute the MAC key for the previous time interval Because of one-way function Challenges How to efficiently store the past data How to efficiently compute many one-way functions for deriving the MAC in home server Forward Secure Authentication Conclusion & Discussion:  Aggregate-commit-prove framework is proposed Concrete protocols Securely computing the median Securely finding the min/max Securely counting the number of distinct elements Securely computing average First paper on handling the secure aggregation problem especially between home server and aggregator Hierachical aggregation is needed in large sensor networks In this paper some protocol is possible, others is impossible Conclusion & Discussion

Add a comment

Related presentations

Related pages

Sia (Sängerin) – Wikipedia

Sia [siːə] (* 18. Dezember 1975 in Adelaide als Sia Kate Isobelle Furler) ist eine australische Sängerin und Songschreiberin. Sie wurde international ...
Read more

Sia - Chandelier (Official Video) - YouTube

Want to watch this again later? Sign in to add this video to a playlist. Sia's official music video for 'Chandelier'. Click to listen to Sia on ...
Read more


Official site for Sia. Includes news, tour dates, videos, webstore, and more!
Read more

Sia - Videos - alle offiziellen Musikvideos von Sia

Alle Musikvideos von Sia - Songs und Hits von Sia - Original-Sia-Musik Videos in Top Qualität!
Read more

Sia Home Fashion

Seit 1963, SIA ist internationaler Marktführer in Kunstblumen und Dekorationsartikeln für Zuhause: Duftkerzen, Geschenkartikel, Tischwäsche, Geschirr ...
Read more

SIA Home Fashion

SIA is an international leader within the decoration industry and is above all recognised for its floral art expertise enriched with tableware, household ...
Read more

Sia — music

Official site for Sia. Includes news, tour dates, videos, webstore, and more!
Read more

Sia - Facebook

Sia will be headlining the Nostalgic For The Present Tour this fall in North America, and she’s bringing out special guests Miguel and AlunaGeorge for ...
Read more

Sia - YouTube

i am sia, i was born from the bumhole of a unicorn named steve. New album 'This Is Acting' out now on Apple Music, Google Play, Amazon, Spotify
Read more

sia | schweizerischer ingenieur- und architektenverein

SIA-Tage der zeitgenössischen Architektur und Ingenieurbaukunst 2016. Im Mai 2016 finden erneut die SIA-Tage der zeitgenössischen Architektur und ...
Read more