Naccache–Stern cryptosystem

Last updated January 29, 2023 • 1 min readFrom Wikipedia, The Free Encyclopedia

The Naccache–Stern cryptosystem is a homomorphic public-key cryptosystem whose security rests on the higher residuosity problem. The Naccache–Stern cryptosystem was discovered by David Naccache and Jacques Stern in 1998.

Scheme Definition

Like many public key cryptosystems, this scheme works in the group $(\mathbb {Z} /n\mathbb {Z} )^{*}$ where n is a product of two large primes. This scheme is homomorphic and hence malleable.

Key Generation

Pick a family of k small distinct primes p₁,...,p_k.
Divide the set in half and set $u=\prod _{i=1}^{k/2}p_{i}$ and $v=\prod _{k/2+1}^{k}p_{i}$ .
Set $\sigma =uv=\prod _{i=1}^{k}p_{i}$
Choose large primes a and b such that both p = 2au+1 and q=2bv+1 are prime.
Set n=pq.
Choose a random g mod n such that g has order φ(n)/4.

The public key is the numbers σ,n,g and the private key is the pair p,q.

When k=1 this is essentially the Benaloh cryptosystem.

Message Encryption

This system allows encryption of a message m in the group $\mathbb {Z} /\sigma \mathbb {Z}$ .

Pick a random $x\in \mathbb {Z} /n\mathbb {Z}$ .
Calculate $E(m)=x^{\sigma }g^{m}\mod n$

Then E(m) is an encryption of the message m.

Message Decryption

To decrypt, we first find m mod p_i for each i, and then we apply the Chinese remainder theorem to calculate m mod $\sigma$ .

Given a ciphertext c, to decrypt, we calculate

$c_{i}\equiv c^{\phi (n)/p_{i}}\mod n$ . Thus

{\begin{matrix}c^{\phi (n)/p_{i}}&\equiv &x^{\sigma \phi (n)/p_{i}}g^{m\phi (n)/p_{i}}\mod n\\&\equiv &g^{(m_{i}+y_{i}p_{i})\phi (n)/p_{i}}\mod n\\&\equiv &g^{m_{i}\phi (n)/p_{i}}\mod n\end{matrix}}

where $m_{i}\equiv m\mod p_{i}$ .

Since p_i is chosen to be small, m_i can be recovered by exhaustive search, i.e. by comparing $c_{i}$ to $g^{j\phi (n)/p_{i}}$ for j from 1 to p_i-1.
Once m_i is known for each i, m can be recovered by a direct application of the Chinese remainder theorem.

Security

The semantic security of the Naccache–Stern cryptosystem rests on an extension of the quadratic residuosity problem known as the higher residuosity problem.

Related Research Articles

In analytic number theory and related branches of mathematics, a complex-valued arithmetic function $:\mathbb {Z} \rightarrow \mathbb {C} }$ is a Dirichlet character of modulus if for all integers $and :$

Stellar dynamics is the branch of astrophysics which describes in a statistical way the collective motions of stars subject to their mutual gravity. The essential difference from celestial mechanics is that the number of body

The Paillier cryptosystem, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing n-th residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based.

In mathematics, specifically the algebraic theory of fields, a normal basis is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of fields has a normal basis. In algebraic number theory, the study of the more refined question of the existence of a normal integral basis is part of Galois module theory.

In abstract algebra, Hilbert's Theorem 90 (or Satz 90) is an important result on cyclic extensions of fields (or to one of its generalizations) that leads to Kummer theory. In its most basic form, it states that if L/K is an extension of fields with cyclic Galois group G = Gal(L/K) generated by an element $and if is an element of L of relative norm 1, that is$

The Ramanujan tau function, studied by Ramanujan (1916), is the function $:\mathbb {N} \rightarrow \mathbb {Z} }$ defined by the following identity:

In mathematics and theoretical physics, a locally compact quantum group is a relatively new C*-algebraic approach toward quantum groups that generalizes the Kac algebra, compact-quantum-group and Hopf-algebra approaches. Earlier attempts at a unifying definition of quantum groups using, for example, multiplicative unitaries have enjoyed some success but have also encountered several technical problems.

In number theory, the law of quadratic reciprocity, like the Pythagorean theorem, has lent itself to an unusually large number of proofs. Several hundred proofs of the law of quadratic reciprocity have been published.

Homomorphic encryption is a form of encryption that permits users to perform computations on its encrypted data without first decrypting it. These resulting computations are left in an encrypted form which, when decrypted, result in an identical output to that produced had the operations been performed on the unencrypted data. Homomorphic encryption can be used for privacy-preserving outsourced storage and computation. This allows data to be encrypted and out-sourced to commercial cloud environments for processing, all while encrypted.

The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem (GM) created in 1985 by Josh (Cohen) Benaloh. The main improvement of the Benaloh Cryptosystem over GM is that longer blocks of data can be encrypted at once, whereas in GM each bit is encrypted individually.

The Naccache–Stern Knapsack cryptosystem is an atypical public-key cryptosystem developed by David Naccache and Jacques Stern in 1997. This cryptosystem is deterministic, and hence is not semantically secure. While unbroken to date, this system also lacks provable security.

In cryptography, most public key cryptosystems are founded on problems that are believed to be intractable. The higher residuosity problem is one such problem. This problem is easier to solve than integer factorization, so the assumption that this problem is hard to solve is stronger than the assumption that integer factorization is hard.

In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently. It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.

The Damgård–Jurik cryptosystem is a generalization of the Paillier cryptosystem. It uses computations modulo $where is an RSA modulus and a (positive) natural number. Paillier's scheme is the special case with . The order of can be divided by . Moreover, can be written as the direct product of . is cyclic and of order, while is isomorphic to . For encryption, the message is transformed into the corresponding coset of the factor group and the security of the scheme relies on the difficulty of distinguishing random elements in different cosets of . It is semantically secure if it is hard to decide if two given elements are in the same coset. Like Paillier, the security of Damgård-Jurik can be proven under the decisional composite residuosity assumption.$

The Okamoto–Uchiyama cryptosystem is a public key cryptosystem proposed in 1998 by Tatsuaki Okamoto and Shigenori Uchiyama. The system works in the multiplicative group of integers modulo n, $, where n is of the form p 2 q and p and q are large primes.$

In computer science, a trace is a set of strings, wherein certain letters in the string are allowed to commute, but others are not. It generalizes the concept of a string, by not forcing the letters to always be in a fixed order, but allowing certain reshufflings to take place. Traces were introduced by Pierre Cartier and Dominique Foata in 1969 to give a combinatorial proof of MacMahon's master theorem. Traces are used in theories of concurrent computation, where commuting letters stand for portions of a job that can execute independently of one another, while non-commuting letters stand for locks, synchronization points or thread joins.

In mathematics the Function Field Sieve is one of the most efficient algorithms to solve the Discrete Logarithm Problem (DLP) in a finite field. It has heuristic subexponential complexity. Leonard Adleman developed it in 1994 and then elaborated it together with M. D. Huang in 1999. Previous work includes the work of D. Coppersmith about the DLP in fields of characteristic two.

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.

Magnetic topological insulators are three dimensional magnetic materials with a non-trivial topological index protected by a symmetry other than time-reversal. In contrast with a non-magnetic topological insulator, a magnetic topological insulator can have naturally gapped surface states as long as the quantizing symmetry is broken at the surface. These gapped surfaces exhibit a topologically protected half-quantized surface anomalous Hall conductivity perpendicular to the surface. The sign of the half-quantized surface anomalous Hall conductivity depends on the specific surface termination.

In first-order arithmetic, the induction principles, bounding principles, and least number principles are three related families of first-order principles, which may or may not hold in nonstandard models of arithmetic. These principles are often used in reverse mathematics to calibrate the axiomatic strength of theorems.

References

Naccache, David; Stern, Jacques (1998). "A New Public Key Cryptosystem Based on Higher Residues". Proceedings of the 5th ACM Conference on Computer and Communications Security. CCS '98. ACM. pp. 59–66. doi: 10.1145/288090.288106 . ISBN 1-58113-007-4.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.