Memoryhard functions (MHFs) are a key cryptographic primitive underlying the design of moderately expensive password hashing algorithms and egalitarian proofs of work. Over the past few years several increasingly stringent goals for an MHF have been proposed including the requirement that the MHF have high sequential spacetime (ST) complexity, parallel spacetime complexity, amortized areatime (aAT) complexity and sustained space complexity. DataIndependent Memory Hard Functions (iMHFs) are of special interest in the context of password hashing as they naturally resist sidechannel attacks. iMHFs can be specified using a directed acyclic graph (DAG) $G$ with $N=2^n$ nodes and low indegree and the complexity of the iMHF can be analyzed using a pebbling game. Recently, Alwen et al. [CCS'17] constructed an DAG called DRSample which has aAT complexity at least $\Omega\left( N^2/\log N\right)$. Asymptotically DRSample outperformed all prior iMHF constructions including Argon2i, winner of the password hashing competition (aAT cost $\mathcal{O}\left(N^{1.767}\right)$), though the constants in these bounds are poorly understood. We show that the the greedy pebbling strategy of Boneh et al. [ASIACRYPT'16] is particularly effective against DRSample e.g., the aAT cost is $\mathcal{O}\left( N^2/\log N\right)$. In fact, our empirical analysis {\em reverses} the prior conclusion of Alwen et al. that DRSample provides stronger resistance to known pebbling attacks for practical values of $N \leq 2^{24}$. We construct a new iMHF candidate (DRSample+BRG) by using the bitreversal graph to extend DRSample. We then prove that the construction is asymptotically optimal under every MHF criteria, and we empirically demonstrate that our iMHF provides the best resistance to {\em known} pebbling attacks. For example, we show that any parallel pebbling attack either has aAT cost $\omega(N^2)$ or requires at least $\Omega(N)$ steps with $\Omega(N/\log N)$ pebbles on the DAG. This makes our construction the first practical iMHF with a strong sustained spacecomplexity guarantee and immediately implies that any parallel pebbling has aAT complexity $\Omega(N^2/\log N)$. We also prove that any sequential pebbling (including the greedy pebbling attack) has aAT cost $\Omega\left( N^2\right)$ and, if a plausible conjecture holds, any parallel pebbling has aAT cost $\Omega(N^2 \log \log N/\log N)$  the best possible bound for an iMHF.
We implement our new iMHF and demonstrate that it is just as fast as Argon2. Along the way we propose a simple modification to the Argon2 round function which increases an attacker's aAT cost by nearly an order of magnitude without increasing running time on a CPU. Finally, we give a pebbling reduction which proves that in the parallel random oracle model (PROM) the cost of evaluating an iMHF like Argon2i or DRSample+BRG is given by the pebbling cost of the underlying DAG. Prior pebbling reductions assumed that the iMHF round function concatenates input labels before hashing and did not apply to practical iMHFs such as Argon2i, DRSample or DRSample+BRG where input labels are instead XORed together.
more »
« less
PREEMPT: Scalable Epidemic Interventions Using Submodular Optimization on MultiGPU Systems
Preventing and slowing the spread of epidemics
is achieved through techniques such as vaccination and social
distancing. Given practical limitations on the number of vaccines
and cost of administration, optimization becomes a necessity.
Previous approaches using mathematical programming methods
have shown to be effective but are limited by computational
costs. In this work, we present PREEMPT, a new approach for
intervention via maximizing the influence of vaccinated nodes on
the network.We prove submodular properties associated with the
objective function of our method so that it aids in construction
of an efficient greedy approximation strategy. Consequently, we
present a new parallel algorithm based on greedy hill climbing
for PREEMPT, and present an efficient parallel implementation
for distributed CPUGPU heterogeneous platforms. Our results
demonstrate that PREEMPT is able to achieve a significant
reduction (up to 6:75) in the percentage of people infected
and up to 98% reduction in the peak of the infection on a cityscale
network. We also show strong scaling results of PREEMPT
on up to 128 nodes of the Summit supercomputer. Our parallel
implementation is able to significantly reduce time to solution,
from hours to minutes on large networks. This work represents
a firstofitskind effort in parallelizing greedy hill climbing and
applying it toward devising effective interventions for epidemics.
more »
« less
 NSFPAR ID:
 10213737
 Date Published:
 Journal Name:
 International Conference for High Performance Computing Networking Storage and Analysis
 ISSN:
 21674337
 Page Range / eLocation ID:
 765799
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


One of the major challenges in parallelization is the difficulty of improving application scalability with conventional techniques. HPX provides efficient scalable parallelism by significantly reducing node starvation and effective latencies while controlling the overheads. In this paper, we present a new highly scalable parallel distributed NBody application using a futurebased algorithm, which is implemented with HPX. The main difference between this algorithm and prior art is that a futurebased request buffer is used between different nodes and along each spatial direction to send/receive data to/from the remote nodes, which helps removing synchronization barriers. HPX provides an asynchronous programming model which results in improving the parallel performance. The results of using HPX for parallelizing Octree construction on one node and the force computation on the distributed nodes show the scalability improvement on an average by about 45% compared to an equivalent OpenMP implementation and 28% compared to a hybrid implementation (MPI+OpenMP) [1] respectively for one billion particles running on up to 128 nodes with 20 cores per each.more » « less

ABSTRACT Efficient contact tracing and isolation is an effective strategy to control epidemics, as seen in the Ebola epidemic and COVID19 pandemic. An important consideration in contact tracing is the budget on the number of individuals asked to quarantine—the budget is limited for socioeconomic reasons (e.g., having a limited number of contact tracers). Here, we present a Markov Decision Process (MDP) framework to formulate the problem of using contact tracing to reduce the size of an outbreak while limiting the number of people quarantined. We formulate each step of the MDP as a combinatorial problem, MinExposed, which we demonstrate is NPHard. Next, we develop two approximation algorithms, one based on rounding the solutions of a linear program and another (greedy algorithm) based on choosing nodes with a high (weighted) degree. A key feature of the greedy algorithm is that it does not need complete information of the underlying social contact network, making it implementable in practice. Using simulations over realistic networks, we show how the algorithms can help in bending the epidemic curve with a limited number of isolated individuals.more » « less

Efficient contact tracing and isolation is an effective strategy to control epidemics, as seen in the Ebola epidemic and COVID19 pandemic. An important consideration in contact tracing is the budget on the number of individuals asked to quarantine—the budget is limited for socioeconomic reasons (e.g., having a limited number of contact tracers). Here, we present a Markov Decision Process (MDP) framework to formulate the problem of using contact tracing to reduce the size of an outbreak while limiting the number of people quarantined. We formulate each step of the MDP as a combinatorial problem, MinExposed, which we demonstrate is NPHard. Next, we develop two approximation algorithms, one based on rounding the solutions of a linear program and another (greedy algorithm) based on choosing nodes with a high (weighted) degree. A key feature of the greedy algorithm is that it does not need complete information of the underlying social contact network, making it implementable in practice. Using simulations over realistic networks, we show how the algorithms can help in bending the epidemic curve with a limited number of isolated individuals.more » « less

Evaluating AMR parsing accuracy involves comparing pairs of AMR graphs. The major evaluation metric, SMATCH (Cai and Knight,2013), searches for onetoone mappings between the nodes of two AMRs with a greedy hillclimbing algorithm, which leads to search errors. We propose SEMBLEU, a robust metric that extends BLEU (Papineni et al., 2002) to AMRs. It does not suffer from search errors and considers nonlocal correspondences in addition to local ones. SEMBLEU is fully contentdriven and punishes situations where a system’s output does not preserve most information from the input. Preliminary experiments on both sentence and corpus levels show that SEMBLEU has slightly higher consistency with human judgments than SMATCH. Our code is available athttp://github.com/freesunshine0316/sembleu.more » « less