In　the　era　of　cloud　computing,　the　cloud　server　always　plays　a　significant　role　to　carry　the　heavy　tasks　of　computation.　As　for　storage　services,　it　provides　an　efficient　manner　for　accessing　data.　For　data　privacy,　encryption　is　usually　referred　to　as　a　simple　approach,　but　in　fact　cloud　services　cannot　work　with　the　traditional　encryption.　Therefore,　outsourced　computing　over　encrypted　data　receives　attention　of　preserving　privacy　in　the　cloud　setting.　The　notion,　privacy-preserving　outsourced　similarity　test　(PPOS)　over　encrypted　data,　is　introduced　to　capture　the　following　scenario.　The　cloud　stores　encrypted　data　with　the　encrypted　feature　vector　and　then　picks　up　the　target　data　by　testing　similarity　between　those　vectors　and　the　search　query.　Recently,　Zhang　et　al.　proposed　a　PPOS　scheme　based　on　additive　homomorphic　encryption,　garbled　circuits,　and　ciphertext-policy　attribute-based　encryption.　In　this　paper,　we　aim　for　presenting　the　formal　security　model　and　new　scheme　of　PPOS.　We　use　as　few　primitives　as　possible　to　minimize　cryptographic　building　blocks.　Our　solution　avoids　using　homomorphic　encryption　and　constructs　the　PPOS　scheme　simply　from　garbled　circuits　and　ciphertext-policy　attribute-based　encryption.　©　2018　IEEE.