{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T18:08:00Z","timestamp":1757614080958,"version":"3.44.0"},"reference-count":89,"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":[[2025,7]]},"abstract":"<jats:p>\n            Decentralized Knowledge Graph (DKG) platforms allow the sharing of knowledge with multiple owners. While data owners can share their data with others by encrypting their data before sharing it, this na\u00efve approach prevents data encrypted by different owners from being queried together, as it compromises query verifiability, an essential DKG platform feature. We propose Pistis, the first DKG platform capable of preserving ownership while also enabling verifiable SPARQL queries. Two novel techniques facilitate this:\n            <jats:italic toggle=\"yes\">owner-managed end-to-end encryption<\/jats:italic>\n            and\n            <jats:italic toggle=\"yes\">collaborative query verification.<\/jats:italic>\n            In Pistis, data owners thus encrypt their data individually and collaborate to construct an authenticated data structure (ADS) with a global key by means of secret sharing and secure multi-party computation. Then, by indexing KG data as ciphertext over the ADS, Pistis offers a cryptographic scheme called VO-SPARQL that facilitates verifiable queries on encrypted KG data with multiple owners. Pistis provides succinct proofs for two-stage SPARQL queries, including subgraph queries based on the ADS and aggregation on encrypted intermediate results based on a key-aggregate cryptographic primitive. A theoretical analysis and an empirical study provide detailed insight into the performance of Pistis while offering provable security.\n          <\/jats:p>","DOI":"10.14778\/3749646.3749716","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T17:55:06Z","timestamp":1757008506000},"page":"4602-4615","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Pistis: A Decentralized Knowledge Graph Platform Enabling Ownership-Preserving SPARQL Querying"],"prefix":"10.14778","volume":"18","author":[{"given":"Enyuan","family":"Zhou","sequence":"first","affiliation":[{"name":"PolyU SZRI"}]},{"given":"Song","family":"Guo","sequence":"additional","affiliation":[{"name":"HKUST"}]},{"given":"Zicong","family":"Hong","sequence":"additional","affiliation":[{"name":"HKUST"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aalborg University"}]},{"given":"Yang","family":"Xiao","sequence":"additional","affiliation":[{"name":"Xidian University"}]},{"given":"Jinwen","family":"Liang","sequence":"additional","affiliation":[{"name":"HK PolyU"}]},{"given":"Dalin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Aalborg University"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.59"},{"key":"e_1_2_1_2_1","unstructured":"ActivityPub. 2025. ActivityPub. https:\/\/activitypub.rocks\/. Accessed: 2025-05-01."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-21348-0_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30793-6_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3450037"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589334.3645704"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.24297\/ijmit.v2i1.1406"},{"key":"e_1_2_1_8_1","volume-title":"Tutorial: Deploying Secure Multi-Party Computation on the Web Using JIFF. 2019 IEEE Cybersecurity Development (SecDev)","author":"Albab Kinan Dak","year":"2019","unstructured":"Kinan Dak Albab, Rawane Issa, Andrei Lapets, Peter Flockhart, Lucy Qin, and Ira Globus-Harris. 2019. Tutorial: Deploying Secure Multi-Party Computation on the Web Using JIFF. 2019 IEEE Cybersecurity Development (SecDev) (2019), 3\u20133."},{"key":"e_1_2_1_9_1","volume-title":"A survey of RDF stores & SPARQL engines for querying knowledge graphs. The VLDB Journal","author":"Ali Waqas","year":"2022","unstructured":"Waqas Ali, Muhammad Saleem, Bin Yao, Aidan Hogan, and Axel-Cyrille Ngonga Ngomo. 2022. A survey of RDF stores & SPARQL engines for querying knowledge graphs. The VLDB Journal (2022), 1\u201326."},{"volume-title":"Proc. of the EuroSys Conference","year":"2018","key":"e_1_2_1_10_1","unstructured":"Elli. Androulaki. 2018. Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains. In Proc. of the EuroSys Conference (Porto, Portugal) (EuroSys). Article 30, 15 pages."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457558"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3538598.3538599"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1315245.1315318"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380177"},{"key":"e_1_2_1_15_1","volume-title":"20th USENIX Conference on File and Storage Technologies (FAST 22)","author":"Bacs Andrei","year":"2022","unstructured":"Andrei Bacs, Saidgani Musaev, Kaveh Razavi, Cristiano Giuffrida, and Herbert Bos. 2022. {DUPEFS}: Leaking Data Over the Network With Filesystem Deduplication Side Channels. In 20th USENIX Conference on File and Storage Technologies (FAST 22). 281\u2013296."},{"key":"e_1_2_1_16_1","first-page":"2","volume-title":"Ipfs-content addressed, versioned","author":"Benet Juan","year":"2014","unstructured":"Juan Benet. 2014. Ipfs-content addressed, versioned, p2p file system. arXiv preprint arXiv:1407.3561 (2014)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2007.11"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-007-9005-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978429"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00020"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988760"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001459910006"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54631-0_7"},{"key":"e_1_2_1_24_1","first-page":"173","article-title":"Practical byzantine fault tolerance","volume":"99","author":"Castro Miguel","year":"1999","unstructured":"Miguel Castro, Barbara Liskov, et al. 1999. Practical byzantine fault tolerance. In Proc. of OSDI, Vol. 99. 173\u2013186.","journal-title":"Proc. of OSDI"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17373-8_33"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Daniel Demmler Thomas Schneider and Michael Zohner. 2015. ABY-A framework for efficient mixed-protocol secure two-party computation. In NDSS.","DOI":"10.14722\/ndss.2015.23113"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/EuroSP57164.2023.00017"},{"key":"e_1_2_1_28_1","unstructured":"Ethereum. 2013. Go Ethereum. https:\/\/github.com\/ethereum\/go-ethereum."},{"key":"e_1_2_1_29_1","unstructured":"Apache Software Foundation. 2025. Apache Jena. https:\/\/jena.apache.org\/."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543873.3587583"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP54263.2024.00125"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3511947"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00686-1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2023.3235951"},{"key":"e_1_2_1_35_1","volume-title":"Secure Data Deduplication with Dynamic Ownership Management in Cloud Storage. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE). IEEE, 69\u201370","author":"Hur Junbeom","year":"2017","unstructured":"Junbeom Hur, Dongyoung Koo, Youngjoo Shin, and Kyungtae Kang. 2017. Secure Data Deduplication with Dynamic Ownership Management in Cloud Storage. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE). IEEE, 69\u201370."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00072"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2016.58"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417872"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3481997"},{"key":"e_1_2_1_40_1","unstructured":"Chenxin Li Peilun Li Dong Zhou Zhe Yang Ming Wu Guang Yang Wei Xu Fan Long and Andrew Chi-Chih Yao. 2020. A decentralized blockchain with high throughput and fast confirmation. In 2020 {USENIX} Annual Technical Conference ({USENIX}{ATC } 20). 515\u2013528."},{"key":"e_1_2_1_41_1","unstructured":"Jinyuan Li and David Mazieres. 2007. Beyond One-Third Faulty Replicas in Byzantine Fault Tolerant Systems.. In NSDI. 10\u201310."},{"key":"e_1_2_1_42_1","volume-title":"Authenticated Keyword Search on Large-Scale Graphs in Hybrid-Storage Blockchains. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE","author":"Li Siyu","year":"2024","unstructured":"Siyu Li, Zhiwei Zhang, Jiang Xiao, Meihui Zhang, Ye Yuan, and Guoren Wang. 2024. Authenticated Keyword Search on Large-Scale Graphs in Hybrid-Storage Blockchains. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 1958\u20131971."},{"key":"e_1_2_1_43_1","volume-title":"Authenticated Keyword Search on Large-Scale Graphs in Hybrid-Storage Blockchains. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE","author":"Li Siyu","year":"2024","unstructured":"Siyu Li, Zhiwei Zhang, Jiang Xiao, Meihui Zhang, Ye Yuan, and Guoren Wang. 2024. Authenticated Keyword Search on Large-Scale Graphs in Hybrid-Storage Blockchains. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 1958\u20131971."},{"key":"e_1_2_1_44_1","volume-title":"Authenticated Subgraph Matching in Hybrid-Storage Blockchains. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE","author":"Li Siyu","year":"2024","unstructured":"Siyu Li, Zhiwei Zhang, Meihui Zhang, Ye Yuan, and Guoren Wang. 2024. Authenticated Subgraph Matching in Hybrid-Storage Blockchains. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 1986\u20131998."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2022.3213283"},{"key":"e_1_2_1_46_1","volume-title":"IEEE Transactions on Dependable and Secure Computing","author":"Liu Zhuotao","year":"2021","unstructured":"Zhuotao Liu, Yangxi Xiang, Jian Shi, Peng Gao, Haoyu Wang, Xusheng Xiao, Bihan Wen, Qi Li, and Yih-Chun Hu. 2021. Make Web3. 0 Connected. IEEE Transactions on Dependable and Secure Computing (2021)."},{"key":"e_1_2_1_47_1","volume-title":"In Proc. of the conference on the theory and application of cryptographic techniques. Springer","author":"Merkle Ralph C","year":"1987","unstructured":"Ralph C Merkle. 1987. A digital signature based on a conventional encryption function. In In Proc. of the conference on the theory and application of cryptographic techniques. Springer, Springer, Amsterdam, The Netherlands, 369\u2013378."},{"key":"e_1_2_1_48_1","unstructured":"MetaMask. 2025. MetaMask. https:\/\/metamask.io\/."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1149976.1149977"},{"key":"e_1_2_1_50_1","volume-title":"Bitcoin: A peer-to-peer electronic cash system.","author":"Nakamoto Satoshi","year":"2008","unstructured":"Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. (2008)."},{"key":"e_1_2_1_51_1","unstructured":"Ontotext. 2025. GraphDB. https:\/\/graphdb.ontotext.com\/."},{"key":"e_1_2_1_52_1","unstructured":"OriginTrail. 2025. OriginTrail. https:\/\/origintrail.io\/. Accessed: 2025-03-01."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22792-9_6"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35170-9_23"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00019"},{"key":"e_1_2_1_56_1","volume-title":"Adaptive distributed RDF graph fragmentation and allocation based on query workload","author":"Peng Peng","year":"2018","unstructured":"Peng Peng, Lei Zou, Lei Chen, and Dongyan Zhao. 2018. Adaptive distributed RDF graph fragmentation and allocation based on query workload. IEEE Transactions on Knowledge and Data Engineering (2018)."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00019"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043566"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2818696"},{"key":"e_1_2_1_60_1","unstructured":"Eric Prudhommeaux. 2008. SPARQL query language for RDF. http:\/\/www.w3.org\/TR\/rdf-sparql-query\/."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/3329772.3329775"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2017.12.005"},{"key":"e_1_2_1_63_1","unstructured":"Andrei Vlad Sambra Essam Mansour Sandro Hawke Maged Zereba Nicola Greco Abdurrahman Ghanem Dmitri Zagidulin Ashraf Aboulnaga and Tim Berners-Lee. [n.d.]. Solid: a platform for decentralized social applications based on linked data. ([n. d.])."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389144"},{"key":"e_1_2_1_65_1","volume-title":"29th USENIX Security Symposium (USENIX Security 20)","author":"Shafagh Hossein","year":"2020","unstructured":"Hossein Shafagh, Lukas Burkhalter, Sylvia Ratnasamy, and Anwar Hithnawi. 2020. Droplet: Decentralized authorization and access control for encrypted data streams. In 29th USENIX Security Symposium (USENIX Security 20). 2469\u20132486."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629489"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00190"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554826"},{"key":"e_1_2_1_70_1","volume-title":"Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper","author":"Wood Gavin","year":"2014","unstructured":"Gavin Wood. 2014. Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper (2014)."},{"key":"e_1_2_1_71_1","first-page":"782","article-title":"Integrity Auditing of Outsourced Data","volume":"7","author":"Xie Min","year":"2007","unstructured":"Min Xie, Haixun Wang, Jian Yin, and Xiaofeng Meng. 2007. Integrity Auditing of Outsourced Data.. In VLDB, Vol. 7. 782\u2013793.","journal-title":"VLDB"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300083"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2023.3267071"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523212"},{"key":"e_1_2_1_75_1","volume-title":"Cluster-Based Joins for Federated SPARQL Queries","author":"Yang Fan","year":"2021","unstructured":"Fan Yang, Adina Crainiceanu, Zhiyuan Chen, and Don Needham. 2021. Cluster-Based Joins for Federated SPARQL Queries. IEEE Transactions on Knowledge and Data Engineering (2021)."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/MNET.2023.10110018"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415540"},{"key":"e_1_2_1_78_1","volume-title":"2022 USENIX Annual Technical Conference (USENIX ATC 22)","author":"Yang Zuoru","year":"2022","unstructured":"Zuoru Yang, Jingwei Li, and Patrick PC Lee. 2022. Secure and Lightweight Deduplicated Storage via Shielded {Deduplication-Before-Encryption}. In 2022 USENIX Annual Technical Conference (USENIX ATC 22). 37\u201352."},{"key":"e_1_2_1_79_1","volume-title":"Proc. of the 27th Annual Symposium on Foundations of Computer Science (SFCS '86)","author":"Chi-Chih Yao Andrew","year":"1986","unstructured":"Andrew Chi-Chih Yao. 1986. How to generate and exchange secrets. In Proc. of the 27th Annual Symposium on Foundations of Computer Science (SFCS '86). IEEE, 162\u2013167."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40000.2020.00008"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583152"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389773"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535570.2488333"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415567"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.43"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813711"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589334.3645631"},{"key":"e_1_2_1_88_1","volume-title":"Proceedings of the VLDB Endowment.","author":"Zhou Enyuan","year":"2024","unstructured":"Enyuan Zhou, Song Guo, Zicong Hong, Christian S Jensen, Yang Xiao, Dalin Zhang, Jinwen Liang, and Qingqi Pei. 2024. VeriDKG: A Verifiable SPARQL Query Engine for Decentralized Knowledge Graphs. In Proceedings of the VLDB Endowment."},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457308"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3749646.3749716","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T03:32:53Z","timestamp":1757043173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3749646.3749716"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":89,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.14778\/3749646.3749716"],"URL":"https:\/\/doi.org\/10.14778\/3749646.3749716","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}