Encryption Techniques for Searchable Data in Crowdsourcing

Searchable Encryption and Privacy-Preserving Task Recommendation in Crowdsourcing Xiaohua Jia City University of Hong Kong Dept. of Computer Science City University of Hong Kong

Search over Encrypted Data Searchable encryption (SE) is a technique that allows clients to securely search over encrypted data stored on untrusted servers Data owner stores data on a server in encrypted form Data user sends a trapdoor of a keyword to the server for search Server returns encrypted data matching the keyword Dept. of Computer Science City University of Hong Kong 1 1

An Example of Searchable Encryption token k1 1 4 2 k1 k2 3 6 4 2 5 1 k3 F1 F2 F3 F4 F5 F6 Leak no more information than below: Search pattern: whether a search query is repeated Access pattern: pointers to (encrypted) files that satisfy a search query Dept. of Computer Science City University of Hong Kong 2

Major Techniques for Searchable Encryption Searchable symmetric encryption (SSE) Data owner generates indexes and encrypts it by a secret key. The encrypted index is then uploaded to server Data user must use the same key to generate trapdoor of keywords for search (Single-owner and Single-user) Public-key encryption with keyword search (PEKS) Multiple data owners generate indexes and encrypt them by the targeted user s public key Data user uses its own private key to generate trapdoor for search (Multi-owner and Single-user) Dept. of Computer Science City University of Hong Kong 3

Research Issues in Searchable Encryption Similerity search (fuzzy search) Secure range queries Secure conjunctive queries Search with dynamic data updates Dept. of Computer Science City University of Hong Kong 4

Privacy-Preserving Task Recommendation in Crowdsourcing Crowdsourcing is a paradigm that enables users (requesters) to outsource tasks to an undefined and large group of people (workers) via an online platform tasks to a large group of undefined people (called workers). Benefited from crowd wisdom and powerful devices (especially mobile devices), tasks that require intensive human involvement or computing power can be completed efficiently with an affordable price. As the ever increasing number of tasks that are call- for-workers, workers can no longer manually select their interested tasks. To facilitate the auto-matching of tasks with their potential workers, crowdsourcing platforms (called brokers) are introduced, as shown in Fig. 1. In such a platform, requesters publish crowdsourcing tasks to the broker, each with a set of requirements (e.g., qualifications, locations, devices, etc.); while each worker submits to the broker a set of interests (e.g., expertise, device model, current locations, etc.). The broker will perform the matching between tasks and workers, and recommend tasks to the most suitable workers. The broker is usually deployed in a public cloud due to the intensive computing and storage resources it needs. 1.Background of Research Crowdsourcing is an emerging paradigm that enables task-requesters (called requesters) to outsource Task recommendation is to recommend suitable tasks to matched workers Privacy requirements in task recommendation Dept. of Computer Science City University of Hong Kong 5 Information security and privacy becomes an important concern in this public crowdsourcing platform [1]. Task requesters do not want to leak out any information about tasks to the broker, and the workers also do not want to reveal any information about their personal interests to the broker. The primary goal of this project is to develop a Privacy-Preserving Task Recommendation (PPTR) scheme that can protect the privacy of both requesters and workers against the broker, while still enables the broker to perform matching between task requirements and worker interests. The PPTR problem is closely related to the searchable encryption [2] problem that aims to enable the comparison between the encrypted indexes and the trapdoors without leaking any information about the search keywords. But, they have fundamental differences. Firstly, in the PPTR problem, there are multiple requesters that encrypt their task requirements individually and the broker needs to provide matching across tasks from different requester with multiple workers; while most of searchable encryption schemes [2]-[17], [21]-[24], [26]-[28] only allow a single user holding the secret key to search. Secondly, in the PPTR problem, the group of workers that may take a task cannot be pre-defined/pre- known; while the existing searchable encryption schemes [5][36][34][37][38] can only support a pre- defined group of users to search. Thirdly, tasks and workers are highly dynamic as new tasks being published and old tasks expired all the time. This requires that the generation of task requirements, generation of worker interests, and the matching between them, be done in an efficient way. This prohibits the interactive searchable encryption [14][40] and the attribute-based searchable encryption [42] to be applicable to the PPTR problem. It is a non-trivial issue to develop the PPTR scheme. The challenges are: 1) support of multiple requesters and multiple workers (M2M) in PPTR for crowdsourcing; 2) support of efficient numeric range matching in PPTR; 3) support of matching of tasks whose requirements are expressed in complex structures of multiple keywords. To address these challenges, this project consists of the following three tasks: 1)Design a PPTR scheme that supports M2M crowdsourcing with keyword equality matching. The crowdsourcing systems should be able to support multiple requesters to publish tasks and multiple workers to subscribe crowdsourced tasks. Starting with the keyword equality matching, this task focuses on developing a new framework that achieves privacy-preserving while enabling M2M task matching. 1

Difficulties in Privacy-preserving Task Recommendation Multi-requester/Multi-worker (M/M) Scalability: large number of task-requesters and workers Dynamics of task-requesters and workers Dynamic task publications and workers revocation No owner-enforced search authorization Expressiveness and conjunctive queries Rich expressions of task requirements or worker interests Conjunctive queries with Boolean operations User collusions Dept. of Computer Science City University of Hong Kong 6

Proxy Re-encryption Scheme for Secure Task Recommendation We propose a proxy re-encryption scheme for secure task matching It is keyword-based matching between task requirements and worker interests KMS generates a pair of keys for each user, one for the user and the other for the broker The broker re-encrypts the ciphertexts encrypted by task-requesters or workers, and performs matching over the re-encrypted ciphertexts Dept. of Computer Science City University of Hong Kong 7

System Model KMS K K K K j b u ib j iu encrypted worker interests encrypted task content &task requirement push encrypted task to suitable workers task requester broker worker secure communication Dept. of Computer Science City University of Hong Kong 8

Steps of Secure Task Recommendation 1) Registration of users (task-requesters and workers) 2) Worker submits interests (encrypted keywords) Broker builds indexes of workers 3) Task requester publishes task with requirement (encrypted keywords) Broker generates trapdoor from task requirement 4) Broker performs task-workers matching and recommends tasks to matched workers 5) Worker decrypts content of matched tasks Dept. of Computer Science City University of Hong Kong 9

System Initialization ???? 1? ??????,??? ?????? = (?,?,?, = ??,?,??) ??? = (?,?) ?: a cyclic group ?: a generator of ? ?: a prime order of ? ?: a collision resistant hash function ??: {0,1} ?? ??? = ??, public key , a pseudorandom function with a seed ? , secret key ? Dept. of Computer Science City University of Hong Kong 10

User Registration (Key Generation) ?????? ???,? ???,??? KMS chooses ??,1 User side key: ???= (??,1,?) Broker side key: ???= ??,2 The broker builds a table for user-key mapping (?,???) ??? and computes ??,2= ? ??,1: user-key userID Broker side key User ? KMS Broker ??? ??? ? (?,???) ??? ? .. Dept. of Computer Science City University of Hong Kong 11

Workers Submit Interests (Keywords) Worker Enc ???,?? ? (??) ??= ??,1, ,??,??: interest of worker ? Worker ? encrypts each ??,?as ? ??,? = ?1=? ?1?? ?2= ?? ?????????= ?????1????? ??? I (key , value) ?1, ?2: keyword workerIDs ??? ??, ??, (random number) ? = ??(??,?) ?1 Broker Enc ???,? (??) ?(??) For each ? ??,?, the broker computes ??? ?2= (? ?1??)??? ?????1?????= ??? ? ??,?= ?1 Dept. of Computer Science City University of Hong Kong 12

Task Encryption and Trapdoor Generation Task Enc ???,? ? Given task requirement ?, requester ? encrypts ? = ?1=??+? ??? ?1, ?2, ?3: ?2= ?1 ?3= ?(???) ??? ? = ??(?), ? (random number) Broker ???????? ???,? ? Broker computes trapdoor ? = ?1,?2: ?1= ( ?1)??? ?2= ?1 ?2= ?3=?(???) ???+???= (??+? )?= ???+?? Dept. of Computer Science City University of Hong Kong 13

Secure Matching between Task and Workers Match Match ?,? Given ? = ?1,?2, broker searches keyword in index table ? by testing: I (key , value) ?2= ?(?1 ??????? 1) keyword workerIDs ??? ??, ??, The equation holds iff ? = ? Notice: trapdoor ? = ?1,?2: ?1= ???+?? ?2= ?(???) Dept. of Computer Science City University of Hong Kong 14

Task Content Encryption and Decryption K K K K u ib iu j b j M ED-U-Enc ED-B-Enc rK = = * j r rx r ( ) ( , ) ( ) ( , ) c M g g M c M g g M j u M ED-B-Dec ED-U-Dec rK = ' r ( ) ( , ) c M g g M i u i Requester j Broker Worker i Dept. of Computer Science City University of Hong Kong 15

Task Recommendation without Proxy Re-encryption Disadvantages of proxy re-encryption method Vulnerable to collusion attacks Extra computation and storagecost at the broker Task-worker matching without proxy re-encryption: Given ciphertext of a keyword and a trapdoor, the broker can perform the matching directly without re-encryption To apply SSE or PEKS to M/M crowdsourcing, the critical issue is how to share the secret key among multiple users We design a scheme to derive multiple secret keys {???} from a single secret key ?? Dept. of Computer Science City University of Hong Kong 16

System Model and Fundamentals The broker performs direct matching between The ciphertext (of a keyword) encrypted by public params, and The trapdoor generated by a user s secret key (Ski) KMS Shamir secret sharing: Use a polynomial function of degree ? 1 (? > 1) with the secret key as constant Embed ? (? < ?) secret shares into the public parameters Embed ? ? secret shares into a user secret key Params SKi, SKj, SKk, ... SKk Tk Tj SKj Test Ti SKi Broker Task Requesters Workers Dept. of Computer Science City University of Hong Kong 17

Construction Algorithms ????(1?) ??????,??? Generate two multiplicative cyclic groups ?1, ?2of the same prime order ?, a bilinear map ?:?1 ?1 ?2, and a resistant hash function ?:{0,1} ?1. Let ? be a generator of ?1. ??? Select random numbers ?1, ?2, ?1, ? polynomial function ? ? = ?1+ ?1?. The public parameters are as: ?????s = (?1,?2,?,?,?,?1,?2,?,??), and generate a secret ?(?) ?1 where ?1= ??1, ?2= ??2and ?? = ? The system master secret key is as: ??? = (?1, ?2, ?1, ?) Dept. of Computer Science City University of Hong Kong 18

Generation of Secret Keys for Workers ?????? ??????,MSK ??? ??? and set = ? ??; Randomly choose ?? Compute ???= ??,?? for each worker: ?1 ?, (0) ??= ?2 ?(??) ??, (0) ??= ?2 Note: ?, ? is Lagrange interpolation polynomial ? ? ? ? ?, ? = ? ,? ? Dept. of Computer Science City University of Hong Kong 19

Task Encryption and Trapdoor Generation Task Enc ??????,? ? ??? For task-keyword ?, randomly choose ?1, ?2 ciphertext ? = {?1,?2,?3,?4}, where ?1~ ?4are as follows: and encrypt ? into ?2?(?)?1, ?2= ?1 ?1, ?3= ???2, ?4= ??2 ?1= ?2 Worker ???????? ??????,???,? ? ??? For worker-interest w , randomly choose ? trapdoor ? = {?1,?2,?3,?4} for w , where ?1~ ?4are as follows: ?1= ?1 ?2= ?(? )?, and generate ?, ? ?, ?3= ?? ?4= ?? Dept. of Computer Science City University of Hong Kong 20

Matching between Keyword-ciphertext and Trapdoor ????(?,?) 1/0 The following equation holds only if ? = ? : ? ?1,?1 = ?(?2,?2) ?(?3,?3) ?(?4,?4) Dept. of Computer Science City University of Hong Kong 21

Correctness Proof ?2,?1 ?1,?(? )?) ?) e(?(?)?1,?1 ?) ? ?1,?1 = e(?2 ? ?2,?2 = e(?1 ? ?3,?3 = e(?,?2)?2??(?) ?, (0) ? ?4,?4 = e(?,?2)?2??(??) ??, (0) ? ?3,?3 ? ?4,?4 ?2? ? ? ?, 0 +? ?? ??, 0 = e ?,?2 = e ?,?2 = e ?,?2 = e(?1,?2)?2? ?2??(0) ?2??1 ? = ? iff ? ?1,?1 = ?(?2,?2) ?(?3,?3) ?(?4,?4) Dept. of Computer Science City University of Hong Kong 22

Worker Revocation Problem Revocation incurs very high cost! When a worker leaves the system, secret keys of other users and the task index table (ciphertexts) all need to be regenerated (recomputed) Dept. of Computer Science City University of Hong Kong 23

Research Issues in Secure Task Recommendation Multi-keywords of task requirements Range requirement of tasks Conjunctive functions of task requirements and worker interests Dept. of Computer Science City University of Hong Kong 24

Summary SSE and PEKS are the major techniques for searchable encryption They are not suitable for secure matching between multi-requesters and multi-workers in crowdsourcing Two privacy-preserving task recommendation schemes for crowdsourcing Proxy re-encryption method Server direct matching without re-encryption Dept. of Computer Science City University of Hong Kong 25

Thank You! Q&A Dept. of Computer Science City University of Hong Kong 26