Pairing-free re-encryption exists at least for single-hop

[WildCryptoFox]

This paper specifies for single-hop but multi-hop may follow. The major contribution is reducing single-hop re-encryption to DLog without pairings.

https://eprint.iacr.org/2018/1136

A Provably-Secure Unidirectional Proxy Re-Encryption Scheme Without Pairing in the Random Oracle Model

S. Sharmila Deva Selvi and Arinjita Paul and C. Pandu Rangan

Abstract: Proxy re-encryption (PRE) enables delegation of decryption rights by entrusting a proxy server with special information, that allows it to transform a ciphertext under one public key into a ciphertext of the same message under a different public key. It is important to note that, the proxy which performs the re-encryption learns nothing about the message encrypted under either public keys. Due to its transformation property, proxy re-encryption schemes have practical applications in distributed storage, encrypted email forwarding, Digital Rights Management (DRM) and cloud storage. From its introduction, several proxy re-encryption schemes have been proposed in the literature, and a majority of them have been realized using bilinear pairing. In Africacrypt 2010, the first PKI-based collusion resistant CCA secure PRE scheme without pairing was proposed in the random oracle model. In this paper, we point out an important weakness in the scheme. We also present the first collusion-resistant pairing-free unidirectional proxy re-encryption scheme which meets CCA security under a variant of the computational Diffie-Hellman hardness assumption in the random oracle model.

Category / Keywords: public-key cryptography / Proxy Re-Encryption, Random Oracle Model, Chosen Ciphertext Security, provably secure, unidirectional.

[zmre]

Interesting. I'd love to see a multi-hop variant on this, although I suspect the key sizes are pretty big in this scheme in practice. So a speed vs. size trade-off here if it could be made to work in a collision-safe multi-hop manner.

Some of the more interesting PRE schemes of late, at least to me, are claimed to be CCA-secure, multi-hop, and unidirectional, but based on lattices and the LWE security assumption. Some papers that I found interesting, which you might also enjoy:

• https://www.iacr.org/archive/pkc2014/83830204/83830204.pdf
• https://eprint.iacr.org/2016/278.pdf
• https://dl.acm.org/citation.cfm?id=3128607

[WildCryptoFox]

The public keys are just two elements, that isn't large? Unless there is a scaling issue when considering multi-hop costs?

Thanks for the links. Which use cases do you see PRE fitting best? Although I find PRE interesting I'm not convinced the PRE-based storage service is necessary, isn't it a niche case?

[zmre]

The large size comment was because the modulus size in this scheme would need to be quite large -- like RSA large as opposed to ECC.

We've chosen to apply PRE primarily to access control and to public key cryptography using groups. So, for example, if you want to encrypt to more than a couple of people, you run into all kinds of issues with classic public key crypto. The way we do things, you'd instead encrypt to a group, which delegates to group members. This has some huge advantages, including:

• "Unlimited" group size
• Ability to add and remove group members without touching the already encrypted data

So in building systems, you can back access controls with public key cryptography and you can change access to data even if you don't hold the data. Those properties are pretty powerful. We've gone on to do some even more interesting things on top of those mechanics. One example is what we call our GDPR pattern. Here's how that works in the simplest form:

1. A user logs into a website.
2. Under the hood, keys are generated for them.
3. They have their own group and they administer the group.
4. They encrypt their personal info (home address, driver's license number, whatever) to their group. This happens in the browser.
5. They delegate access to a company.
6. The company independently determines which users and systems can decrypt.

Now every decrypt requires a transform first, so you get a nice audit trail of every data access regardless of where the data is stored. You get per-user delete capabilities (crypto-shredding) in the form of revoking access from the company. This handles copies of the (encrypted) data in backups, persistent queues, databases, etc. so the Right to Erasure can be managed.

In almost any system where you want to secure data and where you have users that change over time, but you don't want to just have a central trusted server or to share secrets everywhere, PRE is a very handy solution.

One more thing we do that you might find interesting: we actually consider every user to be a group of devices. You can only decrypt using device keys (we use multi-party computation tricks on the group and user keys so they can't directly decrypt). Device keys don't leave devices. You approve a new trusted device (or browser or whatever) and it can decrypt. Now we can shut off access to a compromised computer quickly. This relies on multihop (group->user->device) by default.

If you'd like to read up more on some of this, you can find details in this paper:

https://dl.acm.org/citation.cfm?id=3201602

[WildCryptoFox]

The biggest problem I see with PRE and alternatives is revocation (unless I'm missing something from the more developed pairing schemes). If you already trust the server to erase the re-encryption keys, then you can just use Macaroons with arbitrary access constraints. This would require the PRE service to keep the ciphertexts secret from revoked parties, but that isn't any stretch for this position and forward-secure transport communications already. Delegation becomes as simple as (decryption key, macaroon). Macaroons need only a PRF and the enc/decryption may be any asymmetric solution; say ElGamal or DH for symmetric auth-enc.

I can see PRE being useful when combined with either an n-of-n or k-of-n threshold system to guarantee the revocation if 1 or n-k+1 parties honestly erase; with a deployment where no single party administers all. I.e. This might be fine for several collaborating organizations to cooperate to enforce their shared policies. However, this extension directly follows over to the macaroon-case too, and may contribute in a multi-party fashion for either ElGamal or DH.

Group -> user -> device, using multihop, is cool but again, macaroons are much more flexible for access control - when the server is trusted to enforce revocation.

At least one benefit of secure erasure is, that if the server was honest and is later compromised, the re-encryption key was already erased. Is this property worth the cost? Perhaps. Interesting to see at least. :)

Google Scholar was unable to find an alternative host for that paper which doesn't require purchasing it from ACM (or coming from a university network?). But I can see related work.

[zmre]

I think you're confusing a semi-trusted proxy, which is trusted in the revocation case, but not otherwise, with a fully trusted server. If you're looking for a fully zero-trust system that allows delegation of access, I don't know of one. At best you could distribute the semi-proxy so that entity A owns their own groups and the transforms for those groups while entity B runs a server for managing its groups and transforms. That kind of federation is very possible.

This would require the PRE service to keep the ciphertexts secret from revoked parties

That's a bad requirement. We fundamentally assume that ciphertexts can live anywhere.

macaroons are much more flexible for access control

You're talking about schemes for proving who a person is. I'm talking about data access controls -- schemes for proving who can decrypt data. These are related, but separate concerns. Ours is less a concern of identity and more a concern of controlling who can decrypt data in a changing environment.

For the paper, you can get it for free if you follow the link on our website. Search for ACM on this page: https://ironcorelabs.com/docs/ironcore-cryptography

I'm going to close this issue now as it isn't really an issue for the repository. Hope that's helped.

[WildCryptoFox]

That's a bad requirement. We fundamentally assume that ciphertexts can live anywhere.

Certainly a good property of your design.

You're talking about schemes for proving who a person is. I'm talking about data access controls -- schemes for proving who can decrypt data.

No, I'm talking about data access controls without access control lists. Macaroons are unrelated to identity, they are PRF-based capabilities with arbitrary constraints. I.e. Say I create a directory, I get a macaroon representing the full access control over that directory, then later I want to delegate a select file to you, so I take my all-powerful credential and add a caveat, restricting it to the one file, and give that to you. No identities are necessary here at all.

I can set the credential to expire some time after it was minted (server time in both cases) or have it poll out to me for every time someone attempts to use it, such that I can log how often it is used and reject requests.

I do recommend reading the full paper.

Fair to close. Thanks for the link.

[WildCryptoFox]

That link didn't work for me but.. There is a beta link on acm for their new site, which does let me get the PDF. I don't know if that was there before clicking the /authorize link but.. it works.

https://dlnext.acm.org/doi/abs/10.1145/3201595.3201602

[zmre]

Glad you got it. I'll read up on Macaroons. I thought it played in a different space. Appreciate the pointer.

On Thu, Oct 31, 2019 at 12:18 PM, WildFox < notifications@github.com > wrote:

That link didn't work for me but.. There is a beta link on acm for their new site, which does let me get the PDF. I don't know if that was there before clicking the /authorize link but.. it works.

https:/ / dlnext. acm. org/ doi/ abs/ 10. 1145/ 3201595. 3201602 ( https://dlnext.acm.org/doi/abs/10.1145/3201595.3201602 )

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub ( https://github.com/IronCoreLabs/recrypt-rs/issues/93?email_source=notifications&email_token=AAARQ3Z34TUC6ROICIF5EMDQRMOP7A5CNFSM4JEFVPEKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOECYYNNQ#issuecomment-548505270 ) , or unsubscribe ( https://github.com/notifications/unsubscribe-auth/AAARQ35QQB5NH3QPNYT7RC3QRMOP7ANCNFSM4JEFVPEA ).

[OluAgunloye]

This paper specifies for single-hop but multi-hop may follow. The major contribution is reducing single-hop re-encryption to DLog without pairings.

https://eprint.iacr.org/2018/1136

A Provably-Secure Unidirectional Proxy Re-Encryption Scheme Without Pairing in the Random Oracle Model

S. Sharmila Deva Selvi and Arinjita Paul and C. Pandu Rangan

Abstract: Proxy re-encryption (PRE) enables delegation of decryption rights by entrusting a proxy server with special information, that allows it to transform a ciphertext under one public key into a ciphertext of the same message under a different public key. It is important to note that, the proxy which performs the re-encryption learns nothing about the message encrypted under either public keys. Due to its transformation property, proxy re-encryption schemes have practical applications in distributed storage, encrypted email forwarding, Digital Rights Management (DRM) and cloud storage. From its introduction, several proxy re-encryption schemes have been proposed in the literature, and a majority of them have been realized using bilinear pairing. In Africacrypt 2010, the first PKI-based collusion resistant CCA secure PRE scheme without pairing was proposed in the random oracle model. In this paper, we point out an important weakness in the scheme. We also present the first collusion-resistant pairing-free unidirectional proxy re-encryption scheme which meets CCA security under a variant of the computational Diffie-Hellman hardness assumption in the random oracle model.

Category / Keywords: public-key cryptography / Proxy Re-Encryption, Random Oracle Model, Chosen Ciphertext Security, provably secure, unidirectional.

@WildCryptoFox Actually do you care to talk more about this? Is there a way to reach out to discuss this particular thing more?