We introduce a new notion called Q-secure pseudorandom isometries (PRI). A pseudorandom isometry is an efficient quantum circuit that maps an n-qubit state to an (n+m)-qubit state in an isometric manner. In terms of security, we require that the output of a q-fold PRI on \rho, for \rho \in Q, for any polynomial q, should be computationally indistinguishable from the output of a q-fold Haar isometry on \rho. By fine-tuning Q, we recover many existing notions of pseudorandomness. We present a construction of PRIs and assuming post-quantum one-way functions, we prove the security of Q-secure pseudorandom isometries (PRI) for different interesting settings of Q. We also demonstrate many cryptographic applications of PRIs, including, length extension theorems for quantum pseudorandomness notions, message authentication schemes for quantum states, multi-copy secure public and private encryption schemes, and succinct quantum commitments.
more »
« less
On One-way Functions and Kolmogorov Complexity
We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial t(n) ≥ (1 + ε)n, ε > 0, the following are equivalent: • One-way functions exists (which in turn is equivalent to the existence of secure private-key encryption schemes, digital signatures, pseudorandom generators, pseudorandom functions, commitment schemes, and more); • t-time bounded Kolmogorov Complexity, Kt, is mildly hard-on-average (i.e., there exists a polynomial p(n) > 0 such that no PPT algorithm can compute Kt, for more than a 1 − 1/p(n) fraction of n-bit strings). In doing so, we present the first natural, and well-studied, computational problem characterizing the feasibility of the central private-key primitives and protocols in Cryptography.
more »
« less
- Award ID(s):
- 1704788
- PAR ID:
- 10233398
- Date Published:
- Journal Name:
- IEEE Symposium on Foundations of Computer Science (FOCS)
- Subject(s) / Keyword(s):
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Existing proofs that deduce BPP = P from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown . Specifically, assuming exponential lower bounds against randomized NP ∩ coNP circuits, formally known as randomized SVN circuits, we convert any randomized algorithm over inputs of length n running in time t ≥ n into a deterministic one running in time t 2+α for an arbitrarily small constant α > 0. Such a slowdown is nearly optimal for t close to n , since under standard complexity-theoretic assumptions, there are problems with an inherent quadratic derandomization slowdown. We also convert any randomized algorithm that errs rarely into a deterministic algorithm having a similar running time (with pre-processing). The latter derandomization result holds under weaker assumptions, of exponential lower bounds against deterministic SVN circuits. Our results follow from a new, nearly optimal, explicit pseudorandom generator fooling circuits of size s with seed length (1+α)log s , under the assumption that there exists a function f ∈ E that requires randomized SVN circuits of size at least 2 (1-α′) n , where α = O (α)′. The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.more » « less
-
In this paper, we propose an iterative method for using SOS programming to estimate the region of attraction of a polynomial vector field, the conjectured convergence of which necessitates the existence of polynomial Lyapunov functions whose sublevel sets approximate the true region of attraction arbitrarily well. The main technical result of the paper is the proof of existence of such a Lyapunov function. Specifically, we usetheHausdorffdistancemetrictoanalyzeconvergenceandin the main theorem demonstrate that the existence of an n-times continuously differentiable maximal Lyapunov function implies that for any ε >0, there exists a polynomial Lyapunov function and associated sub-level set which together prove stability of a set which is within ε Hausdorff distance of the true region of attraction. The proposed iterative method and probably convergence is illustrated with a numerical example.more » « less
-
Meka, Raghu (Ed.)Given a weighted graph G = (V,E,w), a (β, ε)-hopset H is an edge set such that for any s,t ∈ V, where s can reach t in G, there is a path from s to t in G ∪ H which uses at most β hops whose length is in the range [dist_G(s,t), (1+ε)dist_G(s,t)]. We break away from the traditional question that asks for a hopset H that achieves small |H| and small diameter β and instead study the sensitivity of H, a new quality measure. The sensitivity of a vertex (or edge) given a hopset H is, informally, the number of times a single hop in G ∪ H bypasses it; a bit more formally, assuming shortest paths in G are unique, it is the number of hopset edges (s,t) ∈ H such that the vertex (or edge) is contained in the unique st-path in G having length exactly dist_G(s,t). The sensitivity associated with H is then the maximum sensitivity over all vertices (or edges). The highlights of our results are: - A construction for (Õ(√n), 0)-hopsets on undirected graphs with O(log n) sensitivity, complemented with a lower bound showing that Õ(√n) is tight up to polylogarithmic factors for any construction with polylogarithmic sensitivity. - A construction for (n^o(1), ε)-hopsets on undirected graphs with n^o(1) sensitivity for any ε > 0 that is at least inverse polylogarithmic, complemented with a lower bound on the tradeoff between β, ε, and the sensitivity. - We define a notion of sensitivity for β-shortcut sets (which are the reachability analogues of hopsets) and give a construction for Õ(√n)-shortcut sets on directed graphs with O(log n) sensitivity, complemented with a lower bound showing that β = Ω̃(n^{1/3}) for any construction with polylogarithmic sensitivity. We believe hopset sensitivity is a natural measure in and of itself, and could potentially find use in a diverse range of contexts. More concretely, the notion of hopset sensitivity is also directly motivated by the Differentially Private All Sets Range Queries problem [Deng et al. WADS 23]. Our result for O(log n) sensitivity (Õ(√n), 0)-hopsets on undirected graphs immediately improves the current best-known upper bound on utility from Õ(n^{1/3}) to Õ(n^{1/4}) in the pure-DP setting, which is tight up to polylogarithmic factors.more » « less
-
Ene, Alina; Chattopadhyay, Eshan (Ed.)Abstract: We study the problem of solving linear programs of the form Ax ≤ b, x ≥ 0 with differential privacy. For homogeneous LPs Ax ≥ 0, we give an efficient (ε,δ)-differentially private algorithm which with probability at least 1-β finds in polynomial time a solution that satisfies all but O(d²/ε log²(d/(δβ))√{log 1/ρ₀}) constraints, for problems with margin ρ₀ > 0. This improves the bound of O(d⁵/ε log^{1.5} 1/ρ₀ polylog(d,1/δ,1/β)) by [Kaplan-Mansour-Moran-Stemmer-Tur, STOC '25]. For general LPs Ax ≤ b, x ≥ 0 with potentially zero margin, we give an efficient (ε,δ)-differentially private algorithm that w.h.p drops O(d⁴/ε log^{2.5} d/δ √{log dU}) constraints, where U is an upper bound for the entries of A and b in absolute value. This improves the result by Kaplan et al. by at least a factor of d⁵. Our techniques build upon privatizing a rescaling perceptron algorithm by [Hoberg-Rothvoss, IPCO '17] and a more refined iterative procedure for identifying equality constraints by Kaplan et al.more » « less
An official website of the United States government

