It seems that the lattice functions are either surjective (SIS) or injective (LWE), due to the error that is basically intended to destroy the structure and provide security. I was wondering whether there exist bijective functions for lattice, more precisely trapdoor permutations? Is there any work that has studied this?

  • $\begingroup$ Problems are not functions, so calling them injective or surjective does not make sense. Decision problems return yes/no, and computational problems return a solution, which is usually a single group element with a special property. And encryption schemes from trapdoor functions have to be statistically bijective or they are not encryption schemes $\endgroup$
    – tylo
    Jan 10 '19 at 16:25
  • 1
    $\begingroup$ One-way permutations (with or without trapdoor) are not yet known from any standard lattice problem. However, there are constructions from indistinguishability obfuscation (iO)—whose candidate constructions are somehow lattice-related (but not with any great confidence about their security). $\endgroup$ Jan 11 '19 at 19:18
  • $\begingroup$ @ChrisPeikert Thanks for the reply. Can you point me to some of these work? Also what exactly “somehow lattice-related” mean here? $\endgroup$
    – tinker
    Jan 11 '19 at 19:30
  • 1
    $\begingroup$ Start here: eprint.iacr.org/2015/752 . “Somehow lattice-based” means that the constructions use ideas from lattices, but don’t have security proofs based on any standard hard lattice problem. (And indeed, many of the constructions ended up being breakable without having to solve any lattice problem.) $\endgroup$ Jan 11 '19 at 19:33
  • $\begingroup$ @ChrisPeikert Do you mind incorporating your comments into an answer? They appear to answer the question. $\endgroup$
    – Ella Rose
    Jan 11 '19 at 23:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.