{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:30:41Z","timestamp":1761294641893},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p>\n            Order-preserving encryption (OPE) allows efficient comparison operations over encrypted data and thus is popular in encrypted databases. However, most existing OPE schemes are vulnerable to inference attacks as they leak plaintext frequency. To this end, some\n            <jats:italic>frequency-hiding<\/jats:italic>\n            order-preserving encryption (FH-OPE) schemes are proposed and claim to prevent the leakage of frequency. FH-OPE schemes are considered an important step towards mitigating inference attacks.\n          <\/jats:p>\n          <jats:p>\n            Unfortunately, there are still vulnerabilities in all existing FH-OPE schemes. In this work, we revisit the security of all existing FH-OPE schemes. We are the first to demonstrate that plaintext frequency hidden by them is recoverable. We present three ciphertext-only attacks named\n            <jats:italic>frequency-revealing attacks<\/jats:italic>\n            to recover plaintext frequency. We evaluate our attacks in three real-world datasets. They recover over 90% of plaintext frequency hidden by any existing FH-OPE scheme. With frequency revealed, we also show the potentiality to apply inference attacks on existing FH-OPE schemes.\n          <\/jats:p>\n          <jats:p>Our findings highlight the limitations of current FH-OPE schemes. Our attacks demonstrate that achieving frequency-hiding requires addressing the leakages of both non-uniform ciphertext distribution and insertion orders of ciphertexts, even though the leakage of insertion orders is always ignored in OPE.<\/jats:p>","DOI":"10.14778\/3611479.3611513","type":"journal-article","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T02:08:08Z","timestamp":1692929288000},"page":"3124-3136","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Frequency-Revealing Attacks against Frequency-Hiding Order-Preserving Encryption"],"prefix":"10.14778","volume":"16","author":[{"given":"Xinle","family":"Cao","sequence":"first","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Liu","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongsheng","family":"Shen","sequence":"additional","affiliation":[{"name":"Hang Zhou City Brain Co., Ltd, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaohua","family":"Ye","sequence":"additional","affiliation":[{"name":"Hang Zhou City Brain Co., Ltd, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kui","family":"Ren","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,8,24]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"https:\/\/www.ssa.gov\/. Accessed","year":"2023","unstructured":"[n.d.]. https:\/\/www.ssa.gov\/. Accessed in July 2023 . [n.d.]. https:\/\/www.ssa.gov\/. Accessed in July 2023."},{"key":"e_1_2_1_2_1","volume-title":"https:\/\/www.osi.ca.gov\/CalHEERS.html. Accessed","year":"2023","unstructured":"[n.d.]. https:\/\/www.osi.ca.gov\/CalHEERS.html. Accessed in July 2023 . [n.d.]. https:\/\/www.osi.ca.gov\/CalHEERS.html. Accessed in July 2023."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-32833-1_36"},{"key":"e_1_2_1_4_1","volume-title":"Breach-resistant structured encryption. Cryptology ePrint Archive","author":"Amjad Ghous","year":"2018","unstructured":"Ghous Amjad , Seny Kamara , and Tarik Moataz . 2018. Breach-resistant structured encryption. Cryptology ePrint Archive ( 2018 ). Ghous Amjad, Seny Kamara, and Tarik Moataz. 2018. Breach-resistant structured encryption. Cryptology ePrint Archive (2018)."},{"key":"e_1_2_1_5_1","unstructured":"Arvind Arasu Spyros Blanas Ken Eguro Raghav Kaushik Donald Kossmann Ravishankar Ramamurthy and Ramarathnam Venkatesan. 2013. Orthogonal Security with Cipherbase. In CIDR.  Arvind Arasu Spyros Blanas Ken Eguro Raghav Kaushik Donald Kossmann Ravishankar Ramamurthy and Ramarathnam Venkatesan. 2013. Orthogonal Security with Cipherbase. In CIDR."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236217"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3324301.3324309"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3324301.3324309"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01001-9_13"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22792-9_33"},{"key":"e_1_2_1_11_1","unstructured":"Xinle Cao Jian Liu Yongsheng Shen Xiaohua Ye and Kui Ren. 2023. Frequency-revealing attacks against Frequency-hiding Order-preserving Encryption. Cryptology ePrint Archive Paper 2023\/1122. https:\/\/eprint.iacr.org\/2023\/1122 https:\/\/eprint.iacr.org\/2023\/1122.  Xinle Cao Jian Liu Yongsheng Shen Xiaohua Ye and Kui Ren. 2023. Frequency-revealing attacks against Frequency-hiding Order-preserving Encryption. Cryptology ePrint Archive Paper 2023\/1122. https:\/\/eprint.iacr.org\/2023\/1122 https:\/\/eprint.iacr.org\/2023\/1122."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00098"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15985-5_6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978379"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417275"},{"key":"e_1_2_1_16_1","volume-title":"Statistical methods for research workers","author":"Fisher Ronald Aylmer","unstructured":"Ronald Aylmer Fisher . 1954. Statistical methods for research workers ; 20 th ed. Oliver and Boyd , Edinburgh . https:\/\/cds.cern.ch\/record\/724001 Ronald Aylmer Fisher. 1954. Statistical methods for research workers; 20th ed. Oliver and Boyd, Edinburgh. https:\/\/cds.cern.ch\/record\/724001","edition":"20"},{"key":"e_1_2_1_17_1","volume-title":"29th USENIX Security Symposium (USENIX Security 20)","author":"Grubbs Paul","year":"2020","unstructured":"Paul Grubbs , Anurag Khandelwal , Marie-Sarah Lacharit\u00e9 , Lloyd Brown , Lucy Li , Rachit Agarwal , and Thomas Ristenpart . 2020 . Pancake: Frequency smoothing for encrypted data stores . In 29th USENIX Security Symposium (USENIX Security 20) . 2451--2468. Paul Grubbs, Anurag Khandelwal, Marie-Sarah Lacharit\u00e9, Lloyd Brown, Lucy Li, Rachit Agarwal, and Thomas Ristenpart. 2020. Pancake: Frequency smoothing for encrypted data stores. In 29th USENIX Security Symposium (USENIX Security 20). 2451--2468."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.44"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183754"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978386"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813629"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660277"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/sp40000.2020.00029"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00002"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3484224.3484228"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Matteo Maffei M. Reinert and Dominique Schr\u00f6der. 2017. On the Security of Frequency-Hiding Order-Preserving Encryption. In CANS.  Matteo Maffei M. Reinert and Dominique Schr\u00f6der. 2017. On the Security of Frequency-Hiding Order-Preserving Encryption. In CANS.","DOI":"10.1007\/978-3-030-02641-7_3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749455"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813651"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813651"},{"key":"e_1_2_1_30_1","volume-title":"An Ideal-Security Protocol for Order-Preserving Encoding. 2013 IEEE Symposium on Security and Privacy","author":"Popa Raluca A.","year":"2013","unstructured":"Raluca A. Popa , Frank H. Li , and Nickolai Zeldovich . 2013 . An Ideal-Security Protocol for Order-Preserving Encoding. 2013 IEEE Symposium on Security and Privacy (2013), 463--477. Raluca A. Popa, Frank H. Li, and Nickolai Zeldovich. 2013. An Ideal-Security Protocol for Order-Preserving Encoding. 2013 IEEE Symposium on Security and Privacy (2013), 463--477."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043566"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978345"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560610"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45608-8_3"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535573.2488336"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3611479.3611513","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T22:20:57Z","timestamp":1695507657000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611479.3611513"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":35,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.14778\/3611479.3611513"],"URL":"https:\/\/doi.org\/10.14778\/3611479.3611513","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,7]]},"assertion":[{"value":"2023-08-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}