skip to main content


Title: Multiparty Non-Interactive Key Exchange and More From Isogenies on Elliptic Curves
Abstract 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. Our framework builds a cryptographic invariant map , which is a new primitive closely related to a cryptographic multilinear map, but whose range does not necessarily have a group structure. Nevertheless, we show that a cryptographic invariant map can be used to build several cryptographic primitives, including NIKE, that were previously constructed from multilinear maps and indistinguishability obfuscation.  more » « less
Award ID(s):
1703321
PAR ID:
10173991
Author(s) / Creator(s):
; ; ; ; ; ; ;
Date Published:
Journal Name:
Journal of Mathematical Cryptology
Volume:
14
Issue:
1
ISSN:
1862-2976
Page Range / eLocation ID:
5 to 14
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Let $A$ be a non-isotrivial ordinary abelian surface over a global function field of characteristic $p>0$ with good reduction everywhere. Suppose that $A$ does not have real multiplication by any real quadratic field with discriminant a multiple of $p$ . We prove that there are infinitely many places modulo which $A$ is isogenous to the product of two elliptic curves. 
    more » « less
  2. Abstract Given a K3 surface X over a number field K with potentially good reduction everywhere, we prove that the set of primes of K where the geometric Picard rank jumps is infinite. As a corollary, we prove that either $X_{\overline {K}}$ has infinitely many rational curves or X has infinitely many unirational specialisations. Our result on Picard ranks is a special case of more general results on exceptional classes for K3 type motives associated to GSpin Shimura varieties. These general results have several other applications. For instance, we prove that an abelian surface over a number field K with potentially good reduction everywhere is isogenous to a product of elliptic curves modulo infinitely many primes of K . 
    more » « less
  3. Aerial drones are becoming an integral part of application domains including but not limited to, military operations, package delivery, construction, monitoring and search/rescue operations. It is critical to ensure the cyber security of networked aerial drone systems in these applications. Standard cryptographic services can be deployed to provide basic security services; however, they have been shown to be inefficient in terms of energy and time consumption, especially for small aerial drones with resource-limited processors. Therefore, there is a significant need for an efficient cryptographic framework that can meet the requirements of small aerial drones. We propose an improved cryptographic framework for small aerial drones, which offers significant energy efficiency and speed advantages over standard cryptographic techniques. (i) We create (to the best of our knowledge) the first optimized public key infrastructure (PKI) based framework for small aerial drones, which provides energy efficient techniques by harnessing special precomputation methods and optimized elliptic curves. (ii) We also integrate recent light-weight symmetric primitives into our PKI techniques to provide a full-fledged cryptographic framework. (iii) We implemented standard counterparts and our proposed techniques on an actual small aerial drone (Crazyflie 2.0), and provided an in-depth energy analysis. Our experiments showed that our improved cryptographic framework achieves up to 35× lower energy consumption than its standard counterpart. 
    more » « less
  4. Abstract. We study the extent to which curves over finite fields are characterized by their zeta functions and the zeta functions of certain of their covers. Suppose C and C ′ are curves over a finite field K, with K-rational base points P and P ′ , and let D and D ′ be the pullbacks (via the Abel–Jacobi map) of the multiplication-by-2 maps on their Jacobians. We say that (C, P) and (C ′ , P ′ ) are doubly isogenous if Jac(C) and Jac(C ′ ) are isogenous over K and Jac(D) and Jac(D ′ ) are isogenous over K. For curves of genus 2 whose automorphism groups contain the dihedral group of order eight, we show that the number of pairs of doubly isogenous curves is larger than na¨ıve heuristics predict, and we provide an explanation for this phenomenon. 
    more » « less
  5. This paper studies a multi-party private set union (mPSU), a fundamental cryptographic problem that allows multiple parties to compute the union of their respective datasets without revealing any additional information. We propose an efficient mPSU protocol which is secure in the presence of any number of colluding semi-honest participants. Our protocol avoids computationally expensive homomorphic operations or generic multi-party computation, thus providing an efficient solution for mPSU. The crux of our protocol lies in the utilization of new cryptographic tool, namely, Membership Oblivious Transfer (mOT). We believe that the mOT may be of independent interest. We implement our mPSU protocol and evaluate its performance. Our protocol shows an improvement of up to $80.84 times$ in terms of running time and $405.73 times$ bandwidth cost compared to the existing state-of-the-art protocols.

     
    more » « less