In this paper, we investigate the effect of participating as a near-peer mentor for computing activities in undergraduate courses across disciplines. Many studies on near-peer mentorship have demonstrated academic and professional growth--as well as an increase in self-efficacy--of mentees. In this paper, we focus on how participation as a mentor in an undergraduate Computing Fellows program contributes to the strengthening and expansion of the mentors' computing identity through their interactions in the program, including via investigation of the mutual benefits of the program on mentees and mentors. The Computing Fellows program "attaches" near-peer mentors to undergraduate courses across the sciences, social sciences, humanities, and the arts. The mentors support the integration of computing into courses through activities including in-class workshops and drop-in office hours. In a mixed-methods study, we conducted semi-structured interviews over two years with mentors (all of whom identify as women) after their participation and we cross-reference the results with course evaluation data. We find that fellows' experience in the program, both as near-peer mentors and through their engagement in critical discussions about computing and computing pedagogy as part of their training, expands and deepens their computing identity and the various ways they can engage with computing in their lives in and beyond college.

We describe initial research results investigating the impact of a new Computing Fellows program. The program provides computing-related peer mentoring and teaching in undergraduate courses across disciplines. Results suggest that the program positively contributes to both fellows and students engagement with computing.

We describe our experience developing and running a Computer Science Living-Learning Community (LLC) for first-year women at Rutgers University, now in its third year. Each year, around 20 first-year undergraduate women who intend to major in computer science (CS) apply and are selected to participate. LLC participants live in a common residence hall and are provided with an educational, mentoring, and community-building program that supports their progress as students and CS majors. Participants take a "house course," Great Ideas and Insights in Computer Science, as a group, and also take a course on Knowledge and Power: Issues in Women's Leadership. Program activities include study sessions and industry interactions, as well as opportunities to participate in K-12 outreach programs, hackathons, and computing research. To evaluate the program, participants and a similar comparison group are surveyed at the beginning and end of the academic year and a focus group is conducted with program participants. Program participants find the program valuable and would recommend it to others, but both program participants and the comparison group report some lack of confidence in their potential success as computer scientists.

We have developed the Douglass-SAS-DIMACS Computer Science Living-Learning Community (LLC) for first-year women at Rutgers, now in its second year. Each year, around 20 first-year women undergraduates at Rutgers who intend to major in computer science are selected for the LLC. LLC participants live in a common dorm and are provided with an educational, mentoring, and community-building program that supports their progress as Rutgers students and as computer science majors. To our knowledge, this is the first undergraduate living-learning community for women in computer science at any university. A focus group conducted with women from the inaugural cohort revealed that faculty support contributed to feelings of belonging, both in the program and in the CS department, among the participants; participants valued the academic support they received as part of the program and felt communication structures within the program were effective; and participants expressed a desire for advanced undergraduate peer mentors. A quasi-experimental study of this cohort indicated that LLC participants showed a decrease in satisfaction with the CS department at Rutgers; a decrease in computing-related self-efficacy; and an increase in the belief that computing ability is inborn. Follow up interviews suggested that the efficacy of the LLC might be dependent on two factors: participants' commitment to a CS major coming into the program and participants' level of involvement with the LLC group. In response to these results, we have made some changes to the program and continue to carefully study the program in order to maximize its effectiveness.

We discuss the widely increasing range of applications of a cryptographic technique called multi-party computation. For many decades, this was perceived to be of purely theoretical interest, but now it has started to find application in a number of use cases. We highlight in this paper a number of these, ranging from securing small high-value items such as cryptographic keys, through to securing an entire database.

Abstract Machine learning algorithms based on deep Neural Networks (NN) have achieved remarkable results and are being extensively used in different domains. On the other hand, with increasing growth of cloud services, several Machine Learning as a Service (MLaaS) are offered where training and deploying machine learning models are performed on cloud providers’ infrastructure. However, machine learning algorithms require access to the raw data which is often privacy sensitive and can create potential security and privacy risks. To address this issue, we present CryptoDL, a framework that develops new techniques to provide solutions for applying deep neural network algorithms to encrypted data. In this paper, we provide the theoretical foundation for implementing deep neural network algorithms in encrypted domain and develop techniques to adopt neural networks within practical limitations of current homomorphic encryption schemes. We show that it is feasible and practical to train neural networks using encrypted data and to make encrypted predictions, and also return the predictions in an encrypted form. We demonstrate applicability of the proposed CryptoDL using a large number of datasets and evaluate its performance. The empirical results show that it provides accurate privacy-preserving training and classification.

Models of human mobility have broad applicability in urban planning, ecology, epidemiology, and other fields. Starting with Call Detail Records (CDRs) from a cellular telephone network that have gone through a straightforward anonymization procedure, the prior WHERE modeling approach produces synthetic CDRs for a synthetic population. The accuracy of WHERE has been validated against billions of location samples for hundreds of thousands of cell phones in the New York and Los Angeles metropolitan areas. In this paper, we introduce DP-WHERE, which modifies WHERE by adding controlled noise to achieve differential privacy, a strict definition of privacy that makes no assumptions about the power or background knowledge of a potential adversary. We also present experiments showing that the accuracy of DP-WHERE remains close to that of WHERE and of real CDRs. With this work, we aim to enable the creation and possible release of synthetic models that capture the mobility patterns of real metropolitan populations while preserving privacy.

We present a framework for the design and analysis of probing methods to monitor network performance, an important technique for collecting measurements in tasks such as fault detection. We use this framework to study the interaction among numerous, possibly conflicting, optimization goals in the design of a probing algorithm. We present a rigorous definition of a probing-algorithm design problem that can apply broadly to network-measurement scenarios. We also present several metrics relevant to the analysis of probing algorithms, including probing frequency and network coverage, communication and computational overhead, and the amount of algorithm state required. We show inherent tradeoffs among optimization goals and give hardness results for achieving some combinations of optimization goals. We also consider the possibility of developing approximation algorithms for achieving some of the goals and describe a randomized approach as an alternative, evaluating it using our framework. Our work aids future development of low-overhead probing techniques and introduces principles from IP-based networking to theoretically grounded approaches for concurrent path-selection problems.

We propose a focus on accountability as a mechanism for ensuring security in information systems. To that end, we present a formal definition of it accountability in information systems. Our definition is more general and potentially more widely applicable than the accountability notions that have previously appeared in the security literature. In particular, we treat in a unified manner scenarios in which accountability is enforced automatically and those in which enforcement must be mediated by an authority; similarly, our formalism includes scenarios in which the parties who are held accountable can remain anonymous and those in which they must be identified by the authorities to whom they are accountable. Essential elements of our formalism include event traces and it utility functions and the use of these to define punishment and related notions.

We present our recent work (ICS 2011) on dynamic environments in which computational nodes, or decision makers, follow simple and unsophisticated rules of behavior (e.g., repeatedly "best replying" to others' actions, and minimizing "regret") that have been extensively studied in game theory and economics. We aim to understand when convergence of the resulting dynamics to an equilibrium point is guaranteed if nodes' interaction is not synchronized (e.g., as in Internet protocols and large-scale markets). We take the first steps of this research agenda. We exhibit a general non-convergence result and consider its implications across a wide variety of interesting and timely applications: routing, congestion control, game theory, social networks and circuit design. We also consider the relationship between classical nontermination results in distributed computing theory and our result, explore the impact of scheduling on convergence, study the computational and communication complexity of asynchronous dynamics and present some basic observations regarding the effects of asynchrony on no-regret dynamics.

Consider fully dynamic data, where we track data as it gets inserted and deleted. There are well developed notions of private data analyses with dynamic data, for example, using differential privacy. We want to go beyond privacy, and consider privacy together with security, formulated recently as pan-privacy by Dwork et al. (ICS 2010). Informally, pan-privacy preserves differential privacy while computing desired statistics on the data, even if the internal memory of the algorithm is compromised (say, by a malicious break-in or insider curiosity or by fiat by the government or law).

Autonomous routing algorithms, such as BGP, are intended to reach a globally consistent set of routes after nodes iteratively and independently collect, process, and share network information. Generally, the important role of the mechanism used to share information has been overlooked in previous analyses of these algorithms. In this paper, we explicitly study how the network-communication model affects algorithm convergence. To do this, we consider a variety of factors, including channel reliability, how much information is processed from channels, and how many channels are processed simultaneously. Using these factors, we define a taxonomy of communication models and identify particular models of interest, including those used in previous theoretical work, those that most closely model real-world implementations of BGP, and those of potential interest for the design of future routing algorithms. We characterize an extensive set of relationships among models in our taxonomy and show that convergence depends on the communication model in nontrivial ways. These results highlight that certain models are best for proving conditions that guarantee convergence, while other models are best for characterizing conditions that might permit nonconvergence.

We consider the problem of distributed reinforcement learning (DRL) from private perceptions. In our setting, agents' perceptions, such as states, rewards, and actions, are not only distributed but also should be kept private. Conventional DRL algorithms can handle multiple agents, but do not necessarily guarantee privacy preservation and may not guarantee optimality. In this work, we design cryptographic solutions that achieve optimal policies without requiring the agents to share their private information.

We study situations in which autonomous systems (ASes) may have incentives to send BGP announcements differing from the AS-level paths that packets traverse in the data plane. Prior work on this issue assumed that ASes seek only to obtain the best possible outgoing path for their traffic. In reality, other factors can influence a rational AS's behavior. Here we consider a more natural model, in which an AS is also interested in attracting incoming traffic (e.g., because other ASes pay it to carry their traffic). We ask what combinations of BGP enhancements and restrictions on routing policies can ensure that ASes have no incentive to lie about their data-plane paths. We find that protocols like S-BGP alone are insufficient, but that S-BGP does suffice if coupled with additional (quite unrealistic) restrictions on routing policies. Our game-theoretic analysis illustrates the high cost of ensuring that the ASes honestly announce data-plane paths in their BGP path announcements.

No abstract available.

We present a simple I/O-efficient k-clustering algorithm that was designed with the goal of enabling a privacy-preserving version of the algorithm. Our experiments show that this algorithm produces cluster centers that are, on average, more accurate than the ones produced by the well known iterative A;-means algorithm. We use our new algorithm as the basis for a communication-efficient privacy-preserving k-clustering protocol for databases that are horizontally partitioned between two parties. Unlike existing privacy-preserving protocols based on the A;-means algorithm, this protocol does not reveal intermediate candidate cluster centers.

Approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting where the inputs are held by different parties and may be extremely large. Furthermore, for some applications, the parties want to compute a function of their inputs securely without revealing more information than necessary. In this work, we study the question of simultaneously addressing the above efficiency and security concerns via what we call secure approximations. We start by extending standard definitions of secure (exact) computation to the setting of secure approximations. Our definitions guarantee that no additional information is revealed by the approximation beyond what follows from the output of the function being approximated. We then study the complexity of specific secure approximation problems. In particular, we obtain a sublinear-communication protocol for securely approximating the Hamming distance and a polynomial-time protocol for securely approximating the permanent and related #P-hard problems.

Traditionally, many data mining techniques have been designed in the centralized model in which all data is collected and available in one central site. However, as more and more activities are carried out using computers and computer networks, the amount of potentially sensitive data stored by business, governments, and other parties increases. Different parties often wish to benefit from cooperative use of their data, but privacy regulations and other privacy concerns may prevent the parties from sharing their data. Privacy-preserving data mining provides a solution by creating distributed data mining algorithms in which the underlying data need not be revealed. In this paper, we present privacy-preserving protocols for a particular data mining task: learning a Bayesian network from a database vertically partitioned among two parties. In this setting, two parties owning confidential databases wish to learn the Bayesian network on the combination of their databases without revealing anything else about their data to each other. We present an efficient and privacy-preserving protocol to construct a Bayesian network on the parties' joint data

Advances in computer networking and database technologies have enabled the collection and storage of vast quantities of data. Data mining can extract valuable knowledge from this data, and organizations have realized that they can often obtain better results by pooling their data together. However, the collected data may contain sensitive or private information about the organizations or their customers, and privacy concerns are exacerbated if data is shared between multiple organizations.Distributed data mining is concerned with the computation of models from data that is distributed among multiple participants. Privacy-preserving distributed data mining seeks to allow for the cooperative computation of such models without the cooperating parties revealing any of their individual data items. Our paper makes two contributions in privacy-preserving data mining. First, we introduce the concept of arbitrarily partitioned data, which is a generalization of both horizontally and vertically partitioned data. Second, we provide an efficient privacy-preserving protocol for k-means clustering in the setting of arbitrarily partitioned data.

Protection of privacy has become an important problem in data mining. In particular, individuals have become increasingly unwilling to share their data, frequently resulting in individuals either refusing to share their data or providing incorrect data. In turn, such problems in data collection can affect the success of data mining, which relies on sufficient amounts of accurate data in order to produce meaningful results. Random perturbation and randomized response techniques can provide some level of privacy in data collection, but they have an associated cost in accuracy. Cryptographic privacy-preserving data mining methods provide good privacy and accuracy properties. However, in order to be efficient, those solutions must be tailored to specific mining tasks, thereby losing generality. In this paper, we propose efficient cryptographic techniques for online data collection in which data from a large number of respondents is collected anonymously, without the help of a trusted third party. That is, our solution allows the miner to collect the original data from each respondent, but in such a way that the miner cannot link a respondent’s data to the respondent. An advantage of such a solution is that, because it does not change the actual data, its success does not depend on the underlying data mining problem. We provide proofs of the correctness and privacy of our solution, as well as experimental data that demonstrates its efficiency. We also extend our solution to tolerate certain kinds of malicious behavior of the participants. 1.

In order to protect individuals' privacy, the technique of k-anonymization has been proposed to de-associate sensitive attributes from the corresponding identifiers. In this paper, we provide privacy-enhancing methods for creating k-anonymous tables in a distributed scenario. Specifically, we consider a setting in which there is a set of customers, each of whom has a row of a table, and a miner, who wants to mine the entire table. Our objective is to design protocols that allow the miner to obtain a k-anonymous table representing the customer data, in such a way that does not reveal any extra information that can be used to link sensitive attributes to corresponding identifiers, and without requiring a central authority who has access to all the original data. We give two different formulations of this problem, with provably private solutions. Our solutions enhance the privacy of k-anonymization in the distributed scenario by maintaining end-to-end privacy from the original customer data to the final k-anonymous results.

Privacy has become an increasingly important issue in data mining. In this paper, we consider a scenario in which a data miner surveys a large number of customers to learn classification rules on their data, while the sensitive attributes of these customers need to be protected. Solutions have been proposed to address this problem using randomization techniques. Such solutions exhibit a tradeoff of accuracy and privacy: the more each customer's private information is protected, the less accurate result the miner obtains; conversely, the more accurate the result, the less privacy for the customers. In this paper, we propose a simple cryptographic approach that is efficient even in a many-customer setting, provides strong privacy for each customer, and does not lose any accuracy as the cost of privacy. Our key technical contribution is a privacy-preserving method that allows a data miner to compute frequencies of values or tuples of values in the customers’ data, without revealing the privacy-sensitive part of the data. Unlike general-purpose cryptographic protocols, this method requires no interaction between customers, and each customer only needs to send a single flow of communication to the data miner. However, we are still able to ensure that nothing about the sensitive data beyond the desired frequencies is revealed to the data miner. To illustrate the power of our approach, we use our frequency mining computation to obtain a privacy-preserving naive Bayes classifier learning algorithm. Initial experimental results demonstrate the practical efficiency of our solution. We also suggest some other applications of privacy-preserving frequency mining.

As more and more activities are carried out using computers and computer networks, the amount of potentially sensitive data stored by business, governments, and other parties increases. Different parties may wish to benefit from cooperative use of their data, but privacy regulations and other privacy concerns may prevent the parties from sharing their data. Privacy-preserving data mining provides a solution by creating distributed data mining algorithms in which the underlying data is not revealed.In this paper, we present a privacy-preserving protocol for a particular data mining task: learning the Bayesian network structure for distributed heterogeneous data. In this setting, two parties owning confidential databases wish to learn the structure of Bayesian network on the combination of their databases without revealing anything about their data to each other. We give an efficient and privacy-preserving version of the K2 algorithm to construct the structure of a Bayesian network for the parties' joint data.

This note is prepared for Michael Fischer's 60th birthday celebration at PODC 2003. In it, I briefly describe some of Michael Fischer's work on distributed cryptographic protocols.

Distributed systems inherently involve dynamic changes to the value of security-relevant attributes such as the goodness of encryption keys, trustworthiness of participants, and synchronization between principals. Since concurrent knowledge is usually infeasible or impractical, it is often necessary for the participants of distributed protocols to determine and act on beliefs that may not be supported by the current state of the system. Policies for determining beliefs in such situations can range from extremely conservative, such as only believing statements if they are very recent, to extremely optimistic, such as believing all statements that are not yet known to be revoked. Such security policies often are heavily dependent on timing of received messages and on synchronization between principals. We present a logic for analyzing cryptographic protocols that has the capability to specify time and synchronization details. This capability considerably advances the scope of known techniques both for expressing practical authentication policies of protocol participants as constraints and for reasoning about protocol goals subject to these constraints.

Motivated by the application of private statistical analysis of large databases, we consider the problem of selective private function evaluation (SPFE). In this problem, a client inter-acts with one or more servers holding copies of a database z = zt,...,z, in order to compute f(z~t,...,z~,,,) , for some function f and indices i = it,...,i, ~ chosen by the client. Ideally, the client must learn nothing more about the database than f(zit,..., zi,,~), and the servers should learn nothing. Generic solutions for this problem, based on standard techniques for secure function evaluation, incur communi-cation complexity that is at least linear in n, making them prohibitive for large databases even when f is relatively sim-ple and m is small. We present various approaches for con-structing sublinear-communication $PFE protocols, both for the general problem and for special cases of interest. Our so-lutions not only offer sublinear communication complexity, but are also practical in many scenarios. 1.

We consider scalable certificate revocation in a public-key infrastructure (PKI). We introduce depender graphs, a new class of graphs that support efficient and fault-tolerant revocation. Nodes of a depender graph are participants that agree to forward revocation information to other participants. Our depender graphs are k-redundant, so that revocations are provably guaranteed to be received by all non-failed participants even if up to k−1 participants have failed. We present a protocol for constructing k-redundant depender graphs that has two desirable properties. First, it is load-balanced, in that no participant need have too many dependers. Second, it is localized, in that it avoids the need for any participant to maintain the global state of the depender graph. We also give a localized protocol for restructuring the graph in the event of permanent failures.

We consider scalable certificate revocation in a public-key infrastructure (PKI). We introduce depender graphs, a new class of graphs that support efficient and fault-tolerant revocation. Nodes of a depender graph are participants that agree to forward revocation information to other participants. Our depender graphs are k-redundant, so that revocations are provably guaranteed to be received by all nonfailed participants even if up to k \\Gamma1 participants have failed. We present a protocol for constructing k-redundant depender graphs that has two desirable properties. First, it is load-balanced, in that no participant need have too many dependers. Second, it is localized, in that it avoids the need for any participant to maintain the global state of the depender graph. We also give a localized protocol for restructuring the graph in the event of permanent failures. 1. INTRODUCTION Public keys and their certificates eventually become invalid. Most certificates have an expiration dat...

In the real world, insurance is used to mitigate financial risk to individuals in many settings. Similarly, it has been suggested that insurance can be used in distributed systems, and in particular, in authentication procedures, to mitigate an individual's risks there. We further explore the use of insurance for public-key certificates and other kinds of statements. We also describe an application using threshold cryptography in which insured keys would also have an auditor involved in any transaction using the key, allowing the insurer better control over its liability. We provide a formal yet simple insurance logic that can be used to deduce the amount of insurance associated with statements based on the insurance associated with related statements. Using the logic, we show how trust relationships and insurance can work together to provide confidence.

Byzantine quorum systems enhance the availability and efficiency of fault-tolerant replicated services when servers may suffer Byzantine failures. An important limitation of Byzantine quorum systems is their dependence on a static threshold limit on the number of server faults. The correctness of the system is only guaranteed if the actual number of faults is lower than the the threshold at all times. However, a threshold chosen for the worst case wastes expensive replication in the common situation where the number of faults averages well below the worst case. In this paper, we present protocols for dynamically raising and lowering the resilience threshold of a quorum-based Byzantine fault-tolerant data service in response to current information on the number of server failures. Using such protocols, a system can operate in an efficient low-threshold mode with relatively small quorums in the absence of faults, increasing and decreasing the quorum size (and thus the tolerance) as faults appear and are dealt with, respectively.

In this paper we present probabilistic masking quorum systems, a technique for replicating data that can mask, with high probability, the arbitrary (Byzantine) failure of data servers from clients. This technique generalizes previous work on probabilistic quorum systems to mask Byzantine server failures in their full generality, and improves over previous masking quorum systems by offering better data availability and access efficiency. We define probabilistic masking quorum systems, demonstrate a novel access protocol for implementing replicated data with them, and prove general and tight lower bounds on the performance that they can achieve. We also present a probabilistic masking quorum construction that outperforms strict masking constructions in measures of both availability and efficiency.

Services replicated using a quorum system allow operations to be performed at only a subset (quorum) of the servers, and ensure consistency among operations by requiring that any two quorums intersect. In this paper we explore the consequences of requiring this intersection property to hold only with very high probability. We show that doing so can offer dramatic improvements in the performance and availability of the service, both for services tolerant of benign server failures and services tolerant of arbitrary (Byzantine) ones. We also prove a lower bound on the performance that can be achieved with this technique. 1 Introduction Quorums are tools for increasing the availability and efficiency of replicated services. A quorum system is a set of subsets of servers, every pair of which intersect. Intuitively, the intersection property guarantees that if a "write" operation is performed at one quorum, and later a "read" operation at another quorum, then there is some server that obse...

In this paper we i.ntroduce R, a distributed public key management service for open networks. f’l offers interfaces by which clients can register, retrieve, and revoke public keys, and escrow, use (to decrypt messages), and recover private keys, all of which can be subjected to access control policy. R is built using multiple servers in a way that ensures its correct operation despite the malicious corruption of fewer than one-third of its component servers. We describe the design of R, the protocols underlying its operation, performance in our present implementation, and an experimental application of the service.

Distributed systems inherently involve dynamic changes to the value of security attributes such as the goodness of encryption keys.Since concurrent knowledge is usually infeasible or impractical, it is often necessary for the participants of distributed protocols to determine and act on beliefs that may not be supported by the current state of the system.Policies for determining beliefs in such situations can range from extremely conservative, such as only believing statements if they are very recent, to extremely optimistic, such as believing all statements that are not yet known to be revoked.Such security policies often are heavily dependent on timing of received messages and on synchronization between principals.We present a. logic for analyzing cryptographic protocols that has the capability to specify time and synchronization details.This capability considerably advances the scope of known techniques for both expressing practical authentication policies of protocol participants as constraints, and for reasoning about protocol goals subject to these constraints.In the course of reasoning about protocol goals, one is able to deduce requirements for trust between protocol participants, synchronization between protocol participants, and timeliness of message contents.Our logic is flexible, and can support a wide range of security policies.The ability to reason about the conjunction of individual participant policies and protocols will be especially important as public and private key infrastructures are deployed and new and unanticipated policies are put into use.

In this paper we introduce Ω, a distributed public key management service for open networks. Ω offers interfaces by which clients can register, retrieve, and revoke public keys, and escrow, use (to decrypt messages), and recover private keys, all of which can be subjected to access control policy. Ω is built using multiple servers in a way that ensures its correct operation despite the malicious corruption of fewer than one-third of its component servers. We describe the design of Ω, the protocols underlying its operation, performance in our present implementation, and an experimental application of the service.

Phrase-structure grammars are an effective representation for important syntactic and semantic aspects of natural languages, but are computationally too demanding for use as language models in real-time speech recognition. An algorithm is described that computes finite-state approximations for context-free grammars and equivalent augmented phrase-structure grammar formalisms. The approximation is exact for certain context-free grammars generating regular languages, including all left-linear and right-linear context-free grammars. The algorithm has been used to construct finite-state language models for limited-domain speech recognition tasks.