Re: Looking for a cryptographic primitive

[Victor Duchovni]

 
    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 <[EMAIL PROTECTED]> +1 212 762 1198
 

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:[EMAIL PROTECTED]
adr;quoted-printable:;;750 7th Ave.=0D=0A9th floor;New York;New York;10019-6825;USA
fn:Viktor Dukhovni
end:vcard