Search

We describe a framework for constructing an efficient non-interactive key exchange (NIKE) protocol for n parties for any n ≥ 2. Our approach is based on the problem of computing isogenies between isogenous elliptic curves, which is believed to be difficult. We do not obtain a working protocol because of a missing step that is currently an open mathematical problem. What we need to complete our protocol is an efficient algorithm that takes as input an abelian variety presented as a product of isogenous elliptic curves, and outputs an isomorphism invariant of the abelian variety.

In this paper, we introduce a new problem called the Isogenous Embedding Problem (IEP) and relate the existence of solutions to this problem to the primes of bad reduction of complex multiplication curves of genus 3. More precisely, the absence of solutions to IEP implies potentially good reduction. We propose an algorithm for computing the solutions to the IEP and run the algorithm through different families of curves. Using this algorithm, we were able to prove the reduction type of some particular curves at certain primes that were open cases in R. Lercier, Q. Liu, E. Lorenzo García and C. Ritzenthaler, Reduction type of smooth plane quartics, Algebra Number Theory   15 no. 6 2021, 1429–1468. [ABSTRACT FROM AUTHOR]

A lattice of integers is the collection of all linear combinations of a set of vectors for which all entries of the vectors are integers and all coefficients in the linear combinations are also integers. Lattice reduction refers to the problem of finding a set of vectors in a given lattice such that the collection of all integer linear combinations of this subset is still the entire original lattice and so that the Euclidean norms of the subset are reduced. The present paper proposes simple, efficient iterations for lattice reduction which are guaranteed to reduce the Euclidean norms of the basis vectors (the vectors in the subset) monotonically during every iteration. Each iteration selects the basis vector for which projecting off (with integer coefficients) the components of the other basis vectors along the selected vector minimizes the Euclidean norms of the reduced basis vectors. Each iteration projects off the components along the selected basis vector and efficiently updates all information required for the next iteration to select its best basis vector and perform the associated projections. [ABSTRACT FROM AUTHOR]

In this paper, we present a variant of Diem's O˜(q)${\widetilde{O}(q)}$ index calculus algorithm to attack the discrete logarithm problem (DLP) in Jacobians of genus 3 non-hyperelliptic curves over a finite field 𝔽q. We implement this new variant in C++ and study the complexity in both theory and practice, making the logarithmic factors and constants hidden in the O˜-notation precise. Our variant improves the computational complexity at the cost of a moderate increase in memory consumption, but we also improve the computational complexity even when we limit the memory usage to that of Diem's original algorithm. Finally, we examine how parallelization can help to reduce both the memory cost per computer and the running time for our algorithms.

With capability of performing computations on encrypted data without needing the secret key, homomorphic encryption (HE) is a promising cryptographic technique that makes outsourced computations secure and privacy-preserving. A decade after Gentry's breakthrough discovery of how we might support arbitrary computations on encrypted data, many studies followed and improved various aspects of HE, such as faster bootstrapping and ciphertext packing. However, the topic of how to support secure computations on ciphertexts encrypted under multiple keys does not receive enough attention. This capability is crucial in many application scenarios where data owners want to engage in joint computations and are preferred to protect their sensitive data under their own secret keys. Enabling this capability is a non-trivial task. In this article, we present a comprehensive survey of the state-of-the-artmulti-key techniques and schemes that target diferent systems and threat models. In particular, we review recent constructions based on Threshold Homomorphic Encryption (ThHE) and Multi-Key Homomorphic Encryption (MKHE).We analyze these cryptographic techniques and schemes based on a new secure outsourced computation model and examine their complexities. We share lessons learned and draw observations for designing better schemes with reduced overheads. [ABSTRACT FROM AUTHOR]

Research Networks for Women is a recent effort led by the Association for Women in Mathematics to increase gender diversity in specific research areas of mathematics through a grassroots effort to build mentoring and collaborative relationships. In this article, we describe the history and success of this initiative, and share information about how to grow such a network. [ABSTRACT FROM AUTHOR]

We give bounds on the primes of geometric bad reduction for curves of genus 3 of primitive complex multiplication (CM) type in terms of the CM orders. In the case of elliptic curves, there are no primes of geometric bad reduction because CM elliptic curves are CM abelian varieties, which have potential good reduction everywhere. However, for genus at least 2, 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 2. 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. [ABSTRACT FROM AUTHOR]

In 2017, we decided to start the annual series of MathCrypt Workshops in order to encourage more mathematicians and computational number theorists to propose and work on hard problems in cryptography. The opportunity to publish intermediate results in venues like MathCrypt should help to de-risk this endeavor and encourage more mathematician to pursue these research directions. In fact, a Program Officer from NSF spoke at the first MathCrypt workshop in August 2018 and encouraged participants to apply to the NSF SaTC program for potential support for their research. [Extracted from the article]

Background: Advances in DNA sequencing technologies have prompted a wide range of genomic applications to improve healthcare and facilitate biomedical research. However, privacy and security concerns have emerged as a challenge for utilizing cloud computing to handle sensitive genomic data. Methods: We present one of the first implementations of Software Guard Extension (SGX) based securely outsourced genetic testing framework, which leverages multiple cryptographic protocols and minimal perfect hash scheme to enable efficient and secure data storage and computation outsourcing. Results: We compared the performance of the proposed PRESAGE framework with the state-of-the-art homomorphic encryption scheme, as well as the plaintext implementation. The experimental results demonstrated significant performance over the homomorphic encryption methods and a small computational overhead in comparison to plaintext implementation. Conclusions: The proposed PRESAGE provides an alternative solution for secure and efficient genomic data outsourcing in an untrusted cloud by using a hybrid framework that combines secure hardware and multiple crypto protocols. [ABSTRACT FROM AUTHOR]

Background: One of the tasks in the iDASH Secure Genome Analysis Competition in 2016 was to demonstrate the feasibility of privacy-preserving queries on homomorphically encrypted genomic data. More precisely, given a list of up to 100,000 mutations, the task was to encrypt the data using homomorphic encryption in a way that allows it to be stored securely in the cloud, and enables the data owner to query the dataset for the presence of specific mutations, without revealing any information about the dataset or the queries to the cloud. Methods: We devise a novel string matching protocol to enable privacy-preserving queries on homomorphically encrypted data. Our protocol combines state-of-the-art techniques from homomorphic encryption and private set intersection protocols to minimize the computational and communication cost. Results: We implemented our protocol using the homomorphic encryption library SEAL v2.1, and applied it to obtain an efficient solution to the iDASH competition task. For example, using 8 threads, our protocol achieves a running time of only 4 s, and a communication cost of 2 MB, when querying for the presence of 5 mutations from an encrypted dataset of 100,000 mutations. Conclusions: We demonstrate that homomorphic encryption can be used to enable an efficient privacy-preserving mechanism for querying the presence of particular mutations in realistic size datasets. Beyond its applications to genomics, our protocol can just as well be applied to any kind of data, and is therefore of independent interest to the homomorphic encryption community. [ABSTRACT FROM AUTHOR]

Supersingular isogeny graph–based cryptography has not yet been standardized, but the underlying hard problem has now been proposed as the basis for many cryptographic protocols. This motivates further investigation into the hardness of the underlying problem and the security of the proposed protocols. [ABSTRACT FROM PUBLISHER]

Motivation: We introduce PRINCESS, a privacy-preserving international collaboration framework for analyzing rare disease genetic data that are distributed across different continents. PRINCESS leverages Software Guard Extensions (SGX) and hardware for trustworthy computation. Unlike a traditional international collaboration model, where individual-level patient DNA are physically centralized at a single site, PRINCESS performs a secure and distributed computation over encrypted data, fulfilling institutional policies and regulations for protected health information. Results: To demonstrate PRINCESS' performance and feasibility, we conducted a family-based allelic association study for Kawasaki Disease, with data hosted in three different continents. The experimental results show that PRINCESS provides secure and accurate analyses much faster than alternative solutions, such as homomorphic encryption and garbled circuits (over 40 000x faster). [ABSTRACT FROM AUTHOR]

Biological data science is an emerging field facing multiple challenges for hosting, sharing, computing on, and interacting with large data sets. Privacy regulations and concerns about the risks of leaking sensitive personal health and genomic data add another layer of complexity to the problem. Recent advances in cryptography over the last five years have yielded a tool, homomorphic encryption, which can be used to encrypt data in such a way that storage can be outsourced to an untrusted cloud, and the data can be computed on in a meaningful way in encrypted form, without access to decryption keys. This paper introduces homomorphic encryption to the bioinformatics community, and presents an informal “manual” for using the Simple Encrypted Arithmetic Library (SEAL), which we have made publicly available for bioinformatic, genomic, and other research purposes. [ABSTRACT FROM AUTHOR]

The outsourcing of genomic data into public cloud computing settings raises concerns over privacy and security. Significant advancements in secure computation methods have emerged over the past several years, but such techniques need to be rigorously evaluated for their ability to support the analysis of human genomic data in an efficient and cost-effective manner. With respect to public cloud environments, there are concerns about the inadvertent exposure of human genomic data to unauthorized users. In analyses involving multiple institutions, there is additional concern about data being used beyond agreed research scope and being prcoessed in untrused computational environments, which may not satisfy institutional policies. To systematically investigate these issues, the NIH-funded National Center for Biomedical Computing iDASH (integrating Data for Analysis, 'anonymization' and SHaring) hosted the second Critical Assessment of Data Privacy and Protection competition to assess the capacity of cryptographic technologies for protecting computation over human genomes in the cloud and promoting cross-institutional collaboration. Data scientists were challenged to design and engineer practical algorithms for secure outsourcing of genome computation tasks in working software, whereby analyses are performed only on encrypted data. They were also challenged to develop approaches to enable secure collaboration on data from genomic studies generated by multiple organizations (e.g., medical centers) to jointly compute aggregate statistics without sharing individual-level records. The results of the competition indicated that secure computation techniques can enable comparative analysis of human genomes, but greater efficiency (in terms of compute time and memory utilization) are needed before they are sufficiently practical for real world environments. [ABSTRACT FROM AUTHOR]

Motivation: Genome-wide association studies (GWAS) have been widely used in discovering the association between genotypes and phenotypes. Human genome data contain valuable but highly sensitive information. Unprotected disclosure of such information might put individual's privacy at risk. It is important to protect human genome data. Exact logistic regression is a bias-reduction method based on a penalized likelihood to discover rare variants that are associated with disease susceptibility. We propose the HEALER framework to facilitate secure rare variants analysis with a small sample size. Results: We target at the algorithm design aiming at reducing the computational and storage costs to learn a homomorphic exact logistic regression model (i.e. evaluate P-values of coefficients), where the circuit depth is proportional to the logarithmic scale of data size. We evaluate the algorithm performance using rare Kawasaki Disease datasets. [ABSTRACT FROM AUTHOR]

Let d1 and d2 be discriminants of distinct quadratic imaginary orders Od1 and Od2 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 factorization 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 Od1 and Od2 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 Od1 and Od2 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ℓ (J(d1 ,d2 )) for any pair of discriminants d1 ≠ d2 and any prime ℓ >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. [ABSTRACT FROM AUTHOR]

We study the problem of efficiently constructing a curve $C$ of genus $2$ over a finite field $\mathbb{F}$ for which either the curve $C$ itself or its Jacobian has a prescribed number $N$ of $\mathbb{F}$-rational points.In the case of the Jacobian, we show that any ‘CM-construction’ to produce the required genus-$2$ curves necessarily takes time exponential in the size of its input.On the other hand, we provide an algorithm for producing a genus-$2$ curve with a given number of points that, heuristically, takes polynomial time for most input values. We illustrate the practical applicability of this algorithm by constructing a genus-$2$ curve having exactly $10^{2014}+9703$ (prime) points, and two genus-$2$ curves each having exactly $10^{2013}$ points.In an appendix we provide a complete parametrization, over an arbitrary base field $k$ of characteristic neither two nor three, of the family of genus-$2$ curves over $k$ that have $k$-rational degree-$3$ maps to elliptic curves, including formulas for the genus-$2$ curves, the associated elliptic curves, and the degree-$3$ maps.Supplementary materials are available with this article. [ABSTRACT FROM PUBLISHER]

This paper presents an algorithm to construct cryptographically strong genus $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}2$ curves and their Kummer surfaces via Rosenhain invariants and related Kummer parameters. The most common version of the complex multiplication (CM) algorithm for constructing cryptographic curves in genus 2 relies on the well-studied Igusa invariants and Mestre’s algorithm for reconstructing the curve. On the other hand, the Rosenhain invariants typically have much smaller height, so computing them requires less precision, and in addition, the Rosenhain model for the curve can be written down directly given the Rosenhain invariants. Similarly, the parameters for a Kummer surface can be expressed directly in terms of rational functions of theta constants. CM-values of these functions are algebraic numbers, and when computed to high enough precision, LLL can recognize their minimal polynomials. Motivated by fast cryptography on Kummer surfaces, we investigate a variant of the CM method for computing cryptographically strong Rosenhain models of curves (as well as their associated Kummer surfaces) and use it to generate several example curves at different security levels that are suitable for use in cryptography. [ABSTRACT FROM PUBLISHER]

Let $\mathcal{O}$ be a maximal order in a definite quaternion algebra over $\mathbb{Q}$ of prime discriminant $p$, and $\ell $ a small prime. We describe a probabilistic algorithm which, for a given left $\mathcal{O}$-ideal, computes a representative in its left ideal class of $\ell $-power norm. In practice the algorithm is efficient and, subject to heuristics on expected distributions of primes, runs in expected polynomial time. This solves the underlying problem for a quaternion analog of the Charles–Goren–Lauter hash function, and has security implications for the original CGL construction in terms of supersingular elliptic curves. [ABSTRACT FROM PUBLISHER]

We present a new algorithm to compute the classical modular polynomial Φl in the rings Z[X, Y ] and (Z/mZ)[X, Y ], for a prime l and any positive integer m. Our approach uses the graph of l-isogenies to efficiently compute Φl mod p for many primes p of a suitable form, and then applies the Chinese Remainder Theorem (CRT). Under the Generalized Riemann Hypothesis (GRH), we achieve an expected running time of O(l3(log l)3 log log l), and compute Φl mod m using O(l2(log l)2+l2 logm) space. We have used the new algorithm to compute Φl with l over 5000, and Φl mod m with l over 20000. We also consider several modular functions g for which Φg l is smaller than Φl, allowing us to handle l over 60000. [ABSTRACT FROM AUTHOR]