Skip to main content
Loading Explore guides…
Predicate Encryption & EDHOC Protocol · Acedra
Home
Explore
Computer Science
Predicate Encryption & EDHOC Protocol
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
114 segments
Copy
Hide video
0:00
- So hi everyone, I am Olivier Blazy. So welcome to the first talk of the cryptography track of RSA and the first station about public key cryptography. So I'm going to speak about public key identity-based revocation scheme fully attribute-hiding and function private. So I'm a Professor at Ecole Polytechnique and this is a joint Prof with Sayantan Mukherjee, who is at IIT-JAM.
0:24
Okay, so the main purpose of this talk is to speak about predicate encryption. And a predicate encryption is some special kind of public key encryption where decryption is possible if predicated is verified. So it means this is some relation between the secret and in the safe text and some secret process by your user is verified. So it's a generalization of standard public key cryptography where you have a secret key associated with a decryption key associated with a public encryption key.
0:52
Here it can be a little more advanced. And two of the main kind of predicate encryption that I studied are inner product encryption and identity-based multi-recipient encryption. On inner product encryption, we are going to consider the inner-product between a secret Y that is identified for TEX and a secret process by the user X and classical version. So zero in our product encryption you are going to be able to decrypt if your secret is orthogonal to the secret embed text
1:23
and variation is nonzero in our product encryption and it's the opposite. You are able to decrypt if and only if your secret is not orthogonal to the secret in the cipher text. For identity-based multi recipient encryption, it's a generalization of identity-based encryption. So normally with identity-based encryption you are encrypted for one user and you are stating that,
1:44
"Okay we only Alice is able to decorate the cipher text." Here you have the broadcast version where you're going to say every person who is a female cryptographer for example can crypto the hyper text and so all the identity in this set are going to be able to decrypt and you have the opposite. You can do identify vocations, so it's everybody who is not inside the set that is able to take. And so we're going to try to link all the primitive together to show that in fact it can be done.
2:12
It can be achieved in the standard model with source security.
2:16
Okay, so when we speak about security for the scheme, we are four main kind of properties that we're going to expect. So the first basic one is confidentiality. It means that if an adversary picks two messages, M zero and M1, we give him an encryption of one of them. He should not be able to guess which message was encrypted as long as it doesn't is not authorized to decrypt this type of text. So that's really the direct equivalent of inability that you have on self text.
2:47
Then we want more advanced properties so that are called the weak anonymity or weak attribute guiding. It means that if I give you a cipher text for challenge Y zero Y one, you should not be able to guess which of the two challenge I used and for the weak version, as long as you are not allowed to decrypt for those challenges.
3:10
In the full version, it's a little bit stronger. You should not be able to guess if I use Y zero Y one to mask to generate myself a text and that either if your keys are not authorized or if they're authorized for both self a text. So it means that even if you can decrypt, you should not know for which challenge you are able to decrypt. You should just know that your key is working
3:35
and then you have a strong another variant which is predicate or function privacy. And here it's when I give you a secret key, you should, you should not know which set of constraint you are secret key is associated with. And so if you come back to the previous side, you should not know whether I encrypted it for X zero or X one and here it's something that you may want or may not want depending on the application case. Where you won't want it is
4:06
like when you receive a key normally you like to know for which set of attributes you're able to decrypt or to do something of it. And so in this case we don't really want function privacy but if you are generated keys for a set of user for example attend this to conference, they may not, you may want to add some special access or some special information associated with the key. Okay, so already some generic transformation exists. So you have a transformation from a inner product encryption
4:35
to database multi receiver encryption and the transformation, their main purpose is to preserve confidentiality
4:43
and if you go to the suitcases, so the cells that were on the right, then you can convert anonymous or fully anonymous zero in our product encryption to anonymous or fully anonymous in a space, the broadcast encryption. However, we don't know how to build until now a full, a fully anonymous zero in our product encryption. So this transformation is nice to be generic but in fact it's never happening because something doesn't exist yet and you have the same for function privacy on revocation.
5:15
Okay, and so we are, we have this problem and the main trick is that
5:25
so generic transformation on inner product encryption don't preserve function privacy and we wanted to solve it, okay,
5:34
so to come up a little in more detail on the properties that we want. So the first one is message hiding. And so to define the security experiment for message hiding we're going to have a set of algorithm and so the setup is just here to generate public keys and secret keys and so of course the adversary has access to the master public key and hopefully doesn't have access to the master secret key. Then the rosary is allowed to do key queries. So it's going to get identities from a set
6:04
and it's going to get a secret key associated with the identities and the rosary is going to provide a challenge message. So M zero, M1 and M1
6:13
and the set of identity, we want this set to be polymerized because otherwise there's an issue and you cannot just run the algorithm and it is going to provide all entity in the set
6:26
and we are going to return the encryption of one of the message for the set. So if we are in the case where we want vocation means that the address for every identity in the set, the adversary is not able to decrypt and for every identity outside the set, it should be able to decrypt.
6:45
The adversary is still able to do key queries for entities in the set
6:50
and the adversary is going to outputted guess and he's going to win if he managed to decrypt the message, even if he well never got a key that should allow him to decrypt. Okay, if we go to attributing, it's somewhat the same except this time instead of considering the identities is going to provide set of identities is going to provide messages and two different set of identities.
7:18
The set again needs to be polynomial size, otherwise there's a problem in the definition of the issue and we're going to encrypt according to one of the sets and it should not be able to guess
7:29
which message was encrypted and for which set. And so again we have the switch from weak attributing where the identity should not be authorized and full attributing either are not authorized or both are authorized as are authorized for both set of identities. So it's just a matter of allowing the adversary to process more information and still remain secure.
7:55
Okay, and the last property is function privacy. And again, it's somewhat the same except this time
8:02
the adversary is going to have a secret X embedded in the key and the way we represent the secret here, we need to consider distribution of the secret to get some way to consider the fact that they are hidden. And so the distribution should be somewhat similar
8:23
and independent and the rest of the experiments is going to run somewhat the same and again the adversary should not be able to guess which thing was encoded and for X which X resident.
8:36
Okay and so where we are is that there's a gap in the ecosystem and so there's many, many zero knowledge, sorry, zero in our product encryption, but there's no non-zero inner product encryption scheme in the solar model even if we can anonymity. And here it comes from the fact that the classical way to build is to use some kind of linear encoding to achieve a linear secret sharing. And so what's going to happen is that we're going to have some term that are going to be computed
9:12
to generate some kind of keys and this term is going to be an element in Stargate group raised to a value beta, which is going to be the main secret plus some function of the inner product and the adversary is going to be able to compute this value in some way hoping on the fact that the inner product is zero and so we will have some kind of magical simplification and so if you take the two terms that are presented, you have GT to the beta plus gamma, GT raised to minus K times gamma
9:40
plus some delta of the inner product, the adversary if it process K, it can simplify on the last term the minus K gamma to a minus gamma and if XY is equal to zero, then you can simplify on the first time recover GT to the beta and be happy and do a one time pad to decrypt the message
9:59
and so that you can do it normally when you have, you are able to converge to one single value and you need the fact that inner product zero,
10:08
but in case we're in instant zeroes and it's complicated because you're just saying it's a random value that is not new and you cannot have this kind of reconciliation that was nice to build a zero in our product encryption. And so here it's a problem because either you are able to explicitly compute this value which is somewhat opposite to the fact that you're going to add X and y also. And so we needed to find a way to do it anyway.
10:36
And so to do so we're going, we process in several step and so first we construct and predicate only zero in our product encryptions within our group and shows that it's fully attributing and function private under a new assumption. So just because we're introducing new assumption, we also prove that secure in the general group model, but it's normally a reasonable assumption. And then we produce a compiler, so general transformation from predicate only the IP to into an IP
11:08
and show that this compiler preserve all the properties that you have. And so this way we obtain an IP that is fully attributed and function private and while we're doing this, we also show that this transformation we can take the initial transformation from a inner product encryption to identity based, the multi receiver encryption to do an IP to IBR. And so built also first efficient somewhat identity based revocation system.
11:36
And so and again we show that this preserve the properties.
11:40
Okay, so ask him is this way, which is somewhat ugly but in fact it's an adaptation of the KSAN V 15 qua adaptive zero knowledge proof framework. And so in fact we, the thing that is scary about it is that it's using nutrition notation and it tries to be very generic. Does that work? Yes, but in fact you can when you have an element that is in bold font we without square around it, it just a matrix of discrete logarithm. So at the beginning, we're generating several discrete log algorithms,
12:20
so think of that as secret keys and in fact it's exactly what we say. We say that the master secret key is going to be all those matrices of discrete logarithm. Then the public key in a standard gamel scheme for example, it's often a group element associated with the discrete logarithm and that's what is said when you have brackets, square brackets, it means that you have the associated element, the group element associated with the discrete logarithm.
12:44
And so it's just mattresses of group elements and when you have a product, so it's a group element raised to a scholar, so it's still a group element except that you don't know, the adversary will not know the discrete logarithm. So you will see that just a plain group element. And so we have lots of elements that are generated but it's somewhat classical and elegant in the design , at least you have some structures that appears. To do the encryption, we are going exactly the same way,
13:14
so we're going to put some random elements that are going to be discrete logarithm. Generator ax with a main element like in neuro Gamal, which is H two ZR, but it's noted SA because it's a matrix, the hypertext is a little more involved but it's somewhat the same. We are adding the secret Y in it and with an extra term to avoid some kind of probability and the sax is going to be the set of elements. The kitchen is the same but on the other side, so we are going to take the X secret,
13:45
I did a little the same way go into the other groups. So in group two instead of group one generate the element and the key is going to depend whether we are on zero or one, but that's some more or less the same. And to test, we just going to do some kind of pairings and if the pairing match, we say that we say that we encoded the message one and if the pairing don't match we say that we encoded the message zero. What's interesting with this kind of notation, in fact we can rely on
14:16
many, many different kind of hypothesis. If Kegel one is just a standard D man or symmetric external D man version, so it's U gamal and the mattresses really collapsed to two elements. If KL two then it's a decisional linear problem. You should prefer symmetric curves and it's the same way and here the matrices are going to be two times three elements or six element, sorry, two times five, three times five element but the same and you can take care as big as you want,
14:52
so the elements are going to be very big, but you increase security. But I mean in front of a control measures anyway, there's no point in going above, but if we have problem on curves in between, it still works. Okay, so we can prove that this scheme is secure for all the properties under the K-M-D-D-H assumption. So under some kind of Mann assumption and we have a loss in the query made by the linear loss in the query of made by the adversaries, but it's not too much the art trick,
15:25
if we want to be tight just we still, we lose a lot on efficiency of the scheme.
15:32
Okay, so then we need to build our compiler to transform the our predicate IP to an IP and in fact we're more or less going to use it sub plug and play version. So we take the setup, we don't change anything to generate a key, we don't change anything and it's just when we're going to encrypt, that's the part where it's going to be somewhat inefficient for each bit of the message we're going to generate a new value and so instead of having a vector, we're going
16:01
to have a metrics of element to do us some self text and because it's an IP, we need to think backwards and so to hide the things, we're going to sort the vector one, one, one to the values that we compute that just, I mean you can take the convention that you do, you don't need this, but at least here it's more direct when you do the computation, okay.
16:29
So we can do this. If we compare to a previous scheme that was building on IP, we are less efficient because now we are relying on the less length of the encrypted message. So it's worse. However, in term of security, we're much better because instead of being only a weak attributing, we are fully attributing and the previous scheme even have restriction on the kind of queries the adversary is able to do. Here we don't have restriction and we are function private so we can hide even the secret
16:58
that is given to the user in security.
17:02
So that's a trade off, but it shows that it's doable.
17:07
There's a compiler that say now if you find a better scheme then you have a better, a better final scheme and you don't choose anything in term of security, okay.
17:19
Okay, then we can consider our second transformation and it's going to work more or less the same. Here's the identity, we are going to transform it into a vector that's going to be also explanation of the identity up to some value.
17:38
To encrypt this, we're going to do an interpolation of the identity for some secret coefficient, A zero K, but that's somewhat a classical transformation that you can find anywhere. It just we're taking the framework and showing that it can be applied and today crib, that's the part that's a little in fact magical. It works exactly the same way as before. You take the multiple, the master public key, your secret key, the safe text and you run test on it
18:03
and it works and there's no issue appearing and you don't need the trick of reversing because the way you embed the poly.
18:12
So this scheme is roughly similar, which is logical because we use the same kind of transformation.
18:19
You can see the poly appearing here and it's just going to give you a base value to add in the rest, but it's not too much for an attic, the decryption, again, it works the same way. You're going to do pairing computation, check whether this computation are fine or not and be and it's going to work.
18:40
Okay sorry. Okay, in terms of efficiency, so we did a previous result where we showed the first transformation of an idea but with lots of restriction. So before you were, when you relocating a key, you are relocating every possible key for a set of user, but now you can revive a key and give a new key for the same user for the same identities that's going to work. Before we needed to have a banding collision, it means that beforehand we were, we had to say that only 10 user can collude
19:14
and above that we don't consider that part of the experiment. Now we don't have this and we are fully attributing and function for having, So in term of master public key it's not great because before the master public key was one element. Here we have still something that is linear in both vector and the encrypted message. However, for the secret key we have again before it was credit in the length of the encrypted message. Now it's just linear and for ax where a tiny bit bigger
19:42
but of the same of the magnitude. So in this case the transformation is much better than for the previous one and we are much better in term of security and we don't have an artificial restriction on the kind of attacks adversary we can do.
19:55
Okay, so to conclude, we managed to do several transformation. So the first one is a transformation from a zero in our product encryption to a non-zero in our product encryption. And the key takeaway of doing this is that instead of trying to converge to the same value, we exploit the fact that zero randomized is still a zero and while a non-zero randomized is the non-zero. And so we managed to do this in a way that's efficient and it gives one bit of information when you do the decoding,
20:28
the transformation from this pre IP to an IP, it's the first one that conserve both at the same time as the fully attributing property and the function privacy property because previous papers were focusing on one or the other property and it's the same for the BR
20:48
and here we managed to be comparable in efficiency or tiny bit more efficient depending on what property you you seek than the current set of the,
20:58
the problem is that our transformation is moderately efficient, it's academic efficient but not practically efficient let's say because there's a linear loss in the message lens. And the question is can we do better? So probably, I mean there's no result that says that we cannot have an efficient transformation. It's just our technique because we are exploiting one fact on the abilities that gives one bit of information. We need to do that for every bit of the message.
21:23
And so from our approach this analysis is there
21:30
and we did this transformation from the IP to an IP and just from a theoretical point of view, it can be interesting to check whether the opposite can be there.
21:38
And so the efficiency takeaway, it's what I said before, we have some loss for an IP but gain security for the IBR. We have loss and win, but we are also better in time of security. So thank you for your attention and if you have question. (audience clapping)
22:05
- Good morning. My name is Loic Ferreira from Orange. I am going to present the paper entitled Computational Security Analysis of the Full EDHOC Protocol.
22:20
The context is the following. With the rise of the internet of things, an increasing number of end devices are deployed on the field. According to some figures, there may be up to 30 billion active IO OT devices by 2030.
22:38
These devices are leveraged in various use cases.
22:43
In smart cities, they're used to monitor sensitive sites to detect fires or to control air pollution, for instance. Plugged in smart home equipment. They can be used to control heating or lightning.
22:58
They may also equipped medical devices such as pacemakers and defibrillators which are implanted inside the human body.
23:08
They are also a component of drones and vehicular systems and they are also deployed among other contexts in industrial IOT to remotely monitor industrial devices.
23:24
In so far as all these use cases imply a secure communication link between the remote and device and a server or a ground station, cryptographic mechanisms must be executed by the IOT device starting with a proper authenticated key exchange to initiate this secure connection.
23:47
However, these end devices are constraints in terms of resources in particular regarding the memory footprint, the computation capabilities and the energy supply. Very often a critical trade-off in fact difficult to achieve has to be found between security and efficiency
24:09
and it may happen that the result can be read afterwards in newspapers when they describe successful attacks and some security mechanisms deployed in such low resource and devices.
24:22
This illustrates the need for an adequate solution both in terms of security and efficiency for this kind of devices.
24:34
This has motivated the IETF working group like to devise a new authenticated key exchange protocol. The result has been named ephemeral or EDHOC for short and the last EDHOC draft, the number 23 is now RFC 95 28.
24:56
These two party protocol aims at being lightweight in terms of number of exchange messages during a protocol run, the size of the messages and the code and memory footprint compared to other protocols that one may deem as lightweight enough to be executed by IOT and devices such as compact TLS or DTLS EDHOC outperforms these protocols, at least regarding the amount of data exchanged during a run.
25:28
The EDHOC protocol is essentially based on the Sigma protocol devised by CHEK in 2003
25:36
and it provides four different ways for the two communicating parties to authenticate. These parties can use either a signature or a static defying monkey,
25:51
so the initiator and the responder can independently choose the way they will authenticate to each other, which results in four different authentication methods and influences are the number of messages.
26:06
If the number, if the initiator authenticates with a signature, then the protocol flow comprises the three messages, otherwise it comprise four messages.
26:19
The physionomy of the EDHOC protocol is the following.
26:24
The key exchange is based on the DFI mechanism. Authentication as said, is done either with a signature or a static DFI key and in such a case a MAC tag is computed with a key derived from the static defying private key.
26:42
Identity protection is guaranteed by encrypting the identifiers, which can be public keys or certificates of the communicating parties as well as the signatures when they're used.
26:57
In more details, we can have a look on one of the four EDHOC method, the so-called signature static method.
27:07
With this method, the initiator authenticates with the static DFI key and the responder with a signature and the protocol flow is the following.
27:19
As said, the key exchange phase is essentially done with the DFI man mechanism.
27:24
The responder authenticates first and does this with a signature.
27:31
The signature together with an identifier are encrypted to protect the responder's identity.
27:39
The signature protects a context that gathers the transcript of the messages exchanged so far and the responders authentication credentials.
27:50
The signature also covers a MAC tag, which is always computed whatever the authentication method used that is with or without a signature.
28:03
The initiator authenticates with the MAC tag and this tag is set encrypted together with the initiator's identifier so that the receiver can retrieve the correct credential to verify the MAC tag.
28:19
This tag is computed with the key derived from the initial, the fieldman key exchange and the initiators static, the fieldman private key.
28:28
The data protected by the MAC tag includes a transcript of the messages exchanged so far and the initiator's credential.
28:37
Then the responder sends an authenticated and encrypted message computed from a key derived from the main share secrets. That is in this case the initial, the FEARMAN key exchange and the initiators static the fearman privacy.
28:55
In addition to other parameters which are related to this specific protocol run. This message proves to the initiator that the responder is indeed able to compute the key material necessary to output the final session key and the third message sent by the initiator fulfills the same function for the responder.
29:20
Finally, the session key pure key out is computed from these shared secrets.
29:28
EDHOC makes use of the same kind of paradigm as the HKDF scheme devised by craft check. That is an extract function is fed with the different shared secrets such as the DMA shared secret in order to provide secret seeds
29:45
and an expand function is used to output intermediary symmetric keys and other parameters.
29:54
The different messages exchanged during each specific protocol run are progressively accumulated and incorporated into the several computations done during the run.
30:07
The final EDHOC specification is the result of multiple drafts. Several analysis either with formal methods or in the computational setting have been made of different such drafts, for instance 12, 14, 17, et cetera. Regarding the computational analysis, only one different authentication method has been scrutinized. Moreover, the security models used in these works do not incorporate exactly the same security properties, so what we have done is first to devise a strong security model
30:44
that captures all these different security properties.
30:49
Our computational security analysis also covers the different changes that have been made successively after the different previous security analysis and we have considered the four EDHOC authentication methods instead of one only. Finally, from our theoretical security bounds, we have computed concrete estimates for these bounds based on different possible adversarial resources.
31:17
EDHOC proposes different CY suites and these concrete estimates enable to choose the proper surface suites depending on the actual context the protocol is deployed.
31:30
The security properties captured by our model are the following.
31:35
First, entity authentication, informally. This guarantees that an instance ending in accepting state as one and only one communicating partner during the protocol run. Key indistinguishability guarantees that the final session key is indistinguishable from value from the same set of keys uniformly chosen at random for what secrecy bears on the security of the past stations when the long-term secret is disclosed. Finally, identity privacy guarantees that the identity
32:09
of the parties involved in a protocol run remains confidential and also that different protocol runs cannot be linked, which forbids an anniversary from tracking a given party.
32:23
This security property is based on the notion of virtual identifier and during the corresponding security experiments, the adversary chooses two identities and the challenger runs the protocol with one out of two. The attacker's goal is then to guess which party is actually involved in the protocol execution.
32:47
The adversary can basically do anything but to get access to the session state as long as this does not lead to triple attacks. That is an attack which essentially is unavoidable and does not depend on the protocol features.
33:04
More precisely, the adversary is active, it controls all communication and can forward alter, drop any message exchanged by harness party or insert new messages.
33:18
It can corrupt long-term keys, reveal session keys and unmasked identities,
33:27
so we provide theoretical bounds, security bounds for all ODHEC authentication methods. We establish the protocol security based on the strong and gap Mann assumptions, mainly, for the key inability property, the inability of the signature scheme or the MAC function depending on the EDHOC method for the entity authentication property and the cipher text indistinguishability provided by the symmetric key functions for the identity privacy property.
34:02
As said earlier, different cypress suites are available in the EDHOC. The specification defines in particular two cypress suites for high security applications. One is based on AS-256 and the other on SASHA 20. From the theoretical security bond that we get, we can compute concrete estimates based on different adversarial resources in terms of computation and time, and these estimates show that the CFO suite based on AS256 appears more suitable for such high security applications.
34:40
To sum up, we have performed a computational security analysis of the EDHOC protocol and its four authentication methods. In a strong security model, we have got theoretical security bounds, which in turn enable to compute concrete estimates based on various adversarial resources and these estimates can be used to choose the proper EDHOC cipher suites depending on the context of use. We have also shown in particular that the cipher suites based on AS-256
35:13
appears preferable for high security applications. Finally, in the context of the threat post by the development of quantum computing and the post quantum transition, a challenging area of future research is to devise a quantum resistant version of the EDHOC protocol.
35:33
This ends my presentation and I thank you for your attention.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat