Cryptographic hash functions from expander graphs were proposed by Charles, Goren, and Lauter in [CGL] based on the hardness of finding paths in the graph. In this paper, we propose a new candidate for a hash function based on the hardness of finding
paths in the graph of Markoff triples modulo p. These graphs have been studied extensively in number theory and various other fields, and yet finding paths in the graphs remains difficult. We discuss the hardness of finding paths between points, based on the structure of the Markoff graphs. We investigate several possible avenues for attack and estimate their running time to be greater than O(p). In particular, we analyze a recent groundbreaking proof in [BGS1] that such graphs are connected and discuss how this proof gives an algorithm for finding paths
Remote monitoring to support aging in place is an active area of research. Advanced computer vision technology based on deep learning can provide near real-time home monitoring to detect falling and symptoms related to seizure, and stroke. Affordable
webcams, together with cloud computing services (to run machine learning algorithms), can potentially bring significant social and health benefits. However, it has not been deployed in practice because of privacy and security concerns. People may feel uncomfortable sending their videos of daily activities (with potentially sensitive private information) to a computing service provider (e.g., on a commercial cloud). In this paper, we propose a novel strategy to resolve this dilemma by applying fully homomorphic encryption (FHE) to an alternative representation of human actions (i.e., skeleton joints), which guarantees information confidentiality while retaining high-performance action detection at a low cost. We design an FHE-friendly neural network for action recognition and present a secure neural network evaluation strategy to achieve near real-time action detection. Our framework for private inference achieves an 87.99% recognition accuracy (86.21% sensitivity and 99.14% specificity in detecting falls) with a latency of 3.1 seconds on real-world datasets. Our evaluation shows that our elaborated and fine-tuned method reduces the inference latency by 23.81%~74.67% over a straightforward implementation.
In this paper, we study isogeny graphs of supersingular elliptic curves. Supersingular isogeny graphs were introduced as a hard problem into cryptography by Charles, Goren, and Lauter for the construction of cryptographic hash functions [CGL06]. Thes
e are large expander graphs, and the hard problem is to find an efficient algorithm for routing, or path-finding, between two vertices of the graph. We consider four aspects of supersingular isogeny graphs, study each thoroughly and, where appropriate, discuss how they relate to one another. First, we consider two related graphs that help us understand the structure: the `spine $mathcal{S}$, which is the subgraph of $mathcal{G}_ell(overline{mathbb{F}_p})$ given by the $j$-invariants in $mathbb{F}_p$, and the graph $mathcal{G}_ell(mathbb{F}_p)$, in which both curves and isogenies must be defined over $mathbb{F}_p$. We show how to pass from the latter to the former. The graph $mathcal{S}$ is relevant for cryptanalysis because routing between vertices in $mathbb{F}_p$ is easier than in the full isogeny graph. The $mathbb{F}_p$-vertices are typically assumed to be randomly distributed in the graph, which is far from true. We provide an analysis of the distances of connected components of $mathcal{S}$. Next, we study the involution on $mathcal{G}_ell(overline{mathbb{F}_p})$ that is given by the Frobenius of $mathbb{F}_p$ and give heuristics on how often shortest paths between two conjugate $j$-invariants are preserved by this involution (mirror paths). We also study the related question of what proportion of conjugate $j$-invariants are $ell$-isogenous for $ell = 2,3$. We conclude with experimental data on the diameters of supersingular isogeny graphs when $ell = 2$ and compare this with previous results on diameters of LPS graphs and random Ramanujan graphs.
We give bounds on the primes of geometric bad reduction for curves of genus three of primitive CM type in terms of the CM orders. In the case of genus one, there are no primes of geometric bad reduction because CM elliptic curves are CM abelian varie
ties, which have potential good reduction everywhere. However, for genus at least two, the curve can have bad reduction at a prime although the Jacobian has good reduction. Goren and Lauter gave the first bound in the case of genus two. In the cases of hyperelliptic and Picard curves, our results imply bounds on primes appearing in the denominators of invariants and class polynomials, which are important for algorithmic construction of curves with given characteristic polynomials over finite fields.
Let $C$ be a smooth, absolutely irreducible genus-$3$ curve over a number field $M$. Suppose that the Jacobian of $C$ has complex multiplication by a sextic CM-field $K$. Suppose further that $K$ contains no imaginary quadratic subfield. We give a bo
und on the primes $mathfrak{p}$ of $M$ such that the stable reduction of $C$ at $mathfrak{p}$ contains three irreducible components of genus $1$.
Bruinier and Yang conjectured a formula for intersection numbers on an arithmetic Hilbert modular surface, and as a consequence obtained a conjectural formula for CM(K).G_1 under strong assumptions on the ramification in K. Yang later proved this con
jecture under slightly stronger assumptions on the ramification. In recent work, Lauter and Viray proved a different formula for CM(K).G_1 for primitive quartic CM fields with a mild assumption, using a method of proof independent from that of Yang. In this paper we show that these two formulas agree, for a class of primitive quartic CM fields which is slightly larger than the intersection of the fields considered by Yang and Lauter and Viray. Furthermore, the proof that these formulas agree does not rely on the results of Yang or Lauter and Viray. As a consequence of our proof, we conclude that the Bruinier-Yang formula holds for a slightly largely class of quartic CM fields K than what was proved by Yang, since it agrees with the Lauter-Viray formula, which is proved in those cases. The factorization of these intersection numbers has applications to cryptography: precise formulas for them allow one to compute the denominators of Igusa class polynomials, which has important applications to the construction of genus 2 curves for use in cryptography.
In this paper we prove an explicit formula for the arithmetic intersection number (CM(K).G1)_{ell} on the Siegel moduli space of abelian surfaces, generalizing the work of Bruinier-Yang and Yang. These intersection numbers allow one to compute the de
nominators of Igusa class polynomials, which has important applications to the construction of genus 2 curves for use in cryptography. Bruinier and Yang conjectured a formula for intersection numbers on an arithmetic Hilbert modular surface, and as a consequence obtained a conjectural formula for the intersection number (CM(K).G1)_{ell} under strong assumptions on the ramification of the primitive quartic CM field K. Yang later proved this conjecture assuming that O_K is freely generated by one element over the ring of integers of the real quadratic subfield. In this paper, we prove a formula for (CM(K).G1)_{ell} for more general primitive quartic CM fields, and we use a different method of proof than Yang. We prove a tight bound on this intersection number which holds for all primitive quartic CM fields. As a consequence, we obtain a formula for a multiple of the denominators of the Igusa class polynomials for an arbitrary primitive quartic CM field. Our proof entails studying the Embedding Problem posed by Goren and Lauter and counting solutions using our previous article that generalized work of Gross-Zagier and Dorman to arbitrary discriminants.
Let d1 and d2 be discriminants of distinct quadratic imaginary orders O_d1 and O_d2 and let J(d1,d2) denote the product of differences of CM j-invariants with discriminants d1 and d2. In 1985, Gross and Zagier gave an elegant formula for the factoriz
ation of the integer J(d1,d2) in the case that d1 and d2 are relatively prime and discriminants of maximal orders. To compute this formula, they first reduce the problem to counting the number of simultaneous embeddings of O_d1 and O_d2 into endomorphism rings of supersingular curves, and then solve this counting problem. Interestingly, this counting problem also appears when computing class polynomials for invariants of genus 2 curves. However, in this application, one must consider orders O_d1 and O_d2 that are non-maximal. Motivated by the application to genus 2 curves, we generalize the methods of Gross and Zagier and give a computable formula for v_p(J(d1,d2)) for any distinct pair of discriminants d1,d2 and any prime p>2. In the case that d1 is squarefree and d2 is the discriminant of any quadratic imaginary order, our formula can be stated in a simple closed form. We also give a conjectural closed formula when the conductors of d1 and d2 are relatively prime.
Bruinier and Yang conjectured a formula for an intersection number on the arithmetic Hilbert modular surface, CM(K).T_m, where CM(K) is the zero-cycle of points corresponding to abelian surfaces with CM by a primitive quartic CM field K, and T_m is t
he Hirzebruch-Zagier divisors parameterizing products of elliptic curves with an m-isogeny between them. In this paper, we examine fields not covered by Yangs proof of the conjecture. We give numerical evidence to support the conjecture and point to some interesting anomalies. We compare the conjecture to both the denominators of Igusa class polynomials and the number of solutions to the embedding problem stated by Goren and Lauter.
