IRIS: A Robust Information System Against Insider DoS-Attacks

In this work we present the first scalable distributed information system,i.e., a system with low storage overhead, that is provably robust againstDenial-of-Service (DoS) attacks by a current insider. We allow acurrent insider to have complete knowledge about the information systemand to have the power to block any \epsilon-fraction of its serversby a DoS-attack, where \epsilon can be chosen up to a constant. The taskof the system is to serve any collection of lookup requests with at most oneper non-blocked server in an efficient way despite this attack. Previously,scalable solutions were only known for DoS-attacks of past insiders, where apast insider only has complete knowledge about some past time pointt_0 of the information system. Scheideler et al. (DISC 2007, SPAA 2009) showedthat in this case it is possible to design an information system so that anyinformation that was inserted or last updated after t_0 is safe against a DoS-attack. But their constructions would not work at all for a current insider. The key idea behindour IRIS system is to make extensive use of coding. More precisely, we presenttwo alternative distributed coding strategies with an at most logarithmicstorage overhead that can handle up to a constant fraction of blocked servers.