2. Multilinear map constructions

Problem 2.1.
[Kristin Lauter] Can we construct a bilinear pairing which takes values in E(F_q) where the source groups are also DiscreteLogHard?
Remark. [Dan Boneh] This would give a 4mmap.

Remark. [Lauter] One possible approach would be to use Weil restrictions...


Problem 2.2.
[Amit Sahai] Does there exist a quantumresistant bilinear map?
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?
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 ppower order?
Remark. [Lenstra] If the characteristic is not equal to $p$ then you can just look at Galois actions.

Remark. [Krashen] What about tori? Semiabelian 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 BonehSilverberg paper.

Remark. [Krashen] Lets add torusvalued 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 wedgeproduct structure. Can we find a way to get better target group?
Remark. Is zerotesting 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?
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 klinear 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?
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?
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 metaquestion 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.