• Definition Paillier’s function is a one-way trapdoor permutation (OWTP). It therefore provides public key encryption and digital signatures. Theory
  • Applications
  • Recommended Reading
    		•

    Paillier Encryption and Signature




    Download 2.18 Mb.
    Pdf ko'rish
    bet5/155
    Sana04.08.2023
    Hajmi2.18 Mb.
    #78028
    1   2   3   4   5   6   7   8   9   ...   155
    Bog'liq
    gu2011
    AQLLI SHAHAR, TEST, 1-мактаб тўгарак жадвал, BUYRUQ. YASIN BREND, TAQRIZ YANGI, 2, Tarjima SPLINES, DIFFERENTIAL EQUATIONS, AND OPTIMAL, (11-ozbetinshe K.U.A)Q.Zafar, APPLIKATSIYADA QIRQISHNI HAR HIL USULLARINI BAJARISH, EDUCATION SYSTEM OF UZBEKISTON, O’zbekistonning va jahon hamjamiyati, OCHILOVA NIGORANING, 7 yosh inqirozi uning sabablari va alomatlari, TEXNIKA MADANIYATI, AAA
    Paillier Encryption and Signature
    Schemes
    Pascal Paillier
    CryptoExperts, Paris, France
    Related Concepts
    
    Homorphic Encryption
    ;
    
    One-Way Trapdoor Permuta-
    tion
    ;
    
    Public Key Cryptography
    Definition
    Paillier’s function is a one-way trapdoor permutation
    (OWTP). It therefore provides public key encryption and
    digital signatures.
    Theory
    Let n
    = pq be a product of two large primes and let
    ϕ
    (n) = (p − )(q − ) and λ = λ(n) = l cm(p − , q − )
    be the Euler and Carmichael functions of n, respectively.
    The group
    Z
    ∗
    n

    ≃ Z
    n
    × Z
    ∗
    n
    has ϕ
    (n

    ) = nϕ(n) elements
    and for any w
    ∈ Z
    ∗
    n

    , w
    λ
    =  mod n and w
    nλ
    =  mod n

    .
    An integer z is said to be an n-residue modulo n

    if there
    exists some y
    ∈ Z
    ∗
    n

    such that z
    = y
    n
    mod n

    . The set of
    n-residues forms a subgroup of
    Z
    ∗
    n

    of order ϕ
    (n). Each
    n-residue in
    Z
    ∗
    n

    has exactly n roots of degree n. Let g
    ∈ Z
    ∗
    n

    be an element of order αn where 
    ≤ α ≤ λ. Paillier’s
    one-way trapdoor function maps a pair
    (x, y) ∈ Z
    n
    ×Z
    ∗
    n
    to
    E
    g,n
    (x, y) = g
    x
    y
    n
    mod n

    .
    The mapping E
    g,n
    is one-to-one over
    Z
    ∗
    n

    ≃ Z
    n
    × Z
    ∗
    n
    . The
    n-residuosity class of an element w
    ∈ Z
    ∗
    n

    with respect to
    g is defined as the unique integer x
    ∈ Z
    n
    for which there
    exists y
    ∈ Z
    ∗
    n
    such that w
    = E
    g,n
    (x, y) and is written x =
    [w]
    g
    . Note that
    [w]
    g
    =  if and only if w is an n-residue.
    Additionally,
    [w

    w

    mod n

    ]
    g
    = [w

    ]
    g
    + [w

    ]
    g
    mod n,
    so that the class function w
    ↦ [w]
    g
    is an additive homo-
    morphism from
    Z
    ∗
    n

    to
    Z
    n
    . The set S
    n
    = {u ∈ Z
    n

    : u
    =
     mod n
    } is a subgroup of Z
    ∗
    n

    over which L
    (u) = (u−)/n
    is a well-defined function. For any integer r, L
    (u
    r
    mod
    n

    ) = rL(u) mod n, and therefore, extracting discrete log-
    arithms is trivial in the group S
    n
    . Paillier’s function can be
    inverted knowing λ. If w
    = E
    g,n
    (x, y) then
    x
    =
    L
    (w
    λ
    mod n

    )
    L
    (g
    λ
    mod n

    )
    mod n,
    ()
    y
    = (wg
    −x
    )

    /n mod λ
    mod n.
    ()
    It is believed that computing the class
    [w]
    g
    of elements w
    ∈
    Z
    ∗
    n

    without knowing the factors of n is intractable. This is
    referred to as the Composite Residuosity (CR) assump-
    tion. The Decision Composite Residuosity (DCR) assump-
    tion states that distinguishing n-residues from arbitrary
    elements of
    Z
    ∗
    n

    is intractable. Paillier introduced several
    public-key encryption schemes from the one-way trapdoor
    function E
    g,n
    :
    ● A deterministic encryption scheme where a plaintext
    m
    = m

    + nm

    ∈ Z
    n

    is encrypted as c
    = E
    g,n
    (m

    , m

    )
    and the ciphertext c is decrypted to
    (m

    , m

    ) using the

    Pairing-Based Key Exchange
    P
    
    P
    two computation steps (

    ) and (

    ) as above. The public
    key is
    (g, n) and the private key is λ. This scheme
    is proven to be one-way under the RSA assumption
    where n is taken as public exponent. However, it does
    not provide semantic security.
    ● A probabilistic encryption scheme where the encryp-
    tion of a plaintext m
    ∈ Z
    n
    is c
    = E
    g,n
    (m, r) where r ∈ Z
    n
    is taken at random. The plaintext m is recovered by per-
    forming computation step (

    ) above and ignoring the
    second step that retrieves the randomness r. The public
    key is
    (g, n) and the private key is λ.
    ● A subgroup variant where m ∈ Z
    n
    is encrypted as
    c
    = g
    m
    +rn
    mod n

    where r
    ∈ Z
    n
    is taken at random. The
    base g must be of order αn and the plaintext is recov-
    ered as m
    = L(c
    α
    mod n

    )/L(g
    α
    mod n

    ) mod n. The
    private key is therefore α in this scheme and can be
    made significantly smaller than λ, thus speeding up
    decryption. This encryption scheme is one-way and
    semantically secure under stronger versions of the CR
    and DCR assumptions.
    The two probabilistic encryption schemes above are
    homomorphic for addition; if c

    is an encryption of m

    and
    c

    and encryption of m

    then c

    = c

    c

    mod n

    decrypts
    to m

    = m

    + m

    mod n. Digital signatures are obtained
    through the hash-and-sign paradigm. To sign a message
    m
    ∈ {, }
    ∗
    , a hash function H mapping arbitrary bit-
    strings to integers modulo n

    is used. The signature is then
    (s

    , s

    ) = E
    −
    g,n
    (H(m)) and is verified by checking whether
    E
    g,n
    (s

    , s

    ) = H(m). This scheme is secure under adaptive
    chosen-message attacks under the CR assumption in the
    random oracle model.
    Applications
    Paillier encryption has applications in private informa-
    tion retrieval, threshold decryption, traitor tracing, proofs
    of knowledge, e-vote, e-auctions, multiparty computation,
    standard-model chosen-ciphertext encryption, commit-
    ment schemes, and secret sharing.
    Recommended Reading
    . Catalano D, Gennaro R, Howgrave-Graham N, Nguyen PQ ()
    Paillier’s cryptosystem revisisted. In: Proceedings of the th
    ACM conference on computer and communications security,
    pp –
    . Catalano D, Gennaro R, Howgrave-Graham N () The bit
    security of Paillier’s encryption scheme and applications. In:
    Proceedings of Eurocrypt’, LNCS , pp –
    . Cramer R, Shoup V () Universal hash proofs and a paradigm
    for chosen ciphertext secure public-key encryption. In: Proceed-
    ings of Eurocrypt’, LNCS , pp –
    . Damgård I, Jurik M () A generalisation, a simplification and
    some applications of Paillier’s probabilistic public-key system. In:
    Proceedings of PKC’, LNCS , pp –
    . Galbraith SD () Elliptic curve Paillier schemes. J Cryptol
    ():–
    . Paillier P () Public-key cryptosystems based on composite
    degree residuosity classes. In: Proceedings of Eurocrypt’, LNCS
    , pp –
    . Paillier P, Pointcheval D () Efficient public-key cryptosys-
    tems provably secure against active adversaries. In: Proceedings
    of Asiacrypt’, LNCS , pp –
    . Schmidt-Samoa K, Takagi T () Paillier’s cryptosystem mod-
    ulo pq and its applications to trapdoor commitment schemes.
    In: Proceedings of Mycrypt, LNCS , pp –

    Download 2.18 Mb.
    1   2   3   4   5   6   7   8   9   ...   155




    Download 2.18 Mb.
    Pdf ko'rish