Practical Data-intensive Secure Computation: a Data Structural Approach

Lead Research Organisation: Newcastle University
Department Name: Sch of Computing

Abstract

In the past a few year, we have seen a dramatic increase in the scale and financial damage caused by cyber attacks. A survey commissioned by the government's Department for Business, Innovations and Skills (BIS) found that 93% of large businesses and 87% of smaller businesses suffered security breaches during 2013. An estimation from IDC says that companies around the world will spend $364 billion for dealing with data breaches in 2014. Data security is of paramount importance for most organisations. Compounding the problem, changes in computing -- particularly the booming of Cloud computing and collaborative data analysis -- has added another layer of complexity to the security landscape.

Secure computation has the potential to completely reshape the cybersecruity landscape, but this will happen only if we can make it practical. Despite significant improvements recently, secure computation is still orders of magnitude slower than computation in the clear. Even with the latest technology, running the killer apps, which are often data-intensive, in secure computation is still a mission impossible. To make secure computation practical, we propose this groundbreaking data structural approach.

In computer science, there are two fundamental approaches to improve performance of computation: by using a better algorithm, or by using a proper data structure. In secure computation, we have seen many improvements through the algorithmic approach. But surprisingly, data structures have been largely overlooked in the past. Recently, we have found ample evidence in our own and also others' research that data structures can be a key efficiency and scalability booster of secure computation. Based on the evidence, we believe the situation is sure to change: with data playing the central role and driving the computation, data structural design will become an indispensable part of secure computation.

It is time to systematically investigate the design of data structures and accompanied protocols in the context of secure computation. Our proposed research will make scientific advances by investigating both data structures and cryptography. The starting point will be comprehensive case-by-case studies. Then the focus will be solving more complex problems by composition and to make data structures generic across multiple secure computation frameworks. Eventually we will draw design principles to guide future design practice.

Planned Impact

Who will benefit from the research and how:

* Academia, including researchers in secure computation or more broadly the security and cryptography community, and researchers from other communities such as data mining/management, networking and systems. We will open a new research area, and provide results for others to exploit.

*Private sector, such as practitioners in IT security industry, developers of secure application, cloud computing providers, data analytics companies that provide data analysis services to clients. Furthermore, corporates including banks will benefit from better platform security and easier information sharing across organisation borders. We will enable technology that gives private sector companies competitive advantage, by making it possible to integrate secure computation in their products and/or deploy secure computation in their critical applications.

* Government and public sector, many parts of which will deploy data analysis applications and requires effective integration/sharing of data from different departments (e.g., NHS, HMRC, DVLA). There are obvious concerns over information leaks, especially when a significant part of the data is sensitive or private (e.g. medical records). We will enable technology that provides a secure open data exchange platform that encourages information sharing and facilitates information integration, thus will help to improve services and support better decision making.

*Researcher in this project, will be trained with skills, including transferable skills, highly sought by industry and academia. The person will gain experiences, forge collaborations, and prepare for the job market.

Publications

10 25 50
publication icon
Abadi A (2019) Efficient Delegated Private Set Intersection on Outsourced Private Datasets in IEEE Transactions on Dependable and Secure Computing

publication icon
Dong C (2017) Approximating Private Set Union/Intersection Cardinality With Logarithmic Complexity in IEEE Transactions on Information Forensics and Security

publication icon
Gao C (2020) MAS-Encryption and Its Applications in Privacy-Preserving Classifiers in IEEE Transactions on Knowledge and Data Engineering

publication icon
Guo X (2021) VeriFL: Communication-Efficient and Fast Verifiable Aggregation for Federated Learning in IEEE Transactions on Information Forensics and Security

publication icon
Hao F (2018) Analyzing and Patching SPEKE in ISO/IEC in IEEE Transactions on Information Forensics and Security

publication icon
Jiang P (2018) Encryption Switching Service: Securely Switch Your Encrypted Data to Another Format in IEEE Transactions on Services Computing

publication icon
Li J (2021) Searchable Symmetric Encryption with Forward Search Privacy in IEEE Transactions on Dependable and Secure Computing

publication icon
Liu Z (2020) EncodeORE: Reducing Leakage and Preserving Practicality in Order-Revealing Encryption in IEEE Transactions on Dependable and Secure Computing

publication icon
Liu Z (2020) Eurus: Towards an Efficient Searchable Symmetric Encryption with Size Pattern Protection in IEEE Transactions on Dependable and Secure Computing

publication icon
Metere R (2017) Computer Network Security

publication icon
Song X (2020) Forward Private Searchable Symmetric Encryption with Optimized I/O Efficiency in IEEE Transactions on Dependable and Secure Computing

Related Projects

Project Reference Relationship Related To Start End Award Value
EP/M013561/1 01/01/2016 31/03/2016 £377,537
EP/M013561/2 Transfer EP/M013561/1 01/04/2016 30/11/2020 £357,256
 
Description The aim of the project is to investigate the design of data structures and accompanying protocols in the context of secure computation, to enable practical secure computation for large-scale data processing.
1 Significant new knowledge has been generated in this project. Our investigation focused on 2 typical scenarios in which large datasets are processed:
* Outsourced Computation: The data owner has massive datasets and wants to offload computation securely to a Cloud. In this case, both data privacy and integrity are great concerns, yet traditional cryptographic solutions often bring prohibitively high computational (which also translates into financial) overhead. We leveraged data structures to make secure computation in the cloud more efficient and viable. The main results include: verifiable delegated private set intersection on outsourced private datasets (based on hashtables, in TDSC); efficient verifiable cloud computing (based on blockchains, in CCS); efficient searchable encryption (based on linked lists and trees) with forward privacy, forward search privacy and without leaking size patterns (all in TDSC);
* Peer-to-peer computation: Multiple data owners want to jointly analyse their data, to gain useful knowledge without having to share the data with the others. In the past, such computation, although can be executed securely, consumes computational recourses and network bandwidth linearly (or even more) in the size of the data input. For large data, it is not scalable. We leveraged sketches, small data structures that can summarise massive data, and broke the linear bound, and brought down the overhead to logarithmic. From linear to logarithmic means computation that previously needs several hours or days to complete, now only needs seconds or a few minutes. Main results include: protocols for private set union/intersection cardinality (in TIFS), private distributed cardinality estimation (in Usenix security).

2 The project has opened up important new research questions: During the project, we have addressed many challenges relating to efficiency and scalability, entangled with security. The finding opened up new research questions:
* Privacy solutions for machine learning: The massive (mis)use of personal data in machine learning has caused significant concerns. Secure computation is a promising technology in remedying privacy issues. In the project, we have developed new cryptographic algorithms (in TKDE) and protocols (in TIFS), tailored for machine learning tasks. Data structures are widely used in the machine learning community for various purposes, except privacy. Hence it is interesting to see how much benefit we can gain by applying the data structure based secure computation in machine learning.
* Secure computation, differential privacy and sketches: In secure computation, although exchanged data and intermediate results are encrypted, the final results have to be outputted in plaintext. Anyone who obtained the output can infer, with his knowledge, about private input data being used. If we want to prevent this type of inference attack, adding noise and making the output differentially private is perhaps the best choice. In our study (in Usenix security), we found that by using sketches, the output can be made differentially private, without adding extra noise. This is very interesting, and open up a new direction for designing differentially private mechanisms.

3 The project has generated research capability: Two PDRAs was involved in this project. They both received adequate training, on the technical side and non-technical side. A PhD student was trained in the context of this project, on Machine-Checked Formalisation and Automatic Verification of Cryptographic Protocols.
Exploitation Route Academic route: The research output from this project has been disseminated in major conferences and scientific journals. We have also delivered multiple talks. There are early signs of the impact of the work, indicated by the growing citation numbers (300+). Follow up work has been carried out in various research groups around the world. We will also take the result forward by new projects, building on top of the findings in the project.

Non-academic route: We will continue to seek opportunities for exploitation outside academia. Big Internet companies are one possibility. We have engaged with a few industrial research labs. Blockchain companies are another possibility. There are several startup companies trying to address scalability/privacy problem in blockchain systems, using secure computation technology. In the public sector, there are needs for data analysis across administrative boundaries, and secure computation can be a possible way of addressing the potential privacy problem in this setting.
Sectors Digital/Communication/Information Technologies (including Software),Healthcare,Government, Democracy and Justice

 
Description Grigorios 
Organisation King's College London
Department Department of Informatics
Country United Kingdom 
Sector Academic/University 
PI Contribution Had one week visit to the collaborator in August 2016, and worked together at Issac Newton Institute for 2 weeks.
Collaborator Contribution Had one week visit to Newcastle in September 2016, and worked together at Issac Newton Institute for 2 weeks.
Impact A journal paper is published in IEEE Transactions on Information Forensics and Security. It is multi-disciplinary, mine is in cyber security and collaborator is in data mining.
Start Year 2016
 
Description Jie Zhang 
Organisation University of Southampton
Department School of Electronics and Computer Science Southampton
Country United Kingdom 
Sector Academic/University 
PI Contribution We are investigating the application of game theory in security research. Have visited the collaborator a few times.
Collaborator Contribution Meetings and discussions.
Impact not yet.
Start Year 2017
 
Description Jin Li 
Organisation Guangzhou University
Country China 
Sector Academic/University 
PI Contribution Visited the collaborator for a week in May 2016.
Collaborator Contribution Allocated a research student working on the topic we collaborate.
Impact Jin Li, Yanyu Huang, Yu Wei, Siyi Lv, Zheli Liu, Changyu Dong and Wenjing Lou Searchable Symmetric Encryption with Forward Search Privacy IEEE Transactions on Dependable and Secure Computing (2019)
Start Year 2016
 
Description Qiuliang Xu 
Organisation Shandong University
Department School of Computer Science and Technology
Country China 
Sector Academic/University 
PI Contribution Visited the collaborator in June 2016 for a week.
Collaborator Contribution A research student will visit and work at Newcastle in 2017.
Impact Xiangfu Song, Changyu Dong, Dandan Yuan, Qiuliang Xu, Minghao Zhao Forward Private Searchable Symmetric Encryption with Optimized I/O Efficiency IEEE Transactions on Dependable and Secure Computing Preprint (2018)
Start Year 2016
 
Description CCS 2016 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact Met delegates from major companies including Microsoft, IBM, Google, discussed our research and applications.
Year(s) Of Engagement Activity 2016
 
Description Keynote Speech at ML4CS 2020 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact Gave keynote speech on Secure Computation and Machine Learning at the 3rd International Conference on Machine Learning for Cyber Security.
Year(s) Of Engagement Activity 2020
 
Description Keynote speech at CSS 2019 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact Gave keynote speech on Secure Computation and Machine Learning at the 11th International symposium on cyberspace safety and security
Year(s) Of Engagement Activity 2019
 
Description MMM-ACNS 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact Presented our research, discussed our research and potential applications.
Year(s) Of Engagement Activity 2017
 
Description Participating CCS 2017 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact Presented research on cryptocurrency, met delegates from major IT companies including Microsoft, IBM and Huawei, discussed our research and potential applications.
Year(s) Of Engagement Activity 2017
 
Description Participating CCS 2019 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact Met delegates from major IT companies including Microsoft, IBM and Huawei, discussed our research and potential applications.
Year(s) Of Engagement Activity 2019
 
Description asiaccs 2016 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact Met delegates from major IT companies including Microsoft, IBM and Huawei, discussed our research and potential applications. Invited by a delegate to give a talk at Shaanxi Normal University after the conference.
Year(s) Of Engagement Activity 2016