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

1. Public Key Encryption


    1. Add remark

      Problem 1.1.

      [Amit Sahai] Provide a public key encryption scheme using only a one-way function given as a circuit.
        1. Remark. It is known that if the One-Way Function is given as a black box then this is provably impossible.
            • Remark. If we can provably show obfuscation then this is possible. This was elaborated on in Rachel Lin’s talk.


                • Add remark

                  Problem 1.2.

                  [Sanjam Garg] Construct a PKE scheme from hardness of discrete-log problem in a specific group.


                    • Add remark

                      Problem 1.3.

                      [Dan Boneh] Explore security of obfuscation constructions that use current candidate multilinear maps.
                        1. Remark. [Garg] One example of this would be the "MDDH without zeroes" assumption that will be described in detail in Zhandry’s talk.


                            • Add remark

                              Problem 1.4.

                              [Rachel Lin] What is the security of d-local pseudorandom number generators? This means that each bit of the string depends on at most d bits of the seed.
                                1. Remark. [Lin] If $d \le 4$ then these are broken, but very little is known for $d \ge 5$.


                                    • Add remark

                                      Problem 1.5.

                                      [Rachel Lin] Can we construct local pseudorandom number generators from algebraic methods?

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