| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

2. Multilinear map constructions


    1. Add remark

      Problem 2.1.

      [Kristin Lauter] Can we construct a bilinear pairing which takes values in E(F_q) where the source groups are also Discrete-Log-Hard?
        1. Remark. [Dan Boneh] This would give a 4-mmap.
            • Remark. [Lauter] One possible approach would be to use Weil restrictions...


                • Add remark

                  Problem 2.2.

                  [Amit Sahai] Does there exist a quantum-resistant bilinear map?
                    1. Remark. For this to exist, we would not be able to have canonical representations...


                        • Add remark

                          Problem 2.3.

                          [Kristin Lauter] Can we construct multilinear maps from supersingular isogeny graphs?
                            1. Remark. These are already used for cryptographic hash functions.


                                • Add remark

                                  Problem 2.4.

                                  [Ted Chinburg] When can you find algebraically defined multilinear maps involving group schemes of p-power order?
                                    1. Remark. [Lenstra] If the characteristic is not equal to $p$ then you can just look at Galois actions.
                                        • Remark. [Krashen] What about tori? Semi-abelian varieties? DLP will be hard, but is there a reasonable pairing?
                                            • Remark. [Silverberg] One should bear in mind the "impossibility result" at the end of the 2003 Boneh-Silverberg paper.
                                                • Remark. [Krashen] Lets add torus-valued multilinear maps.


                                                    • Add remark

                                                      Problem 2.5.

                                                      [Huang] Can we get multilinear maps from cohomological constructions? In particular, there is a natural multiplication map from $A[\ell]^{2g}$ into $\mu_\ell^{\otimes g}$ essentially given by the wedge-product structure. Can we find a way to get better target group?
                                                        1. Remark. Is zero-testing possible in Chow groups?


                                                            • Add remark

                                                              Problem 2.6.

                                                              [Dan Boneh] Can we find a pairing friendly elliptic curve with embedding degree $13$? Destiny estimates suggest they exist, but how do we find them?
                                                                1. Remark. [Boneh] Can find them with embedding degree 12, but a prime would be better.


                                                                    • Add remark

                                                                      Problem 2.7.

                                                                      [Rachel Lin] Is there a way to have direct bootstrapping from k-linear maps to (k+1)-linear maps that do not take advantage of specific properties of the map?


                                                                        • Add remark

                                                                          Problem 2.8.

                                                                          [Tiboushi] The intersection product on cycles defines a linear map. Unfortunately, the target is ${\mathbb Z}$ where the discrete log problem is easy. Can we define an equivalence relation on cycles so that there is a canonical representative that might make this more useful? Would changing the coefficient ring of cohomology help?
                                                                            1. Remark. Concretely, what if we look at K3 surfaces?


                                                                                • Add remark

                                                                                  Problem 2.9.

                                                                                  [Ted Chinburg] Let X be an abelian surface over the algebraic closure of a finite field of characteristic different from $\ell$. One candidate for a multilinear map might be the cup product \[H^1(X, \mu_\ell) \times H^1(X, \mu_\ell) \times H^2(X, \mu_\ell) \rightarrow H^4(X,\mu_\ell^{\otimes 3}) \cong \mu_\ell\]

                                                                                  Would this work?

                                                                                  Specifically, $H^2(X,\mu_\ell)$ is related to the Brauer group $Br(X)[\ell]$. How hard is it to do concrete calculations in this group?
                                                                                    1. Remark. [Lauter] Try Kolyvagin classes?
                                                                                        • Remark. [Chinburg] More generally, think about $H^{2d}(X, \mu_\ell^{\otimes d+1}) \cong \mu_{\ell}$ for any smooth, projective variety $X$ of dimension $d$.
                                                                                            • Remark. [Krashen] One issue might be coefficients. Maybe look at ${\mathbb Z}/\ell {\mathbb Z}$?
                                                                                                • Remark. [Kedlaya] A more general meta-question is when etale cohomology is computable at all?
                                                                                                    • Remark. [org.aimpl.user:ted@math.upenn.edu] When X is an abelian surface, Ed Schaefer suggested writing elements of $H^2(X,\mu_\ell)$ as sums of cup products coming from $H^1(X,Z/\ell) \times H^1(X,\mu_\ell)$. In the cup product map $$H^1(X,\mu_\ell) \times H^1(X,\mu_\ell) \times H^1(X,Z/\ell) \times H^1(X,\mu_\ell) \to H^4(X,\mu_\ell^{\otimes 3})$$ one could consider fixing on of the arguments, e.g. the one in $H^1(X,Z/\ell)$.

                                                                                                          Cite this as: AimPL: Constructing cryptographic multilinear maps, available at http://aimpl.org/cryptomultilin.