Skip to main navigation Skip to Content

Computer Science

University of Toronto
  • U of T Portal
  • Student Support
  • Contact
  • About
    • Why Study CS at U of T
    • Career Options
    • History of DCS
    • Giving to DCS
    • Computer Science at UofT Mississauga
    • Computer Science at UofT Scarborough
    • Contact
    • Employment Opportunities for Faculty/Lecturers
    • How to Find Us
  • Undergraduate
    • Prospective Undergraduates
    • Current Undergraduates
  • Graduate
    • Prospective Graduate students
    • Current Graduate students
  • Research
    • Research Areas
    • Partner with us
  • People
    • Faculty
    • Staff
    • In Memoriam
    • Alumni and Friends
    • Honours & Awards
    • Women in Computer Science
    • Graduate Student Society
    • Undergraduate Student Union
    • Undergraduate Artificial Intelligence Group
    • Undergraduate Theory Group
  • News & Events
    • News
    • Events
    • @DCS Update
    • Alumni
    • Donate
You are viewing: > Home > News & Events > Events > Theory Seminar: Aug 14
  • About
  • Undergraduate
  • Graduate
  • Research
  • People
  • News & Events

Theory Seminar: Aug 14

Event date: Friday, August 14, 2015, at 11:10 AM
Location: GB 244

Speaker: Dan Brownstein, Ben Gurion University

Title: Functional Encryption for Cascade Automata

Abstract:

We introduce a functional encryption scheme based on the security of bilinear maps for the class of languages accepted by extended automata. In such an automaton, $n$ DFAs, each with at most $q$ states, are linked in a cascade such that the first DFA receives the input to the system and a feedback symbol from the last DFA, and in each transition the $i$-th DFA, $i=1,\ldots,n$, both performs its own transition and outputs a symbol that acts as the input for DFA number $i+1\mod n$. The state of the whole system is an $n$-tuple consisting of the state of each component DFA.Our work extends the work of Waters (Crypto'12) by replacing a single DFA with a cascade. Although both models accept all regular languages, a cascade automata reduces the number of states and therefore the key size for certain regular languages by an exponential factor. In both systems, a message $m$ is encrypted with a word $w$ and can be decrypted only by a key that is associated with an automaton that accepts $w$. Our scheme has key size $O(nq^2)$ and all its other efficiency measures including the ciphertext length, encryption and decryption times are linear in the length of $w$. As an example of the additional power that a cascade provides, we show a construction of a cascade that accepts a word in a regular language only if it is accompanied by a standard public key signature on that word. Our work improves on alternative approaches using functional encryption for general circuits or programs, by either being based on weaker assumptions, i.e. bilinear maps, or by being more efficient.

 

 



All rights reserved copyright Computer Science, University of Toronto | Site Map