Di Wang, Xiangyu Guo, Chaowen Guan, Shi Li · 5 authors
Recently, many machine learning and statistical models such as non-linear regressions, the Single Index, Multi-index, Varying Coefficient Index Models and Two-layer Neural Networks can be reduced to or be seen as a special case of a new model which is called the \textit{Stochastic Linear Combination of Non-linear Regressions} model. However, due to the high non-convexity of the problem, there is no previous work study how to estimate the model. In this paper, we provide the first study on how to estimate the model efficiently and scalably. Specifically, we first show that with some mild assumptions, if the variate vector $x$ is multivariate Gaussian, then there is an algorithm whose output vectors have $\ell_2$-norm estimation errors of $O(\sqrt{\frac{p}{n}})$ with high probability, where $p$ is the dimension of $x$ and $n$ is the number of samples. The key idea of the proof is based on an observation motived by the Stein's lemma. Then we extend our result to the case where $x$ is bounded and sub-Gaussian using the zero-bias transformation, which could be seen as a generalization of the classic Stein's lemma. We also show that with some additional assumptions there is an algorithm whose output vectors have $\ell_\infty$-norm estimation errors of $O(\frac{1}{\sqrt{p}}+\sqrt{\frac{p}{n}})$ with high probability. We also provide a concrete example to show that there exists some link function which satisfies the previous assumptions. Finally, for both Gaussian and sub-Gaussian cases we propose a faster sub-sampling based algorithm and show that when the sub-sample sizes are large enough then the estimation errors will not be sacrificed by too much. Experiments for both cases support our theoretical results. To the best of our knowledge, this is the first work that studies and provides theoretical guarantees for the stochastic linear combination of non-linear regressions model.
Md Sadek Ferdous, Mohammad Jabed Morshed Chowdhury, Mohammad A. Hoque, Alan Colman
In recent years, blockchain technology has received unparalleled attention from academia, industry, and governments all around the world. It is considered a technological breakthrough anticipated to disrupt several application domains. This has resulted in a plethora of blockchain systems for various purposes. However, many of these blockchain systems suffer from serious shortcomings related to their performance and security, which need to be addressed before any wide-scale adoption can be achieved. A crucial component of any blockchain system is its underlying consensus algorithm, which in many ways, determines its performance and security. Therefore, to address the limitations of different blockchain systems, several existing as well novel consensus algorithms have been introduced. A systematic analysis of these algorithms will help to understand how and why any particular blockchain performs the way it functions. However, the existing studies of consensus algorithms are not comprehensive. Those studies have incomplete discussions on the properties of the algorithms and fail to analyse several major blockchain consensus algorithms in terms of their scopes. This article fills this gap by analysing a wide range of consensus algorithms using a comprehensive taxonomy of properties and by examining the implications of different issues still prevalent in consensus algorithms in detail. The result of the analysis is presented in tabular formats, which provides a visual illustration of these algorithms in a meaningful way. We have also analysed more than hundred top crypto-currencies belonging to different categories of consensus algorithms to understand their properties and to implicate different trends in these crypto-currencies. Finally, we have presented a decision tree of algorithms to be used as a tool to test the suitability of consensus algorithms under different criteria.
In fifth-generation (5G) networks and beyond, communication latency and network bandwidth will be no longer be bottlenecks to mobile users. Thus, almost every mobile device can participate in distributed learning. That is, the availability issue of distributed learning can be eliminated. However, model safety will become a challenge. This is because the distributed learning system is prone to suffering from byzantine attacks during the stages of updating model parameters and aggregating gradients among multiple learning participants. Therefore, to provide the byzantine-resilience for distributed learning in the 5G era, this article proposes a secure computing framework based on the sharding technique of blockchain, namely PiRATE. To prove the feasibility of the proposed PiRATE, we implemented a prototype. A case study shows how the proposed PiRATE contributes to distributed learning. Finally, we also envision some open issues and challenges based on the proposed byzantine- resilient learning framework.
For the modern world where data is becoming one of the most valuable assets,\nrobust data privacy policies rooted in the fundamental infrastructure of\nnetworks and applications are becoming an even bigger necessity to secure\nsensitive user data. In due course with the ever-evolving nature of newer\nstatistical techniques infringing user privacy, machine learning models with\nalgorithms built with respect for user privacy can offer a dynamically adaptive\nsolution to preserve user privacy against the exponentially increasing\nmultidimensional relationships that datasets create. Using these privacy aware\nML Models at the core of a Federated Learning Ecosystem can enable the entire\nnetwork to learn from data in a decentralized manner. By harnessing the\never-increasing computational power of mobile devices, increasing network\nreliability and IoT devices revolutionizing the smart devices industry, and\ncombining it with a secure and scalable, global learning session backed by a\nblockchain network with the ability to ensure on-device privacy, we allow any\nInternet enabled device to participate and contribute data to a global privacy\npreserving, data sharing network with blockchain technology even allowing the\nnetwork to reward quality work. This network architecture can also be built on\ntop of existing blockchain networks like Ethereum and Hyperledger, this lets\neven small startups build enterprise ready decentralized solutions allowing\nanyone to learn from data across different departments of a company, all the\nway to thousands of devices participating in a global synchronized learning\nnetwork.\n
Although Federated Learning allows for participants to contribute their local data without it being revealed, it faces issues in data security and in accurately paying participants for quality data contributions. In this paper, we propose an EOS Blockchain design and workflow to establish data security, a novel validation error based metric upon which we qualify gradient uploads for payment, and implement a small example of our blockchain Federated Learning model to analyze its performance.
David Froelicher, Juan Ramón Troncoso-Pastoriza, João Sá Sousa, Jean‐Pierre Hubaux
Data sharing has become of primary importance in many domains such as big-data analytics, economics and medical research, but remains difficult to achieve when the data are sensitive. In fact, sharing personal information requires individuals' unconditional consent or is often simply forbidden for privacy and security reasons. In this paper, we propose Drynx, a decentralized system for privacy-conscious statistical analysis on distributed datasets. Drynx relies on a set of computing nodes to enable the computation of statistics such as standard deviation or extrema, and the training and evaluation of machine-learning models on sensitive and distributed data. To ensure data confidentiality and the privacy of the data providers, Drynx combines interactive protocols, homomorphic encryption, zero-knowledge proofs of correctness, and differential privacy. It enables an efficient and decentralized verification of the input data and of all the system's computations thus provides auditability in a strong adversarial model in which no entity has to be individually trusted. Drynx is highly modular, dynamic and parallelizable. Our evaluation shows that it enables the training of a logistic regression model on a dataset (12 features and 600,000 records) distributed among 12 data providers in less than 2 seconds. The computations are distributed among 6 computing nodes, and Drynx enables the verification of the query execution's correctness in less than 22 seconds.
Secure multiparty computation enables a set of parties to securely carry out a joint computation on their private inputs without revealing anything but the output. A particularly motivated setting is that of three parties with a single corruption (hereafter denoted 3PC). This 3PC setting is particularly appealing for two main reasons: (1) it admits more efficient MPC protocols than in other standard settings; (2) it allows in principle to achieve full security (and fairness). Highly efficient protocols exist within this setting with security against a semi-honest</> adversary; however, a significant gap remains between these and protocols with stronger security against a malicious</> adversary. In this paper, we narrow this gap within concretely efficient protocols. More explicitly, we have the following contributions: Concretely Efficient Malicious 3PC. We present an optimized 3PC protocol for arithmetic circuits over rings with (amortized) communication of 1 ring element per multiplication gate per party, matching the best semi-honest protocols. The protocol applies also to Boolean circuits, significantly improving over previous protocols even for small circuits. Our protocol builds on recent techniques of Boneh et al. (Crypto 2019) for sublinear zero-knowledge proofs on distributed data, together with an efficient semi-honest protocol based on replicated secret sharing (Araki et al., CCS 2016). We present a concrete analysis of communication and computation costs, including several optimizations. For example, for 40-bit statistical security, and Boolean circuit with a million (nonlinear) gates, the overhead on top of the semi-honest protocol can involve less than 0.5KB of communication for the entire circuit,</> while the computational overhead is dominated by roughly 30 multiplications per gate in the field F247. In addition, we implemented and benchmarked the protocol for varied circuit sizes. Full Security. We augment the 3PC protocol to further provide full security</> (with guaranteed output delivery) while maintaining amortized 1 ring element communication per party per multiplication gate, and with hardly any impact on concrete efficiency. This is contrasted with the best previous 3PC protocols from the literature, which allow a corrupt party to mount a denial-of-service attack without being detected.
Karan Ganju, Qi Wang, Wei Yang, Carl A. Gunter · 5 authors
With the growing adoption of machine learning, sharing of learned models is becoming popular. However, in addition to the prediction properties the model producer aims to share, there is also a risk that the model consumer can infer other properties of the training data the model producer did not intend to share. In this paper, we focus on the inference of global properties of the training data, such as the environment in which the data was produced, or the fraction of the data that comes from a certain class, as applied to white-box Fully Connected Neural Networks (FCNNs). Because of their complexity and inscrutability, FCNNs have a particularly high risk of leaking unexpected information about their training sets; at the same time, this complexity makes extracting this information challenging. We develop techniques that reduce this complexity by noting that FCNNs are invariant under permutation of nodes in each layer. We develop our techniques using representations that capture this invariance and simplify the information extraction task. We evaluate our techniques on several synthetic and standard benchmark datasets and show that they are very effective at inferring various data properties. We also perform two case studies to demonstrate the impact of our attack. In the first case study we show that a classifier that recognizes smiling faces also leaks information about the relative attractiveness of the individuals in its training set. In the second case study we show that a classifier that recognizes Bitcoin mining from performance counters also leaks information about whether the classifier was trained on logs from machines that were patched for the Meltdown and Spectre attacks.
Ravi Kiran Raman, Roman Vaculín, Michael Hind, Sekou L. Remy · 9 authors
Large-scale computational experiments, often running over weeks and over large datasets, are used extensively in fields such as epidemiology, meteorology, computational biology, and healthcare to understand phenomena, and design high-stakes policies affecting everyday health and economy. For instance, the OpenMalaria framework is a computationally-intensive simulation used by various non-governmental and governmental agencies to understand malarial disease spread and effectiveness of intervention strategies, and subsequently design healthcare policies. Given that such shared results form the basis of inferences drawn, technological solutions designed, and day-to-day policies drafted, it is essential that the computations are validated and trusted. In particular, in a multi-agent environment involving several independent computing agents, a notion of trust in results generated by peers is critical in facilitating transparency, accountability, and collaboration. Using a novel combination of distributed validation of atomic computation blocks and a blockchain-based immutable audits mechanism, this work proposes a universal framework for distributed trust in computations. In particular we address the scalaibility problem by reducing the storage and communication costs using a lossy compression scheme. This framework guarantees not only verifiability of final results, but also the validity of local computations, and its cost-benefit tradeoffs are studied using a synthetic example of training a neural network.
Hyesung Kim, Jihong Park, Mehdi Bennis, Seong‐Lyun Kim
In this letter, we propose a block-chained federated learning (BlockFL)
architecture, where mobile devices' local learning model updates are exchanged
and verified by leveraging blockchain. This enables on-device machine learning
without any central coordination, even when each device lacks its own training
data samples. We investigate the end-to-end learning completion latency of
BlockFL, thereby yielding the optimal block generation rate as well as
important insights in terms of network scalability and robustness.
Gihan J. Mendis, Moein Sabounchi, Wei Jin, Rigoberto Roche
Deep learning algorithms have recently gained attention due to their inherent capabilities and the application opportunities that they provide. Two of the main reasons for the success of deep learning methods are the availability of processing power and big data. Both of these two are expensive and rare commodities that present limitations to the usage and implementation of deep learning. Decentralization of the processing and data is one of the most prevalent solutions for these issues. This paper proposes a cooperative decentralized deep learning architecture. The contributors can train deep learning models with private data and share them to the cooperative data-driven applications initiated elsewhere. Shared models are fused together to obtain a better model. In this work, the contributors can both design their own models or train the models provided by the initiator. In order to utilize an efficient decentralized learning algorithm, blockchain technology is incorporated as a method of creating an incentive-compatible market. In the proposed method, Ethereum blockchain's scripting capabilities are employed to devise a decentralized deep learning mechanism, which provides much higher, collective processing power and grants access to large amounts of data, which would be otherwise inaccessible. The technical description of the mechanism is described and the simulation results are presented.
In this article, the authors propose an approach for privacy preserving distributed clustering that assumes malicious model. In the literature, there do exist, numerous approaches that assume a semi honest model. However, such an assumption is, at best, reasonable in experimentations; rarely true in real world. Hence, it is essential to investigate approaches for privacy preservation using a malicious model. The authors use the Pederson's Verifiable Secret Sharing scheme ensuring the privacy using additively homomorphic secret sharing scheme. The trustworthiness of the data is assured using homomorphic commitments in Pederson's scheme. In addition, the authors propose two variants of the proposed approach - one for horizontally partitioned dataset and the other for vertically partitioned dataset. The experimental results show that the proposed approach is scalable in terms of dataset size. The authors also carry out experimentations to highlight the effectiveness of Verifiable Secret Sharing scheme against Zero Knowledge Proof scheme.
For the general problem of minimizing a convex function over a compact convex domain, we will investigate a simple iterative approximation algorithm based on the method by Frank & Wolfe 1956, that does not need projection steps in order to stay inside the optimization domain. Instead of a projection step, the linearized problem defined by a current subgradient is solved, which gives a step direction that will naturally stay in the domain. Our framework generalizes the sparse greedy algorithm of Frank & Wolfe and its primal-dual analysis by Clarkson 2010 (and the low-rank SDP approach by Hazan 2008) to arbitrary convex domains. We give a convergence proof guaranteeing ε-small duality gap after O(1/ε) iterations. The method allows us to understand the sparsity of approximate solutions for any l1-regularized convex optimization problem (and for optimization over the simplex), expressed as a function of the approximation quality. We obtain matching upper and lower bounds of Θ(1/ε) for the sparsity for l1-problems. The same bounds apply to low-rank semidefinite optimization with bounded trace, showing that rank O(1/ε) is best possible here as well. As another application, we obtain sparse matrices of O(1/ε) non-zero entries as ε-approximate solutions when optimizing any convex function over a class of diagonally dominant symmetric matrices. We show that our proposed first-order method also applies to nuclear norm and max-norm matrix optimization problems. For nuclear norm regularized optimization, such as matrix completion and low-rank recovery, we demonstrate the practical efficiency and scalability of our algorithm for large matrix problems, as e.g. the Netflix dataset. For general convex optimization over bounded matrix max-norm, our algorithm is the first with a convergence guarantee, to the best of our knowledge.
Zero-knowledge set is a primitive introduced by Micali, Rabin, and Kilian (FOCS 2003) which enables a prover to commit a set to a verifier, without revealing even the size of the set. Later the prover can give zero-knowledge proofs to convince the verifier of membership/nonmembership of elements in/not in the committed set. We present a new primitive called Statistically Hiding Sets (SHS), similar to zero-knowledge sets, but providing an information theoretic hiding guarantee. This is comparable to relaxing zero-knowledge proofs to witness independent proofs. More precisely, we continue to use the simulation paradigm for our definition, but do not require the simulator (nor the distinguisher) to be efficient. We present a new scheme for statistically hiding sets, which does not fit into the “Merkletree/mercurial-commitment” paradigm used for all zero-knowledge set constructions so far. This not only provides some efficiency gains compared to the best possible schemes in that paradigm, but also lets us provide statistical hiding, without the prover having to maintain growing amounts of state with each new proof; this is not known to be possible with the previous approach.
2 source records
Advanced Steganography and Watermarking Techniques
Rahul Jain, Alexandra Kolla, Gatis Midrijānis, Ben W. Reichardt
Let L be a language decided by a constant-round quantum Arthur-Merlin (QAM)\nprotocol with negligible soundness error and all but possibly the last message\nbeing classical. We prove that if this protocol is zero knowledge with a\nblack-box, quantum simulator S, then L in BQP. Our result also applies to any\nlanguage having a three-round quantum interactive proof (QIP), with all but\npossibly the last message being classical, with negligible soundness error and\na black-box quantum simulator.\n These results in particular make it unlikely that certain protocols can be\ncomposed in parallel in order to reduce soundness error, while maintaining zero\nknowledge with a black-box quantum simulator. They generalize analogous\nclassical results of Goldreich and Krawczyk (1990).\n Our proof goes via a reduction to quantum black-box search. We show that the\nexistence of a black-box quantum simulator for such protocols when L notin BQP\nwould imply an impossibly-good quantum search algorithm.\n