hello yes as you hear we'll be talking about dice this is a joint work that I did while at visa research and we're hiring and have intern positions so we asked the question of like how would you want to encrypt sensitive data or store sensitive data and as any good computer scientist does they first go to stack overflow and find a reasonable answer and follow that and if you do that you'll end up with something similar to this first you'll have your message on some computer you'll sample a secret key you'll then run some encryption
algorithm but since you don't want to store your encryption key next to the data you should probably put the secret key on like a different machine somewhere that's safe and this is what you end up with the problem with this solution is that the secret or the the server with the secret key could be compromised by some sort of adversary and then it you lose all your security and this in general is just sort of forms a single point of failure and so some of the traditional solutions might be to use trusted hardware such as
an HSM and this can protect the key but it has several downsides including they can be very expensive there's side-channel attacks that if you get a physical access to it and also there's a lack of flexibility mate you can't the functionality that least HSMs provide our limited and so what we'd like to ask is is is there a software only solution and an immediate idea that can come to mind is what if we secret share this key between several servers and in this case so long as there's at least one good server or on a
server the secret key remains safe however when we want to use the secret key we're gonna have to reconstruct it so say we want to decrypt the ciphertext C well that means all these servers are gonna have to send their share of the secret key to one central location to perform the decryption and now again we have a single point of failure if this location is compromised by the adversary and so in this talk we're gonna try to tackle this problem and this is not a new problem dating back quite a ways that people have
studied and this is sort of known as threshold cryptography and the primary focus of these traditional works have been focused on the public key setting our signature encryption signatures some of the problems with when we started looking at these solutions as that the security that they actually deliver isn't what we're interested in and their efficiency is leaves room for improvement especially for traditional symmetric keys settings and applications so some of the applications that were interested in is the encryption and uh of data possibly a large amount of data or such as like a password file
with tokens while just sitting at rest on a server we're also interested in like network authentication and ticketing granting services such as when you log into some sort of online service and another application that has come up is when you have a group of devices that are often near each other such as like a cell phone and a watch and they'd like to help authenticate each other to do like a purchase or someone so other tasks where location of in proximity is important a second general-purpose solution is known as multi-party computation here these techniques can
compute any function so in our case we're interested in encryption and decryption and there's been a several recent works that have sort of targeted this scenario but some of the downsides is that the achieves even higher overhead in terms of communication and computation as compared to a traditional threshold cryptography approaches and so in our in our solution we define new game based definitions for what it means for a symmetric key symmetric encryption in the distributed setting and so this entails that we want to be able to perform encryption and decryption operations so long as T
out of the N possible parties are available online we want to ensure correctness we care about privacy of the messages being encrypted even from the other servers and authenticity and that you can't Forge ciphertext and we'll get over go into more detail and then we provide a generic construction based upon any distributed PRF and there's two that we consider one which we gives us this notion of strong security that we define this is based on an exponentiation protocol and zero knowledge proof and then there's a sort of a relaxed notion of security that we consider
it's still quite strong but and this is based on a purely based on a es so it's highly efficient no public key operations would be required for this scenario and for example we can process up to 1 million encryption for a second with T talk while communicating with T out of the end servers and the latency is also very less than a millisecond that's pretty much just network latency so our setting is that we want to we have T or we have n server's total and we want to just be able to talk to T
of them and with this bit do it generate our encryption or decryption and we consider the best possible corruption model and that t minus 1 of the servers that are involved in the protocol can be corrupt and we still want to be secure against this scenario we're in the static corruption model where the adversary gets to pick which servers that are gonna be corrupt at the beginning of the protocol and we also assume authenticated point-to-point channels which will be used later so with this I'll move on to our definitions of what it actually means for
a symmetric a distributed symmetric key encryption and so we define it using three algorithms there's a set up algorithm which is a randomized algorithm that generates a secret key that will be distributed between the parties so here I use this bracket notation to define a seeker Shang where each one of the parties holds their individual share of that secret key and together they can come together and reconstruct it then there's an encryption algorithm which takes some subset of the secret keys and a message provided by one of the parties and generates a ciphertext C and
so yeah here's like a possible subset of the service of this top server doesn't need to be connected at all and for efficiency reasons we only consider that sort of challenge and response scenario so you get to send one message and receive one message from each server and they don't communicate with each other our definitions don't require this but this is sort of what our implementations ends up looking like and only the the person initiating the message or the protocol should learn them at the ciphertext C and then encryption look can be performed or decryption
excuse me it also takes a possible different subset of the servers and a ciphertext and delivers the message to whoever initiated it so this being able to work with different set of subsets of the parties we call this a consistency property and then we consider two versions of correctness the basic version of correctness says that if something bad happens to the ciphertext during the protocol or in between encryption decryption then when decrypt the decryption protocol is run we are they get back to the original correct message or it aborts so that what that means is
during the encryption it's possible for the malicious parties to sort of corrupt the ciphertext in some way but in no way they cannot make the message to decrypt it something else then we consider strong correctness and this here we put extra requirements on this encryption algorithm in that a either generates a perfectly valid ciphertext C or it aborts so the malicious parties cannot make the protocol do anything other than abort and this is true and during encryption and decryption and then somewhat unique to our protocols versus a traditional threshold cryptography is that we are a
conservative message privacy and that when you run a an encryption or decryption the server's that are helping should not learn the message or the ciphertext that is being operated on and then we also consider an authenticity property that turns out to be somewhat subtle to actually define which I'll talk about now so intuitive authenticity authenticity says that an adversary can't generate ciphertex without using the secret key in this case what that means is it needs to be online and interacting with a tea out of the impossible parties and if we compare this to traditional sort
of the non distributed setting of authenticity is that the game the game based definitions typically go like this that you allow the adversary to adapt lis pick several messages and query this encryption Oracle which gives back the corresponding ciphertext and then at the end of this once they're satisfied with the queries there their task is to generate a new ciphertext C prime which isn't the same as the ones that the encryption or gave them but decrypt correctly and so if we have authenticity then this game doesn't succeed with any noticeable probability so it's this extra
clean definition but in our distributed setting you know there's a lot of stuff going on there's a protocol going here there's messages that are being sent and received and so it's not clear how you can directly translate that definition but one thing that we can sort of bring over is that when the adversary initiates a encryption the ciphertext that they learn at the end shouldn't count as a forgery because this is sort of legitimate activity and so we need some way to say that the ciphertext avais the absolute legitimately generates aren't forgeries so one idea
it might be is that you can put these cipher texts that they generate on sort of like a list such as in the traditional setting and then these don't simply don't count towards forgeries however in the set of in the case of protocols this actually becomes very difficult and that this ciphertext might not be well-defined if like the adversary simply sends garbage and so you what you need is some sort of like an extractor in these protocols which would be quite uh can be heavyweight and would to implement in addition which is unique to our
setting versus the traditional setting is that an honest party can initiate an encryption and he when this happens we want to say that the address a shouldn't learn this ciphertext and if they did they could help as a forgery so this adds additional complications to trying to define what is and what isn't a forgery and there's also other scenarios I'm not going to get into that for the complicated but we sort of take a step back and look at it more sort abstractly is that we're in a threshold setting and so that what that means
is that at the adversary has to at least contact one honest party for each encryption or decryption operation and so we simply count how many times the adversary contacts the an honest party and then we say that they should not be able to generate more than that many ciphertext so there are one more definition of authenticity and so this allows us sort of to bypass all these complicated edge cases and so now moving on to my construction how do we actually implement this well our main ingredient is a distributed PRF and this has two algorithms
a set up algorithm which outputs secret keys shares to each of the parties and then there's a D PRF protocol which takes a subset of the keys and an X and to live out puts up the output Y and this X is public while this Y value is private to the person who initiates it and there's a pseudo randomness property on this Y in that without actually running the protocol this Y value is sort of unpredictable and then in the malicious setting we consider two different flavors strong and here's where why the that is learned
from interacting with a protocol a pseudo-random and correct with respect to like honest parties but in the malicious setting these corrupt service could try to alter this the output distribution and we say so if we have a strong pseudo-random distribute PRF then this can't happen it's always correct or abort and then we consider a weak notion and this only requires pseudo randomness where the adversary can influence the output of this Y but and we build two different types of schemes based on this which both achieve strong correctness but yes well but different efficiency just to
give you an example of what these look like so one over one of the approaches based on a DDH type assumption is to perform Shamir's secret sharing in the exponent of these and so these lambda terms can be computed locally they're sort of public based on Sameer secret sharing and then they can multiply it with their local key and then each of these individual terms can be one of the Y's that get sent back to the initiating party and reconstruct the final opf value their DP is too many things so as a warm up here's
sort of like where we started when you started thinking about this how could you implement such a protocol and the traditional approach for authenticated encryption is this sort of encrypt-then-mac paradigm and so this is sort of what we'll do here first we'll sample a nonce R then apply the D PRF to this value R and get back a secret key why use this to encrypt the message and then we to get authenticity we need to mak this encryption e and to do that we'll simply use the D PRF again and get our Mac T and
then our ciphertext will just be the concatenation of these terms and one issue with this is that it's four rounds and we were really interested in getting good efficiency of just having two rounds which also enables a variety of other nice properties and it seems like this encrypt driving this key Y has to be distributed right local decryption and that you needed to contact the other parties to be able to decrypt later on and this Mac macking term seems to have to be distributed to ensure that once you generate one of these I predict so
you can't change it out later by manipulating what the ciphertext is and the traditional encrypt and Mac approach has been shown to be insecure and so we had to come up with some other approach to get around this issue and our idea is that we can somehow in the first round bind the message m to the key that we generate in the first round and what this looks like is that we still generate this nonce R but we use as the randomness to a commitment and to get Q of the message and then we apply
the D PRF to this cube message and get back our key why and then we run an encryption and we have to encrypt the randomness now in order to check the commitment later and our ciphertext is this commitment queue which sort of down is acting like a Mac and our ciphertext E and then decryption is sort of just obvious saying you query the the DPR F again on cue and you can done decrypt and check the commitment so intuitively what we want to say is that its commitment is sort of binding the ciphertext to the
underlying message M but there's some subtleties here in that here's one possible attack is that you can use you can keep cue the same which has the so this distributed property applied to it but you can change the underlying ciphertext E so you might keep the same mess it's still deep Crips to the same message but you can generate additional ciphertext so we would lose authenticity and so to get around this we ensure that this encryption scheme is deterministic and this is not too hard to do but it takes extra care and then there's also
another subtle attack here in that an adversary can masquerade a decryption query as an encryption query since the decryption and encryption from the protocol view looks very simple same you just send a commitment and you get back the corresponding value and so an adversary could come along and say hey let me encrypt this message which has this commitment cue but you're really decrypting one of the cipher texts that you've observed from somehow and so we want to prevent this otherwise message privacy wouldn't be ensured and so what we can do is add this sort of
identity tag here which says that when you're performing an encryption you can you can only query the DPR F using your own identity and that way you can't masquerade decription queries as encryption and so this is our full protocol and it's so it's quite simple we just run the DPR F and correctly construct this ciphertext and then we provide several different instantiations of this DPR F 1 has this strong notion of correctness and all privacy and authenticity property while the weaker notion only doesn't get our strong notion of correctness in that we're bad ciphertext would
be caught encryption or decryption and we provide several implementations and yeah so for performance here we consider 18 possible 18 servers and a variety of thresholds so here at the table our threshold to T equals two that means you have to contact two servers maybe one is counting yourself to generate a ciphertext and you can see that we can perform up to 1 million encryptions per second where the DPR F is based on this just any PRF in this case we use hardware accelerated AES and so it's very efficient and then these DDH based protocols
don't get as high of throughput because they require exponentiation but the last one here with 226 encryptions per second also gets a strong notion of correctness where bad cipher texts are caught immediately encryption and then we can also consider latency and here you can see with a threshold of two our latency is 0.1 milliseconds so it's very efficient and even with very high threshold of 16 parties our latency is only 2 second milliseconds or up to 55 milliseconds with a strong correctness property and we also consider various other values of n so number of parties
and we achieve roughly with smaller end you get more performance but it's not too much different than this and so in summary we initiate the study of threshold symmetric key authenticated encryption we perform propose a general framework that requires any to be implemented with any distributed PRF and we implement it using variety all our implementation is very fast and can scale to a large number of parties some future directions is that there's some so I was talking about that masquerade and encryption as a decryption the inverse is also true but maybe it's not as bad
so you could look at trying to present such such attacks and then you can also look at other forms of security such as protecting against nonsense misuse and in the many user settings so these are just sort of different environments to analyze the security of protocol and and with that I'd like to thank you let's dice I have a probably a stupid question but could you shed some light on why an authenticated encryption mode doesn't compose with the DPR F oh yes so the one of the main problems is just using a traditional authenticated encryption
scheme is that you might be able to generate many ciphertext so in that Center additional setting the person who generated ciphertext will do it honestly but here the person generating the ciphertext could be an adversary and so they could generate many ciphertext based upon their might not just be one way to generate that ciphertext they could keep generating many ciphertext after they arrive the first initial key and so you lose authenticity because an adversary knows more information than in the traditional setting where and an encryption Oracle performs the encryption a little bit of like an
ill-informed question but ok I'm just curious like order of magnitude if you would compare what you're doing to what you could get with like a good secure computation protocol pre-processing beauties I mean can you give an order of magnitude how much faster you would be so if you pre-process the oaties so then then you fill two extension oh yeah sure without yeah it would seem we're two orders of magnitude more efficient so like the actual communication that we send is like at least in the AES base case we send 128 bits to each party and
then we get 128 bits back so like you're gonna be much more than that order of magnitude money are you assuming a wide area network there or even over I mean I mean I know the communication is amader but it but it you're saying it's communication dominated rather than computation well I don't know in this case it's well you it's hard to say for short messages it spike communication bound and yeah and in that case like users if you use ot based approaches you're gonna be communicating you know more even if the round complexity isn't
much different I mean it depends on N and T also but but yeah so you but let's even to party you think you're a hundred times faster I would think so you know at least yeah but that between that and ten oh yeah so they only go up in the AES based approach and this is has to do with we in this AES base D PRF it has this replicated secret sharing scheme and what that means is yet like you send the same share to more than one person and you actually get some sort of
bad comment oryx right when the threshold is that one half and so when you start getting back towards where you need almost all the parties you don't have to account for so many different possible subsets get you better performance