[6758] in cryptography@c2.net mail archive
Re: Looking for a cryptographic primitive
daemon@ATHENA.MIT.EDU (Victor Duchovni)
Thu Mar 9 14:59:15 2000
Message-ID: <38C7E929.FE601DB2@msdw.com>
Date: Thu, 09 Mar 2000 13:10:49 -0500
From: Victor Duchovni <Victor.Duchovni@msdw.com>
Reply-To: Victor.Duchovni@msdw.com
MIME-Version: 1.0
To: bram <bram@gawth.com>
Cc: cryptography@c2.net
Content-Type: multipart/alternative; boundary="------------8AFB06496E77FDE00A29AD90"
--------------8AFB06496E77FDE00A29AD90
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Every finite field F is a finite abelian group under addition, and so has a
minimal annihilator or characteristic p which must be prime with the property
that a + ... + a (p times) = 0 for every element a of F. So
-a = a + ... + a (p-1 times).
Now this is supposed to be hard to compute. We can use the standard trick
to speed up modular exponents in order to compute (p-1) . a quickly (write p-1
in binary add recursively double and add as necessary). So if we know the
characteristic the whole game is roughly as hard as log2(p).
Arithmetic in fields the logarithm of whose characteristic is prohibitively
large is not going to be practical. Hiding the characteristic and still being
able to define the arithmetic seems implausible.
--
Viktor.
bram wrote:
> Does anybody know of a field in which a + b and a * b can be computed
> quickly but (and this is important) it's computationally intractable to
> compute the additive inverse of a?
>
> I need it for a technique I'm working on.
>
> -Bram
>
> [Bram: All fields of n elements are isomorphic to all other fields of
> n elements, and in any of the fields I'm familiar with, it is trivial
> to compute an additive (or multiplicative) inverse. Given this, I
> suspect what you want to do is rather hard -- you would have to
> conceal the isomorphism to, say, GF(n) somehow. Any readers have any
> other insights here? --Perry]
--------------8AFB06496E77FDE00A29AD90
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<BR> Every finite field <B>F </B>is a finite abelian
group under addition, and so has a minimal annihilator or characteristic
<B>p</B> which must be prime with the property that <B><I>a + ... + a</I>
</B>(<B>p<I> </I></B>times)
<B>= 0 </B>for every element <B><I>a </I></B>of
<B>F.</B> So<B><I></I></B>
<P><B><I> -a = a + ... + a </I></B>(<B>p-</B>1 times).
<P><B> </B>Now this is supposed to be hard to compute.
We can use the standard trick to speed up modular exponents in order to
compute (<B>p-</B>1<B>) . <I>a</I></B> quickly (write <B>p-</B>1 in binary
add recursively double and add as necessary). So if we know the characteristic
the whole game is roughly as hard as <B>log2(p).</B>
<P> Arithmetic in fields the logarithm of whose characteristic
is prohibitively large is not going to be practical. Hiding the characteristic
and still being able to define the arithmetic seems implausible.
<P>--
<BR> Viktor.
<P>bram wrote:
<BLOCKQUOTE TYPE=CITE>Does anybody know of a field in which a + b and a
* b can be computed
<BR>quickly but (and this is important) it's computationally intractable
to
<BR>compute the additive inverse of a?
<P>I need it for a technique I'm working on.
<P>-Bram
<P>[Bram: All fields of n elements are isomorphic to all other fields of
<BR>n elements, and in any of the fields I'm familiar with, it is trivial
<BR>to compute an additive (or multiplicative) inverse. Given this, I
<BR>suspect what you want to do is rather hard -- you would have to
<BR>conceal the isomorphism to, say, GF(n) somehow. Any readers have any
<BR>other insights here? --Perry]</BLOCKQUOTE>
</HTML>
--------------8AFB06496E77FDE00A29AD90--
