Research
I am mainly interested in Algorithmic Information Security (Computer Security in general) and particularly in the study of Authenticated Data Structures, namely devising algorithms and protocols that enable storing any data structure at some untrusted entity (server) so that trusted entities (clients) can efficiently verify the integrity of answers to standard data structure queries, by using widely-acceptable cryptographic primitives and at the same time locally storing asymptotically less space than the data structure itself (preferably constant). In our framework efficiency implies that, ideally, the added security guarantee does not add any extra asymptotical overhead to the complexity of non-authenticated data structures (e.g., maintain O(log n) query complexity for an authenticated dictionary). Our research has led to optimal solutions for some data structures. However, matching known lower bounds of some non-authenticated data structures (e.g., hash table) remains an open problem. Along with this line of theoretical research I have also investigated dynamic solutions that achieve security guarantees by minimizing the communication complexity at some probabilistic cost, under the Provable Data Possession model. I am finally implementing my theoretical solutions and have produced software systems for authenticated file systems (Athos) and authentication of outsourced storage (Authenticated Amazon S3).
While at Intel Research Berkeley, I also worked on declarative security, where the main goal is to abstract certain security notions such as integrity, public verifiability and privacy and be able to describe and prove correctness of distributed computing protocols that use these security properties without referring to certain implementations. This provides great flexibility to underlying applications and aims at enhanced general performance.
Finally, I am also interested and have worked on Computational Geometry, Algorithmic Aspects of Sensor Networks and Design and Analysis of Algorithms.
CONFERENCE
1. Chris Erway, Alptekin Küpçü, Charalampos Papamanthou and Roberto Tamassia. Dynamic Provable Data Possession. In Proc. of the ACM Int. Conference on Computer and Communications Security (CCS), pages xx, Chicago IL, USA, 2009. [.pdf ]
2. Charalampos Papamanthou, Roberto Tamassia, and Nikos Triandopoulos. Authenticated Hash Tables. In Proc. of the ACM Int. Conference on Computer and Communications Security (CCS), pages 437-448, Alexandria VA, USA, 2008. [.pdf ]
3. Alexander Heitzmann, Bernardo Palazzi, Charalampos Papamanthou, and Roberto Tamassia. Efficient Integrity Checking of Untrusted Network Storage. In Proc. of the ACM CCS Int. Workshop on Storage Security and Survivability (STORAGESS), pages 43-54, Alexandria VA, USA, 2008. [.pdf ]
4. Micheal Goodrich, Charalampos Papamanthou, Roberto Tamassia, and Nikos Triandopoulos. Athos: Efficient Authentication of Outsourced File Systems. In Proc. of the Int. Information Security Conference (ISC), Lecture Notes in Computer Science 5222, Springer-Verlag, pages 80-96, Taipei, Taiwan, 2008. [.pdf ]
5. Charalampos Papamanthou, Franco P. Preparata, and Roberto Tamassia. Algorithms for Location Estimation Based on RSSI Sampling. In Proc. of the ICALP Int. Workshop on Algorithms for Sensor Networks (ALGOSENSORS), Lecture Notes in Computer Science 5389, Springer-Verlag, pages 72-86, Reykjavik, Iceland, 2008. [.pdf ]
6. Roberto Tamassia, Bernardo Palazzi and Charalampos Papamanthou. Graph Drawing for Security Visualization. In Proc. of the Int. Conference on Graph Drawing (GD), Lecture Notes in Computer Science 5417, Springer-Verlag, pages 2-13, Heraklion, Greece, 2008. [.pdf ]
7. Alexander Heitzmann, Bernardo Palazzi, Charalampos Papamanthou, and Roberto Tamassia. Effective Visualization of File System Access-Control. In Proc. of the Int. Workshop on Security Visualization (VIZSEC), Lecture Notes in Computer Science 5210, Springer-Verlag, pages 18-25, Boston MA, USA, 2008. [.pdf ]
8. Charalampos Papamanthou and Roberto Tamassia. Time and Space Efficient Algorithms for Two-Party Authenticated Data Structures. In Proc. of the Int. Conference on Information and Communications Security (ICICS), Lecture Notes in Computer Science 4861, Springer-Verlag, pages 1-15, Zhengzhou, China, 2007. [.pdf ]
9. Micheal T. Goodrich, Charalampos Papamanthou, and Roberto Tamassia. On the Cost of Persistence and Authentication in Skip Lists. In Proc. of the Int. Workshop on Experimental Algorithms (WEA), Lecture Notes in Computer Science 4525, Springer-Verlag, pages 94-107, Rome, Italy, 2007. [.pdf ]
10. Charalampos Papamanthou and Ioannis G. Tollis. Parameterized st-Orientations of Graphs: Algorithms and Experiments. In Proc. of the Int. Conference on Graph Drawing (GD), Lecture Notes in Computer Science 4372, Springer-Verlag, pages 220-233, Karlsrühe, Germany, 2006. [.pdf ]
11. Charalampos Papamanthou and Ioannis G. Tollis. Applications of Parameterized st-Orientations in Graph Drawing Algorithms. In Proc. of the Int. Conference on Graph Drawing (GD), Lecture Notes in Computer Science 3843, Springer-Verlag, pages 355-367, Limerick, Ireland, 2005. [.pdf ]
12. Charalampos Papamanthou, Ioannis G. Tollis, and Martin Doerr. 3D Visualization of Semantic Metadata Models and Ontologies. In Proc. of the Int. Conference on Graph Drawing (GD), Lecture Notes in Computer Science 3383, Springer-Verlag, pages 377-388, New York City NY, USA, 2004. [.pdf ]
13. Charalampos Papamanthou and Konstantinos Paparrizos. A Visualization of the Primal Simplex Algorithm for the Assignment Problem. In Proc. of the ACM Int. Conference on Innovation and Technology in Computer Science Education (ITICSE), page 267, Thessaloniki, Greece, 2003. [.pdf ]
JOURNAL
14. Charalampos Papamanthou, Konstantinos Paparrizos, Nikolaos Samaras and Angelo Sifaleras. On the Initialization Methods of an Exterior Point Algorithm for the Assignment Problem. International Journal of Computer Mathematics, to appear.
15. Charalampos Papamanthou and Ioannis G. Tollis. Algorithms for Computing a Parameterized st-Orientation. Theoretical Computer Science, 408:224-240, 2008. [.pdf ]
16. Claire Mathieu and Charalampos Papamanthou. Distortion Lower Bounds for Line Embeddings. Information Processing Letters, 108(4):175-178, 2008. [.pdf ]
17. Charalampos Papamanthou, Konstantinos Paparrizos, Nikolaos Samaras, and Konstantinos Stergiou. Worst Case Examples of an Exterior Point Algorithm for the Assignment Problem. Discrete Optimization, 5(3):605-614, 2008. [.pdf ]
18. Charalampos Papamanthou, Konstantinos Paparrizos, and Nikolaos Samaras. A Parametric Visualization Software for the Assignment Problem. Yugoslav Journal of Operations Research, 15(1):147-158, 2005. [.pdf ]
19. Charalampos Papamanthou, Konstantinos Paparrizos, and Nikolaos Samaras. Computational Experience with Exterior Point Algorithms for the Transportation Problem. Journal of Applied Mathematics and Computation, 158:459-475, 2004. [.pdf ]
OTHER
20. Charalampos Papamanthou. Computing Longest Path Parameterized st-Orientations of Graphs: Algorithms and Applications. Master's thesis, University of Crete, Heraklion, Greece, July 2005. [.pdf ]
21. Charalampos Papamanthou. Effective Programming, Computational Study and Internet Visualization of Network Programming Problems Algorithms. Bachelor's thesis, University of Macedonia, Thessaloniki, Greece, June 2003. [.pdf ]