Eltayesh, Faryed (2017) Verifiable Outsourced Database Model: A Game-Theoretic Approach. Masters thesis, Concordia University.
Preview |
Text (application/pdf)
1MBEltayesh_MASc_S2017.pdf - Accepted Version |
Abstract
In the verifiable database (VDB) model, a computationally weak client (database owner) delegates
his database management to a database service provider on the cloud, which is considered
untrusted third party, while users can query the data and verify the integrity of query results. Since
the process can be computationally costly and has a limited support for sophisticated query types
such as aggregated queries, we propose in this research a framework that helps bridge the gap between
security and practicality. The proposed framework remodels the verifiable database problem
using Stackelberg security game. In the new model, the database owner creates and uploads to
the database service provider the database and its authentication structure (AS). Next, the game is
played between the defender (verifier), who is a trusted party to the database owner and runs scheduled
randomized verifications using Stackelberg mixed strategy, and the database service provider.
The idea is to randomize the verification schedule in an optimized way that grants the optimal payoff
for the verifier while making it extremely hard for the database service provider or any attacker
to figure out which part of the database is being verified next.
We have implemented and compared the proposed model performance with a uniform randomization
model. Simulation results show that the proposed model outperforms the uniform randomization
model. Furthermore, we have evaluated the efficiency of the proposed model against
different cost metrics.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Concordia Institute for Information Systems Engineering |
|---|---|
| Item Type: | Thesis (Masters) |
| Authors: | Eltayesh, Faryed |
| Institution: | Concordia University |
| Degree Name: | M.A. Sc. |
| Program: | Information Systems Security |
| Date: | 10 January 2017 |
| Thesis Supervisor(s): | Bentahar, Jamal and Mizouni, Rabeb |
| ID Code: | 982103 |
| Deposited By: | Fared Mansour Eltayesh |
| Deposited On: | 09 Jun 2017 14:31 |
| Last Modified: | 18 Jan 2018 17:54 |
References:
An, B., Tambe, M., Ordonez, F., Shieh, E. A., & Kiekintveld, C. (2011). Refinement of strongstackelberg equilibria in security games. In Aaai.
Chen, X., Li, J., Huang, X., Ma, J., & Lou, W. (2015). New publicly verifiable databases with
efficient updates. IEEE Transactions on Dependable and Secure Computing, 12(5), 546–
556.
Chen, X., Li, J., Weng, J., Ma, J., & Lou, W. (2014). Verifiable computation over large database
with incremental updates. In European symposium on research in computer security (pp.
148–162).
Devanbu, P., Gertz, M., Martel, C., & Stubblebine, S. G. (2002). Authentic third-party data publication.
In Data and application security (pp. 101–112). Springer.
Goodrich, M. T., Tamassia, R., & Triandopoulos, N. (2008). Super-efficient verification of dynamic
outsourced databases. In Topics in cryptology–ct-rsa 2008 (pp. 407–424). Springer.
Korzhyk, D., Conitzer, V., & Parr, R. (2010). Complexity of computing optimal stackelberg strategies
in security resource allocation games. In Aaai.
Li, F., Hadjieleftheriou, M., Kollios, G., & Reyzin, L. (2006). Dynamic authenticated index structures
for outsourced databases. In Proceedings of the 2006 acm sigmod international conference
on management of data (pp. 121–132).
Ma, D., Deng, R. H., Pang, H., & Zhou, J. (2005). Authenticating query results in data publishing.
In International conference on information and communications security (pp. 376–388).
Merkle, R. C. (1989). A certified digital signature. In Conference on the theory and application of
cryptology (pp. 218–238).
M’hamdi, M. A., & Bentahar, J. (2012). Scheduling reputation maintenance in agent-based communities
using game theory. Journal of Software, 7(7), 1514–1523. Retrieved from http://
dx.doi.org/10.4304/jsw.7.7.1514-1523 doi: 10.4304/jsw.7.7.1514-1523
Mykletun, E., Narasimha, M., & Tsudik, G. (2003). Providing authentication and integrity in
outsourced databases using merkle hash trees. UCI-SCONCE Technical Report.
Mykletun, E., Narasimha, M., & Tsudik, G. (2006). Authentication and integrity in outsourced
databases. ACM Transactions on Storage (TOS), 2(2), 107–138.
Narasimha, M., & Tsudik, G. (2005). Dsac: integrity for outsourced databases with signature aggregation
and chaining. In Proceedings of the 14th acm international conference on information
and knowledge management (pp. 235–236).
Narasimha, M., & Tsudik, G. (2006). Authentication of outsourced databases using signature
aggregation and chaining. In International conference on database systems for advanced
applications (pp. 420–436).
Osborne, M. J., & Rubinstein, A. (1994). A course in game theory. MIT press.
Pang, H., Zhang, J., & Mouratidis, K. (2009). Scalable verification for outsourced dynamic
databases. Proceedings of the VLDB Endowment, 2(1), 802–813.
Papamanthou, C., & Tamassia, R. (2007). Time and space efficient algorithms for two-party authenticated
data structures. In International conference on information and communications
security (pp. 1–15).
Paruchuri, P., Pearce, J. P., Marecki, J., Tambe, M., Ordonez, F., & Kraus, S. (2008a). Efficient
algorithms to solve bayesian stackelberg games for security applications. In Proc. of aaai (pp.
1559–1562).
Paruchuri, P., Pearce, J. P., Marecki, J., Tambe, M., Ordonez, F., & Kraus, S. (2008b). Playing
games for security: an efficient exact algorithm for solving bayesian stackelberg games. In
Proceedings of the 7th international joint conference on autonomous agents and multiagent
systems-volume 2 (pp. 895–902).
Pita, J., Jain, M., Marecki, J., Ord´o˜nez, F., Portway, C., Tambe, M., . . . Kraus, S. (2008). Deployed
armor protection: the application of a game theoretic model for security at the los angeles
international airport. In Proceedings of the 7th international joint conference on autonomousagents and multiagent systems: industrial track (pp. 125–132).
Pointcheval, D., & Stern, J. (2000). Security arguments for digital signatures and blind signatures.
Journal of cryptology, 13(3), 361–396.
Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and
public-key cryptosystems. Communications of the ACM, 21(2), 120–126.
Rogaway, P., & Shrimpton, T. (2004). Cryptographic hash-function basics: Definitions, implications,
and separations for preimage resistance, second-preimage resistance, and collision
resistance. In International workshop on fast software encryption (pp. 371–388).
Thompson, B., Haber, S., Horne, W. G., Sander, T., & Yao, D. (2009). Privacy-preserving computation
and verification of aggregate queries on outsourced databases. In International symposium
on privacy enhancing technologies symposium (pp. 185–201).
Von Stackelberg, H. (1934). Marktform und gleichgewicht. J. springer.
Wahab, O. A., Bentahar, J., Otrok, H., & Mourad, A. (2016). A stackelberg game for distributed
formation of business-driven services communities. Expert Systems with Applications, 45,
359–372.
Wang, J., Chen, X., Huang, X., You, I., & Xiang, Y. (2015). Verifiable auditing for outsourced
database in cloud computing. IEEE Transactions on Computers, 64(11), 3293–3303.
Xie, M.,Wang, H., Yin, J.,&Meng, X. (2007). Integrity auditing of outsourced data. In Proceedings
of the 33rd international conference on very large data bases (pp. 782–793).
Yang, Y., Papadias, D., Papadopoulos, S., & Kalnis, P. (2009). Authenticated join processing in
outsourced databases. In Proceedings of the 2009 acm sigmod international conference on
management of data (pp. 5–18).
Yin, Z., Korzhyk, D., Kiekintveld, C., Conitzer, V., & Tambe, M. (2010). Stackelberg vs. nash in
security games: Interchangeability, equivalence, and uniqueness. In Proceedings of the 9th
international conference on autonomous agents and multiagent systems: volume 1-volume 1
(pp. 1139–1146).
Yuan, J., & Yu, S. (2013). Flexible and publicly verifiable aggregation query for outsourced
databases in cloud. In Communications and network security (cns), 2013 ieee conference
on (pp. 520–524).
Zhang, L. F., & Safavi-Naini, R. (2014). Verifiable delegation of computations with storageverification
trade-off. In European symposium on research in computer security (pp. 112–
129).
Zhu, Y., Ahn, G.-J., Hu, H., Yau, S. S., An, H. G., & Hu, C.-J. (2013). Dynamic audit services for
outsourced storages in clouds. IEEE Transactions on Services Computing, 6(2), 227–238.
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.
Repository Staff Only: item control page
Download Statistics
Download Statistics