Secure two-party context free language recognition

Abstract

The growth of the internet provides opportunities for cooperative computation, it also requires development of protocols that can accomplish this task among mutually untrusting parties. The aim is to develop methods which ensure both the correct evaluation of the function and privacy of individual inputs. Multiparty Computation protocols help to achieve the aim without using a trusted third party. In this paper we consider the problem of context-free language recognition in a two-party setting. Alice has the description of a context-free language L while Bob has a secret string whose membership in L is to be checked. Neither Alice nor Bob is ready to disclose his/her input to the other. Here we propose a protocol which accomplishes secure two party context-free language recognition. The novelty of this paper lies in the use of formal languages based approach for multiparty computations. © Springer-Verlag Berlin Heidelberg 2005.