
## 2. Multilinear map constructions

1. #### 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...
• #### 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...
• #### Problem 2.3.

[Kristin Lauter] Can we construct multilinear maps from supersingular isogeny graphs?
1. Remark. These are already used for cryptographic hash functions.
• #### 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.
• #### 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?
• #### 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.
• #### 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?
• #### 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?
• #### 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.