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$
$\endgroup$
5
-
$\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$– tyloCommented Jan 10, 2019 at 16:25
-
2$\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$– Chris PeikertCommented Jan 11, 2019 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$– user4936Commented Jan 11, 2019 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$– Chris PeikertCommented Jan 11, 2019 at 19:33
-
$\begingroup$ @ChrisPeikert Do you mind incorporating your comments into an answer? They appear to answer the question. $\endgroup$– Ella RoseCommented Jan 11, 2019 at 23:29
Add a comment
|