Results 1 to 2 of 2

Math Help - What is the variable "u" in the Paillier cryptosystem?

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    1

    What is the variable "u" in the Paillier cryptosystem?

    In the Paillier cryptosystem, one of the stages during the key generation is "Ensure n divides the order of g by checking the existence of the following modular multiplicative inverse: *where function L is defined as " (from wikipedia)
    The variable "u" is never defined though, which leads me to my question regarding what this variable is.
    The closest thing I've been able to find as an answer to this is in the original document outlining the Paillier cryptosystem where it states :
    u = 1 \bmod n (http://www.ippari.unict.it/~catalano...3-Paillier.pdf Page 41), however if n>1 (which it is), "u" would always be 1 (which it cannot be according to the function "L" shown previously), and using the Extended Euclidean Algorithm the following would happen:
    u = 1 \bmod n
    u - 1 = qn
    u - qn= 1
    The variable "n" is known.
    Therefore "q" would be equal to 1, and "u" would equal (n+1), which would satisfy the previous relationship, however I do not think that this is correct.
    Thanks
    Last edited by Scorzerci; August 10th 2009 at 03:48 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Hi

    It tells us that S_N=\{u<N^2 \ | \ u\equiv 1 \ mod \ N\}

    The key there is that u is less than N squared, not just N. Hope that helps. I'm not too familiar with cryptology and stuff, but just from considering that set, u = qN + 1 < N^2, and q would be integers that satisfy the condition, i.e. q = 0,1,2,3,...,N-1. There would b N u's also ...

    Hope that helps, again, I'm not too familiar with cryptology, so I don't know if there would be any exceptions, or any modifications to how the mod is applied, but just from a basic number theory perspective, and considering that set ... that's what I get. Also, basically L(u)=q

    Hope that helps a bit
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 16th 2011, 02:08 AM
  2. Replies: 2
    Last Post: June 4th 2011, 01:11 PM
  3. Replies: 2
    Last Post: April 24th 2011, 08:01 AM
  4. Replies: 1
    Last Post: October 25th 2010, 05:45 AM
  5. Replies: 1
    Last Post: June 4th 2010, 11:26 PM

Search Tags


/mathhelpforum @mathhelpforum