| NSF Org: |
CNS Division Of Computer and Network Systems |
| Recipient: |
|
| Initial Amendment Date: | September 16, 2015 |
| Latest Amendment Date: | July 18, 2016 |
| Award Number: | 1526950 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
Shannon Beck
CNS Division Of Computer and Network Systems CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 15, 2015 |
| End Date: | August 31, 2018 (Estimated) |
| Total Intended Award Amount: | $166,600.00 |
| Total Awarded Amount to Date: | $166,600.00 |
| Funds Obligated to Date: |
FY 2016 = $65,893.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
3112 LEE BUILDING COLLEGE PARK MD US 20742-5100 (301)405-6269 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
MD US 20742-5141 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): |
CSR-Computer Systems Research, Secure &Trustworthy Cyberspace |
| Primary Program Source: |
01001617DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Data structures have a prominent modern computational role, due to their wide applicability, such as in database querying, web searching, and social network analysis. This project focuses on the interplay of data structures with security protocols, examining two different paradigms: the security for data structures paradigm (SD) and the data structures for security paradigm (DS). The objectives of this project are, in the SD paradigm, to provide security and privacy both for data elements in data sets and also for the inter-relationships and distributions between such data elements, such as links between nodes in a social network, and, in the DS paradigm, to develop new data structures to improve the efficiency of algorithms for security and/or privacy applications.
The project explores methods for achieving these objectives include algorithm design, theoretical analysis, rigorous proofs of security and correctness, and experimental validation of claims of practicality. This research focuses on the security and cybersecurity uses of three advanced data structures: tree structures, invertible Bloom filters and cascading tables. The project advances knowledge on (a) authenticated data structures and verifiable query execution within the SD paradigm, and (b) secure deduplication, searchable encryption, and privacy-preserving memory allocators within the DS paradigm.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
The project studied various relations between data structures and security, focusing on how data structures can enhance the performance of security protocols and more generally on the impact of data structure design on the security of data management.
One of the area that was explored is searching encrypted dynamic data, namely how to encrypt your personal information, send it to an untrusted repository/server, and then enable the server do some simple computation (search) without ever seeing the data in plaintext. We focused on the most challenging problem of supporting updates, such as edits, insertions and deletions, in the outsourced encrypted data collection without sacrificing privacy or efficiency (e.g., we do not re-encrypt the whole database whenever an update takes place). We particularly explored advanced security guarantees for this problem, such as backward privacy. For example, we want to make sure that our dynamic algorithms do not reveal which documents were deleted, after a deletion takes place.
A second area that was explored was data structures whose operation can be verified (authenticated data structures) with applications to blockchains. We considered the problem of distributing authenticated data structures, such that every party stores individual proofs for certain elements in the dataset, and all proofs are easily updatable when an update on the data structure takes place. This type of data structure has applications in stateless transaction validation, where network nodes do not maintain the whole blockchain state (but just a succinct digest), and the state is distributed across multiple parties/users of the blockchain.
The project contributed in the professional development of several PhD students and postdocs.
Last Modified: 02/26/2019
Modified by: Charalampos Papamanthou
Please report errors in award information by writing to: awardsearch@nsf.gov.
