New Security Definitions, Constructions and Applications of Proxy Re-Encryption

Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions New Security Definitions, Constructions and Applications of Proxy Re-Encryption David Nu˜nez Advisors: Isaac Agudo and Javier Lopez Department of Computer Science Universidad de M´alaga, Spain Email: [email protected] STM 2017 – Oslo, Norway 1 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Outline 1. Introduction 2. Security Definitions for Proxy Re-Encryption 3. New Proxy Re-Encryption Constructions 4. Some Applications of Proxy Re-Encryption 5. Conclusions and Future Work 2 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Motivation: Cloud computing Great expectations: better performance, cost reduction, etc. Great concerns: security and privacy risks Conventional security premise: ⇒attackers should not get inside the security domain •Goal: Keep the attacker away from the protected assets •Measures: access control systems, firewalls, etc. •Cloud provider must be fully trusted to not bypass these measures A more realistic premise: ⇒attackers have potential access to users’ data •Implication: Data must be stored in encrypted form •Trust in the cloud provider can be reduced 3 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Secure Data Sharing Scenario Consumer DomainOwner Domain Storage Domain Cloud Service Provider Data Owner Other CSPs Data Consumers Data owner's devices Encrypted data outsources data storage retrieves data grants access to data Producer Domain produces data Data Producers Data owner's devices 4 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Secure Data Sharing Scenario Producer Domain Heart rate monitor Consumer DomainOwner Domain Storage Domain Cloud Service Provider Doctor Encrypted data outsource data storage retrieves data shares data produces data 5 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Encrypted data in the cloud Critical requirement: the provider should not have access to the decryption keys Not an easy task: •Symmetric encryption cannot be used alone, since it implies that the same key is shared or agreed •Public-key encryption implies fixing a recipient in advance •Increasingly complex problem: multiple pieces of data, diverse producers and consumers Need for non-traditional cryptosystems that provide advanced functionalities 6 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Proxy Re-Encryption Alice (Delegator) Bob (Delegatee) Proxy delegation of decryption rights cB=ReEnc(rkA→B,c A) cA=Enc(pkA,m) rkA→B (pkA,sk A) (pkB,sk B) 7 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Secure Data Sharing Scenario and PRE Owner Domain Data Owner (pkA,sk A) Re-Encryption Keys Generation Data owner's public and private keys 8 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Secure Data Sharing Scenario and PRE Owner Domain Data Owner Producer Domain Data Producers (pkA,sk A) pkA Re-Encryption Keys Generation Data owner's public key Data owner's public and private keys 8 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions 1. Introduction 2. Security Definitions for Proxy Re-Encryption Definitions of Security Relations among security notions Attack to PRE scheme from PKC’2014 Summary 3. New Proxy Re-Encryption Constructions 4. Some Applications of Proxy Re-Encryption 5. Conclusions and Future Work 13 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Syntax of a Proxy Re-Encryption Scheme A PRE scheme is composed of functions KeyGen, Enc, Dec, ReKeyGen, and ReEnc: KeyGen(n)→(pki, ski). On input security parameter n, the key generation algorithm KeyGen outputs a pair of public and secret keys (pki, ski)for user i. Enc(pki, m)→ci. On input the public key pkiand a message m∈ M, the encryption algorithm Enc outputs a ciphertext ci∈ C. Dec(ski, ci)→m. On input the secret key skiand a ciphertext ci∈ C, the decryption algorithm Dec outputs a message m∈ M or the symbol ⊥indicating ciis invalid. 14 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Syntax of a Proxy Re-Encryption Scheme ReKeyGen(pki, ski, pkj, skj)→rki→j. On input the pair of public and secret keys (pki, ski)for user iand the pair of public and secret keys (pkj, skj)for user j, the re-encryption key generation algorithm ReKeyGen outputs a re-encryption key rki→j. ReEnc(rki→j, ci)→cj. On input a re-encryption key rki→jand a ciphertext ci∈ C, the re-encryption algorithm ReEnc outputs a second ciphertext cj∈ C or the symbol ⊥indicating ciis invalid. 15 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions The Indistinguishability game (IND) It formalizes the inability of an adversary to distinguish which message, from two possible options m0and m1, is encrypted under ciphertext c∗. Challenger Adversary m0, m1 ←−−−−−−−−−−−−−−−−−− c∗ −−−−−−−−−−−−−−−−−−→ m? ←−−−−−−−−−−−−−−−−−− The adversary has some capabilities in the form of oracles 16 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions The Indistinguishability game (IND): Phase 1 Challenger Adversary (A1) (pk∗, sk∗)←KeyGen(n) pk∗ −−−−−−−−−−−−−−−−−−→ . . . Queries to oracles Ω1 ←−−−−−−−−−−−−−−−−−− −−−−−−−−−−−−−−−−−−→ . . . m0, m1 ←−−−−−−−−−−−−−−−−−− 17 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions The Indistinguishability game (IND): Phase 2 Challenger Adversary (A2) δR ←− {0,1} c∗←Enc(pk∗, mδ) c∗ −−−−−−−−−−−−−−−−−−→ . . . Queries to oracles Ω2 ←−−−−−−−−−−−−−−−−−− −−−−−−−−−−−−−−−−−−→ . . . δ? =δ0δ0 ←−−−−−−−−−−−−−−−−−− 18 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Definitions of Security for Public-Key Encryption Decryption oracle:Odec(c)→m The IND game admits different attack models: •CPA ⇒Ω1=∅Ω2=∅ •CCA1 ⇒Ω1={Odec}Ω2=∅ •CCA2 ⇒Ω1={Odec}Ω2={Odec} Attack models for PKE: {CCAi|0≤i≤2} ⇒The index iindicates the last phase of the game where Odec is available: CCA0 (= CPA), CCA1, CCA2 [Bellare et al., CRYPTO 1998] 19 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Definitions of Security for Proxy Re-Encryption Reuse of PKE definitions of security: •The Indistinguishability (IND) game •Decryption oracle: Odec(pk, c)→m In PRE, we also need to add a re-encryption oracle: Oreenc(pk, pk0, c)→c0 This addition makes the definitions of security more complex. 20 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Parametrizing attack models Attack models for PKE: {CCAi|0≤i≤2} The index iindicates the last phase of the security game where Odec is available Contribution: Parametric family of attack models Attack models for PRE: {CCAi,j |0≤i, j ≤2} The index iindicates the last phase of the security game where Odec is available The index jindicates the last phase of the security game where Oreenc is available 21 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Parametric Family of Attack Models for PRE Ω1Ω2Attack model ∅ ∅ CCA0,0= CPA {Oreenc}∅CCA0,1 {Oreenc} {Oreenc}CCA0,2 {Odec}∅CCA1,0 {Odec,Oreenc}∅CCA1,1 {Odec,Oreenc} {Oreenc}CCA1,2 {Odec} {Odec}CCA2,0 {Odec,Oreenc} {Odec}CCA2,1 {Odec,Oreenc} {Odec,Oreenc}CCA2,2 22 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions The heart of the attack Challenger Adversary Oreenc b b0=b·rk 29 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions The heart of the attack Challenger Adversary Oreenc b= 1 b0=rk 30 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions The heart of the attack Challenger Adversary Oreenc bt(row vector) b0t=bt·rk (rk is a matrix) 31 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions The heart of the attack Challenger Adversary Oreenc (1,0, ..., 0)t b0t= (1,0, ..., 0)t·rk =row1(rk) 32 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions The heart of the attack Challenger Adversary Oreenc (0,1, ..., 0)t b0t= (0,1, ..., 0)t·rk =row2(rk) 33 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Finalizing the attack The adversary can extract arbitrary rows of rk The scheme violates the privacy of re-encryption keys ⇒The scheme cannot be IND-CCA1,1 IND-CCA2,2 IND-CCA2,1 IND-CCA2,0 IND-CCA1,2 IND-CCA1,1 IND-CCA1,0 IND-CCA0,2 IND-CCA0,1 IND-CCA0,0 34 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Summary We propose a parametric family of attack models for PRE We formalize the private re-encryption keys property and show what happens when it is violated ⇒Attacks can be based exclusively on Oreenc We exemplify this by showing an attack to a PRE scheme 35 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions 1. Introduction 2. Security Definitions for Proxy Re-Encryption 3. New Proxy Re-Encryption Constructions NTRUReEncrypt Generic CCA-Secure Transformations Summary 4. Some Applications of Proxy Re-Encryption 5. Conclusions and Future Work 36 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions New Proxy Re-Encryption Constructions Part of the motivation of this thesis is to investigate more concrete aspects of PRE schemes, such as those related to performance and security constructions. •Design faster PRE schemes •Increase security of PRE schemes Two separate contributions: •We explore the use of lattice-based crypto to construct more efficient PRE schemes •We study the application of generic transformations to increase the security of PRE schemes 37 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions NTRUReEncrypt: Efficient PRE scheme based on NTRU We propose new PRE schemes based on NTRU, a widely known lattice-based cryptosystem. Lattice-based cryptography is a promising field: •Post-quantum security •Efficiency through parallelization We provide two different schemes: •The first is based on the conventional NTRU cryptosystem •The second is based on an NTRU variant that is CPA-secure under the Ring-LWE assumption. Our experimental results show that the first scheme outperforms previous proposals by an order of magnitude. 38 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions NTRUReEncrypt: Analysis Space costs: Keys and ciphertexts are polynomials of size O(n·log2q)bits Other lattice-based schemes have ciphertexts of size O(n2) Table: Comparison of space costs (in KB) Size Aono et al. NTRUReEncrypt Public keys 60.00 1.57 Secret key 60.00 1.57 Re-Encryption key 2520.00 1.57 Ciphertext 0.66 1.57 45 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions PS-NTRUReEncrypt NTRUReEncrypt does not have a proof of security Contribution: PS-NTRUReEncrypt Provable secure version of NTRUReEncrypt IND-CPA secure under the Ring-LWE assumption Extension of the NTRU variant proposed by Stehl´e and Steinfeld [Eurocrypt’11] More of theoretical interest ⇒Not very efficient with current parameters 46 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions 1. Introduction 2. Security Definitions for Proxy Re-Encryption 3. New Proxy Re-Encryption Constructions NTRUReEncrypt Generic CCA-Secure Transformations Summary 4. Some Applications of Proxy Re-Encryption 5. Conclusions and Future Work 47 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Motivation We just described a PRE scheme that is proven CPA-secure. An immediate objective would be to improve its security notion, hopefully achieving full CCA-security Two possible strategies can be applied: •Redesign, from scratch, a new scheme based on the original •Bootstrap the achieved security notion into a stronger one by means of a generic method. We focus on the second strategy 48 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Motivation Several generic methods exist for achieving CCA-security PKE schemes from weakly secure cryptosystems ⇒E.g., Fujisaki-Okamoto, REACT, GEM This is not the case of proxy re-encryption Several flawed attempts to reuse these transformations Goal ⇒To explore the adaptation of these methods to PRE 49 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Fujisaki-Okamoto Transformation (FOT) [J. Crypto, 2013] Let PKE be a public-key encryption scheme, Sym a symmetric encryption scheme, and Hand Ghash functions Encryption: 1. Samples a random σ 2. c←Sym.Enc(G(σ), m) 3. e←PKE.Enc(pk, σ;H(σ, c)) 4. Output (e, c) Decryption: 1. σ←PKE.Dec(sk, e) 2. m←Sym.Dec(G(σ), c) 3. Check: e? =PKE.Enc(pk, σ;H(σ, c)) 4. Output mif check holds; otherwise output ⊥ 50 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Fujisaki-Okamoto Transformation (FOT) [J. Crypto, 2013] Let PKE be a public-key encryption scheme, Sym a symmetric encryption scheme, and Hand Ghash functions Encryption: 1. Samples a random σ 2. c←Sym.Enc(G(σ), m) 3. e←PKE.Enc(pk, σ;H(σ, c)) 4. Output (e, c) Decryption: 1. σ←PKE.Dec(sk, e) 2. m←Sym.Dec(G(σ), c) 3. Check: e? =PKE.Enc(pk, σ;H(σ, c)) 4. Output mif check holds; otherwise output ⊥ 50 / 93 FOT produces a CCA-secure scheme in the Random Oracle Model if PKE is OW-CPA secure Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Applying FOT to Proxy Re-Encryption It is tempting to directly use FOT in PRE Re-Encryption: input (e, c) 1. e0←PRE.ReEnc(rk, e) 2. Output (e, c) Recall that the check during decryption involves reconstructing the ciphertext If the re-encryption alters the randomness of the ciphertext, the check will fail The “CCA-secure” PRE scheme by Aono et al. [IndoCrypt 2013] suffers from this flaw 51 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Perfect Key-Switching A solution could be to require that the PRE scheme does not alter the randomness during re-encryption Contribution: Perfect Key-Switching property Re-encryption simply “switches” one public key for another, without altering the original randomness ReEnc(rki→j,Enc(pki, m;r)) = Enc(pkj, m;r) E.g.: PRE scheme from Blaze, Bleumer, and Strauss ( (ga) |{z} pkA r, gr·m)Re-encryption −−−−−−−−→ ( (gb) |{z} pkB r, gr·m) 52 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Perfect Key-Switching A solution could be to require that the PRE scheme does not alter the randomness during re-encryption Contribution: Perfect Key-Switching property Re-encryption simply “switches” one public key for another, without altering the original randomness ReEnc(rki→j, Enc(pki, m;r) ) = Enc(pkj, m;r) E.g.: PRE scheme from Blaze, Bleumer, and Strauss ( (ga) |{z} pkA r, gr·m)Re-encryption −−−−−−−−→ ( (gb) |{z} pkB r, gr·m) 52 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Applying FOT to Proxy Re-Encryption: Security However, there is a flaw... •Suppose the adversary creates an ill-formed ciphertext (e, c)where the randomness in edoes not come from H: e=PRE.Enc(pk, σ;r), for random r •If (e, c)is inputed to the re-encryption oracle, it will get rejected •This behavior does not match the real execution This strategy results in invalid proofs...although it is used by >10 PRE schemes Conclusion ⇒The security proof cannot rely on the random oracle tables for constructing the re-encryption oracle 55 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Applying FOT to Proxy Re-Encryption: Security Alternative: strengthen the requirements on the underlying PRE scheme ⇒We require IND-CCA0,1security Security proof: ⇒Reduction to the IND-CCA0,1 security of the PRE scheme ⇒Without using the random oracle tables for Oreenc IND-CCA2,1security in the ROM Contribution: Extending FOT to PRE We provide a security proof for FOT in PRE 56 / 93 IND-CCA2,2 IND-CCA2,1 IND-CCA2,0 IND-CCA1,2 IND-CCA1,1 IND-CCA1,0 IND-CCA0,2 IND-CCA0,1 IND-CCA0,0 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Summary NTRUReEncrypt is a highly-efficient proxy re-encryption scheme based on the NTRU cryptosystem The main strength of this scheme is its performance ⇒Outperforms other schemes by an order of magnitude We also propose PS-NTRUReEncrypt, a provably-secure variant that is CPA-secure under the Ring-LWE assumption 57 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Summary We analyze the integration of generic transformations to PRE Negative results: •It is not possible to apply known transformations directly •>10 PRE schemes are flawed Positive results: •FOT can be applied if the PRE scheme satisfies Perfect Key-Switching and is IND-CCA0,1secure •It achieves IND-CCA2,1security in the random oracle model These results can be extended to other generic transformations (e.g., REACT, GEM) 58 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions 1. Introduction 2. Security Definitions for Proxy Re-Encryption 3. New Proxy Re-Encryption Constructions 4. Some Applications of Proxy Re-Encryption BlindIdM: Privacy-Preserving IdM as a Service Delegated Access to Hadoop clusters Escrowed Decryption System Summary 5. Conclusions and Future Work 59 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions BlindIdM: Motivation Identity Management is a ubiquitous service Costly ⇒specific applications and personnel Identity Management as a Service (IDaaS) 60 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions BlindIdM: Identity Management as a Service Cloud Identity Provider Service Provider Host Organization Employee belongs to requests service outsources identity management direct trust direct trust indirect trust retrieves identity provides identity information 61 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions BlindIdM: Motivation Classic problem of cloud computing ⇒Organizations lose control of their data Now we are talking about identity data... ⇒Data protection laws and regulations Trust problem ⇒Organizations have to trust the provider Goal: Cryptographic safeguards that support IdM service without compromising users’ data 62 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions BlindIdM: Proposal Contribution: BlindIdM Privacy-preserving IDaaS system based on PRE Identity attributes are encrypted by the user and decrypted by the requester The Identity Provider (IdP) stores encrypted attributes ⇒Still capable of offering an identity service Integrated with SAML 2.0 ⇒IdM standard for the description and exchange of identity information (e.g., attributes) First proposal that tackles this problem 63 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions BlindIdM: Our idea Cloud Identity Provider Service Provider Host Organization rkH→SP (pkH,sk H) (pkSP ,sk SP ) ca c� a Honest-but-curious provider: The cloud provider will respect protocol fulfillment, but will try to read users’ data 64 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Big Data: Apache Hadoop The most prominent framework for processing big datasets. Storing and processing of datasets by clusters of machines. The workload is divided into parts and distributed throughout the cluster. Hadoop was not designed with security in mind However, it is widely used by organizations that have strong security requirements regarding data protection. 71 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Big Data: Hadoop operation TaskTracker TaskTracker Data store (e.g. HDFS) JobTracker Map Map · · · Input Splits TaskTracker Red · · · · · · Map phase Reduce phase Distribution of workload and coordination 72 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Big Data: Our proposal TaskTracker TaskTracker Encrypted Lockbox Encrypted data Plaintext data Encrypted data JobTracker MapDec Enc MapDec Enc · · · Encrypted Splits (Blocks) TaskTracker RedDec Enc · · · · · · Re-Encrypted Lockbox Map phase Reduce phase 73 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Big Data: Experiment Execution of the WordCount benchmark, a simple application that counts the occurrence of words over a set of files. The job input was a set of 1800 encrypted files of 64 MB each Almost 30 billions of words, approximately 112.5 GB. Execution time: •Clean version: 1932.09 seconds •Prototype: 1960.74 seconds •Difference: 28.74 seconds :Overhead: 1.49% 74 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions 1. Introduction 2. Security Definitions for Proxy Re-Encryption 3. New Proxy Re-Encryption Constructions 4. Some Applications of Proxy Re-Encryption BlindIdM: Privacy-Preserving IdM as a Service Delegated Access to Hadoop clusters Escrowed Decryption System Summary 5. Conclusions and Future Work 75 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Escrowed Decryption: Motivation Dilemma between data confidentiality and law enforcement investigations Perception of “impunity” derived from the use of confidential communications. Growing concern coming from governments and law enforcement agencies (LEAs) Demand for mechanisms that break confidentiality of communications Lack of accountability from the government and LEAs 76 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Escrowed Decryption: Original idea Accountable Escrowed Encryption: Proposed by Liu, Ryan and Chen in CSF 2013 PKE scheme with Escrowed Decryption This solution does not involve key escrow Authorities can request decryption of ciphertexts to a coalition of third-party entities called custodians Custodians log all requests in a public log :Accountability Drawbacks: •The custodians can decrypt any message if they collude •The protocol for escrow decryption is composed of 2 synchronous rounds involving all custodians 77 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Escrowed Decryption: Our idea Contribution Escrow decryption system based on PRE Authorities can request the re-encryption of a ciphertext to custodians and decrypt the result Re-encryption should be “shared” by the custodians ⇒Re-encryption key is split in escrow shares Our proposal uses a multiplicative homomorphism: rk = n Y i=1 rki ReEnc(rk, CT) = n Y i=1 ReEnc(rki, CT) 78 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Escrowed Decryption: Our idea Escrow shares Key generation request Certified public key Alice Certification Authority Custodians 79 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Escrowed Decryption: Our idea Custodians Encrypted message Alice Bob Message intercepted Escrow decryption Law Enforcement Agency 80 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Contributions We examined the notions of security for PRE: •We propose a parametric family of attack models •Fine-grained security notions, whose relations we also analyze. •We define the Private Re-Encryption Keys property and show why it is relevant We present new proxy re-encryption schemes: •NTRUReEncrypt, based on the NTRU cryptosystem and extremely efficient •PS-NTRUReEncrypt, a provably-secure version that is CPA-secure under lattice-based assumptions. 87 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Contributions We study the application of generic CCA-secure transformations to PRE: •We focus on the Fujisaki-Okamoto transformation and formulate sufficient conditions that allow to use it directly in PRE. •These conditions include a new property called perfect key-switching •We detect flaws in 12 PRE schemes that are allegedly “CCA-secure”. We propose several applications of PRE: •A model for privacy-preserving Identity Management as a Service •A system for delegating access to encrypted information in Big Data •An escrowed decryption system 88 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Contributions - Parametric Family of Attack Models for Proxy Re-Encryption - Application of Generic CCA-Secure Transformations - NTRUReEncrypt - Escrowed Decryption System - Data Confidentiality in Big Data - Blind Identity Management as a Service - Survey of Proxy Re-Encryption Constructions and Applications Security Definitions Constructions Applications ↳IEEE CSF 2015 ↳Security and Communication Networks ↳ACM AsiaCCS 2015 ↳Journal of Network and Computer Applications ↳Manuscript ↳IEEE CloudCom 2014 ↳International Journal of Information Security ↳IEEE CloudCom 2012 ↳Commercial applications and patents 89 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Publications Articles in ISI-JCR Journals D. Nu˜nez, I. Agudo, and J. Lopez. Proxy Re-Encryption: Analysis of Constructions and its Application to Secure Access Delegation Journal of Network and Computer Applications, 87:193-209, 2017. D. Nu˜nez, I. Agudo, and J. Lopez. On the Application of Generic CCA-Secure Transformations to Proxy Re-Encryption. Security and Communication Networks, 9(12):1769-1785, 2016. D. Nu˜nez, and I. Agudo. BlindIdM: A Privacy-Preserving Approach for Identity Management as a Service. International Journal of Information Security, 13(2):199-215, 2014. International conference papers D. Nu˜nez, I. Agudo, and J. Lopez. A Parametric Family of Attack Models for Proxy Re-Encryption. IEEE CSF 2015, pp. 290-301. D. Nu˜nez, I. Agudo, and J. Lopez. NTRUReEncrypt: An Efficient Proxy Re-Encryption Scheme Based on NTRU. ACM AsiaCCS 2015, pp. 179-189. D. Nu˜nez, I. Agudo, and J. Lopez. Delegated Access for Hadoop Clusters in the Cloud. IEEE CloudCom 2014, pp. 374-379. D. Nu˜nez, I. Agudo, and J. Lopez. Integrating OpenID with Proxy Re-Encryption to enhance privacy in cloud-based identity services. IEEE CloudCom 2012, pp. 241-248. 90 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Open Issues and Future Work Family of attack models and security notions for PRE •We studied some of the relations between these notions •We do not rule out the possibility of additional separations and implications NTRUReEncrypt: •Achieving CCA-security 91 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions Open Issues and Future Work Generic transformations: •Concrete estimations of the obtained security level ⇒Permit to define sets of parameters and to perform meaningful comparison •Transformations that are not defined in the random oracle model Applications •BlindIdM ⇒Integration with other IdM standards •Big Data ⇒Improve the integration with the Hadoop •Escrow ⇒Reduce trust in the Certification Authority 92 / 93 Introduction Security Definitions for PRE New PRE Constructions Applications Conclusions New Security Definitions, Constructions and Applications of Proxy Re-Encryption David Nu˜nez Advisors: Isaac Agudo and Javier Lopez Department of Computer Science Universidad de M´alaga, Spain Email: [email protected] STM 2017 – Oslo, Norway 93 / 93 94 / 93 Creating an Encrypted Lockbox Data Symmetric encryption PRE encryption Data key Data owner's public key Encrypted lockbox 95 / 93 Delegating an Encrypted Lockbox Re-Encryption Re-Encryption key Encrypted lockbox Encrypted lockbox 96 / 93 Separation strategies We show two separation strategies: 1. Leaking re-encryption keys from the target user to a honest user •The adversary does not know the secret key of honest users 2. Leaking re-encryption keys from the target user to a corrupt user •The adversary knows the secret key of corrupt users 103 / 93 Exploiting the target-to-honest re-encryption key leakage Suppose that a PRE scheme leaks rkpk∗→pkhthrough Oreenc The attack strategy works as follows: 1. Extract rkpk∗→pkhfrom Oreenc queries 2. Obtain the challenge ciphertext c∗ 3. Re-encrypt the challenge ciphertext locally: c0=ReEnc(rkpk∗→pkh, c∗) 4. Call the decryption oracle Odec with (pkh, c0)to obtain mδ We need Oreenc at some phase and Odec in phase 2 Separation IND-CCA2,06⇒ IND-CCA2,1(Theorem 4.7) 104 / 93 Exploiting the target-to-corrupt re-encryption key leakage Suppose that a PRE scheme leaks rkpk∗→pkxthrough Oreenc The attack strategy works as follows: 1. Extract rkpk∗→pkxfrom Oreenc queries 2. Obtain the challenge ciphertext c∗ 3. Re-encrypt the challenge ciphertext locally: c0=ReEnc(rkpk∗→pkx, c∗) 4. Decrypt c0locally: mδ=Dec(skx, c0) We only need Oreenc at some phase Separation IND-CCA2,06⇒ IND-CCA0,1(Theorem 4.8) Impossibility result A PRE scheme that violates the private re-encryption keys property can only be IND-CCAi,0, for i∈ {0,1,2}(i.e., a security notion without Oreenc) 105 / 93 The PRE scheme from Kirshanova (PKC’14) KeyGen(n): 1. Choose A0←Znׯm q,R1, R2←DRand an invertible matrix H←Znk×nk q 2. Define A1=−A0R1∈Zn×nk qand A2=−A0R2∈Zn×nk q 3. Compose the matrix A= [A0|A1|A2]∈Zn×m q 4. The public key is the pair pk = (A, H). The secret key is matrix sk = [R1|R2]∈Z¯m×2nk 106 / 93 The PRE scheme from Kirshanova (PKC’14) Enc(pk = ([A0|A1|A2], H), m ∈ {0,1}nk): 1. Choose a non-zero invertible matrix Hu, and a vector s←Zn q 2. Set Au= [A0|A1+HG|A2+HuG] 3. Sample error vector e←De 4. Compute bt= 2(stAumod q) + et+ (0,0, enc(m))tmod 2q where the first zero vector has dimension ¯m, the second has dimension nk and enc is an encoding function 5. Output the ciphertext c= (Hu, b)∈Zn×n q×Zm 2q :The main part of the ciphertext is vector b 107 / 93 The PRE scheme from Kirshanova (PKC’14) Dec(pk = ([A0|A1|A2], H), sk = [R1|R2], c = (Hu, b)): 1. Using matrix Hu, compute Au= [A0|A1+HG|A2+HuG] 2. With the secret key call algorithm InvertO([R1|R2], Au, b mod q, Hu). As output we receive two vectors z∈Zn qand e∈Zm qthat satisfy bt=ztA+etmod q 3. Let v=b−emod 2q 4. Compute vt  R1R2 I0 0I mod 2q and apply enc−1to the last nk coordinates 108 / 93 The PRE scheme from Kirshanova (PKC’14) ReKeyGen(pk = ([A0|A1|A2], H), sk = [R1|R2], pk0= ([A0 0|A0 1|A0 2], H0)): 1. Let Y= [A0 0|A0 1+H0G|A0 2−A2]and yibe the i-th column of Y 2. Execute SampleO(yi,[A0|A1], R1, H)for each column vector yiand concatenate the column vector outputs to form matrix X. This matrix satisfies that [A0|A1]X=Y 3. Parse matrix Xas [X0|X1|X2], where the block X0∈Z( ¯m+nk)ׯmis the output corresponding to the first part of Y,X1∈Z( ¯m+nk)×nk to the second one, and X2∈Z( ¯m+nk)×nk to the last part 4. Finally, output the re-encryption key rkpk→pk0: rkpk→pk0="X0X1X2 0 0 I# :The re-encryption key is a matrix 109 / 93 The PRE scheme from Kirshanova (PKC’14) ReEnc(rkpk→pk0, c = (Hu, b)): to change the underlying public key in the ciphertext component b, compute b0t=bt·rkpk→pk0 Finally, output c0= (Hu, b0). :The only operation during re-encryption is the multiplication of a vector b(the ciphertext) by a matrix (the re-encryption key), obtaining another vector b0(the re-encrypted ciphertext) 110 / 93 Finalizing the attack Using the unit vectors as input ciphertexts to the re-encryption oracle, one can extract arbitrary rows of the re-encryption key matrix. The adversary queries the re-encryption oracle from the target user to a corrupt one. After ¯m+nk queries the adversary can reconstruct the re-encryption key rkpk∗→pkx The adversary continues the generic attack strategy when target-to-corrupt re-encryption keys are leaked: 1. Extract rkpk∗→pkxfrom Oreenc queries 2. Obtain the challenge ciphertext c∗ 3. Re-encrypt the challenge ciphertext locally: c0=ReEnc(rkpk∗→pkx, c∗) 4. Decrypt c0locally: mδ=Dec(skx, c0) 111 / 93 Refining the attack One could argue that unit vectors don’t look as ciphertexts... In fact, the probability that a unit vector is output from the encryption function is negligible. The oracle could take the risk and reject them or return garbage. The adversary doesn’t know whether these ciphertexts were valid encryptions under pk∗ 112 / 93 NTRUReEncrypt: Re-Encryption Re-Encryption Input: a re-encryption key rkA→Band a ciphertext CA Samples a random polynomial e∈ RNT RU Output re-encrypted ciphertext CB=CA·rkA→B+p·e The noise eprevents Bfrom extracting A’s private key 119 / 93 NTRUReEncrypt: Re-Encryption Why does it work? Re-encrypted ciphertext: CB=CA·rkA→B+p·emod q = (p·g·f−1 A·s+M)·fA·f−1 B+p·emod q =p·g·f−1 B·s+fA·f−1 B·M+p·emod q Decrypting a re-encrypted ciphertext: fB·CBmod p=((((((( ( (p·g·s+p·e) + fA·Mmod p =fA·Mmod p =M 120 / 93 NTRUReEncrypt: Analysis Bidirectional: Given rkA→B=fAf−1 B, one can easily compute rkB→A= (rkA→B)−1=fBf−1 A Limited multihop Not collusion-safe: Secret keys can be extracted from the re-encryption key if the proxy colludes with a user involved fA=rkB→A·fB This is common in interactive bidirectional PRE schemes 121 / 93 Preliminaries Φ(x)is the cyclotomic polynomial xn+ 1, with na power of 2 qis a prime integer such that q= 1 mod 2n Ris the ring Z[x]/Φ(x) Rq=R/q =Zq[x]/Φ(x) R× qis the set of invertible elements of Rq 122 / 93 The Ring-LWE problem The Ring Learning With Errors (Ring-LWE) problem is a hard decisional problem based on lattices We use a variant of this problem proposed by Stehl´e and Steinfeld. s∈ Rqand ψa distribution over R× q A× s,ψ is the distribution that samples pairs of the form (a, b) •ais chosen uniformly from R× q •b=a·s+e, for some esampled from ψ The Ring-LWE problem is to distinguish distribution A× s,ψ from a uniform distribution over R× q×Rq The Ring-LWE assumption is that this problem is computationally infeasible 123 / 93 PS-NTRUReEncrypt: Setup and Key Generation Setup: Global parameters: (n, q, p, α, σ) Key Generation: DZn,σ is a Gaussian distribution over Znwith standard deviation σ The keys are computed as follows: 1. Sample f0from DZn,σ Let fA= 1 + p·f0; if (fAmod q)6∈ R× q, resample 2. Sample gAfrom DZn,σ; if (gAmod q)6∈ R× q, resample 3. Compute hA=p·gA·f−1 A 4. Return secret key skA=fAand pkA=hA 124 / 93 PS-NTRUReEncrypt: Encryption and Decryption Encryption: Input: public key pkAand message M∈ M Sample noise polynomials s, e from a distribution Ψα Output ciphertext: CA=hAs+pe +M∈ Rq Decryption: Input: secret key skA=fAand ciphertext CA Compute C0 A=CA·fA Output the message M= (C0 Amod p)∈ M 125 / 93 PS-NTRUReEncrypt: Re-Encryption Key Generation and Re-Encryption Re-Encryption Key Generation: Input: secret keys skA=fAand skB=fB The re-encryption key between users Aand Bis rkA→B=skA·sk−1 B=fA·f−1 B Re-Encryption: Input: a re-encryption key rkA→Band a ciphertext CA Samples a random polynomial e0from a distribution Ψα Output re-encrypted ciphertext CB=CA·rkA→B+pe0 126 / 93 Multihop Correctness Ciphertext re-encrypted Ntimes: CN=pg0f−1 Ns+pe0f0f−1 N+pe1f1f−1 N+... +peN−1fN−1f−1 N+peN+Mf0f−1 N =pg0f−1 Ns+"N−1 X i=0 peifif−1 N#+peN+Mf0f−1 N When decrypting CN(assuming no decryption failures): C0 N=CN·fN=pg0s+"N X i=0 peifi#+Mf0 Since, f0= 1 mod pand pg0s=peifi= 0 mod p, then: C0 Nmod p=M 127 / 93 Experimental setting Implementation of our proposals: •NTRUReEncrypt is implemented on top of an available open-source Java implementation of NTRU •PS-NTRUReEncrypt was coded from scratch, using the Java Lattice-Based Cryptography (jLBC) library Execution enviroment: Intel Core 2 Duo @ 2.66 GHz 128 / 93 Economic analysis: example scenario IDaaS provider that handles 1 million attribute requests per day ⇒1 million re-encryptions per day Approx. 2000 USD per year Reasonable cost for an average-sized company, considering that their information is encrypted at the cloud provider 135 / 93 DASHR Delegated Access System for Hadoop based on Re-Encryption Data is stored encrypted in the cluster and the owner can delegate access rights to the computing cluster for processing. The data lifecycle is composed of three phases: 1. Production phase: data is generated by different data sources, and stored encrypted under the owner’s public key for later processing. 2. Delegation phase: the data owner produces the necessary master re-encryption key for initiating the delegation process. 3. Consumption phase: This phase occurs each time a user of the Hadoop cluster submits a job; is in this phase where encrypted data is read by the worker nodes of the cluster. At the beginning of this phase, re-encryption keys for each job are generated. 136 / 93 DASHR: Production phase Generation of data by different sources Data is split into blocks by the filesystem (e.g., HDFS) Each block is an encrypted lockbox, which contains encrypted data and an encrypted key, using the public key of the data owner pkDO 137 / 93 DASHR: Delegation phase The dataset owner produces a master re-encryption key mrkDO to allow the delegation of access to the encrypted data The master re-encryption key is used to derive re-encryption keys in the next phase. The delegation phase is done only once for each computing cluster 138 / 93 DASHR: Delegation phase This phase involves the interaction of three entities: 1. Dataset Owner (DO), with a pair of public and secret keys (pkDO, skDO), the former used to encrypted generated data for consumption 2. Delegation Manager (DM), with keys (pkDM , skDM ), and which belongs to the security domain of the data owner, so it is assumed trusted. It can be either local or external to the computing cluster. If it is external, then the data owner can control the issuing of re-encryption keys during the consumption phase. The delegation manager has a pair of public and secret keys, pkDM and skDM . 3. Re-Encryption Key Generation Center (RKGC), which is local to the cluster and is responsible for generating all the re-encryption keys needed for access delegation during the consumption phase. 139 / 93 DASHR: Delegation Protocol Re-Encryption Key Generation Center Delegation Manager Data Owner mrkDO =skDM ·sk−1 DO 1.t 2.t·sk−1 DO skDO skDM 3.t·skDM ·sk−1 DO 140 / 93 DASHR: Consumption phase This phase is performed each time a user submits a job to the Hadoop cluster A pair of public and private keys (pkTT , skT T )for the TaskTrackers is initialized in this step, which will be used later during encryption and decryption. The Delegation Manager, the Re-Encryption Key Generation Center, the JobTracker and the TaskTrackers interact in order to generate the re-encryption key rkDO→T T The final re-encryption key rkDO→T T held by the JobTracker, who will be the one performing re-encryptions. This process could be repeated in case that more TaskTrackers’ keys are in place. 141 / 93 DASHR: Re-Encryption Key Generation Protocol JobTracker TaskTracker Re-Encryption Key Generation Center Delegation Manager 2.u·sk−1 DM 3.u·sk−1 DM 4.u·rkDM→TT 5.u·rkDM→TT skDM skTT 1.u 6.rk DO→TT mrkDO 142 / 93 Experimental setting Focused on the main part of the consumption phase, where the processing of the data occurs. From the Hadoop perspective, the other phases are offline processes, since are not related with Hadoop’s flow. Environment: •Virtualized environment on a rack of IBM BladeCenter HS23 servers connected through 10 gigabit Ethernet, running VMware ESXi 5.1.0. •Each of the blade servers is equipped with two quad-core Intel(R) Xeon(R) CPU E5-2680 @ 2.70GHz. •Cluster of 17 VMs (1 master node and 16 slave nodes) •Each of the VMs has two logical cores and 4 GB of RAM, running a modified version of Hadoop 1.2.1. 143 / 93 Experimental setting: Cryptographic details Proxy Re-Encryption scheme from Weng et al. Implemented using the NIST P-256 curve, which provides 128 bits of security and is therefore appropriate for encapsulating 128 bits symmetric keys. AES-128-CBC for symmetric encryption. We make use of the built-in support for AES included in some Intel processors through the AES-NI instruction set. 144 / 93