Patent ID: 7649991

Claim:
A receiver-side apparatus for decrypting transmission data, said receiver-side apparatus comprising: a key generation unit; and a decryption unit, wherein the key generation unit: (a): creates a secret key given by an expression: p, q: prime numbers p≡ 3(mod 4), q≡ 3(mod 4) and further, (b) creates a public key given by an expression: N=p d q (d is odd number) k=|N| G:{0,1} k 0 →{0,1} n+k 1 hash function, H:{0,1} n+k 1 →{0,1} k 0 hash function wherein a sender-side apparatus calculates an expression: y=w 2 mod N and defines this result y as a ciphertext so as to transmit said ciphertext to the receiver-side apparatus, wherein said decryption unit, using said secret key: (c) calculates, from said ciphertext y, an expression: α 0 = y p + 1 4 ⁢ mod ⁢ p , ⁢ β 0 = α 0 , ⁢ α k = 1 2 ⁢ β k - 1 ⁢ ( y ⁢ ⁢ mod ⁢ ⁢ p k + 1 - β k - 1 2 p k ) ⁢ mod ⁢ p , ( k ≥ 1 ) β k = ∑ i = 0 k ⁢ α i ⁢ p i ⁢ ⁢ ( k ≥ 1 ) , and, using this result, (d) calculates an expression: x p = ∑ i = 0 d - 1 ⁢ α i ⁢ p i and further, (e) calculates an expression: x q = y q + 1 4 ⁢ ⁢ mod ⁢ ⁢ q and, concerning each of expressions φ(x p , x q ), φ(−x p , x q ), φ(x p , −x q ), and φ(−x p , −x q ) (where, φ designates a ring isomorphism mapping from Z/(p)×Z/(q) to Z/(pq) by Chinese remainder theorem), (f) sets each of said expressions to be as given by an expression: s′∥t′ (s′ε{0,1} n+k 1 , t′ε{0,1} k 0 ) and (g) calculates an expression: r′=H ( s′ )⊕ t′, x′∥z′=s′⊕G ( r′ ) ( x′ε{ 0,1} n , z′ε{ 0,1} k 1 ) and (h) obtains a decryption result given by an expression: { x ′ if ⁢ ⁢ z ′ = 0 k 1 * otherwise wherein, it is stipulated that, in a case where said decryption result is * or invalid, said receiver-side apparatus denies said ciphertext, wherein p and q are prime numbers, wherein (N, k, G, H) represents a public key, and each of N, k, G, and H represent a function of the public key, wherein n is a natural number, wherein r is a random number, wherein Z represents an aggregate of integers, and wherein d is an integer.