Real World Crypto conference 2020: session 14

all right so we're ready for the last session of the day in a real world crypto all right so we have block chains and distribute Ledger's and we have three great talks in that session so first one is titled challenges cryptographic solutions with payment channel networks and the speaker is Pedro Moreno of sensors with next to me and about ready to go now before I leave the stage quick announcement there is a letter zelda bag like i'm not sure what if this could be like some little device here so if you lost it or forgot it in the bathroom it will be just right here okay with this I'll just pass it to paid off right okay thank you for interaction hello everybody and thank you for attending to my talk this point of the conference today I'm going to talk about scalability problems so Bitcoin and many other cryptocurrencies have a scalability issues and this is because they rely on a decentralized data structure that records every single transaction happen in the system this is good because we provide public believability so we can check all the transactions that happen in the system however it requires a global consensus that in practice limits the transaction rate to around ten transactions per second and this is far from what we have in our systems like Visa or MasterCard this is clearly the problem has been tackling the community and we can roughly group the approaches in two trends one is on chain were mainly they tweak the consensus algorithms and protocols to improve the transaction the transaction rate the other approach is off chain so we use the blockchain as minimum as possible so we use it only to solve the disputes between users this is where payments and networks fault and we have a couple of examples already deployed in practice we have the lighting Network for Bitcoin we have also red and not green etherium and many other research projects some of them are actually implemented already as you can imagine and gonna publish the second second approach today let me start with a little background on payments higher networks reminder we have a lease that has some bitcoins and she wants to buy some product from Bob she can open a payment channel for that in order to do that she creates a transaction where seed transfer five coins to what is called a multi seek contract a contract that can be further spent only when both Alice and Bob agree to make sure that Alice can recover the funds she let Bob sign the refund transaction the transfer the coins back from the multi counter multi-sig contract back to Alice when that's when that has been done then Alice can effectively put the transaction on chain effectively opening the payment channel and she keeps locally that we found transaction just in case the C need is later once the time is open sea can use it to perform several transactions of chain so she can do that by redistributing the coins from the multi-sig contract accordingly mine that she wants to pay one coin to Bob she pays one point from the contact to Bob and the remaining four are paid back to Alice see signs that and this is a valid payment for Bob because the only thing that has to do is to sign himself but he can always do that because he has his own signing key instead of doing that he has waits for more payments from a distance he can do that by accordingly distributing the coins from the multi-sig contract in practice the these payments can be more complex we can have bi-directional payment so Bob can pay back to Alice we have also a revocation mechanisms to revoke all states and when both of them Alice and Bob are done with the reducing the channel they can close it for that yes sign the last state and put it on the blockchain so we have only two transactions on the chain and many many many payments that happen off the chain this payment and this protocol however allows only two users to pay between each other so what we would like to have you practice is a payment from Alice to everybody else and for that Alice could open payment channels to everybody however this is really costly because for every channel she has to lock coins and see might not be so so rich instead what we use in practice is Alice relies on a path of open channels between herself and the intended receiver so in mind that Alice wants to pay to Caro she first sends one Bitcoin to the in the channel that she has with Bob and this will forward this one Bitcoin to carry herself obviously for this to be used in practice we need that the whole operation is atomic in other words Bob's who get the money from Alice if and only if she has actually paid to cut this concept of payment I network it's what is hasn't been implemented in the lighting network itself and here they have tackled this challenge of the atomic atomicity by including more conditions on the payment itself so if Bob receives such a chain payment he can actually put it on the blockchain not only with his signature but also he has to solve a cryptographic challenge which is he's given a value Y which is a hash value and he has to come up with a value X which is a valid pre-image for that cash value and because Bob might not come up with such a ballot pre-image anytime or ever we also need to add what is a time lock after which the Bob can no longer use the transaction can no longer put it on the blockchain in the rest I'm gonna denoted by this notation and I denote that Alice faced Bob one coin if and only if Bob shows some X such that X is a valid preimage of Y before some timeout has expired and now one we have this building block we can concatenate several of these has time block contracts to have a payment from the sender to a receiver let me let me show you how it works in this example so Carol creates both the value X and the hash value of y and gives the value Y 2 twice now Alice can create a conditional payment condition on this value Y to Bob Bob doesn't know the solution but he can forward a conditional payment conditioned in the same value Y to cut now because Karen knows a solution she created at the beginning she can show it to Bob to pull the money from Bob and he can forward it to all itself this is mainly how the light in that world works today and here there are two key points as we should pay attention the first one is that these protocol requires that the time in the left channel is higher than the time in the right channel and this is to make sure that bob has enough time when he receives the value X from a title to forward it to Alice to get the money from her the second requirement is that Bob gets a little more money than the one he has to forward in the payment this difference is called the fee and this is important for him because it's the feed he charged for providing the services of forwarding payments between the sender and the receiver so if you haven't got the details doesn't really matter so what you need to understand for the rest of the talk is that there is assistance called the lighting Network and allow us to perform payments off the chain they are fast because we don't require to go into the blockchain into the Consensus to confirm to confirm the payment it requires some little fees for the intermediary and at the first glance it looks secure use this has time lock contract and it looks private because of privacy reserved because most of the information is not in the blockchain anyway but this obviously is only at first glance and we in our group we ask ourself whether is actually secured and whether it actually provide privacy by privacy by default and if I'm giving here a talk you might imagine that the answer is no for both of them and the next I'm gonna show you what are some of the problems I would have with them in terms of security and privacy regarding security we proved we showed an attack which is called a war home attack and the main idea is that an adversary sitting between the sender and the receiver can let the intermediate nodes to participate in the payment and later steal the field that is suppose or response to this honest note let me show you in the end exam so imagine we have a set in which all the user have already locked coins in this conditional payments in these stl sees now Carol or gives the solution to to Eve and now if instead of rewarding it to Bob he just wait until the time out of that hdl-c aspires for forwarded to if itself okay and then all their attacker forward is to to Alice what happens in practice is that Bob considers that the payment has failed have not been successful and unlocked the funds after some time out the bursary pays one Bitcoin to Cairo but he gets 1.3 from Alice so what has happened is that the attacker can has got his own fee but also the fee that was associated to Bob for forwarding the payment and this in practice is important because this attack takes back the fees for the honest user which is the main incentive that they have to participate in the network there are other all also other implications for example the funds from Bob Channel are locked for the whole entire time lock duration that means that he cannot use those funds for other payments that had been at the same time and might have been successful additionally Bob believes that the payment was was failed was not successful and he doesn't have a way to blame the attacker for that for the attack he doesn't know that the attack has happened from the privacy point of view the situation is not bad so in mind that we have two simultaneous payments where each Alice on the Left wants to pay to each car on the right into deeply what we would like to have his call relationship anonymity to deathly empathic bursaries do not learn who is paying the home a bit more technical what we want to achieve is that diversity cannot distinguish between two cases one case in which blue Holly space two blue Caro and green Ali's place to be in Cairo and the second case were blue alle space to the green cattle and the green Ali's place to the blue cat however if we look how it works in practice the adversary can link or can deterministically determine which of the two cases we are in the example shown in this slide you can see that blue why the Y value is given by the blue Alice and later is forwarded to cutter to the blue car so he can return mind that the blue Alice is paying to the blue car the same manner because only y prime is given by the green alleys and forwarded to the pink color he can link both of them therefore religion sabudana media does not hole in the lighting network either in this test officers we are in our group we are also coming up with crypto attic solutions that provide or improve the security and the privacy in current payment giant networks the main observation that we did is it seems that most of these problems come from the fact that we are using the same y value at each of the hops in the path so it might help if we have a randomized conditions at each of the hops and we can solve them only when we get the key from the right neighbor in order to do that we could add a setup phase where the sender distribute individual randomization factors to each hop in the path okay decide and with these two main ideas we are trying to achieve three properties so the first one is atomicity which means that if the user writes lock get opened then he should be able to open one on the left in that sense we make sure that no no coins are lost we also want to achieve consistency which means that if the user one was able to open the one on the Left means that he had to open the one on the right in that manner a users cannot be over past and we will meet we prevent from the war home attacks finally regarding privacy a users will learn from to learn about no other participants in the path other than the direct neighbor in the length in the left and in the right let me show you and high level how our protocol which is go anonymous moody ha blocks actually work it works in three phases in the first one the setup Alice provides a couple of elements to a couple of a table of information to each user in the path this table has two elements the first one is this randomization factor that I mentioned before second is a condition that puts together all the randomization factors from the users from the sender to the use to that position in the path okay once we have that and Alice puts the concatenation of other randomization factors to the last one to the receiver now they can pairwise perform this lock operation we will see later how its performed where every user face conditioned on the fact that days of the condition given by Alice before for example he won here can get the payment if he can solve the D lock of the element C 1 and they do it from the left to the right now Carol he was given she was given the solution for C 4 already so can really give it back to e 2 2 came to claim the coins now he too can use his own randomization factor to the randomized the key that was got from Carol and forward it to Bob and every users are the same so they got the key a ballot key from the right they randomized it and send it back to to the left when idea is that conditions look random because they differ by a secret random factor that is known only by each of the users in the path and a valid key can only be computed if you get the right the valid key from the right name they said I omitted here how the lock contract works I'm going to show you it here in this slide maybe is that there is a public key sure between both of them Alice and Bob where the bomb the corresponding secret key is signature between both of them Alison Bob and they perform and off chain payment and a two-party protocol to create a transaction a signature of the transaction which is almost valid it's almost valid because they need to come up with a value K with which they can finish the transaction it some of the signature in this case and these two party protocol has to ensure two properties first looking at this half signature ball has to make sure of has to be convinced that whenever he lands the value key K later he should be able to finalize the signature and put the transaction on the blockchain and from the point of view of Alice if Bob ever finishes this the signature and put the transaction the blockchain she should be able to read retrieve the value K because this is what she needs to put it further back in the path for the payment I don't have time to show you the mathematical details or how it works but I encourage you to read in the paper I tell you that we have three constructions we show that we can construct such a two-party protocol from any amorphic one-way function and we have other two constructions one that relies on the H nor these are signatures and the other one that relies on ECBC perhaps the last one is more interesting because it's compatible with many of the cryptocurrencies today mainly Bitcoin idiom and many many others also this we have shown that achieves the security and privacy notions of interest that we were defining in the universal composability framework and the community has done some proof-of-concept implementations not only in the lighting network but also in the case and network and the Kombi network itself our protocol has also other practical advantages for example it reduces the transaction size for conditional payments our conditional payment no longer need the logic to check whether a pre-match of a hash function is correct Wien go to this condition in the signature itself so we need only the verification of digital signatures to have conditional payments moreover perhaps more interested in practice we our construction allows what we go into double double payments Hank so interoperable multi-hop payments Mirena path in which one lock is in Bitcoin or ECDSA waste the next one is defining etherium at the lock based lock we can still perform a payment that go from the sender to the receiver with security and tax in the last five minutes I have I'm going to show you another challenge that has we have studied in the Bitcoin compatible payments on it by Bitcoin compatible here I mean those payments on networks like the Latin Network that do not support Turing complete language like solidity in III collateral is a turned has been used in the blockchain community to deter mined or to denote the amount of resources that we need to perform move the whole payment in terms of coins and time that they are locked for example if we have a payment that goes over n minus two channels each payment of K coins has to be locked or we need a collateral of at least K times and K times and coins K coins at each of the engines also for the reason I has said before the time that the Chan that the coins have to be locked at the channel is staged in other words it depends on the position that you are in the path just for security as I said before for security you need to lock the coins at one channel a tank higher than the one you have in there in the next time bottom line is that the coins right now are locked to long in a path and this opens the problem the open some problem in practice like the Griffin attack the main idea here is that the adversary can perform a payment to itself where in order to do that diversity has to lock K plus some fees and the hole in the first hop for that time and times Delta I mean the last one has to lock kick audience for that time yet while doing that he forces n minus two channels to lock coins and also each of those coins are locked by a time which is proportional to the position that they have in the path therefore the bursary has a time amplification of n minus 2 and this in practice is really important because this Delta has been said in the Latin Network right now for one day so if the attacker uses a path of seven hops let's say coins are locked for seven days for a week and obviously the dagger can make this attack worse by having longer path of using several paths for his payment so they all or what we would like to have in practice is called we call it constant collateral the idea is that we would like to have a payment from the sender the receiver where we have to lock coins but for a fixed time it doesn't the time that you need to lock the coins should not depend on the position of the path that you are this will greatly reduce the overall time where the coins are actually locked for the payment this has been shown feasible in a theory based payment and AdWords so they have two incomplete based contract that actually implements this logic and if you are interested the details are in the sprite paper but also in this paper the conjecture that is not possible to have such a functionality in Bitcoin or in other words you can have it you can emulate such a finality in Bitcoin when you need to modify the scripting language and enlarge it with more functionality we have richer scripting language to have such a solution now our work we show that this conjecture doesn't halt by providing protocol which is called atomic multi-channel updates which is fully backward compatible with Bitcoin and this protocol allows to have a synchronization of engine also with construct long time and it's this protocol allows to have are not only multi-hop payments but opens the door for other applications like crowdfunding netting or the channel rebalancing I'm gonna give you a brief overview of how the protocol works and again the details are in the paper so imagine that we have a really simple scenario where Alice wants to pay to cuddle by by a Bob so Alice wants to pay 8 coins out of tanga from that she has with Bob and then Bob will forward seven coins out of the 30 as he has with the first thing is the first phase is called setup and Alice and Bob split their channels in two sub channels one with eight coins that they will use later in our protocol and two coins which are the remaining currency in the channel that they might use later for other payments or all eventualities second phase they lock these coins up to a time Delta this constant lock time to make sure that if something goes wrong in the protocol they can recover those coins afterwards and third which is the main trick or the main point for atomicity number protocol is that Alice and Bob will pay from this eight from this channels with eight coins to two Bob directly but they will do it from a fresh address a 5v5 which has not been funded yet so because this account has not been funded it doesn't exist so it cannot be put at this point in the blockchain here I have shown only the case for am Alice and Bob but you can imagine that Bob and Carol will do the symmetric transactions and at this point to achieve atomicity we have multi-input multi-output transaction in the face for call enable where both of them Alice and Bob and Bob and Carol put together coins to fund the channels that he created in the phase 3 so they first create this unfunded channels to pay to respective receiver they jointly fund those those payment channels at the enter because at some moment after the time Delta both the locking coins and the constant enable become valid there is a race condition so we have to create a disabled transaction but disable the face for transaction and R is only one valid that point this is a technical detail more discussion in the paper and with that I would like to conclude this talk by saying that payment channel networks have been deployed in practice and as a mitigation for the scalability issues in crypto currencies however they still present several challenges here today I show you challenges in terms of security with the war home attack privacy so in the religious anonymity does not hold and collateral which opens problems like the griffon attack we are proposing to traffic protocols and mitigate them and also I'll open the door for new functionality like crowdfunding or netting obviously however there has to be more challenges we are looking at them in other groups as well and we require more solutions for example one of those is to have a nice cannibal and interoperable routing mechanism that allow us to find the paths between the sender and the receiver in the first place with that I would like to thank you for your attention I'm glad to answer any question that you might have okay we have time for one question please go ahead just go to the mic so it seems that Alice needs to interact with every single entity along the chain isn't this revealing information about commercial relationships between the parties with lots of money that's in the information you might not want to reveal so if they were doing naively will be right so Alice will reveal herself to each hoping it will help in the path what they use is an onion packet where Alice and information to each of the nodes Alatorre fritz and they get the information but they don't know where the information comes from okay maybe one final quick questions all these improvements that you're discovering the Lightning Network an interaction with lagging network team the developers like maybe some of them could be implemented like yeah so we interacted with Latin labs and they had this proof of concept that I mentioned in my slides where they check that was actually possible to run the protocol in in their kernel ad network I also have conversation with block stream where we have discuss also the H noir based solution and what is the advantages and disadvantages with respect to they see they say so yeah and they're looking into it obviously it always takes time to implement it correctly and put it in practice okay thanks I think this figure again alright and we're moving out to the second talk of the session it's the marvelous universe of I admit ization oriented primitives and Tom er is giving a talk tomorrow thank you so this is a joint work with up their alley elements a son sim and Ahava and Alan chip in yak and before we begin some background about even a half ago I spoke to elements this one from Stockwell who told me how magnificent magnificent the ZK stock wolf system is and how it is the future of cryptocurrencies but he also told me that they have a bottleneck in the form of not being able to find an efficient hash function for what they need to do and I find that to be surprising because you know as a cryptographer you always hear about lightweight this and lightweight that so amongst all this lightweightness that has to be something that would be efficient for them but then Ali told me that they have a slightly different design goals so what they need is a hash function that is a cue that operates on field elements and that minimizes the number of film applications and I then immediately cried out or a yes because AES is the cue it natively operates on elements in GF 2 to D 8 which is a fancy way to say that it works on bytes it is well understood heavily crypt analyzed and widely accepted but as Ellie pointed out it doesn't minimize the number of field multiplications but it is a good starting point though and that is what we did and I think we all know roughly how the AES was right it has a fall by fall state and each one has four operations starting with an S box then shift rows mix columns and an ADD round key and it's interesting to observe that all the multiplications the dead objects that were trying to get rid of a limited to the sbox so if you want to optimize the sbox is well we should begin the sbox itself consists of two operations first we find the multiplicative inverse of the input the multiplicative inverse is the value that when you multiply it to the input they give you one and that requires in 11 multiplications followed by a final fine polynomial that requires seven multiplications so let's crunch the numbers and see the cost 12s box we need eleven plus seven which are 18 multiplications in each round we call the sbox 16 times so we have 288 multiplications per round and then to evaluate one aes-128 primitive we have ten rounds which are twenty eight hundred and eighty multiplications and that's the number we are optimizing with respect to the first observation is that zero zero knowledge systems like the ones we are considering allow for something called non determinism we call it non procedural computation which is a wider umbrella term because it has analogues in MPC so together it's non procedural computation but one back to zero knowledge what we do is a verification of a computation and not the computation itself so for example if we have a pair of values x1 and y1 and we want to verify that y1 is the multiplicative inverse of X 1 the naive way would be to directly raise X 1 to the power 254 in AES in the field of a yes those are the 11 multiplications I mentioned before but we can also just multiply x1 and y1 and see that the result equals 1 that's what it means to be a multiplicative inverse so one of those requires 11 multiplications the other requires one multiplication I'm gonna let you decide which one is more efficient although one multiplication is not enough we also need to ensure that Zillow goes to zero but in total we have two multiplications instead of 11 so crunching the numbers again we had eight twenty eight hundred and eighty multiplications and now the sbox only requires nine multiplications times 16s boxes per round times ten rounds fourteen hundred and forty multiplications per a es evaluation which are fifty percent of the original cost of the AES so we'll doing well in optimizing let's continue with that we're now optimizing the affine polynomial the purpose of this affine polynomial is to ensure that when the cipher text is read is described as a function of the plaintext and the key the algebraic degree of this function is high enough otherwise certain attacks are possible AES uses an affine polynomial that is good for AES but we realized that if we use particular polynomials such that the exponent is always a power of two we could get a more efficient computation of this polynomial such polynomials are called linearized polynomials so if we take a low degree polynomial we would have a low degree linearize polynomial it would have efficient computation but it would be of low degree what we also realized is that the inverse of such polynomial is not linearized now it is low degree but due to non procedural computation the thing that I've mentioned before we can still evaluate it efficiently so what we did is to take two linearized polynomials of degree fo and we composed one of them with the inverse of the other the resulting polynomial is of high degree it's not linearized which means that it can't be officially efficiently computed but it can be efficiently verified using only four multiplications to form each polynomial so again crunching the numbers we have 900 sorry before we had 14 hundred and 40 multiplications pearl aes-128 evaluation now instead of 9 multiplications the sbox is only 6 multiplications in total give giving us 960 multiplications which are 33 percent of the original cost of AES then our next observation is that the cost of multiplication is independent of the field size that is not the case for traditional ciphers right if you work with a larger field you would you will need a larger chip it will consume more RAM in the Amish on your machine but that's not the case here one more the cost of one multiplication is 1 so what if instead of walking with a 4x4 state we walk with a 1 by 1 state now we don't need shift all the next columns anymore because the purpose of these operations is to mix the field elements of the state in if you have only one field element there's nothing to mix and we can afford 1s box play around giving us a cost instead of 960 only 60 multiplications which are 2 percent of the original cost of aes-128 the last thing guy these are very small numbers so we still need to determine the number of rounds and the usual trick for that in symmetric-key design is to try all the attacks you're familiar with see which one reaches the largest number of rounds then add some safety margin and that's your cipher and we applied the security argument of AES to this design and found out that we need about the same number of rounds so the resulting algorithm is called Jarvis and it's exactly the way I described it the input goes into the multiplicative inverse then through a polynomial that is a composition of two linearized low degree polynomials one directly and the other by in the inverse form and then key injection and that's one round of charges and we put it on a print hoping that third parties would to analyze this and unfortunately they did and a few sometime later a paper was published attacking Jarvis using an attack called global basis now this is ironic because I remember speaking to early before we published our list and he asked me specifically but what about global basis attacks and I said no these never walk on symmetric-key primitives well turns out sometimes they do so back to the drawing board we need to some somehow fix this it turns out that there is a minimum number of multiplications that if you go below that your cipher will be vulnerable to governmental bases attacks another thing we realized is that if instead is that if we have a 1x1 state it's easy to evaluate the cipher but getting the output would be inefficient so we need more field elements and having more field elements in your state solves both problems the natural thing to do would be to go back to an M by M state or maybe an M by n state like in rainbow but we also saw that having an M by one state we can get a faster diffusion than AES now we know this is called the shulk structure but we were at a well of that back then since we now also have more than one field element we somehow need to mix them so when MDS is the natural candidate and we understood that composing the two polynomials isn't as efficient as just alternating between them which is what we did and of course special attention to governor bases attacks this time and the result is vision our algorithm for binary fields and that's how it works it has a vector of state elements each element goes into the multiplicative inverse then the inverse of a fine linearized port sorry low degree linearized polynomial is evaluated everything is mixed with an MDS key injection and then in the second step in the and again multiplicative inverse now the polynomial is evaluated directly MDS and key injection while we were walking on vision we were told that actually some market demand for the same kind of algorithm operating on prime fields so we took the same approach but now linearized low degree polynomials are not available because of the properties of the field and we understood that we have to get the algebraic degree via the nonlinear operation again we're using non procedural computation in raising to the power alpha and in most cases alpha should be free but the high algebraic degree we get from the functional inverse so the cubic root of the value and that's rescue I will design from for prime field well it has the same kind of state one vector of field elements and we start by getting the inverse of the power map so the cubic root if alpha equals 3 then everything is mixed with an MDS key injection raising to the power alpha MDS again and another key injection and this is rescue these two algorithms are secure and very efficient they're very efficient in zero knowledge in MPC and they have an interesting property so M is flexible how many field elements you will have in the state the larger M the less rounds you need so the number of multiplication remain remains roughly the same no matter how wide your field is that's very efficient for fully homomorphic encryption which requires the circuit be shallow and I I was about to invite you to do crypt analysis on this that I also got the permission to break some interesting news sometimes soon it will be announced so starkwell Ellis company hired committee of experts to evaluate the security of all algorithms in this domain including the ones that Dimitri presented yesterday in this committee I was asked to be very specific on this will recommend well we'll say that vision and rescue are the most secure algorithms in this domain when used as hash functions with fields of 128 bit in sponge mode which is the setting that the case talcs walk in so that's something I'm happy to tell you today some housekeeping announcement in the on Monday Roberto Avanza opened the parenthesis and forgot to close it and I feel it in my body so here's the closing parenthesis and this is the team that walked on this paper which you can find on a print thank you very much all right so we have time for one question so there's a lot of efforts also to do similar work in the setting of secure multi-party computation so maybe you would like to draw some connections or point to differences similarities so in our paper we also evaluate these ciphers in a setting of multi-party computation the main idea or the biggest problem is are the high algebraic degree operations so the inverse cubic would but multi-party computation offers masking right you can shift things to the offline phase and then have a fixed cost online phase if you do that this cycles are extremely secure extremely efficient also for multi-party computation I'm also encouraging you to use them in your multi-party computation applications all right ok so let's thank summer all right ok now that will be the last talk of this session detecting money laundering activities via NBC network flow analysis and the talk will be given by Adam target self well we just disappear it's coming back I think ok all right please go ahead since if the last talk I would like to take this opportunity first of all to thank all the organizers for this stimulating event this week so thanks so this talk is about money laundering and I hope that this slide will convince you that money laundering is just much more sophisticated than knowing what what soap you should use to do it so how did it all start it started with this global what's called global laundromat so that that was a money laundering scheme one of the biggest known currently that occurred between 2011 and 2014 and here we are talking about more than 40 billion dollars that were laundered from about 20 different banks in Russia to various accounts as you can see here there are about 5,000 companies involved in the whole in the whole scheme there are more than 700 banks in 96 different countries so that's a really global global money laundering scheme and the idea is that money has flown from across these accounts until they essentially became untraceable so if you look at the statistics then you would see that a huge part of that that amount went to the UK and that was concerning about the financial authorities in the UK and as you can see recently the financial conduct authority of FCA organised a tech sprint 2019 tech sprint a lot of the people who I see in this audience participated at that explain that was in the summer in July and the goal was to design to use privacy enhancing technologies to detect these global money laundering schemes so as you can see in front the company we work for participated together with Goldman Sachs and Standard Chartered in a team called secret computers and won the public's vote our work for that so today I would like to tell you a little bit about the cryptographic solution behind that scheme so as an overview our goal will be to solve this simple problem so they take money laundering groups across globally across multiple banks and before we do that let's let's try to see why this is relevant so clearly in this global laundromat a lot of these banks that were involved were imposed huge fines for not being able to detect these activities not that they didn't want to detect the activities the problem was that it was impossible to detect the activities because they didn't have access to the transaction data coming from the different banks from the other banks in the scheme so they had a very local view localized view of the transaction after the transaction going on to this scheme but they didn't have a global view of that so the other problem was the transaction monitoring was still a highly manual process so it needs automation even on the level of an individual Bank and then most importantly and most relevant for us is cryptographers is the collaboration across different banks so collaboration is hurt due to that data privacy so in this in this talk I would like to just take some time to review what exists in the plain text literature in the plain text algorithms for statistical versus graph based approaches to detecting money laundering schemes and then tell you a little bit about how you could use secure multi-party computation to detect certain relevant money laundering sub structures in graphs of transaction network and at the end I would say a word about how you can make this algorithm practical so if you want to look at the overview of the literature so you have you have different statistical models that could could be used to detect money laundering activities starting from Bayesian models from temporal sequence matching so going into decision trees so ID 3 and C 4 5 those were the early decision tree algorithms and those who are applied with some Chinese data data in China CBR C is the equivalent of FCA in China and these algorithms work relatively well except that they well they worked well as a first attempt but the false positive rates were still quite high so then people started using more sophisticated machine learning techniques like support vector machines so they tested it on certain banking data coming transaction data coming from Chinese banks as well here you can see some data 1.2 million records 5,000 accounts over seven months and that obviously improved a little bit the existing decision tree models and the DM people also used neural network approaches so what I am going to talk about today is a non machine learning approach to that problem so that you can see that we heard a lot of talks about 10 PC and machine learning so here we want to focus on non machine learning approaches and these approaches are actually graph based approaches so what you do typically is as a bank you analyze your transaction data locally you detect some suspicious activity and then you constrict the graph out of this activity and then your goal is to analyze this graph for many laundering groups that's what we are going to do except that we will consider the privacy concerns so let's take a look at a typical banking data that's a very simplified view of a banking data so we have we have a bank and the bank sees certain transactions so this Bank here is called Z Z and you would see three transactions transaction 15 and transaction 2314 if you look at those what's common is that the source ID of the account of the second transaction matches the destination idea of the first transaction moreover what you see is that the amounts are large and the first amount is slightly more than the second amount also if you look at the timestamp you see that the first amount the first transaction was done a little bit before a day before the second transaction so that's suspicious and that the bank Z Z could detect essentially out of its local view of the data so what the bank does is the bank defines certain rule and that's really how banks work so we had an interaction with banks at this this competition and they explained to us exactly how they work so you are seeing that now we have this is kind of pair of matching transactions going from YY to Z Z these are different banks and then money flowing out of this account in Z Z into another after Bank so this Bank sees this kind of lag structure so we call this a leg stretch and there all these rules that are defining what it means for the transaction to be alike so a bank creates all these leg structures and then the idea is what do you do with them obviously this information is not sufficient so you can stack the graph and our graph will be the following so that the vertices will be of the graph will be accounts and then the edges are going to come from leg structures or suspicious transactions so we are going to increase the weight of an edge if so if first of all if a vertex is not marked and we see a leg with the vertex then we add we mark that that that vertex and we add an edge and anytime we see that same transaction from the two accounts we increase by one the edge so basically if you have two accounts among which you have many fraudulent transactions then that edge will have a higher weight so we defined the weight of an edge that's simple and then what's the goal so the goal is that we would like to detect certain structures that are related to money laundering so there are two simple cases that you can see here one of them is money flowing from a source to a destination account with lots of intermediaries in the middle and then you have a second case where money flows from a source to a destination but through various intermediaries in a linear fashion so in the first case you are separating the fans from the source account and they flow in parallel to several of these accounts the question is can you identify these strictures so we have case one and case two and of course there is a mathematical way to quantify how you could you could measure these structures obviously a single bank is not going to be able to see these structures so that's the important point now let's take a really simple example so we take a source and destination in the two ends and then we have two banks a rep and the Green Bank so what you do is you you have money that gets split between the red and the green and then that get that flows into the destination account double so what you observe here is that if these are intermediary nodes in a money laundering scheme first of all the traffic to these nodes is very similar and then the traffic is large because you are talking about large amounts of money so if you if you draw the adjacency matrix matrices of these graphs then the red bank is going to see a matrix that looks like this here so I guess nothing can be detected from that that particular matrix now similarly the Green Bank is going to see that matrix now what do you observe if you put together this information so you put together the information then you are seeing that the two rows corresponding to y and z are correlated are highly correlated so they're similar in this case but in general they they will give a very high correlation so is it possible that we detect this correlation without actually sharing the transactions of the banks and the answer is yes so we can we can use MPC here the basic idea is that we take these to grab views local grab views and then we seek retreat of them across the two two banks and then we let these banks compute now what what is it that the banks have to compute in order to detect these activities so here is what they have two types of scores that you could compute and the first score is called a balanced score so it really is very simple so note is going to be an intermediary node first of all if it has higher than usual traffic treat and second of all if the number of increment result transactions is is similar to the number of outgoing transactions so this score that you see there it's a complicated mathematical formula but what it tells you is that it has two terms one of them detecting the first the first intuition and then the second one is detecting that the intuition so that the top level is a harmonic mean which becomes higher if you have almost equal incoming and outgoing transactions and down there you are measuring the size of the sum of the way it's going through these accounts so that's that's one possibility and then the other one which is even more interesting for our application is something called structural similarity so here what you do is you are going to essentially quantify the by by using similar if your correlation between two vertices so you're going to quantify what it means that the incoming transactions are equal to the outgoing transactions so that's exactly what you do by again considering something similar to a geometric mean it might be geometrically so here's what you do the plaintext is version now of the algorithm is very simple so you compute these similarities on the graph and then you test whether some of the some of these correlations are higher than a threshold so that's what people would do in plain text and then you determine sets of dense pairs and then after a standard clustering algorithm you are detecting you are detecting ML groups so of course this requires a lot of operations as you can see inversions and square roots that makes it that makes the computation highly inefficient so what you do is we propose an NPC version that only uses a certain small set of operations so what we do is we compute the numerators and the denominators and then we test essentially inequalities without inverting and without square roots so we are going to square and and not not not having to compute square roots and to essentially do the same so that's a that's a that's a very similar application and so now we are going to need these three operations additions multiplications and what we call oblivious comparisons so we are not allowed to expose these these correlations yet so that's why we need to play these comparisons so how do we do that we do this with some app in first technology that we developed so it's a secret computing multi-party computation algorithm it works with real numbers that represent it as integers modulo a large power of two it's suitable for arithmetic circuits and it's not very suitable for inversions and I would say advanced linear algebra so the security model is what we call the full tree shot with offline and online face and trusted dealer or honest but curious dealer and it can potentially be improved later on with verifiability into using techniques like oblivious transfer or cutting choose techniques in multi-party computation so that's on a very high level what's important is that you have this oblivious comparison algorithm and that what as an input you take two numbers that are L bit numbers and that are Secretariat and as an output you get the secret sheer predicate after of the comparison so there are two algorithms there is a naive and there is a divide and conquer algorithm and the naive has the advantage that sometimes it's faster if he has less communication but the divide-and-conquer has less rounds of communication so for certain ranges the divide and conquer is the better algorithm that we use so I won't say much more about this I'd rather give you some real data to see what kind of sizes we are talking about so in the tech spring competition we get we got data coming out of three thousand three hundred and thirty thousand accounts and about 1.5 billion transactions so that's a giant graph as you can imagine so you can't handle it you have to do something else so then then about 300k of these transactions were allotted and then some of them were reported as suspicious activity report and then some of these accounts have just just blacklisted by the banks at the end so here's the idea of how to make it practical so of course we can't talk about adjacency matrices that are 300,000 by 300,000 so what you do is you use a data structure similar to a bloom filter you're going to choose several hash functions that are going to hedge the number of accounts into a very much smaller set so let's say you would catch it into a set of size a thousand and then you are going to basically compress your graph using these hash functions and construct the traps on the output of these hash functions so then then you essentially test test similarity for each of these hash functions independently and using that you could you could conclude that that two accounts are going to be similar so that of course case a probabilities for false positives which we have to calculate precisely that's an open ongoing project but in practice that works quite quite well so some estimates and the complexities so the beaver multiplications here that that are used for the multiplications in the computer complication of the similarities you can see a very large dimension so we can see there are large vectors and and correlations that are computed so this is all this all can be made practical that's the that's the final point oblivious comparisons we can make about 1 million comparisons of ltb are 50 bit numbers in less than two seconds and about the hundred million comparisons of the same size for less than eight minutes so you could you could definitely do these computations in in reasonable time and now in summary what we got so just to summarize so we have provided a graph based approach to allow interbank collaboration on analyzing transaction data so we have kept MPC from the algorithm to compute structural similarities oblivious comparisons to detect dense pairs of account and using standard clustering algorithms to detect the structures that we are interested in so as open questions of course the one of the main mathematical open questions here is understanding this data structure that's behind so understanding the probabilities of false positives which even in the case of bloom filters is a non-trivial problem them also enable verifiability via more sophisticated cryptographic techniques to allow different security models so I would like to thank you here also this is the team to work on that and inter-site alright so we do have time for questions for Demeter so please walk to the mic hello thank you given that banks such as HSBC were involved in money laundering themselves to what extent are your techniques resilient against the bank itself conducting money laundering operations so if a bank itself conducts a money-laundering that's a different question so the the the Assumption here in the text print competition was that banks get fined for not being able to detect properly money laundering activities in general if a bank is malicious you obviously can't use it in the graph analysis so we have to use banks that are kind of motivated by the same goal which is it's game theoretic win-win situations so the bank's want to collaborate they don't want to share the transaction data they want to be able to detect vml activities a new trust goldman sachs so well goldman sachs were interested in not being able to detect activities because they would get so if you look at this global scheme just as a matter of fact they were banks in in latvia and moldova that were actually revoked licenses so these banks no longer existed after this it's a like multi-billion dollar scheme understood thank you I wanted to ask you about the numbers you had how many parties were involved in the computation where were they located how what was how did you benchmark how did you get the numbers you have in the slides so how did they get the numbers of the number of banks that are involved in the inter computations the timings that means you have on this line all the payments in the slides so you mean here okay so I should have said that yeah I should have said that that that's for two in three parties that's a small number of practice in this complexity analysis coming before you have the number of practice appearing in the complexity so so and that that can obviously be improved in the future with that with better techniques but change the number of parties okay with those comparisons think so so it depends what about it hey thanks for the talk I wonder if you have to do some sort of fuzzy matching when it comes to for example name matching for example when it comes to match names or addresses or those inputs that are you know fuzzy in nature so I see so here here we are we have not looked at that I think there are some people who were discussing that during the competition we ourselves we have not looked our assumption was all weeks that essentially the account she has a very specific identifier and and then you you use that I think I think they are there is some research that might be even going on now on that I'm not sure exactly about who is doing that but I have heard about fuzzy matching can money laundering because one of the challenges were going to determine if a person is on the sanction list is actually to do it in a fuzzy matching exactly exactly I think I have seen papers on that so I have seen papers on that in the literature thanks.thanks to talk do you have any insights on what happens as money launderers sort of evolved to avoid the detection techniques so for example you have that diamond just flow and of course the obvious thing is okay route it through to intermediate banks yes yes before rather rather than to so like what what changes that's an excellent question so so we are motivated by by by that so so here this is the very basic step that you detect so you're not detecting call possible structures of money laundering with that yeah so you're at least you're having some measures for what what it means for an out to be a intermediary note but in fact currently I'm even involved in some some projects that are that are non MPC related that are using other techniques other secret sharing techniques to detect such such structures that are more complicated that you have two cops instead of just the flow analysis you're talking about handle clusters of nodes that act like one node that is definitely doing money laundering but individually none of the nodes look suspicious individually none of the nodes look suspicious and individually these nodes their accounts at a particular bank so from the point of view of the bank that doesn't look suspicious so your scarified I mean like suppose you have two nodes that are collectively operating like a middleman doing laundering yes but the individual transactions don't follow the leg structure that you're talking about only when you look at them combined to the leg structures appear can you handle that in this current with this technique you will be able to handle that you you may have to modify a bit your local rules that you apply at each Bank as you see this this kind of algorithm is very specific to the local rules that are applied at each Bank we learn these rules just by talking to banks so essentially we learned about what they are using nowadays and that doesn't mean that they cannot in cancer like improve these books thanks for welcome thanks for Otago is pre interesting I'm wondering you sort of seem to have very ad hoc clustering and there they have a complicated mathematical structure for it for so you have to do a lot of operations yes I'm wondering if you did a spectral method then you just need to compute the eigenvectors and eigenvalues of this matrix and that you can that the main method is multiplication and the banks can even keep the keeps matrix secret and just have shares of the vector and and the main thing is linear yes so that that is that is a very good question we have not tried to apply spectral methods so typically spectral methods they're useful for clustering algorithms so we have not been a we have not tried to that doesn't mean that you can't I think you you you probably can can be able to use even MPC to do to deduce some information so currently our algorithms were just based on these structural similarities but spectral metals are definitely helpful so that's a that's a that's an area to exploit in the future Thanks okay so let's sing ginger again all right and this brings us to the end of the technical program so I'd like us to give a big round of applause to all the speakers and the 36 sponsors that with without their contribution which have been impossible like to run real world Krypton and now the final point I would like a roaring round of applause for Tamil written part the general chair this year thanks very much it's actually quite a pleasure to help organizes events where my favorite events for the year just a few announcements and I'll let you go to happy hours and their Friday afternoon activities so next year real-world crypto will be in Amsterdam so Amsterdam 2021 the year after that we'll be moving to Tokyo for real Road crypto 2022 and after that we're soliciting proposals for locations so if you have a location in mind that you'd like RWC to come to then you should reach out to one of the steering committee members and get some info about how to proceed we sent out a survey to the attendees it's very short it shouldn't take much time but it's really valuable to get feedback from all of you about what we're doing well obviously but also more valuable to get some feedback on what we're not doing well and we really take this to heart to try to make sure that this is serving all of you super well another way to get involved in community you are all now members of the IAC are the International Association of Cryptologic research and that means you'll be eligible to vote in future elections for the leadership for our nonprofit organization that runs cryptographic you know academic cryptographic research conferences and other activities so be on the lookout for for that finally just a few more thanks also thanking the sponsors that we have been putting up here really helps make sure that we can run this and keep it cheap and accessible for people to attend so thank you to them and then particularly had a special recognition that a person one of our 2019 Levchin Award winners Eric where's Cora personally made a donation to support particularly students for women and other underrepresented minorities be able to attend so I think we should give Erika a big round of applause and then finally I think we should thank especially the specifically the Columbia University data science Institute who helped facilitate and host us here at a beautiful venue at Columbia University the student volunteers who sat out in the very cold lobby to make sure that there are people available to answer questions and deal with any issues that came up and then the Columbia event staff who I think did a phenomenal job of running a very large conference and making sure things ran smoothly so let's give all of them a big round of applause and that's it so have safe travels and we'll see you in Amsterdam in 2021 thank you