| NSF Org: |
CNS Division Of Computer and Network Systems |
| Recipient: |
|
| Initial Amendment Date: | August 30, 2013 |
| Latest Amendment Date: | August 30, 2013 |
| Award Number: | 1318880 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Nina Amla
namla@nsf.gov (703)292-7991 CNS Division Of Computer and Network Systems CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | October 1, 2013 |
| End Date: | September 30, 2018 (Estimated) |
| Total Intended Award Amount: | $249,801.00 |
| Total Awarded Amount to Date: | $249,801.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
1 UNIVERSITY OF NEW MEXICO ALBUQUERQUE NM US 87131-0001 (505)277-4186 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
NM US 87131-0001 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Secure &Trustworthy Cyberspace |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Consider a network where each node is either good or bad. The good nodes all run an algorithm that attempts to achieve a specific goal. The hidden set of bad nodes are controlled by an adversary who uses them to thwart this goal.
Informally, cost-competitive analysis considers the resource cost of each good node as a function of the total resource cost of the adversary. The goal is to design algorithms that achieve their objectives, while minimizing this cost. Critically, when bad nodes suffer higher costs than good nodes, it is expected that they will eventually cease their attack, as their resources become depleted.
Goals of this project are to design cost-competitive algorithms for: communication in wireless networks; tolerating distributed denial-of-service attacks; secure routing in peer-to-peer networks; and enabling nodes to come to agreement.
Cost-competitive analysis offers a novel approach for making progress on challenging attacks that cannot be adequately addressed in models that ignore the costs of the attacker. By adopting a more realistic attack model, this approach more accurately quantifies the limits of efficient attack resistance. It is thus expected that a cost-competitive approach will yield more compelling solutions to security challenges in many domains. In particular, this project may have high impact in security challenges involving open environments such as: wireless sensor networks, overlays, reputation systems; and aspects of contemporary problems in industry such as: public cloud computing, reliable versions of MapReduce, and robust distributed lock managers like Google's Chubby lock service.
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.
This grant has had several significant research outcomes.
First, we designed cost-competitive algorithms for proof-of-work-based security. Current proof-of-work(PoW) techniques for systems like Bitcoin require that correct devices perform computational work perpetually, even when the system is not under attack. Our result addresses this issue by designing a general PoW protocol that ensures two properties. First, the network stays secure. In particular, the fraction of identities in the system that are controlled by an attacker is always less than 1/2. Second, our protocol??s computational cost is commensurate with the cost of an attacker. In particular, the total computational cost of correct devices is a linear function of the attackers computational cost plus the number of correct devices that have joined the system. Consequently, if the network is attacked, we ensure security, with cost that grows linearly with the attackers cost; and, in the absence of attack, our computational cost remains small. We prove similar guarantees for bandwidth cost.
Second, we designed cost-competitive algorithms for the problem of Interactive communication, where two parties are trying to compute over a noisy channel. Specifically, we described an algorithm for a two party reliable computation, where the resource costs of both parties scale well with the number of bits that are (adversarially) corrupted on the channel. To the best of our knowledge, it is the first such result. Plans for future work include extending this result to more than two parties.
Thirdly, we designed cost-competitive algorithms for distributing access points (i.e. bridges) to an anti-censorship network (ToR). Specifically, if there are t nodes controlled by an adversary out of n total nodes, then our algorithm requires distributing no more than O(t log n) bridges. Applications include enabling people in countries where censorship occurs to more easily access all of the Internet.
Finally, this project has supported four PhD students, Abhinav Aggarwal, Mahnush Movahedi (female), Aaron Kearns and Mahdi Zamani. Mahnush graduated 2015, and after post docs at UVA and Yale, is now a senior researcher at DFINITY. Mahdi Zamani also graduated in 2015, and after a post doc at Yale is now a Research Scientist at Visa Research. Aaron Kearns graduated with an MS in 2016 and is now employed by the Albuquerque Seismic Lab. Abhinav Aggarwal is expected to earn his PhD in 2020. He gave his first conference presentation in 2018.
Last Modified: 10/01/2018
Modified by: Jared C Saia
Please report errors in award information by writing to: awardsearch@nsf.gov.
