Source author record

Jalaj Upadhyay

Jalaj Upadhyay appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Cryptography and Security Data Structures and Algorithms Machine Learning math.CO

Catalog footprint

What is connected

5works

4topics

3close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

A Framework for Private Matrix Analysis

We study private matrix analysis in the sliding window model where only the last $W$ updates to matrices are considered useful for analysis. We give first efficient $o(W)$ space differentially private algorithms for spectral approximation, principal component analysis, and linear regression. We also initiate and show efficient differentially private algorithms for two important variants of principal component analysis: sparse principal component analysis and non-negative principal component analysis. Prior to our work, no such result was known for sparse and non-negative differentially private principal component analysis even in the static data setting. These algorithms are obtained by identifying sufficient conditions on positive semidefinite matrices formed from streamed matrices. We also show a lower bound on space required to compute low-rank approximation even if the algorithm gives multiplicative approximation and incurs additive error. This follows via reduction to a certain communication complexity problem.

preprint2016arXiv

Multi-prover Proof-of-Retrievability

There has been considerable recent interest in "cloud storage" wherein a user asks a server to store a large file. One issue is whether the user can verify that the server is actually storing the file, and typically a challenge-response protocol is employed to convince the user that the file is indeed being stored correctly. The security of these schemes is phrased in terms of an extractor which will recover the file given any "proving algorithm" that has a sufficiently high success probability. This forms the basis of \emph{proof-of-retrievability} ($\mathsf{PoR}$) systems. In this paper, we study multiple server $\mathsf{PoR}$ systems. We formalize security definitions for two possible scenarios: (i) when a threshold of servers succeed with high enough probability (worst-case) and (ii) when the average of the success probability of all the servers is above a threshold (average-case). We also motivate the study of confidentiality of the outsourced message. We give $\mathsf{M}\mbox{-}\mathsf{PoR}$ schemes which are secure under both these security definitions and provide reasonable confidentiality guarantees even when there is no restriction on the computational power of the servers. We also show how classical statistical techniques used by Paterson, Stinson and Upadhyay (Journal of Mathematical Cryptology: 7(3)) can be extended to evaluate whether the responses of the provers are accurate enough to permit successful extraction. We also look at one specific instantiation of our construction when instantiated with the unconditionally secure version of the Shacham-Waters scheme (Asiacrypt, 2008). This scheme gives reasonable security and privacy guarantee. We show that, in the multi-server setting with computationally unbounded provers, one can overcome the limitation that the verifier needs to store as much secret information as the provers.

preprint2016arXiv

On Low-Space Differentially Private Low-rank Factorization in the Spectral Norm

Low-rank factorization is used in many areas of computer science where one performs spectral analysis on large sensitive data stored in the form of matrices. In this paper, we study differentially private low-rank factorization of a matrix with respect to the spectral norm in the turnstile update model. In this problem, given an input matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ updated in the turnstile manner and a target rank $k$, the goal is to find two rank-$k$ orthogonal matrices $\mathbf{U}_k \in \mathbb{R}^{m \times k}$ and $\mathbf{V}_k \in \mathbb{R}^{n \times k}$, and one positive semidefinite diagonal matrix $\textbfΣ_k \in \mathbb{R}^{k \times k}$ such that $\mathbf{A} \approx \mathbf{U}_k \textbfΣ_k \mathbf{V}_k^\mathsf{T}$ with respect to the spectral norm. Our main contributions are two computationally efficient and sub-linear space algorithms for computing a differentially private low-rank factorization. We consider two levels of privacy. In the first level of privacy, we consider two matrices neighboring if their difference has a Frobenius norm at most $1$. In the second level of privacy, we consider two matrices as neighboring if their difference can be represented as an outer product of two unit vectors. Both these privacy levels are stronger than those studied in the earlier papers such as Dwork {\it et al.} (STOC 2014), Hardt and Roth (STOC 2013), and Hardt and Price (NIPS 2014). As a corollary to our results, we get non-private algorithms that compute low-rank factorization in the turnstile update model with respect to the spectral norm. We note that, prior to this work, no algorithm that outputs low-rank factorization with respect to the spectral norm in the turnstile update model was known; i.e., our algorithm gives the first non-private low-rank factorization with respect to the spectral norm in the turnstile update mode.

preprint2015arXiv

Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing

The Johnson-Lindenstrauss property ({\sf JLP}) of random matrices has immense application in computer science ranging from compressed sensing, learning theory, numerical linear algebra, to privacy. This paper explores the properties and applications of a distribution of random matrices. Our distribution satisfies {\sf JLP} with desirable properties like fast matrix-vector multiplication, sparsity, and optimal subspace embedding. We can sample a random matrix from this distribution using exactly $2n+n \log n$ random bits. We show that a random matrix picked from this distribution preserves differential privacy under the condition that the input private matrix satisfies certain spectral property. This improves the run-time of various differentially private mechanisms like Blocki {\it et al.} (FOCS 2012) and Upadhyay (ASIACRYPT 13). Our final construction has a bounded column sparsity. Therefore, this answers an open problem stated in Blocki {\it et al.} (FOCS 2012). Using the results of Baranuik {\it et al.} (Constructive Approximation: 28(3)), our result implies a randomness efficient matrices that satisfies the Restricted-Isometry Property of optimal order for small sparsity with exactly linear random bits. We also show that other known distributions of sparse random matrices with the {\sf JLP} does not preserves differential privacy; thereby, answering one of the open problem posed by Blocki {\it et al.} (FOCS 2012). Extending on the works of Kane and Nelson (JACM: 61(1)), we also give unified analysis of some of the known Johnson-Lindenstrauss transform. We also present a self-contained simplified proof of an inequality on quadratic form of Gaussian variables that we use in all our proofs.

preprint2012arXiv

A coding theory foundation for the analysis of general unconditionally secure proof-of-retrievability schemes for cloud storage

There has been considerable recent interest in "cloud storage" wherein a user asks a server to store a large file. One issue is whether the user can verify that the server is actually storing the file, and typically a challenge-response protocol is employed to convince the user that the file is indeed being stored correctly. The security of these schemes is phrased in terms of an extractor which will recover or retrieve the file given any "proving algorithm" that has a sufficiently high success probability. This paper treats proof-of-retrievability schemes in the model of unconditional security, where an adversary has unlimited computational power. In this case retrievability of the file can be modelled as error-correction in a certain code. We provide a general analytical framework for such schemes that yields exact (non-asymptotic) reductions that precisely quantify conditions for extraction to succeed as a function of the success probability of a proving algorithm, and we apply this analysis to several archetypal schemes. In addition, we provide a new methodology for the analysis of keyed POR schemes in an unconditionally secure setting, and use it to prove the security of a modified version of a scheme due to Shacham and Waters under a slightly restricted attack model, thus providing the first example of a keyed POR scheme with unconditional security. We also show how classical statistical techniques can be used to evaluate whether the responses of the prover are accurate enough to permit successful extraction. Finally, we prove a new lower bound on storage and communication complexity of POR schemes.