Cryptographic analysis in cubic time

Abstract. It is well-known that context-independent control flow anal-ysis can be performed in cubic time for functional and object-oriented languages. Yet recent applications of control flow analysis to calculi of computation (like the pi-calculus and the ambient calculus) have reported considerably higher complexities. In this paper we introduce two general techniques, the use of Horn clauses with sharing and the use of tiling of Horn clauses, for reducing the worst-case complexity of analyses. Ap-plying these techniques to the pi-calculus and the ambient calculus we reduce the complexity from O(n5) to O(n3) in both cases