Computationele integriteit voor het uitvoeren van SPARQL queries

Serge Morel
Persbericht

Een stap voorwaarts in de re-decentralisatie van data en bescherming van uw privacy

Introductie 

Digitale platformen zoals Facebook of Google zijn onmisbaar in deze digitale wereld. Helaas komen ze ook met privacy problemen. Zo heeft u misschien al gehoord hoe ze uw telefoon afluisteren en deze gesprekken verkopen aan derden om zo winst te maken. In deze scriptie onderzoek ik hoe we deze prachtige platformen kunnen bouwen zónder gebruik te maken van deze datamanipulatie. 

Schets van het probleem 

“Data is de nieuwe olie”, een citaat die u wellicht niet onbekend in de oren klinkt. U vraagt zich misschien af waarom digitale giganten zoals Facebook en Google hun service gratis aanbieden. Infrastructuur die miljarden gebruikers ondersteund, is zeker geen kleine kost. In ruil voor uw data, krijg je toegang tot deze platformen. Op eerste zicht lijkt dit oké, want door deze informatie kunnen ze prachtige snufjes technologie aanbieden. Denk maar aan simpelweg foto’s en video’s doorsturen naar je vrienden op WhatsApp, 30 jaar geleden nog ondenkbaar. 

Helaas is het niet allemaal zonder gevolgen. Zodra u zich inschrijft voor deze services, gaat u akkoord om al uw data te delen. Bedrijven zoals Facebook en Google verkopen deze data aan derden, zodat zij de juiste mensen kunnen aanspreken voor een product te verkopen. Denk maar aan de reclame voor schoenen op Facebook, de dag na dat je even door Zalando scrolde. Uw data is waar zij winst van maken. 

Kunnen we ook een wereld inbeelden waar deze technologische snufjes aanwezig zijn, maar waar we niet onze data hoeven moeten overgeven als “instapkost”? 

Op zoek naar de oplossing 

Tim Berners-Lee, de man achter het internet houdt zich bezig met een nieuw model te ontwikkelen waarin deze digitale giganten geen macht hebben. In de staat zoals het nu is, bezit Facebook over al uw data en u heeft hier geen controle over. In dit nieuwe model, bent U in volledige controle over uw data. 

Data is niet meer voor handen van één datacenter, maar verspreid over de wereld, apart voor elk individu, ook wel re-decentralisatie van het wereldwijde web genoemd. Dit klinkt allemaal héél mooi, maar komt niet zonder zijn technologische uitdagingen. Weten wie je bevriend hebt of wie je nieuwste foto liket wordt dan een kwestie van bronnen te raadplegen die fysiek duizenden kilometers uit elkaar kunnen liggen. Deze berekeningen zijn te ingewikkeld om op een hedendaagse smartphone of computer te doen. Hiervoor is een computer met véél rekencapaciteit nodig, het soort dat alleen grote datacentra hebben om miljoenen gebruikers te voorzien van functionaliteit. 

Helaas, zoals reeds vermeld, is er een groot probleem met informatie door te spelen aan deze datacentra, namelijk de privacy van de deze informatie. Als er een manier was om deze “warenhuizen” vol met computers toch deze zware taken te laten uitvoeren voor ons, zonder dat ze misbruik kunnen maken van onze data, hebben we een oplossing gevonden. 

Verificatie van correcte uitvoering 

In mijn masterproef ging ik op zoek naar een manier om het nieuwe, gedecentraliseerde model van Tim Berners-Lee veiliger te maken. Met veiliger wordt bedoeld, zekerheid geven dat een derde partij onze data niet misbruikt voor eigen winst. De derde partij die ons deze data bezorgt, mag dus niet informatie toevoegen of verwijderen dat hem beter uitkomt, bijvoorbeeld voorliegen dat een vriend geïnteresseerd is in een zeker product. 

Computationele verificatie is een relatief nieuwe academische technologie. Het is een technologie die in staat is om aan te tonen dat een computerprogramma volledig correct is uitgevoerd. Met andere woorden, als een derde partij informatie toevoegt of verwijdert dan wordt dit opgemerkt. Dit is een belangrijke evolutie in de informatietechnologie, zeker met de recente opmars van de “Cloud”. Er is momenteel geen garantie dat “Cloud” services zoals Google Drive of iCloud uw foto’s correct bewaren of deze niet analyseren op hun inhoud. Met deze technologie, kan deze zekerheid ingebouwd worden. 

Hoewel deze technologie nog lang niet ver genoeg staat om op die schaal te functioneren, staat het wel ver genoeg om een oplossing te bieden in het nieuwe internetmodel van Tim Berners-Lee. Met computationele verificatie werd in deze masterproef een staaltje softwareontwikkeld die kan uitgevoerd worden door eender wie. Achterna kan, opnieuw eender wie, verifiëren dat de software volledig correct is uitgevoerd. Met dit idee, is het probleem van zware berekeningen op een hedendaagse smartphone niet langer een bezwaarlijk. Het volstaat de berekeningen te laten uitvoeren door een rekenkrachtige derde partij. 

Toepassingen 

Hoewel de technologie momenteel academisch is en verder onderzoek centraal staat in de praktische haalbaarheid ervan, toch zijn er al volledig praktische toepassingen te bedenken. 

Eén hiervan is gezondheidszorg in afgelegen gebieden zoals bijvoorbeeld in Afrika. Westerse verzorging zoals wij ze kennen is hier vaak niet beschikbaar of ver weg. Het is dus belangrijk dat de eerste zorg die wordt toegepast door lokale dokters en verplegers, volledig up-to-date is met de laatste wetenschap. Er zijn al een aantal bedrijven die hier proberen een oplossing voor te bieden, maar allemaal onafhankelijk en voornamelijk overheidsgebonden. Met een volledig centraal netwerk volgens het hernieuwde model van Tim Berners-Lee kan hier een centrale oplossing voor geboden worden. Het laatste probleem dat overblijft is de gelimiteerde connectiviteit en infrastructuur aanwezig in deze omgeving. Hier biedt de oplossing van deze masterproef een oplossing: door de informatie te laten ophalen door derde partijen is de kost voor de lokale infrastructuur veel lager. De veiligheid en betrouwbaarheid kan dan bekrachtigd worden met Blockchain-technologie. 

Conclusie 

Deze scriptie beschreef kort het probleem en de bijbehorende oplossing van mijn masterproef. Het steunt op een relatief nieuwe technologie die een enorm potentieel heeft om de “Artificiële intelligentie” van 2020 te worden. 

De resultaten waren reeds veelbelovend, de oplossing is namelijk tot 7x sneller dan andere technieken en geeft bovendien volledig vertrouwen in de resultaten, wat eerder niet beschikbaar was. Het is een stap voorwaarts naar de re-decentralisatie van het wereldwijde web en een stap dichter naar de re-introductie van privacy op het internet. 

Bibliografie

  1. [1]  L. Shanhong. (2016) Global big data industry market size 2011-2026. https://www.statista.com/statistics/254266/global-big-data-market-forec….

  2. [2]  R. Verborgh, M. Vander Sande, O. Hartig, J. Van Herwegen, L. De Vocht, B. De Meester, G. Haesendonck, and P. Colpaert, “Triple Pattern Fragments: A low-cost knowledge graph interface for the Web,” Journal of Web Semantics, vol. 37-38, pp. 184–206, 2016.

  3. [3]  T. Berners-Lee. (2018) One Small Step for the Web. . . . https://inrupt.com/blog/one-small-step-for-the-web.

  4. [4]  R. Verborgh. (2019) Getting my personal data out of Facebook. https://ruben.verborgh.org/facebook/.

  5. [5]  C. Buil-Aranda, A. Hogan, J. Umbrich, and P.-Y. Vandenbussche, “SPARQL Web-Querying Infrastructure: Ready for Action?” in The Semantic Web – ISWC 2013. Springer, Berlin, Heidelberg, oct 2013, pp. 277–293.

  6. [6]  R. Verborgh, M. Vander, S. P. Colpaert, S. Coppens, E. Mannens, and R. Van De Walle, “Web-Scale Querying through Linked Data Fragments,” 2014.

  7. [7]  T. Berners-Lee. (2009) Linked Data - Design Issues. https://www.w3.org/DesignIssues/LinkedData.html.

  8. [8]  A. Seaborne and E. Prud’hommeaux, SPARQL Query Language for RDF, http://www.w3.org/TR/2008/REC-rdf-sparql-query-20080115/, W3C Std., jan 2008.

  9. [9]  WorldWideWebSize. (2019) The size of the World Wide Web (The Internet). https://www.worldwidewebsize.com/.

  10. [10]  T. Berners-Lee, J. Hendler, and O. Lassila, “The Semantic Web,” Scientific American, vol. 284, no. 5, pp. 34–43, may 2001.

69

Bibliography 70

  1. [11]  E. Miller, “An Introduction to the Resource Description Framework,” Bulletin of the American Society for Information Science and Technology, vol. 25, no. 1, pp. 15–19, jan 2005.

  2. [12]  Amazon. (2019) Object Storage Classes – Amazon S3. https://aws.amazon.com/s3/storage-classes/.

  3. [13]  G. Graefe and Goetz, “Query evaluation techniques for large databases,” ACM Computing Surveys, vol. 25, no. 2, pp. 73–169, jun 1993.

  4. [14]  R. Verborgh, O. Hartig, B. De Meester, G. Haesendonck, L. De Vocht, M. Vander Sande, R. Cyganiak, P. Colpaert, E. Mannens, and R. Van de Walle, “Querying Datasets on the Web with High Availability,” in The Semantic Web – ISWC 2014. Springer, Cham, oct 2014, pp. 180–196.

  5. [15]  S. Wilkinson, “MetaDisk A Blockchain-Based Decentralized File Storage Application,” 2014.

  6. [16]  Protocol Labs, “Filecoin: A Decentralized Storage Network,” 2017.

  7. [17]  Prover.io, “Authenticity Verification of User Generated Video Files prover.io,” 2018.

  8. [18]  D. Bhowmik and T. Feng, “The multimedia blockchain: A distributed and tamper-proof media transaction framework,” in 2017 22nd International Conference on Digital Signal Processing (DSP). IEEE, aug 2017, pp. 1–5.

  9. [19]  S. Haber and W. S. Stornetta, “How to Time-Stamp a Digital Document,” in Advances in Cryptology-CRYPT0’ 90. Berlin, Heidelberg: Springer Berlin Heidelberg, 1990, pp. 437–455.

  10. [20]  S. Nakamoto, “Bitcoin: A Peer-to-Peer Electronic Cash System,” 2008.

  11. [21]  R. C. Merkle, “A Certified Digital Signature,” in Advances in Cryptology — CRYPTO’ 89

    Proceedings. New York, NY: Springer New York, 1989, pp. 218–238.

  12. [22]  J.-J. Quisquater, M. Quisquater, M. Quisquater, M. Quisquater, L. Guillou, M. A. Guillou, G. Guillou, A. Guillou, G. Guillou, and S. Guillou, “How to Explain Zero-Knowledge Protocols to Your Children,” in Advances in Cryptology — CRYPTO’ 89 Proceedings. Springer New York, 1989, pp. 628–631.

Bibliography 71

  1. [23]  U. Feige, A. Fiat, and A. Shamir, “Zero-knowledge proofs of identity,” Journal of

    Cryptology, vol. 1, no. 2, pp. 77–94, jun 1988.

  2. [24]  S. Goldwasser, S. Micali, and C. Rackoff, “The Knowledge Complexity of Interactive

    Proof Systems,” SIAM Journal on Computing, vol. 18, no. 1, pp. 186–208, feb 1989.

  3. [25]  A. Fiat and A. Shamir, “How To Prove Yourself: Practical Solutions to Identification and Signature Problems,” in Advances in Cryptology — CRYPTO’ 86. Springer Berlin Heidelberg, 1986, pp. 186–194.

  4. [26]  N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer, “From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again,” in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference on - ITCS ’12. ACM Press, 2012, pp. 326–349.

  5. [27]  E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev, “Scalable, transparent, and post-quantum secure computational integrity,” 2018.

  6. [28]  G. Di Crescenzo and H. Lipmaa, “Succinct NP Proofs from an Extractability Assumption,” in Logic and Theory of Algorithms. Springer, Berlin, Heidelberg, 2008, pp. 175–185.

  7. [29]  S. Arora and S. Safra, “Probabilistic checking of proofs: a new characterization of NP,” Journal of the ACM, vol. 45, no. 1, pp. 70–122, jan 1998.

  8. [30]  J. Groth, “Short Pairing-Based Non-interactive Zero-Knowledge Arguments,” in Advances in Cryptology - ASIACRYPT 2010. Springer, Berlin, Heidelberg, 2010, pp. 321–340.

  9. [31]  M. Conti, E. Sandeep Kumar, C. Lal, and S. Ruj, “A Survey on Security and Privacy Issues of Bitcoin,” IEEE Communications Surveys & Tutorials, vol. 20, no. 4, pp. 3416–3452, 2018.

  10. [32]  J. Eberhardt and S. Tai, “ZoKrates - Scalable Privacy-Preserving Off-Chain Computations,” in 2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData). IEEE, jul 2018, pp. 1084–1091.

  11. [33]  I. Meckler and E. Shapiro, “Coda: Decentralized cryptocurrency at scale,” 2018.

Bibliography 72

  1. [34]  B. Bu ̈nz, J. Bootle, D. Boneh, A. Poelstra, P. W. ¶3, and G. Maxwell, “Bulletproofs:

    Efficient Range Proofs for Confidential Transactions,” 2017.

  2. [35]  E. Ben-Sasson, I. Bentov, A. Chiesa, A. Gabizon, D. Genkin, M. Hamilis, E. Pergament, M. Riabzev, M. Silberstein, E. Tromer, and M. Virza, “Computational Integrity with a Public Random String from Quasi-Linear PCPs,” in Advances in Cryptology – EUROCRYPT 2017. Springer, Cham, 2017, pp. 551–579.

  3. [36]  S. D. Warren and L. D. Brandeis, “Right to Privacy,” Harvard Law Review, vol. 4, 1890.

  4. [37]  P. C. K. Hung and V. S. Y. Cheng, Privacy. Springer US, 2009, pp. 2136–2137.

  5. [38]  L. Sweeney, “k-Anonymity: A model for protecting privacy,” International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10, no. 05, pp. 557–570, oct 2002.

  6. [39]  C. Dwork, “Differential Privacy,” in Encyclopedia of Cryptography and Security. Springer US, 2011, pp. 338–340.

  7. [40]  N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer, “From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again,” in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ser. ITCS ’12. ACM, 2012, pp. 326–349.

  8. [41]  B. Parno, J. Howell, C. Gentry, and M. Raykova, “Pinocchio: Nearly practical verifiable computation,” Proceedings - IEEE Symposium on Security and Privacy, pp. 238–252, 2013.

  9. [42]  V. Buterin. (2016) Quadratic Arithmetic Programs: from Zero to Hero - Vitalik Buterin - Medium. https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from- zero-to-hero-f6d558cea649.

  10. [43]  A. Gabizon. (2017) Explaining SNARKs Part I: Homomorphic Hidings - Electric Coin Company. https://electriccoin.co/blog/snark-explain/.

  11. [44]  R. Tamassia, “Authenticated Data Structures,” in Algorithms - ESA 2003. Springer, Berlin, Heidelberg, 2003, pp. 2–5.

Bibliography 73

  1. [45]  Y. Zhang, J. Katz, and C. Papamanthou, “Integridb: Verifiable sql for outsourced databases,” in Proceedings of the 22Nd ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’15. ACM, 2015, pp. 1480–1491.

  2. [46]  Y. Zhang, D. Genkin, J. Katz, D. Papadopoulos, and C. Papamanthou, “vSQL: Verifying Arbitrary SQL Queries over Dynamic Outsourced Databases,” in 2017 IEEE Symposium on Security and Privacy (SP). IEEE, may 2017, pp. 863–880.

  3. [47]  G. Cormode, M. Mitzenmacher, and J. Thaler, “Practical verified computation with streaming interactive proofs,” in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ser. ITCS ’12. ACM, 2012, pp. 90–112.

  4. [48]  Q. Zheng, S. Xu, and G. Ateniese, “Efficient query integrity for outsourced dynamic databases,” in Proceedings of the 2012 ACM Workshop on Cloud computing security workshop - CCSW ’12. New York, New York, USA: ACM Press, 2012, p. 71.

  5. [49]  S. Bajaj and R. Sion, “CorrectDB: SQL Engine with Practical Query Authentication,” 2013.

  6. [50]  NYU and UT Austin. (2017) Pepper: toward practical verifiable computation. https://www.pepper-project.org/.

  7. [51]  B. Braun, A. J. Feldman, Z. Ren, S. Setty, A. J. Blumberg, and M. Walfish, “Verifying computations with state,” in Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, ser. SOSP ’13. ACM, 2013, pp. 341–357.

  8. [52]  R. S. Wahby, S. Setty, Z. Ren, A. J. Blumberg, and M. Walfish, “Efficient RAM and control flow in verifiable outsourced computation,” 2015.

  9. [53]  Q. H. Dang, “Secure Hash Standard,” National Institute of Standards and Technology, Tech. Rep., jul 2015.

  10. [54]  D. Malone and K. O’Dwyer, “Bitcoin Mining and its Energy Footprint,” in 25th IET Irish Signals & Systems Conference 2014 and 2014 China-Ireland International Conference on Information and Communities Technologies (ISSC 2014/CIICT 2014). Institution of Engineering and Technology, 2014, pp. 280–285.

  11. [55]  A. de Vries, “Bitcoin’s Growing Energy Problem,” Joule, vol. 2, no. 5, pp. 801–805, may 2018.

Bibliography 74

  1. [56]  M. Ball, A. Rosen, M. Sabin, and P. Nalini Vasudevan, “Proofs of Useful Work,” 2017.

  2. [57]  R. Taelman, J. Van Herwegen, M. Vander Sande, and R. Verborgh, “Comunica: A Modular SPARQL Query Engine for the Web,” in The Semantic Web – ISWC 2018. Springer, Cham, oct 2018, pp. 239–255.

  3. [58]  E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer, and M. Virza, “SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge,” in Advances in Cryptology – CRYPTO 2013, R. Canetti and J. A. Garay, Eds. Springer Berlin Heidelberg, 2013, pp. 90–108.

  4. [59]  S. Setty, S. Angel, T. Gupta, and J. Lee, “Proving the correct execution of concurrent services in zero-knowledge,” in 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18). USENIX Association, Oct. 2018, pp. 339–356.

Download scriptie
Universiteit of Hogeschool
Universiteit Gent
Master of Science in Computer Science Engineering
Publicatiejaar
2019
Promotor(en)
Prof dr. ir. Ruben Verborgh
Kernwoorden
Share this on: