[6761] in cryptography@c2.net mail archive
Re: Looking for a cryptographic primitive
daemon@ATHENA.MIT.EDU (Victor Duchovni)
Thu Mar 9 17:36:18 2000
Message-ID: <38C821FF.36A08558@msdw.com>
Date: Thu, 09 Mar 2000 17:13:19 -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/mixed;
boundary="------------5116C7990F9580537A4ED71A"
This is a multi-part message in MIME format.
--------------5116C7990F9580537A4ED71A
Content-Type: multipart/alternative;
boundary="------------40E0A9A3E6C55818A55B7113"
--------------40E0A9A3E6C55818A55B7113
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
You posit the difficulty of obtaining additive inverses, this would
suggest that they need to exist, and you likely want addition to be
commutative, so you at least have a ring.
What actual algebraic properties do you need? The possible choices from
most specialized to least specialized (that have addition and multiplication
with distributive laws...) are as follows:
* Field (infinite containing an isomorphic image of Q, or degree n
extension of Zp)
* Algebra over a field (vector space with multiplication, e.g. n x n
matrices over Zp)
* Algebra over a ring (module with multiplication, e.g. n x n matrices
over Zm (m not prime))
* Ring
Presumably the set of elements is to be finite. The last three cases are
all rings, Weddeburn's theorem states that all finite division rings are
fields, so the rings in question must have pairs of non-zero elements whose
product is zero (zero divisors). Do you need multiplication (by non-zero
elements) to be one-to-one?
bram wrote:
> On Thu, 9 Mar 2000, 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?
> >
> > [Bram: All fields of n elements are isomorphic to all other fields of
> > n elements
>
> I'm not using the additive or multiplicative identity, maybe eleminating
> the requirement for those increases the number of mathematical structures
> available?
>
> -Bram
--
Viktor Dukhovni <Victor.Duchovni@msdw.com> +1 212 762 1198
--------------40E0A9A3E6C55818A55B7113
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<br> You posit the difficulty of obtaining additive inverses,
this would suggest that they need to exist, and you likely want addition
to be commutative, so you at least have a ring.
<p> What actual algebraic properties do you need?
The possible choices from most specialized to least specialized (that have
addition and multiplication with distributive laws...) are as follows:
<ul>
<li>
Field (infinite containing an isomorphic image of <b>Q</b>, or degree <b><i>n
</i></b>extension of <b>Z<i>p</i></b>)</li>
<li>
Algebra over a field (vector space with multiplication, e.g. <b><i>n </i>x
<i>n </i></b>matrices over <b>Z<i>p</i></b>)</li>
<li>
Algebra over a ring (module with multiplication, e.g. <b><i>n </i>x <i>n
</i></b>matrices over <b>Z<i>m </i>(<i>m </i></b>not prime))</li>
<li>
Ring</li>
</ul>
Presumably the set of elements is to be finite.
The last three cases are all rings, Weddeburn's theorem states that all
finite division rings are fields, so the rings in question must have pairs
of non-zero elements whose product is zero (zero divisors). Do you
need multiplication (by non-zero elements) to be one-to-one?
<p>bram wrote:
<blockquote TYPE=CITE>On Thu, 9 Mar 2000, bram wrote:
<p>> 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?
<br>>
<br>> [Bram: All fields of n elements are isomorphic to all other fields
of
<br>> n elements
<p>I'm not using the additive or multiplicative identity, maybe eleminating
<br>the requirement for those increases the number of mathematical structures
<br>available?
<p>-Bram</blockquote>
<p>--
<br> Viktor Dukhovni <Victor.Duchovni@msdw.com> +1 212 762 1198
<br> </html>
--------------40E0A9A3E6C55818A55B7113--
--------------5116C7990F9580537A4ED71A
Content-Type: text/x-vcard; charset=us-ascii;
name="Victor.Duchovni.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for Victor Duchovni
Content-Disposition: attachment;
filename="Victor.Duchovni.vcf"
begin:vcard
n:Duchovni;Victor
tel;pager:+1 888 674 9129
tel;fax:+1 212 762 1009
tel;home:+1 212 784 0565
tel;work:+1 212 762 1198
x-mozilla-html:TRUE
org:Morgan Stanley Dean Witter;Security Engineering
version:2.1
email;internet:Victor.Duchovni@msdw.com
adr;quoted-printable:;;750 7th Ave.=0D=0A9th floor;New York;New York;10019-6825;USA
fn:Viktor Dukhovni
end:vcard
--------------5116C7990F9580537A4ED71A--
