Statistics of small subgraph counts such as triangles, fourcycles, and st paths of short lengths reveal important structural properties of the underlying graph. These problems have been widely studied in social network analysis. In most relevant applications, the graphs are not only massive but also change dynamically over time. Most of these problems become hard in the dynamic setting when considering the worst case. In this paper, we ask whether the question of small subgraph counting over dynamic graphs is hard also in the average case. We consider the simplest possible average case model where the updates follow an ErdősRényimore »
PublicKey Cryptography in the FineGrained Setting
Cryptography is largely based on unproven assumptions, which, while believable, might fail. Notably if P=NP, or if we live in Pessiland, then all current cryptographic assumptions will be broken. A compelling question is if any interesting cryptography might exist in Pessiland.
A natural approach to tackle this question is to base cryptography on an assumption from finegrained complexity. Ball, Rosen, Sabin, and Vasudevan [BRSV’17] attempted this, starting from popular hardness assumptions, such as the Orthogonal Vectors (OV) Conjecture. They obtained problems that are hard on average, assuming that OV and other problems are hard in the worst case. They obtained proofs of work, and hoped to use their averagecase hard problems to build a finegrained oneway function. Unfortunately, they proved that constructing one using their approach would violate a popular hardness hypothesis. This motivates the search for other finegrained averagecase hard problems.
The main goal of this paper is to identify sufficient properties for a finegrained averagecase assumption that imply cryptographic primitives such as finegrained public key cryptography (PKC). Our main contribution is a novel construction of a cryptographic key exchange, together with the definition of a small number of relatively weak structural properties, such that if a computational problem satisfies them, more »
 Award ID(s):
 1909429
 Publication Date:
 NSFPAR ID:
 10178933
 Journal Name:
 Advances in Cryptology {\textendash} {CRYPTO} 2019
 Volume:
 11694
 Page Range or eLocationID:
 605635
 Sponsoring Org:
 National Science Foundation
More Like this


A fundamental pursuit in complexity theory concerns reducing worstcase problems to averagecase problems. There exist complexity classes such as PSPACE that admit worstcase to averagecase reductions. However, for many other classes such as NP, the evidence so far is typically negative, in the sense that the existence of such reductions would cause collapses of the polynomial hierarchy(PH). Basing cryptographic primitives, e.g., the averagecase hardness of inverting oneway permutations, on NPcompleteness is a particularly intriguing instance. As there is evidence showing that classical reductions from NPhard problems to breaking these primitives result in PH collapses, it seems unlikely to base cryptographicmore »

Abstract We show a simple reduction which demonstrates the cryptographic hardness of learning a single periodic neuron over isotropic Gaussian distributions in the presence of noise. More precisely, our reduction shows that any polynomialtime algorithm (not necessarily gradientbased) for learning such functions under small noise implies a polynomialtime quantum algorithm for solving worstcase lattice problems, whose hardness form the foundation of latticebased cryptography. Our core hard family of functions, which are wellapproximated by onelayer neural networks, take the general form of a univariate periodic function applied to an affine projection of the data. These functions have appeared in previous seminalmore »

We show a simple reduction which demonstrates the cryptographic hardness of learning a single periodic neuron over isotropic Gaussian distributions in the pres ence of noise. More precisely, our reduction shows that any polynomialtime algorithm (not necessarily gradientbased) for learning such functions under small noise implies a polynomialtime quantum algorithm for solving worstcase lattice problems, whose hardness form the foundation of latticebased cryptography. Our core hard family of functions, which are wellapproximated by onelayer neural networks, take the general form of a univariate periodic function applied to an affine projection of the data. These functions have appeared in previous seminalmore »

Pass, Rafael ; Pietrzak, Krzysztof (Ed.)We initiate a study of pseudorandom encodings: efficiently computable and decodable encoding functions that map messages from a given distribution to a randomlooking distribution. For instance, every distribution that can be perfectly and efficiently compressed admits such a pseudorandom encoding. Pseudorandom encodings are motivated by a variety of cryptographic applications, including passwordauthenticated key exchange, “honey encryption” and steganography. The main question we ask is whether every efficiently samplable distribution admits a pseudorandom encoding. Under different cryptographic assumptions, we obtain positive and negative answers for different flavors of pseudorandom encodings, and relate this question to problems in other areas of cryptography.more »