Prev: what is probability to create two equal hashes for md5 algorithm
Next: help needed
From: Amit on 23 Feb 2007 07:09
On Feb 5, 1:32 am, Kristian Gjøsteen <kristiag+n...(a)math.ntnu.no>
wrote:
> The best idea I've heard is to choose a non-prime.

Are there other constructions based on composites apart from the
"deterministic Paillier method" I mentioned? If so, I'm keen to know
them as this is would be an interesting result.

From: Kristian Gj�steen on 26 Feb 2007 04:19
Amit <amitabh123(a)gmail.com> wrote:
>On Feb 5, 1:32 am, Kristian Gj�steen <kristiag+n...(a)math.ntnu.no>
>wrote:
>> The best idea I've heard is to choose a non-prime.
>
>Are there other constructions based on composites apart from the
>"deterministic Paillier method" I mentioned? If so, I'm keen to know
>them as this is would be an interesting result.

This is in the context of inserting a back-door in a system. If some
party is using a defective (in a certain sense) primality test, you can
use a composite instead of a prime. Then you can solve the DLP modulo
each prime factor and combine the solution.

I believe there have been actual attacks along this line.

--
Kristian Gj�steen
From: Amit on 26 Feb 2007 07:40
On Feb 26, 10:19 am, Kristian Gjøsteen <kristiag+n...(a)math.ntnu.no>
wrote:
> Amit <amitabh...(a)gmail.com> wrote:
> >On Feb 5, 1:32 am, Kristian Gjøsteen <kristiag+n...(a)math.ntnu.no>
> >wrote:
> >> The best idea I've heard is to choose a non-prime.
>
> >Are there other constructions based on composites apart from the
> >"deterministic Paillier method" I mentioned? If so, I'm keen to know
> >them as this is would be an interesting result.
>
> This is in the context of inserting a back-door in a system. If some
> party is using a defective (in a certain sense) primality test, you can
> use a composite instead of a prime. Then you can solve the DLP modulo
> each prime factor and combine the solution.
>
> I believe there have been actual attacks along this line.
>
> --
> Kristian Gjøsteen

thanks for your reply. That appears to be a "weak" cryptosystem (i.e.,
we have to keep the prime factors "small enough" for quickly computing
discrete logs)

Perhaps, a better example would be the BGN cryptosystem based on the
subgroup decision problem (however, it works only if the discrete log
is small, so not what I am looking for).
--
Amitabh

First  |  Prev  | 
Pages: 1 2 3
Prev: what is probability to create two equal hashes for md5 algorithm
Next: help needed