As part of a broader organisational restructure, data networking research at Swinburne University of Technology has moved from the Centre for Advanced Internet Architecture (CAIA) to the Internet For Things (I4T) Research Lab.

Although CAIA no longer exists, this website reflects CAIA's activities and outputs between March 2002 and February 2017, and is being maintained as a service to the broader data networking research community.

STING -- Surveying The INternet's Growth

Measuring and predicting growth in Internet addressing, routing complexity and energy usage

Secure Fast Set Intersection (SeFaSI) Tool

Overview

SeFaSI is a tool that allows multiple parties to securely compute the set intersection cardinality of data sets while keeping the data items private. SeFaSI is secure (with appropriately selected encryption parameters), works with two or more parties, is fast and scalable due to data sampling, and also supports a technique to prevent probe attacks. We developed SeFaSI to use capture-recapture techniques to estimate the used IPv4 space from multiple datasets of observed IPv4 addresses while ensuring the anonymity of the IPv4 addresses in each dataset. However, the underlying technique and a large part of the code is generic, and SeFaSI could be used for other applications.

SeFaSI is based on commutative encryption. Each participating party first encrypts and permutes their own data set. Then all other parties encrypt and permute each other party's encrypted data set. Since the encryption is commutative, the set intersection cardinality of the n-party encrypted and permuted sets is the same as the intersection cardinality of the unencrypted sets. Since the encryption is secure and the data sets are permuted by each party, no party can learn anything about another party's data set apart from the intersection cardinality.

The commutative encryption method is more efficient than other secure set intersection cardinality computation methods, but it still has significant computational and storage/transmission costs. SeFaSI supports hash-based sampling of the input data to drastically speed up the encryption and drastically reduce the storage/ transmission costs for the encrypted data sets. Large performance gains can be achieved with relatively small sampling errors.

SeFaSI can detect probe attacks if the input data is from some known finite set. Probe attacks are attacks where an attacker constructs a data set with mostly invalid/impossible items and only a few valid items. Successful probe attacks allow the attacker to determine if a few specific items are present in other parties' data sets.

SeFaSI runs under Linux and FreeBSD. See INSTALL and README for further information. The approach and the SeFaSI implementation are described in more detail in the tech report CAIA-TR-130930A.pdf. The tech report CAIA-TR-130930B.pdf describes how SeFaSI can be used by multiple collaborators to estimate the size of the used IPv4 space while ensuring the anonymity of the IPv4 addresses each collaborator has observed.

Download

Latest Version

Version 0.5 (released 14th of May 2014):

Release 0.5: renaming of project in doc, small changes in how sample salts are generated

Old versions

Version 0.4 (released 13th of January 2014):

Release 0.4: fix against an attack when input data contains duplicates (i.e. not a proper set) Version 0.3 (released 2nd of December 2013):

Release 0.3: test script reorganisation, added test script for n local parties, bug fixes Version 0.2 (released 18th of November 2013):

Release 0.2: bug fixes Version 0.1 (released 1st of October 2013):

Initial release

Authors

SeFaSI has been developed by the following people:

Sebastian Zander (szander@swin.edu.au)

License and Terms of Use

The SeFaSI source code is publicly available under the terms and conditions of the GNU General Public License version 2 (GPLv2), which can be viewed here.

Acknowledgements

This tool has been made possible in part by an Australian Research Council (ARC) Linkage Project grant (project LP110100240) with APNIC Pty Ltd as partner organisation, for a project titled "Tools and models for measuring and predicting growth in internet addressing and routing complexity".



Last Updated: Wednesday 14-May-2014 14:05:05 EST | Maintained by: Sebastian Zander (szander@swin.edu.au) | Authorised by: Grenville Armitage ( garmitage@swin.edu.au)