In　cloud　era,　it　is　necessary　to　store　sensitive　data　in　an　encrypted　form.　This　arises　the　interesting　and　challenging　problem　of　searching　on　encrypted　data.　However,　previous　Public-key　Encryption　with　Keyword　Search　(PEKS)　inherently　cannot　resist　against　inside　keyword　guessing　attacks.　To　alleviate　this　issue,　recently　Huang　and　Li　proposed　the　notion　of　Public-key　Authenticated　Encryption　with　Keyword　Search　(PAEKS),　which　requires　the　data　sender　not　only　encrypting　a　keyword　using　the　receiver＇s　public　key,　but　also　authenticating　it　using　his　secret　key.　This　paper　first　revisits　HL-PAEKS　security　model　and　finds　that　it　did　not　capture　a　realistic　threat,　called　(outside)　chosen　multi-ciphertext　attacks.　That　is,　an　outside　adversary　can　decide　whether　two　encrypted　files　share　some　identical　keywords　or　not.　To　resolve　this　issue,　we　propose　a　new　PAEKS　security　model　that　captures　both　(outside)　chosen　multi-ciphertext　attacks　and　(inside)　keyword　guessing　attacks.　Then,　we　give　a　concrete　PAEKS　scheme　and　prove　its　security　in　the　new　PAEKS　security　model.　We　also　propose　a　method　to　simplify　data　sender＇s　key　management　using　identity-based　key　exchange　protocol.　Finally,　we　provide　implementation　results　of　our　schemes　to　show　the　comparable　efficiency　of　our　schemes　with　previous　PEKS/PAEKS　schemes.　(C)　2020　Elsevier　Inc.　All　rights　reserved.