Secure　outsourced　computation　is　critical　for　cloud　computing　to　safeguard　data　confidentiality　and　ensure　data　usability.　Recently,　secure　outsourced　computation　schemes　following　a　twin-server　architecture　based　on　partially　homomorphic　cryptosystems　have　received　increasing　attention.　The　Secure　Outsourced　Computation　on　Integers　(SOCI)　toolkit　is　the　state-of-the-art　among　these　schemes　which　can　perform　secure　computation　on　integers　without　requiring　the　costly　bootstrapping　operation　as　in　fully　homomorphic　encryption;　however,　SOCI　suffers　from　relatively　large　computation　and　communication　overhead.　In　this　paper,　we　propose　SOCI+　which　significantly　improves　the　performance　of　SOCI.　Specifically,　SOCI+　employs　a　novel　(2,　2)-threshold　Paillier　cryptosystem　with　fast　encryption　and　decryption　as　its　cryptographic　primitive,　and　supports　a　suite　of　efficient　secure　arithmetic　computation　on　integers　protocols,　including　a　secure　multiplication　protocol　(SMUL),　a　secure　comparison　protocol　(SCMP),　a　secure　sign　bit-acquisition　protocol　(SSBA),　and　a　secure　division　protocol　(SDIV),　all　based　on　the　(2,　2)-threshold　Paillier　cryptosystem　with　fast　encryption　and　decryption.　In　addition,　SOCI+　incorporates　an　offline　and　online　computation　mechanism　to　further　optimize　its　performance.　We　perform　rigorous　theoretical　analysis　to　prove　the　correctness　and　security　of　SOCI+.　Compared　with　SOCI,　our　experimental　evaluation　shows　that　SOCI+　is　up　to　5.3　times　more　efficient　in　online　runtime　and　40%　less　in　communication　overheads.　©　2005-2012　IEEE.