{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T18:55:32Z","timestamp":1772823332379,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,10]]},"abstract":"<jats:p>Data profiling is an important task to understand data semantics and is an essential pre-processing step in many tools. Due to privacy constraints, data is often partitioned into silos, with different access control. Discovering functional dependencies (FDs) usually requires access to all data partitions to find constraints that hold on the whole dataset. Simply applying general secure multi-party computation protocols incurs high computation and communication cost.<\/jats:p>\n          <jats:p>This paper formulates the FD discovery problem in the secure multi-party scenario. We propose secure constructions for validating candidate FDs, and present efficient cryptographic protocols to discover FDs over distributed partitions. Experimental results show that solution is practically efficient over non-secure distributed FD discovery, and can significantly outperform general purpose multi-party computation frameworks. To the best of our knowledge, our work is the first one to tackle this problem.<\/jats:p>","DOI":"10.14778\/3364324.3364332","type":"journal-article","created":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T03:16:00Z","timestamp":1599794160000},"page":"184-196","source":"Crossref","is-referenced-by-count":23,"title":["Secure multi-party functional dependency discovery"],"prefix":"10.14778","volume":"13","author":[{"given":"Chang","family":"Ge","sequence":"first","affiliation":[{"name":"University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ihab F.","family":"Ilyas","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Kerschbaum","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"IBM infosphere master data management. https:\/\/www.ibm.com\/ca-en\/marketplace\/ibm-infosphere-master-data-management.  IBM infosphere master data management. https:\/\/www.ibm.com\/ca-en\/marketplace\/ibm-infosphere-master-data-management."},{"key":"e_1_2_1_2_1","unstructured":"Regulation (eu) 2016\/679 of the european parliament and of the council of 27 april 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data and repealing directive 95\/46\/ec (general data protection regulation). OJ 2016-04-27.  Regulation (eu) 2016\/679 of the european parliament and of the council of 27 april 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data and repealing directive 95\/46\/ec (general data protection regulation). OJ 2016-04-27."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2661884"},{"issue":"12","key":"e_1_2_1_4_1","first-page":"1749","article-title":"From keys to databases - real-world applications of secure multi-party computation","volume":"61","author":"Archer D. W.","year":"2018","unstructured":"D. W. Archer , D. Bogdanov , Y. Lindell , L. Kamm , K. Nielsen , J. I. Pagter , N. P. Smart , and R. N. Wright . From keys to databases - real-world applications of secure multi-party computation . Comput. J. , 61 ( 12 ): 1749 -- 1771 , 2018 . D. W. Archer, D. Bogdanov, Y. Lindell, L. Kamm, K. Nielsen, J. I. Pagter, N. P. Smart, and R. N. Wright. From keys to databases - real-world applications of secure multi-party computation. Comput. J., 61(12):1749--1771, 2018.","journal-title":"Comput. J."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055334"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_2_1_7_1","volume-title":"Sept.","author":"Beskales G.","year":"2010","unstructured":"G. Beskales , I. F. Ilyas , and L. Golab . Sampling the repairs of functional dependency violations under hard constraints. PVLDB, 3(1--2):197--207 , Sept. 2010 . G. Beskales, I. F. Ilyas, and L. Golab. Sampling the repairs of functional dependency violations under hard constraints. PVLDB, 3(1--2):197--207, Sept. 2010."},{"key":"e_1_2_1_8_1","first-page":"48","volume-title":"Third International Symposium, ANTS-III","author":"Boneh D.","year":"1998","unstructured":"D. Boneh . The decision diffie-hellman problem. In Algorithmic Number Theory , Third International Symposium, ANTS-III , Portland, Oregon, USA, June 21--25 , 1998 , Proceedings, pages 48 -- 63 , 1998. D. Boneh. The decision diffie-hellman problem. In Algorithmic Number Theory, Third International Symposium, ANTS-III, Portland, Oregon, USA, June 21--25, 1998, Proceedings, pages 48--63, 1998."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/358549.358563"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35404-5_17"},{"key":"e_1_2_1_11_1","volume-title":"UCI machine learning repository","author":"Dheeru D.","year":"2017","unstructured":"D. Dheeru and E. Karra Taniskidou . UCI machine learning repository , 2017 . D. Dheeru and E. Karra Taniskidou. UCI machine learning repository, 2017."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2977797.2977802"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1216155.1216159"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1985.1057074"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28416"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.668973"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535218_15"},{"key":"e_1_2_1_20_1","first-page":"1257","volume-title":"CCS","author":"Kolesnikov V.","year":"2017","unstructured":"V. Kolesnikov , N. Matania , B. Pinkas , M. Rosulek , and N. Trieu . Practical multi-party private set intersection from symmetric-key techniques . In CCS , pages 1257 -- 1272 , 2017 . V. Kolesnikov, N. Matania, B. Pinkas, M. Rosulek, and N. Trieu. Practical multi-party private set intersection from symmetric-key techniques. In CCS, pages 1257--1272, 2017."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/646765.704129"},{"key":"e_1_2_1_22_1","volume-title":"Secure multiparty computation for privacy-preserving data mining. IACR Cryptology ePrint Archive","author":"Lindell Y.","year":"2008","unstructured":"Y. Lindell and B. Pinkas . Secure multiparty computation for privacy-preserving data mining. IACR Cryptology ePrint Archive , 2008 :197, 2008. Y. Lindell and B. Pinkas. Secure multiparty computation for privacy-preserving data mining. IACR Cryptology ePrint Archive, 2008:197, 2008."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.197"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/645339.650138"},{"key":"e_1_2_1_25_1","volume-title":"VLDB","author":"Madhavan J.","year":"2001","unstructured":"J. Madhavan , P. A. Bernstein , and E. Rahm . Generic schema matching with cupid . In VLDB , 2001 . J. Madhavan, P. A. Bernstein, and E. Rahm. Generic schema matching with cupid. In VLDB, 2001."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732279.2732282"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704383633"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/645504.656418"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756123.1756146"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824086"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915203"},{"key":"e_1_2_1_32_1","first-page":"342","volume-title":"EDBT","author":"Papenbrock T.","year":"2017","unstructured":"T. Papenbrock and F. Naumann . Data-driven schema normalization . In EDBT , pages 342 -- 353 , 2017 . T. Papenbrock and F. Naumann. Data-driven schema normalization. In EDBT, pages 342--353, 2017."},{"key":"e_1_2_1_33_1","first-page":"248","volume-title":"EUROCRYPT","author":"Park C.","year":"1993","unstructured":"C. Park , K. Itoh , and K. Kurosawa . Efficient anonymous channel and all\/nothing election scheme . In EUROCRYPT , pages 248 -- 259 , 1993 . C. Park, K. Itoh, and K. Kurosawa. Efficient anonymous channel and all\/nothing election scheme. In EUROCRYPT, pages 248--259, 1993."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137631"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2006.889687"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00149"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44801-2_11"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.25"},{"key":"e_1_2_1_39_1","first-page":"729","volume-title":"ICDM","author":"Yao H.","year":"2002","unstructured":"H. Yao , H. J. Hamilton , and C. J. Butz . Fdmine: discovering functional dependencies in a database using equivalences . In ICDM , pages 729 -- 732 , 2002 . H. Yao, H. J. Hamilton, and C. J. Butz. Fdmine: discovering functional dependencies in a database using equivalences. In ICDM, pages 729--732, 2002."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3364324.3364332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:01:59Z","timestamp":1672225319000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3364324.3364332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["10.14778\/3364324.3364332"],"URL":"https:\/\/doi.org\/10.14778\/3364324.3364332","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,10]]}}}