TCS Seminar

Date: 23/11/2011 Location: J. Liivi 2, room 317 (next to the coffee room)

Speaker: Wulf Harder

Title: Creating new cryptographic operations
by composing Turing Machine components using the tool TRANSDUCE^TM

Abstract:

There are cryptographic methods based on finite automata compositions: Renji Tao has published the public-key algorithm FAPKC, Syncrosoft has developed a fully homomorphic encryption scheme MCFACT^TM (however, there are no publications of MCFACT^TM design details). These methods rely on the assumption that in general it is hard to decompose large finite automata. The cost of large finite automata is execution time, which is the most critical factor in cloud computing or on mobile devices. For that reason an objective for further research in this field is to find new designs for cryptographic operations using much more compact compositions which are also hard to decompose. This talk will start with an introduction to composition of finite automata. Multiplying large prime numbers can be done efficiently by composing finite automata. This means that there are decomposition problems which are as hard as factoring. Furthermore it will be demonstrated how to generate new designs based on compositions of Turing Machine components of finite and infinite size using QuBalt's tool TRANSDUCE^TM. The composition of such finite and infinite components results in a Turing complete computational model.