JP3615133B2 - Public key encryption / decryption method and system using algebraic field - Google Patents

Description

は、二項係数、即ち、ｎ個のものからｋ個のものを選び出す組合せの数を表すものとする。さらに注意として、ここで使われている代数体、整数環、素イデアルなどの数論の用語については、文献（河田敬義 著，「数論」岩波書店発行）などを参照、特に、通常の整数と代数的整数を区別する必要がある場合は、通常の整数を有理数と呼ぶことにする。
【０００６】
【発明の実施の形態】
図１に鍵生成処理部、図２に暗号化処理部、図３に復号処理部の構成図を示す。
本発明で用いる公開鍵暗号方式の構成法の実施例について、図１、図２、図３を参照して説明する。
（鍵生成処理：図１）
鍵生成処理部は、乱数発生器Ａ（１０１）、互素判定器（１０２）、剰余類判定器（１０３）、乱数発生器Ｂ（１０４）、離散対数器（１０５）、乱数発生器Ｃ（１０６）、加算器Ａ（１０７）から構成される。
【０００７】
ｌ次（エル次）代数体Ｋ、Ｋの整数環Ｏ_Ｋ、Ｏ_Ｋの素イデアルｐ’、剰余類体Ｏ_Ｋ／ｐ’＝ＧＦ（ｑ）の一つの完全代表系Ｒ_ｐ’、ｎとｋを有理整数として、これらを公開する。
（１）Ｋ、Ｏ_Ｋ、ｐ’、ｎ、ｋ、Ｒ_ｐ’を乱数発生器Ａ（１０１）に入力し、乱数発生器Ａ（１０１）、互素判定器（１０２）及び剰余類判定器（１０３）を用いて、整数環Ｏ_Ｋから｛ｐ_１，ｐ_２，・・・，ｐ_ｎ｝でそのノルムが互いに素であり、この任意の部分集合｛ｐ_ｉ１，ｐ_ｉ２，・・・，ｐ_ｉｎ｝が
【０００８】
【数２０】

【０００９】
を満たすようなｎ個の整数｛ｐ_１，ｐ_２，・・・，ｐ_ｎ｝を生成する。
（２）乱数発生器Ｂ（１０４）を用いて、乗法群（Ｏ_Ｋ／ｐ）^×＝ＧＦ（ｑ）^×の生成元ｇを生成する。
（３）次に、剰余類判定器（１０３）で生成したｎ個の整数｛ｐ_１，ｐ_２，・・・，ｐ_ｎ｝と乱数発生器Ｂ（１０４）で生成した生成元ｇを入力し、離散対数計算器（１０５）を用いて、各々の１≦ｉ≦ｎに対してｐ_ｉ≡ｇ^ａｉ（ｍｏｄ ｐ’）を満たすようなａ_１，ａ_２，・・・，ａ_ｎを求める。
（３）さらに、乱数発生器Ｃ（１０６）を用いて、Ｚ／（ｑ−１）Ｚ（（ｑ−１）を法とする整数の体）からの整数（乱数）ｄを発生させる。
（４）最後に、離散対数計算器（１０５）で求めたａ_１，ａ_２，・・・，ａ_ｎと乱数発生器Ｃ（１０６）で発生した整数（乱数）ｄを入力し、加算器Ａ（１０７）を用いて、各々の１≦ｉ≦ｎに対して公開鍵ｂ_ｉ＝（ａ_ｉ＋ｄ） ｍｏｄ（ｑ−１）を求めて出力する。
（剰余類判定器（１０２）について）
剰余類判定器（１０２）の実現方法について二種類説明する。
【００１０】
乱数発生器Ａ（１０１）を用いて、｛ｐ_１，ｐ_２，・・・，ｐ_ｎ｝が、すべて互いに素な有理整数として選ばれた場合、素イデアルｐ’のノルムをＮ（ｐ’）＝ｐ^ｆ（ｐは有理素数、ｆは自然数）とすれば、この任意の部分集合｛ｐ_ｉ１，ｐ_ｉ２，・・・，ｐ_ｉｋ｝が
【００１１】
【数２１】

【００１２】
を満たしているかどうかで判定できる。
次に、Ｋが判別式−Ｄの虚二次体Ｋ＝Ｑ（√（−Ｄ））である場合、素イデアルｐ’が二次のもの、つまり、ｆ＝２を取る場合、−Ｄ≡２，３（ｍｏｄ ４）であれば、ノルムが互いに素なｎ個の整数｛ｐ_１，ｐ_２，・・・，ｐ_ｎ｝で、この任意の部分集合｛ｐ_ｉ１，ｐ_ｉ２，・・・，ｐ_ｉｋ｝が
【００１３】
【数２２】

【００１４】
を満たしているかどうかで判定する。
一方、−Ｄ≡１（ｍｏｄ ４）であれば、
【００１５】
【数２３】

【００１６】
を満たしているかどうかを判定する。但し、今の場合完全代表系はＲ_ｐ’＝｛ｘ＋ｙω｜−ｐ／２＜ｘ， ｙ＜−ｐ／２｝で取っている。ここに［１，ω］は、整数環Ｏ_Ｋの標準基底である。
（暗号化処理：図２）
暗号化処理部は、平文変換器（２０１）、加算器Ｂ（２０２）から構成される。
長さ（ビット数）
【００１７】
【数２４】

の平文をＭとする。
（１）平文Ｍを入力し、平文変換器（２０１）を用いて、長さｎでＨａｍｍｉｎｇ（ハミング）重さがｋであるビット列ｍ＝｛ｍ_１，ｍ_２，・・・，ｍ_ｎ｝に変換する。
（２）平文変換器（２０１）で変換したｍと鍵生成処理部で求めた｛ｂ_１，ｂ_２，・・・，ｂ_ｎ｝を入力し、加算器Ｂ（２０２）を用いて、暗号文
【００１８】
【数２５】

【００１９】
を生成して出力する。
（復号処理：図３）
復号処理部は、乗算・剰余及び減算器（３０１）、巾乗剰余器（３０２）、因子判定器（３０３）、中間復号文変換器（３０４）から構成される。
（１）暗号文ｃ、ｋ、ｑ、秘密鍵ｄを入力し、乗算・剰余及び減算器（３０１）を用いてｒ＝（ｃ−ｋｄ） ｍｏｄ（ｑ−１）を求める。
（２）次に、秘密鍵ｇ、ｐ’と乗算・剰余及び減算器（３０１）で生成したｒを入力し、巾乗剰余器（３０２）を用いて、ｒからｕ＝ｇ^ｒ （ｍｏｄ ｐ’）を生成する。
（３）さらに、巾乗剰余器（３０２）で生成したｕと剰余類判定器（１０３）で生成した｛ｐ_１，ｐ_２，・・・，ｐ_ｎ｝を入力し、因子判定器（３０３）を用いて、長さｎでＨａｍｍｉｎｇ重さｋであるビット列ｍ＝｛ｍ_１，ｍ_２，・・・，ｍ_ｎ｝を、ｐ_ｉ がｕの因子ならばｍ_ｉ＝１とし、因子でないならば、ｍ_ｉ＝０とすることにより求める。
（４）最後に、中間復号文変換器（３０４）を用いて、因子判定器（３０３）で求めたｍを平文Ｍに変換して出力する。
【００２０】
【発明の効果】
本発明で実現する公開鍵暗号システムは、鍵生成処理において素イデアルを法として整数環の剰余類群上の離散対数問題を解くアルゴリズムを利用すること、及び、ｐ，ｐ_１，ｐ_２，・・・，ｐ_ｎ，ｇ，ｄを秘密にすることにより、公開鍵から秘密鍵を直接求める攻撃に耐えうる。また、暗号化処理と復号処理において、長さ
【００２１】
【数２６】

【００２２】
の整数の平文と長さｎでハミング重さｋであるビット列との変換を利用することにより、ナップサック暗号の安全性の指標であるｄｅｎｓｉｔｙ（密度）を十分に高めることができ、したがって、平文から暗号文を直接求めるｌｏｗ−ｄｅｎｓｉｔｙ攻撃に対しても安全である。なお、安全性などの詳細な議論については、文献（Ｔ．Ｏｋａｍｏｔｏ，Ｋ．Ｔａｎａｋａ，Ｓ．Ｕｃｈｉｙａｍａ，”Ｑｕａｎｔｕｍ Ｐｕｂｌｉｃ−Ｋｅｙ Ｃｒｙｐｔｏｓｙｓｔｅｍｓ”，Ｐｒｏｃ．ｏｆ ＣＲＹＰＴＯ２０００，Ｓｐｒｉｎｇｅｒ２０００）を参照されたい。
【図面の簡単な説明】
【図１】本発明の鍵生成処理部の構成図。
【図２】本発明の暗号化処理部の構成図。
【図３】本発明の復号処理部の構成図。
【符号の説明】
１０１ 乱数発生器Ａ
１０２ 互素判定器
１０３ 剰余類判定器
１０４ 乱数発生器Ｂ
１０５ 離散対数器
１０６ 乱数発生器Ｃ
１０７ 加算器Ａ
２０１ 平文変換器
２０２ 加算器Ｂ
３０１ 乗算・剰余及び減算器
３０２ 巾乗剰余器
３０３ 因子判定器
３０４ 中間復号文変換器[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a public key encryption / decryption method and system, and more particularly to a public key encryption / decryption method and system based on the knapsack problem.
[0002]
[Prior art]
Public key cryptosystems are categorized by their security issues.
Problems that can be based on this include prime factorization problems, discrete logarithm problems, and knapsack problems. Currently, most public key cryptosystems that are considered to be safe and practical are based on prime factorization and discrete logarithm problems, and as a public key cryptosystem that uses the knapsack problem as a source of security. , Markle-Hellman ciphers and Chor-Rivest ciphers have been proposed, but most of them have not been analyzed sufficiently, or some successful reports have been reported. ing.
[0003]
[Problems to be solved by the invention]
The prime factorization problem and the discrete logarithm problem, which are the problems used in current practical public key cryptosystems, can be realized when the so-called quantum computer is realized by using the algorithm proposed by Shor. It is known that public key cryptosystems that are solved very efficiently, that is, based on them, are completely decrypted. Literature (P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logics on a quantum computer”, SIAM J. Comput. 26, 5 (Oct. 1997), 14: 1997.14.
The present invention realizes a new public key encryption / decryption method and system that makes the knapsack problem a source of security, which is difficult to decrypt even if a quantum computer is realized.
[0004]
[Means for Solving the Problems]
In the present invention, a key generation process is performed using an integer ring of an algebraic field, its prime ideal, and its residue class field, and an algorithm for solving the discrete logarithm problem is further used to obtain the length.
[Equation 19]

Represents a binomial coefficient, that is, the number of combinations for selecting k out of n. As a further note, for the terms of number theory such as algebraic fields, integer rings, and prime ideals used here, refer to literature (written by Takayoshi Kawada, published by “Number Theory”, published by Iwanami Shoten), especially ordinary integers. When we need to distinguish between algebraic integers and algebraic integers, we call ordinary integers rational numbers.
[0006]
DETAILED DESCRIPTION OF THE INVENTION
FIG. 1 shows a configuration diagram of a key generation processing unit, FIG. 2 shows an encryption processing unit, and FIG. 3 shows a decryption processing unit.
An embodiment of a configuration method of a public key cryptosystem used in the present invention will be described with reference to FIG. 1, FIG. 2, and FIG.
(Key generation process: Fig. 1)
The key generation processing unit includes a random number generator A (101), a homology determiner (102), a residue class determiner (103), a random number generator B (104), a discrete logarithm (105), and a random number generator C ( 106) and an adder A (107).
[0007]
l following (El order) algebraic K, integral ring _O K of K, prime ideal p of _{O K} ', coset body _O K / p' one complete representative system R _p of = GF (q) _', and n Make k public a rational integer.
_{(1) K, O K,} p ', n, k, R p' is input to the random number generator A (101), a random number generator A (101),互素determiner (102) and coset determiner (103) using, from the ring of integers _{O K {p 1, p 2} , ···, p n} is the norm is disjoint in this any subset _{{p i1,} p _i2, ··· , P _in } is [0008]
[Expression 20]

[0009]
N integers {p ₁ , p ₂ ,..., P _n } that satisfy the above are generated.
(2) using a random number generator B (104), generates a multiplicative group ^{_{(O K / p) × =}} GF (q) generator g of ^×.
(3) Next, n integers {p ₁ , p ₂ ,..., P _n } generated by the residue classifier (103) and the generator g generated by the random number generator B (104) are input. and, using a discrete logarithm calculator to (105), _a 1 which satisfies _{p i ≡g} ^ai for each 1 ≦ i ≦ n (mod p '), a 2, ···, the _{a n} Ask.
(3) Furthermore, the random number generator C (106) is used to generate an integer (random number) d from Z / (q-1) Z (an integer field modulo (q-1)).
(4) Finally, enter a discrete _{a 1,} a 2 determined by the logarithm calculator (105), · · ·, _{a n} and random number generator integer generated by C (106) (random number) d, the adder Using A (107), the public key b _i = (a _i + d) mod (q−1) is obtained and output for each 1 ≦ i ≦ n.
(About the residue classifier (102))
Two methods for realizing the remainder classifier (102) will be described.
[0010]
Using the random number generator A (101), if {p ₁ , p ₂ ,..., P _n } are all selected as prime integers that are relatively prime, the norm of the prime ideal p ′ is set to N (p ′ ) = P ^f (where p is a rational prime number and f is a natural number), this arbitrary subset {p _i1 , p _i2 ,..., P _ik } is expressed as follows.
[Expression 21]

[0012]
Can be determined by whether or not
Next, if K is an imaginary quadratic field K = Q (√ (−D)) of discriminant −D, if the prime ideal p ′ is secondary, that is, f = 2, −D≡ 2, 3 (mod 4), n integers {p ₁ , p ₂ ,..., P _n } whose norms are relatively prime, and this arbitrary subset {p _i1 , p _i2 ,. , P _ik } is [0013]
[Expression 22]

[0014]
Judgment is made based on whether or not
On the other hand, if -D≡1 (mod 4),
[0015]
[Expression 23]

[0016]
It is determined whether or not However, in this case, the complete representative system is R _{p ′} = {x + yω | −p / 2 <x, y <−p / 2}. Here [1, omega] is the standard basis integer ring _{O K.}
(Encryption processing: Fig. 2)
The encryption processing unit includes a plaintext converter (201) and an adder B (202).
Length (number of bits)
[0017]
[Expression 24]

Let M be the plaintext of.
(1) A plain text M is input, and a bit string m = {m ₁ , m ₂ ,..., M _n } having a length n and a Hamming weight k is input using the plaintext converter (201). Convert to
(2) plain transducer obtained in converted m and the key generation processing unit in _{(201) {b 1, b} 2, ···, b n} enter a, using the adder B (202), encryption Sentence [0018]
[Expression 25]

[0019]
Is generated and output.
(Decoding process: FIG. 3)
The decryption processing unit includes a multiplier / residue and subtracter (301), a power multiplier remainder (302), a factor determiner (303), and an intermediate decrypted text converter (304).
(1) The ciphertexts c, k, q, and the secret key d are input, and r = (c−kd) mod (q−1) is obtained using the multiplication / remainder and subtractor (301).
(2) Next, the secret keys g and p ′ and the multiplier / remainder and r generated by the subtractor (301) are input, and from the r, u = g ^r (mod p ').
(3) Furthermore, u generated by the modular exponentiation unit (302) and {p ₁ , p ₂ ,..., P _n } generated by the residue classifier (103) are input, and a factor determiner (303 ), A bit string m = {m ₁ , m ₂ ,..., M _n } having a length n and a Hamming weight k is set to m _i = 1 if p _i is a factor of u, and is not a factor. Then, it is obtained by setting m _i = 0.
(4) Finally, using the intermediate decrypted text converter (304), m obtained by the factor determiner (303) is converted into plain text M and output.
[0020]
【The invention's effect】
The public key cryptosystem realized by the present invention uses an algorithm for solving a discrete logarithm problem on a residue class group of an integer ring using a prime ideal in a key generation process, and p, p ₁ , p ₂ ,. • By keeping _pn , g, and d secret, it is possible to withstand an attack that directly obtains a secret key from a public key. In the encryption process and the decryption process, the length [0021]
[Equation 26]

[0022]
By using the conversion between the plaintext of the integer of n and the bit string having the length n and the Hamming weight k, the density (density) that is an index of security of the knapsack encryption can be sufficiently increased. It is safe against a low-density attack that directly asks for ciphertext. For detailed discussions such as safety, refer to the literature (T. Okamoto, K. Tanaka, S. Uchiyama, “Quantum Public-Key Cryptossystems”, Proc. Of CRYPTO2000, Springer 2000).
[Brief description of the drawings]
FIG. 1 is a configuration diagram of a key generation processing unit of the present invention.
FIG. 2 is a configuration diagram of an encryption processing unit of the present invention.
FIG. 3 is a block diagram of a decoding processing unit of the present invention.
[Explanation of symbols]
101 Random number generator A
102 homology determiner 103 residue class determiner 104 random number generator B
105 Discrete logarithm 106 Random number generator C
107 Adder A
201 plaintext converter 202 adder B
301 Multiplier / Remainder and Subtractor 302 Depth Multiplier 303 Factor Determiner 304 Intermediate Decrypted Text Converter

Claims (6)

A key generation processing unit, an encryption processing unit, and a decryption processing unit;
The key generation processing unit
l next generation number field K, an integer ring _O K of K, prime ideal p of _{O K} ', coset body _{O K / p' = GF (} q) one complete representative system R _{p ',} its origin g (mod p '), rational integer n, when a k, n number of elements of _{O K {p 1, p 2} , ···, p n} , the respective norm _{n (p 1), ···,} n For an arbitrary subset {p _i1 , p _i2 ,..., P _ik } of (p _n ) disjoint and consisting of the k elements.

To produce what _{the, p 1, p 2, ···} , from _{p n, p i ≡g} ^ai rational integers _a 1 that satisfies (mod p ') for each 1 ≦ i ≦ n, a _2, ···, generates _{a n (1 ≦ a i <} q-1), randomly d from Z / (q-1) Z (( integer body to q-1) modulo) And a public key b _i = (a _i + d) mod (q−1) is generated for each 1 ≦ i ≦ _n from a ₁ , a ₂ ,.
The encryption processor
length

When the plaintext was M, a M, a Hamming weight k with length n bit string _m = convert _(m 1, m 2, · · ·, _{m n),} the ciphertext from m

Produces
The decryption processor
R = (c−kd) mod (q−1) is generated from the ciphertext c, u = g ^r (mod p ′) is calculated from ^r , and the bit string m = (length n and Hamming weight k) m ₁ , m ₂ ,..., m _n ) is generated by setting m _i = 1 if p _i is a factor of u, and by setting m _i = 0 if p _i is not a factor. A public key encryption / decryption method using an algebraic field, characterized by converting. A key generation processing unit and an encryption processing unit,
The key generation processing unit
l next generation number field K, an integer ring _O K of K, prime ideal p of _{O K} ', coset body _{O K / p' = GF (} q) one complete representative system R _{p ',} its origin g (mod p '), rational integer n, when a k, n number of elements of _{O K {p 1, p 2} , ···, p n} , the respective norm _{n (p 1), ···,} n For an arbitrary subset {p _i1 , p _i2 ,..., P _ik } of (p _n ) disjoint and consisting of the k elements.

To produce what _{the, p 1, p 2, ···} , from _{p n, p i ≡g} ^ai rational integers _a 1 that satisfies (mod p ') for each 1 ≦ i ≦ n, a _2, ···, generates _{a n (1 ≦ a i <} q-1), randomly d from Z / (q-1) Z (( integer body to q-1) modulo) And a public key b _i = (a _i + d) mod (q−1) is generated for each 1 ≦ i ≦ _n from a ₁ , a ₂ ,.
The encryption processor
length

When the plaintext was M, a M, a Hamming weight k with length n bit string _m = convert _(m 1, m 2, · · ·, _{m n),} the ciphertext from m

A public key encryption method using an algebraic field, characterized in that As the key generation process, l next generation number field K, an integer ring _O K of K, prime ideal of _{O K} p ', coset body _{O K / p' = GF (} q) one complete representative system R _{p ',} its a generator g (mod p '), rational integer n, when a k, n number of elements of _{O K {p 1, p 2} , ···, p n} , the respective norm n _(p 1), .., N (p _n ) are relatively prime, and for an arbitrary subset {p _i1 , p _i2 ,..., P _ik } consisting of k elements.

To produce what _{the, p 1, p 2, ···} , from _{p n, p i ≡g} ^ai rational integers _a 1 that satisfies (mod p ') for each 1 ≦ i ≦ n, a _2, ···, generates _{a n (1 ≦ a i <} q-1), randomly d from Z / (q-1) Z (( integer body to q-1) modulo) And a public key b _i = (a _i + d) mod (q−1) is generated for each 1 ≦ i ≦ _n from a ₁ , a ₂ ,.
As an encryption process,
length

When the plaintext was M, a M, a Hamming weight k with length n bit string _m = convert _(m 1, m 2, · · ·, _{m n),} the ciphertext from m

The ciphertext c generated by the encryption method for generating
The decryption processor
R = (c−kd) mod (q−1) is generated from the ciphertext c, u = g ^r (mod p ′) is calculated from ^r , and the bit string m = (length n and Hamming weight k) m ₁ , m ₂ ,..., m _n ) is generated by setting m _i = 1 if p _i is a factor of u, and by setting m _i = 0 if p _i is not a factor. A public key decryption method using an algebraic field, characterized by converting. As key generation processing,
l next generation number field K, an integer ring _O K of K, prime ideal p of _{O K} ', coset body _{O K / p' = GF (} q) one complete representative system R _{p ',} its origin g (mod p ′) and rational integers n and k,
N elements of _{O K {p 1, p 2} , ···, p n} , the respective norm _{N (p 1), ···,} N (p n) are relatively prime, that the k For an arbitrary subset {p _i1 , p _i2 ,..., P _ik } consisting of elements of

A residue classifier that generates
From p ₁ , p ₂ ,..., _pn , rational integers a ₁ , a ₂ ,... satisfying p _i ≡g ^ai (mod p ′) for each 1 ≦ i ≦ n. a discrete logarithm that generates a _n (1 ≦ a _i <q−1);
Z / (q-1) Z (an integer field modulo (q-1)) is taken at random, and from a ₁ , a ₂ ,..., _An , each 1 ≦ i ≦ an adder A that generates a public key b _i = (a _i + d) mod (q−1) for n;
As an encryption process,
length

When the plaintext was M, a M, a Hamming weight k with length n bit string _m = convert _(m 1, m 2, · · ·, _{m n),} the ciphertext from m

An adder B for generating
As a decryption process,
R = (c−kd) mod (q−1) is generated from the ciphertext c, u = g ^r (mod p ′) is calculated from ^r , and the bit string m = (length n and Hamming weight k) m ₁ , m ₂ ,..., m _n ),
If p _i is a factor of u, a factor discriminator is generated by setting m _i = 1, and if p _i is not a factor, m _i = 0,
A public key encryption / decryption system using an algebraic field, comprising an intermediate decryption text converter for converting m into plaintext M. As key generation processing,
l next generation number field K, an integer ring _O K of K, prime ideal p of _{O K} ', coset body _{O K / p' = GF (} q) one complete representative system R _{p ',} its origin g (mod p ′) and rational integers n and k,
N elements of _{O K {p 1, p 2} , ···, p n} , the respective norm _{N (p 1), ···,} N (p n) are relatively prime, that the k For an arbitrary subset {p _i1 , p _i2 ,..., P _ik } consisting of elements of

A residue classifier that generates
From p ₁ , p ₂ ,..., _pn , rational integers a ₁ , a ₂ ,... satisfying p _i ≡g ^ai (mod p ′) for each 1 ≦ i ≦ n. a discrete logarithm that generates a _n (1 ≦ a _i <q−1);
Z / (q-1) Z (an integer field modulo (q-1)) is taken at random, and from a ₁ , a ₂ ,..., _An , each 1 ≦ i ≦ an adder A that generates a public key b _i = (a _i + d) mod (q−1) for n,
As an encryption process,
length

When the plaintext was M, a M, a Hamming weight k with length n bit string _m = convert _(m 1, m 2, · · ·, _{m n),} the ciphertext from m

A public key encryption device using an algebraic field, characterized by comprising an adder B that generates As key generation processing,
l next generation number field K, an integer ring _O K of K, prime ideal p of _{O K} ', coset body _{O K / p' = GF (} q) one complete representative system R _{p ',} its origin g (mod p ′) and rational integers n and k,
N elements of _{O K {p 1, p 2} , ···, p n} , the respective norm _{N (p 1), ···,} N (p n) are relatively prime, that the k For an arbitrary subset {p _i1 , p _i2 ,..., P _ik } consisting of elements of

A residue classifier that generates
From p ₁ , p ₂ ,..., _pn , rational integers a ₁ , a ₂ ,... satisfying p _i ≡g ^ai (mod p ′) for each 1 ≦ i ≦ n. a discrete logarithm that generates a _n (1 ≦ a _i <q−1);
Z / (q-1) Z (an integer field modulo (q-1)) is taken at random, and from a ₁ , a ₂ ,..., _An , each 1 ≦ i ≦ an adder A that generates a public key b _i = (a _i + d) mod (q−1) for n,
As an encryption process,
length

When the plaintext was M, a M, a Hamming weight k with length n bit string _m = convert _(m 1, m 2, · · ·, _{m n),} the ciphertext from m

The ciphertext c generated by the encryption device including the adder B that generates
As a decryption process,
R = (c−kd) mod (q−1) is generated from the ciphertext c, u = g ^r (mod p ′) is calculated from ^r , and the bit string m = (length n and Hamming weight k) m ₁ , m ₂ ,..., m _n ),
If p _i is a factor of u, a factor discriminator is generated by setting m _i = 1, and if p _i is not a factor, m _i = 0,
A public key decryption device using an algebraic field, comprising an intermediate decryption text converter for converting m into plaintext M.

Images