Structured　Encryption　(STE),　which　allows　a　server　to　provide　secure　search　services　on　encrypted　data　structures,　has　been　widely　investigated　in　recent　years.　To　meet　expressive　search　requirements　in　practical　applications,　a　large　number　of　STE　constructions　have　been　proposed　either　on　textual　keywords　or　spatial　data.　However,　STE　on　spatio-textual　data,　which　are　widely　used　in　location-based　services,　has　not　been　fully　investigated.　In　this　paper,　we　formally　define　the　notion　of　Spatial　Keyword　Structured　Encryption　(SKSE)　and　propose　several　concrete　SKSE　constructions　with　various　efficiency-security　trade-offs.　Firstly,　we　propose　a　basic　construction　with　linear　search　complexity,　which　only　leaks　the　private　files　matching　both　spatial　range　query　and　all　query　keywords.　Then,　to　improve　the　search　efficiency　on　large-scale　datasets,　we　present　a　novel　tree-based　construction　with　sub-linear　search　complexity.　Finally,　we　introduce　a　post-validation　approach　to　remove　false　positives　and　further　improve　storage　and　search　performance.　Our　constructions　are　general　in　the　sense　that　they　can　be　constructed　from　any　hidden　vector　encryption　schemes,　including　public-key　setting　and　symmetric-key　setting,　which　can　meet　different　sharing　requirements.　Our　rigorous　security　analysis　and　comprehensive　performance　evaluation　demonstrate　that　the　proposed　constructions　are　secure　and　outperform　the　start-of-the-art　solutions.　©　2005-2012　IEEE.