Subject: [Cfrg] Finite Automata Public Key Cryptography (FAPKC)

From: George Gross <[email-masked]>
Date: Thu, 18 Dec 2003 16:41:35 -0500 (EST)

Hi,

	I've been looking at FAPKC, developed by Renji Tao [Tao]
originally in the late 1980s. Most of the ref'd literature is in Chinese
or otherwise unavailable via the Internet (AFAIK). I did unearth two
published attacks [Bao] [Meskanen] that also pointed to ways to repair the
cipher.

my questions:

1. what is the cryptographic standing of FAPKC? broken? ambiguous?
feasible for experimental use?

2. are there any publically available source implementations in the
Western World? interpreting the math into an accurate implementation is a
daunting prospect ;o)

3. there is an identity-based version of this cipher system (FAPKC3) but I
have not seen any literature in English that describes it, does anyone
know of such a publication online?

 tia,
	George

[Tao] Renji Tao, Shihua Chen, "Generating a kind of nonliniar finite
automata with invertibility by transformation method", Technical Report No
ISCAS-LCS-95.05, Laboratory for Computer Science, Institute of Software,
Chinese Academy of Sciences, Beijing, June 1995. Note: I do not personally
have  this reference in hand, a pointer to an online source would be
appreciated...

[Meskanen] On Finite Automaton Public Key Cryptosystems", T. Meskanen,
Dept. of Mathematics, University of Turku Finland; TUCS Technical Report
No 408, August 2001. ISBN 952-12-0837-6, ISSN 1239-1891

[Bao] "Break Finite Automata Public Key Cryptosystem", F. Bao, Y.
Igarashi, Dept. of Computer Science, Gunma University, Kiryu, 376 Japan.
ICALP 1995.

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: George Gross <[email-masked]>
Date: Mon, 22 Dec 2003 12:05:28 -0500 (EST)

Hi Ariel,
	inline below...

On Mon, 22 Dec 2003, Ariel Waissbein wrote:

> Hi George,
>
>    I am interested in FAPK and will be reading the papers
> you name. I can't answer your questions now.

I look forward to hearing your assessment and those of others on this
list.

> In fact I
> have a question for you. For the last couple of years I
> have been looking for the following functionality: a
> finite state machine, such that all of its states are
> "encrypted", when run the machine goes from encrypted
> state to encrypted state until it reaches the last state;
> once it reaches the final state this state (and maybe the
> whole) machine becomes public.
>
>   One such state machine would have several uses in
> cryptography, and in particular in mobile code security
> and DRM.

I am not clear that I understand what you meant when you said "when run
the machine goes from encrypted state to encrypted state until it reaches
the last state". Perhaps you could clarify. Does this type of FSM already
have a particular name?

>
>   One can argue that arbitrary Turing machines with this
> property can be constructed. I, together with co-workers
> at CoreLabs designed several examples of this. However the
> question of doing this with state machines remains. I would
> be glad if you coudl give me any asnwers.

My survey of finite automata literature was confined to public key
cryptography. Along the way, I encountered references to symmetric cipher
and pseudo-random number generator finite automata constructs. I also
encountered several celluar automata schemes, see www.cell-auto.com for
examples and references. Nothing that I saw met the profile of the FSM
you've described, but I was not looking for it either ;o) So I don't think
I can help answer your question...

Recall that the charter of CFRG was to evaluate cryptographic systems for
for their potential introduction into the IETF standards arena. FAPKC
appears to be a computationally efficient asymmetric cipher when compared
to RSA. While I have yet to prototype/benchmark FAPKC, my hunch is that it
would also out perform ECC and Lattice Reduction schemes. AFAIK, the FAPKC
does not have intellectual property (unless it exists in Mainland China?).
Hence, my query to discover this community's view of FAPKC cryptographic
strength/status and implementation experiences...

br,
	George

>
> best regards,
> Ariel
>
> ps, I read some chinese so papers in chinese are also
> wellcomed.
>
>
> --
> Ariel Waissbein
> Senior Researcher - Corelabs
> Core Security Technologies
>
>
>
>
>
>
> > -----Original Message-----
> >
> >
> > Hi,
> >

---

From: "Ariel Waissbein" <[email-masked]>
Date: Mon, 22 Dec 2003 14:08:56 -0300

Hi George,

you name. I can't answer your questions now. In fact I

best regards,
Ariel