IACR News item: 05 October 2013
Somindu C. Ramanna
ePrint Reportdeterministic finite automata (DFA). The construction uses composite-order bilinear
pairings and is built upon the selectively secure DFA-based FE scheme of Waters (Crypto 2012).
The scheme is proven secure using the dual system methodology under static subgroup decision assumptions.
A dual system proof requires generating of semi-functional components from the instance.
In addition, these components must be shown to be properly distributed in an attacker\'s view.
This can be ensured by imposing a restriction on the automata and strings over which the
scheme is built i.e., every symbol can appear at most once in a string and in the set of
transition tuples of an automata.
First a basic construction with the restrictions is obtained and proved to be adaptively secure.
We then show how to extend this basic scheme to a full scheme where the restrictions can be relaxed
by placing a bound on the number of occurrences of any symbol in a string and in
the set of transitions. With the relaxed restrictions, our system
supports functionality defined by a larger class of regular languages.
Additional news items may be found on the IACR news page.