text:
# Hidden Polynomial(s) Cryptosystems

## 1. Introduction

This paper focuses on Hidden Monomial Cryptosystems, a class of public key (PK) cryptosystems first proposed by Imai and Matsumoto \[IM85\]. In this class, the PK is a system of polynomial nonlinear equations. The private key is the set of parameters that the user chooses to construct the equations. Before we discuss our variations, we review briefly a simplified version of the original cryptosystem, better described in \[Kob99\]. The parties throughout this paper are:

* Alice who wants to receive secure messages;
* Bob who wants to send her secure messages;
* Eve, the eavesdropper.

Alice takes two finite fields $`𝔽_q<𝕂`$, $`q`$ a power of $`2`$, and $`\beta _1,\beta _2,\mathrm{},\beta _n`$ a basis of $`𝕂`$ as an $`𝔽_q`$-vector space. Next she takes $`0<h<q^n`$ such that $`h=q^\theta +1`$, and $`gcd(h,q^n1)=1`$. Then she takes two generic vectors $`𝐮=(u_1,\mathrm{},u_n)`$ and $`𝐯=(v_1,\mathrm{},v_n)`$ upon $`𝔽_q`$, and sets111In this paper we reserve boldface to the elements of $`𝕂`$ thought as vectors upon $`𝔽_q`$ in the fixed private basis. They are considered vectors or field elements, as convenient, without further notice. This shift in practice takes a Chinese Remainder Theorem. Cryptosystem and scheme are synonyms.:

(1)
$$𝐯=𝐮^{q^\theta }𝐮.$$

The condition $`gcd(h,q^n1)=1`$ is equivalent to requiring that the map $`𝐮𝐮^h`$ on $`𝕂`$ is $`\mathit{1}\mathit{1}`$; its inverse is the map $`𝐮𝐮^h^{},`$ where $`h^{}`$ is the inverse multiplicative of $`h`$ modulo $`q^n1`$.

In addition, Alice chooses two secret affine transformations, i.e., two invertible matrices $`A=\{A_{ij}\}`$ and $`B=\{B_{ij}\}`$ with entries in $`𝔽_q`$, and two constant vectors $`𝐜=(c_1,\mathrm{},c_n)`$ and $`𝐝=(d_1,\mathrm{},d_n)`$, and sets:

(2)
$$𝐮=A𝐱+𝐜\text{and}𝐯=B𝐲+𝐝.$$

Recall that the operation of raising to the $`q^k`$-th power in $`𝕂`$ is an $`𝔽_q`$-linear transformation. Let $`P^{(k)}=\{p_{ij}^{(k)}\}`$ be the matrix of this linear transformation in the basis $`\beta _1,\beta _2,\mathrm{},\beta _n`$, i.e.:

(3)
$$\beta _i^{q^k}=\underset{j=1}{\overset{n}{}}p_{ij}^{(k)}\beta _j,p_{ij}^{(k)}𝔽_q,$$

for $`1i,kn`$. Alice also writes all products of basis elements in terms of the basis, i.e.:

(4)
$$\beta _i\beta _j=\underset{\mathrm{}=1}{\overset{n}{}}m_{ij\mathrm{}}\beta _{\mathrm{}},m_{ij\mathrm{}}𝔽_q,$$

for each $`1i,jn`$. Now she expands the equation (1). So she obtains a system of equations, explicit in the $`v`$, and quadratic in the $`u`$. She uses now her affine relations (2) to replace the $`u,v`$ by the $`x,y`$. So she obtains $`n`$ equations, linear in the $`y`$, and of degree $`2`$ in the $`x`$. Using linear algebra, she can get $`n`$ explicit equations, one for each $`y`$ as polynomials of degree $`2`$ in the $`x`$.

Alice makes these equations public. Bob to send her a message $`(x_1,x_2,\mathrm{},x_n)`$, substitutes it into the public equations. So he obtains a linear system of equations in the $`y`$. He solves it, and sends $`𝐲=(y_1,y_2,\mathrm{},y_n)`$ to Alice.

To eavesdrop, Eve has to substitute $`(y_1,y_2,\mathrm{},y_n)`$ into the public equations, and solve the nonlinear system of equations for the unknowns $`x`$.

When Alice receives y, she decrypts:

$`y_1,y_2,\mathrm{},y_n`$
$``$
$`𝐯=B𝐲+𝐝`$
$``$
$`𝐯={\displaystyle v_i\beta _i}`$
$``$
$`𝐮=𝐯^h^{}`$
$``$
$`𝐱=A^1(𝐮𝐜).`$
In Eurocrypt $`{}_{}{}^{}88`$ \[IM89\], Imai and Matsumoto proposed a digital signature algorithm for their cryptosystem.

At Crypto $`{}_{}{}^{}95`$, Jacques Patarin \[Pat95\] showed how to break this cryptosystem. He noticed that if one takes the equation $`𝐯=𝐮^{q^\theta +1}`$, raises both sides on the $`(q^\theta 1)`$-th power, and multiplies both sides by $`\mathrm{𝐮𝐯}`$, he gets the equation $`\mathrm{𝐮𝐯}^{q^\theta }=𝐮^{q^{2\theta }}𝐯`$ that leads to equations in the $`x`$, $`y`$, linear in both sets of variables. Essentially the equations do not suffice to identify uniquely the message, but now even an exhaustive search will be feasible. The system was definitively insecure and breakable, but its ideas inspired a whole class of PK cryptosystems and digital signatures based on structural identities for finite field operations \[HFE, Moh99, Kob99, Pat96a, Pat96b, GP\].

The security of this class rests on the difficulty of the problem of solving systems of nonlinear polynomial equations. This problem is hard iff the equations are randomly chosen. If they really were random, the problem is hard to Alice, too. So, all we try to do is to get systems of equations that are not random, but appear to be the most possible.

Our paper is organized as follows. In the next section we develop an our own, new cryptosystem. Alice builds her PK by manipulations as above, starting from a certain bivariate polynomial.

All of Alice’s manipulations are meant to hide from Eve this polynomial. It is the most important part of the private key. Its knowledge reduces decryption to the relatively easy problem of solving a single univariate polynomial of a moderate degree.

Encryption is probabilistic, in the sense that to a given cleartext correspond zero, one, or more ciphertexts. Decryption is deterministic, in the sense that if encryption succeeds, decryption does succeed, too.

Almost any bivariate nonlinear polynomial can give raise to a PK. This plentitude of choices is an important security parameter.

In the third section we discuss some security issues. In the fourth one we provide our cryptosystem with a digital signature algorithm.

In the fifth we provide a signcryption protocol. Signcryption stands for joint encryption and signature.

In the sixth one we discuss some more variations. Essentially, we replace the single bivariate polynomial by an ideal of a small size.

In the seventh section we mention what Shannon \[Sti02\] calls unconditionally secure cryptosystems. Nowadays they are considered an exclusive domain of the private key cryptography. This is due mostly to the unhappy state of art of the PK one.

In the eighth one we extend our constructions to differential fields of positive characteristic. We hope they are the suitable environment for unconditionally secure PK (USPK) cryptosystems.

## 2. A New Cryptosystem

### 2.1. Key Generation

Alice chooses two finite fields $`𝔽_q<𝕂`$, and a basis $`\beta _1,\beta _2,\mathrm{},\beta _n`$ of $`𝕂`$ as an $`𝔽_q`$-vector space. In practice, $`q=2`$. However, it can be any $`p^r`$, for any $`p`$ prime, and any $`r`$.

Next Alice takes a generic (for now) bivariate polynomial:

(5)
$$f(X,Y)=\underset{ij}{}𝐚_{ij}X^iY^j$$

in $`𝕂[X,Y]`$, such that she is able to find all its roots in $`𝕂`$ with respect to $`X`$; $``$ $`Y𝕂`$, if any. For the range of $`i`$ employed, this is nowadays considered a relatively easy problem. Further, $`f(X,Y)`$ is subject to other few constraints, that we make clear at the opportune moment.

In transforming cleartext into ciphertext message, Alice will work with two intermediate vectors, $`𝐮=(u_1,\mathrm{},u_n)`$ and $`𝐯=(v_1,\mathrm{},v_n)`$; $`𝐮,𝐯𝕂`$. She sets:

(6)
$$\underset{ij}{}𝐚_{ij}𝐮^i𝐯^j=0.$$

For $`𝐚_{ij}0`$, she sets somehow:

(7)
$$i=\underset{k=1}{\overset{n_i}{}}q^{\theta _{ik}}\text{and}j=\underset{k=1}{\overset{n_j}{}}q^{\theta _{jk}},$$

where $`\theta _{ik},\theta _{jk},n_i,n_j,i,j_{}=\{0,1,2,\mathrm{}\}`$.

Here somehow means that (7) may or may not be the $`q`$-ary representation of $`i`$, $`j`$. Taking this freedom, we increase our range of choices, whence the random-looking of the PK. In any fashion, what we are dealing with, are nothing but identities.

Next Alice substitutes the (7) to the exponents in (6), obtaining:

(8)
$$\underset{ij}{}(𝐚_{ij}exp(𝐮,\underset{k=1}{\overset{n_i}{}}q^{\theta _{ik}})exp(𝐯,\underset{k=1}{\overset{n_0}{}}q^{\theta _{jk}}))=0;$$

that is:

(9)
$$\underset{ij}{}(𝐚_{ij}\underset{k=1}{\overset{n_i}{}}𝐮^{q^{\theta _{ik}}}\underset{k=1}{\overset{n_j}{}}𝐯^{q^{\theta _{jk}}})=0.$$

Recall that the operation of raising to the $`q^k`$-th power in $`𝕂`$ is an $`𝔽_q`$-linear transformation. Let $`P^{(k)}=\{p_\mathrm{}m^{(k)}\}`$ be the matrix of this linear transformation in the basis $`\beta _1,\beta _2,\mathrm{},\beta _n`$, i.e.:

(10)
$$\beta _i^{q^k}=\underset{j=1}{\overset{n}{}}p_{ij}^{(k)}\beta _j,p_{ij}^{(k)}𝔽_q;$$

for $`1i,jn`$. Alice also writes all products of basis elements in terms of the basis, i.e.:

(11)
$$\beta _i\beta _j=\underset{k=1}{\overset{n}{}}m_{ijk}\beta _k,m_{ijk}𝔽_q;$$

for $`1i,jn`$.

Now she substitutes $`𝐮=(u_1,u_2,\mathrm{},u_n)`$, $`𝐚_{ij}=(a_{ij1},a_{ij2},\mathrm{},a_{ijn})`$, $`𝐯=(v_1,v_2,\mathrm{},v_n)`$, and the identities (10), (11) to (9), and expands. So she obtains a system of $`n`$ equations of degree $`t`$ in the $`u`$, $`v`$, where:

(12)
$$t=max\{n_i+n_j:𝐚_{ij}0\}.$$

Every term under the $`\mathrm{\Sigma }`$ in (7) contributes by one to the size of $`t`$.

Here we pause to give some constraints on the range of $`i`$, $`j`$ in (6). The aim of this section is to generate a set of polynomials; linear in a set of variables, and nonlinear in another one. For that purpose, we relate (6) and (7): $`𝐚_{ij}0`$ $`\{n_i>1`$, $`n_j=1\}`$.

On the other side, the size of PK is $`𝒪(n^{t+1})`$. So, it grows polynomially with $`n`$, and exponentially with $`t`$. Therefore, we are interested to keep $`t`$ rather modest, e.g., $`t=2,3`$, or so. So, we have to choose $`i`$, $`j`$ in (5), (7) in order to keep $`t`$ under a forefixed bound.

Next she takes $`A=\{A_{ij}\},B=\{B_{ij}\}GL(𝔽_q)`$, $`𝐜,𝐝𝕂`$, and sets:

(13)
$$𝐮=A𝐱+𝐜\text{and}𝐯=B𝐲+𝐝,$$

where $`𝐱=(x_1,x_2,\mathrm{},x_n)`$, $`𝐲=(y_1,y_2,\mathrm{},y_n)`$ are vectors of variables.

Now she substitutes (13) to the equations in the $`u`$, $`v`$ above, and expands. So she obtains a system of $`n`$ equations of degree $`t`$ in the $`x`$, $`y`$; linear in the $`y`$, and nonlinear in the $`x`$.

After the (13) each monomial $`X_iY_j`$ expands into polynomials with terms of each degree, from $`n_i+n_j`$ to zero. So, they shuffle better the terms coming from different monomials of (9). On the other hand, they render the PK very dense, so increase drastically its size.

At this point, we are ready to define the cryptosystem.

### 2.2. The Protocol

With the notations adopted above, we define the HPE Cryptosystem (Hidden Polynomial Equations) as the PK cryptosystem such that:

* The public key is:

+ The set of the polynomial equations in the $`x`$, $`y`$ as above;
    + The field $`𝔽_q`$;
    + The alphabet: a set of elements of $`𝔽_q`$, or strings of them.
* The private key is:

+ The polynomial (5);
    + $`A`$, $`B`$, $`𝐜`$, $`𝐝`$ as in (13);
    + The identities (6) to (11);
    + The field $`𝕂`$.
* Encryption: Bob substitutes the cleartext $`𝐱=(x_1,x_2,\mathrm{},x_n)`$ in the public equations, solves with respect to the $`y`$, and sends $`𝐲=(y_1,y_2,\mathrm{},y_n)`$ to Alice. We assume that solutions exist, and postpone the case when there are not.
* Decryption: Alice substitutes $`𝐯=B𝐲+𝐝𝕂>𝔽_q`$ in (6), and finds all solutions within $`𝕂`$. There is at least one. Indeed, if $`𝐱`$ is Bob’s cleartext, $`𝐮`$ as in (13) is one. For each solution $`𝐮`$, she solves:

(14)
$$𝐱=A^1(𝐮𝐜),$$

and represents all solutions in the basis $`\beta _1,\beta _2,\mathrm{},\beta _n`$. It takes a Chinese Remainder Theorem. With probability $`1`$, all results but one, Bob’s $`(x_1,x_2,\mathrm{},x_n)`$, are gibberish, or even stretch out of the alphabet. We come back later at this point, too.

#### 2.2.1.

The main suspended question is that of the existence of solutions. Well, Bob succeeds to encrypt a certain message x iff Alice’s equation (6) has solutions for u as in (13) for that x. Alice’s polynomial (6) in v for a given u is a random one. It is a well-known fact from algebra that the probability that a random polynomial with coefficients upon a finite field has a root in it is $`1\frac{1}{e}63.2\%`$ \[Kob99, Mar97\].

Here the remedy is probabilistic. Alice renders the alphabet public with letters being sets of elements of $`𝔽_q`$, or sets of strings in it. Bob writes down a plaintext, and starts encryption. If he fails, he substitutes a letter or a string of the cleartext with another one of the same set, and retries. After $`s`$ trials, the probability he does not succeed is $`\frac{1}{e^s}`$; practically good enough.

#### 2.2.2.

The other problem is that Alice may have to distinguish the right solution among a great number of them. Here is a first remedy. Her number of solution is bounded above by the degree in $`X`$ of $`f`$. So, it is beter to keep it moderate. Later we give other remedies, too.

### 2.3. Observations

Solving univariate polynomial equations is used by Patarin, too \[Pat96b, Wol02\]. He takes a univariate polynomial:

$$f(x)=\underset{i,j}{}\beta _{ij}x^{q^{\theta _{ij}}+q^{\phi _{ij}}}+\underset{i}{}\alpha _ix^{q^{\xi _i}}+\mu _0,$$

and with manipulations like ours, both the same as Imai-Matsumoto \[IM85\], he gets his PK; a set of quadratic equations. He uses two affine transformations to shuffle the equations. We claim that the first one adds nothing to the security.

The bigger the degree of $`f`$ is, the more the PK resembles a randomly chosen set of quadratic equations. So, it is a security parameter. On the other side, it slows down decryption, principally by adding a lot of undesired solutions. To face that second problem, to the PK are added other, randomly chosen, equations. This is its Achilles’ heel. It makes the PK overdefined, therefore subject to certain facilities to solve \[SCPK\]. So, it weakens the trapdoor problem.

We do not add equations to discard undesired solutions. Indeed, we take the degree in $`X`$ rather modest, so we do not have so many undesired solutions. Thus, we are not subject to attacks exploiting overdefined equations. If in certain variations we ever do, we need to add less equations, however.

What is most important, we have now a practically infinite range of choices of $`f`$. This is not Patarin’s case. There the choices are bounded below because of being easy to attack cases, and above because of being impractical to the legitimate users.

The only few constraints we put on monomials of $`f`$ aim to:

* keep PK equations linear in the $`y`$;
* have less undesired solutions in decryption process;
* keep the size of PK moderate;
* keep all PK equations nonlinear in the $`x`$.

The constraint that all PK equations must be nonlinear in the $`x`$ is the only non-negotiable one. Indeed, if Alice violates it, the trapdoor problem becomes fatally easy to Gröbner techniques.

We can take the degree in y arbitrarily huge. It gives no trouble to us. We only require the monomials of $`f`$ to be of the form $`𝐱^i𝐲^{q^j}`$ for $`i,j_{}`$, so the public equations come linear with respect to the $`y`$.

Assume now that PK is nonlinear in the $`y`$. Once Bob substitutes the $`x`$ in the public equations, he is required to find any solution of the system that he obtains. This can be done within polynomial time with respect to Bezout number of the system. Later we give settings to keep PK nonlinear of low total degree in the $`y`$.

Each of such solutions (if any) is encryption to the same cleartext. So we have set up a probabilistic encryption protocol. To a single cleartext may correspond zero, one, or more ciphertexts.

## 3. Security Issues

The main data to Eve are the system of public equations and the order of extension. By brute force, she has to take $`(y_1,y_2,\mathrm{},y_n)`$, to substitute it in the PK equations, to solve within the base field, and to take the sensate solution. Almost surely, there is only one sensate solution among those that she finds. She has to find it among $`t^n`$ of them. However, the main difficulty to her is just solving the system. Supposedly, it will pass through the complete calculus of a Gröbner basis. It is a well-known hard problem.

So, the complexity of the trapdoor problem is $`𝒪(t^n)`$. On the other hand, the size of the PK is $`𝒪(n^{t+1})`$. This fully suggests the values of the parameters. It is better to take $`n`$ huge. This diminishes the probability that Alice confuses decryption, however close to zero, and, what is most important, it renders Eve’s task harder. Alice and Bob will have to solve sets of bigger systems of linear equations, and face Chinese Remainder Theorem for bigger $`n`$.

If we take $`t`$ very small, we restrict somehow choices of $`f`$. If very big, it renders the size of PK impractical. Actually, $`n100`$ and $`t=2,3,4`$ are quite good sample values. If we only take the monomials of $`f`$ to be univariate, PK size is roughly the same as $`HFE`$, and we have infinite choices still. In any case, later in section 6 we present better settings that all in one: moderate the size of the PK, increase its randomness, and contain better the number of undesired solutions.

There exist well-known facilities \[SCPK\] to solve overdefined systems of equations. Unlike most of the rest, our PK is irrendundant, so it is not subject to such facilities.

Now, by exhaustive search we mean that Eve substitutes the $`y`$ in the public equations, and tries to solve it by substituting values to the $`x`$. If we have $`d`$ letters each of them being represented by a single element of $`𝔽_q`$, the complexity of an exhaustive search is $`𝒪(d^n)`$. It is easy for Alice to render exhaustive search more cumbersome than Gröbner attack. The last one seems to be the only choice to Eve.

Affine multiple attack \[Pat96b\] seems of no use in these settings.

Obviously, infinitely many bivariate polynomials give raise to the same public key. Indeed, fixed the ground field, the degree of extension $`n`$, and the degree of PK equations, we have a finite number of public keys. On the other hand, there are infinitely many bivariate polynomials that can be used like private keys.

On how does it happen, nothing is known. If ever found, any such regularity will only weaken the trapdoor problem.

## 4. A Digital Signature Algorithm

For Bob to be able to sign messages, he builds a cryptosystem as above with $`[𝕂_B:𝔽_{q_B}]=n_B`$. Assume now that we are publicly given a set of hash functions that send cleartexts to $`n_B`$-tuples of $`𝔽_{q_B}`$.

Bob to sign a message $`M`$:

* calculates $`H(M)=(y_1,y_2,\mathrm{},y_{n_B})=𝐲_B`$, then $`𝐯_B=B_B𝐲_B+𝐝_B`$;
* finds one solution (if any; otherwise, see section 2.2.1) $`𝐮_B`$ of $`f_B(𝐮_B,𝐯_B)=0`$ in $`𝕂_B`$.
* calculates $`𝐱=A_{B}^{}{}_{}{}^{1}(𝐮_B𝐜_B)`$;
* appends $`𝐱=(x_1,x_2,\mathrm{},x_{n_B})`$ to $`M`$, encrypts, and sends it to Alice. $`(x_1,x_2,\mathrm{},x_{n_B})`$ is a signature to $`M`$.

To authenticate, Alice first decrypts, then she calculates $`H(M)=(y_1,y_2,\mathrm{},y_{n_B})`$. If $`(x_1,x_2,\mathrm{},x_{n_B})`$, $`(y_1,y_2,\mathrm{},y_{n_B})`$ is a solution of Bob’s PK, she accepts the message; otherwise she knows that Eve has been causing trouble.

If Eve tries to impersonate Bob and send to Alice her own message with hash value $`𝐲=(y_1,y_2,\mathrm{},y_{n_B})`$, then to find a signature $`(x_1,x_2,\mathrm{},x_{n_B})`$, she may try to find one solution of Bob’s system of equations for y. We trust on the hardness of this problem for the security of authentication.

Actually, the hash functions play no role in this class of signatures. They may as well output parts of the cleartext itself.

## 5. A Signcryption Protocol

Here is the shortest possible description. Let $`F_A`$ and $`F_B`$ be Alice’s and Bob’s PK functions respectively. To send a message x to Alice, Bob sends her a random element of $`F_A(F_B^1(𝐱))`$, that she can decrypt by calculating $`F_B(F_A^1(F_A(F_B^1(𝐱))))`$. So if $`F_A(F_B^1(𝐱))\mathrm{}`$. Otherwise, the approach is probabilistic, as in the previous section.

Here is the extended description. Each letter (or some of them, only) is represented by a set of few (two, e.g.) elements of the field, or strings of them. For ease of explanation, assume that $`𝔽_{q_A}=𝔽_{q_B}`$ and $`n_A=n_B`$.

Bob writes down the cleartext $`X`$, calculates $`𝐯_B=B_BX+𝐝_B`$, and finds one solution (if any, otherwise see section 2.2.1) $`𝐮_B`$ of his private polynomial $`f_B(X,Y)`$. Next he calculates $`𝐱_B=A_{B}^{}{}_{}{}^{1}(𝐮_B𝐜_B)`$, that he encrypts as above by means of Alice’s PK, and sends her the result.

Alice now first decrypts as in section 2.2. Next, she substitutes the x-es she finds into Bob’s PK variables $`x`$, and solves. There is at least one solution, and at most few of them. One of them is Bob’s message.

What is the trapdoor problem now? Well, on authentication matter, nothing new. Eve has the same chances to forge here that she had before. Recall that this class of signatures is already considered best with respect to the other ones.

On security, instead, there is a very good improvement. By brute force, Eve has to take the ciphertext, substitute on Alice’s PK, find all solutions, substitute them all on Bob’s PK, and take the sensate ones.

Let us assume that the letters are strings of a fixed length. For an exhaustive search Eve now has to run throughout all the $`n`$-tuples of all elements of Alice’s ground field; not just throughout $`n`$-tuples made of letters. She sets up such $`n`$-tuples, checks whether they are solutions of Alice’s PK for Bob’s ciphertext y substituted to the variables $`y`$. If yes, she substitutes to Bob’s PK, and takes the sensate ones.

So, Alice now has a full freedom on building alphabet. In decryption she discards a priori the solutions that contain non-letters. Now practically the good solution is unique.

Apart all, we save the space and calculi of the signature.

## 6. Hidden Ideal Equations

Instead of a single bivariate polynomial, Alice may employ an ideal of a very modest size. She separates the variables that she employs within two sets, $`\{X_i\}`$, $`\{Y_j\}`$; one for encryption, one for decryption. She may decide to leave one of the equations employed of higher degree in the $`\{Y_j\}`$ after manipulations, so she gives raise to a probabilistic encryption protocol. Alice obtains her PK with manipulations as in section 2.1 on all variables $`\{X_i\}`$, $`\{Y_j\}`$. Her parameters are:

* $`n=[𝕂:𝔽_q]`$;
* the number $`s_1`$, $`s_2`$ of variables $`\{X_i\}`$, $`\{Y_j\}`$, respectively;
* the number $`r`$ of private equations.

So, the number of PK equations is $`nr`$, the number of the variables $`x_{ij}`$ is $`ns_1`$, and that of the $`y_{kl}`$ is $`ns_2`$.

Alice’s number of variables, the $`\{X_i\}`$, is insignificant so far, so she is supposed to be able to appeal to Gröbner techniques in order to solve her system of equations within the field of coefficients for Bob’s $`\{Y_j\}`$.

What is most important here and throughout, if Bob succeeds to encrypt, Alice does always succeed to decrypt.

For ease of treatment, assume now that Alice does not apply affine transformations to her variables. Bob fails encryption for a certain cleartext $`(X_1,\mathrm{}X_{s_1})`$ iff Alice’s private ideal has no solutions in the $`Y`$ for such an $`(X_1,\mathrm{}X_{s_1})`$. Alice’s private ideal is a random one. If she takes $`rs_2`$, the probability that it has no solutions is $`0`$, and $`1`$ for $`r>s_2`$. So, it suffices that Alice takes $`rs_2`$. The rare critical cases that may supervene are faced simply changing alphabet.

With slight changes, this reasoning holds in the case that Alice applies affine transformations, too.

The real problem is indeed that the solutions to Alice may be too many; and in any case finitely many, as the base field is finite. The best remedy to that is that Alice takes $`r=s_1`$. So, the ideal that she obtains after substitution of Bob’s ciphertext is zerodimensional (quite easy to cause it happen), and the number of solutions is bounded above by the total degree of the system. So, she can contain the number of solutions by taking the total degree in the $`\{X_i\}`$ modest.

Alice can take all equations of very low degree in the $`X`$, and then transform that basis of the ideal they generate to another one of very high degrees in the $`X`$. So she has a low Bezout number of the ideal, and higher degrees in the $`X`$, and transformations as above can take place. If she takes the first basis linear, the number of solutions of her equations reduce to one: Bob’s cleartext. She can substitute Bob’s ciphertext to any of bases of her private ideal, e.g., to a linear one.

As soon as $`r>s_1`$, the PK becomes overdefined.

Alice applies a permutation to the equations and a renumeration to the variables before publishing her key, so Eve does not know how are they related. She may apply affine transformations, or may not, or may apply to only some of the $`X_i`$, $`Y_j`$; at her discretion.

If $`s_1<s_2`$, the size of the ciphertext is bigger than that of cleartext, and nothing else wrong. By this case, encryption is practically always probabilistic. Indeed, even when the equations are linear with respect to the $`y_{kl}`$, since there are more variables than equations, the solutions exist, and are not unique.

Actually, Alice can take a big $`s_2`$. She may choose to manipulate some of the $`Y_j`$ within a subfield of $`𝕂`$, rather than within $`𝕂`$. Doing so, she is allowed a big $`s_2`$, and a contained size of the ciphertext. The number of the variables $`y_{kl}`$ now is no more $`ns_2`$.

One can employ this protocol for signcryption. The sizes of ciphertexts throughout are roughly equal to those of the plaintext ones. So, one can use all the protocols we describe throughout for multiple encryption as well. They seem suitable for private key schemes, too.

Now the size of the PK is $`𝒪(s_1(n)^{t+1})`$, and the complexity of the trapdoor problem is $`𝒪(t^{ns_1})`$.

Even though the size of PK throughout grows polynomially with $`n`$, before $`n`$ becomes interesting, the PK is already quite cumbersome. So, opting for the choices of this section we can employ much smaller $`n`$, whence moderate a lot the size of the public key.

Actually, $`n=20`$ or so is quite good. We are allowed some more values of $`t`$, too. Alice takes $`s_1`$ as big as she can handle, e.g., $`s_1=5,6,7`$, or more.

For $`ns_1`$ fixed, the bigger $`s_1`$ is, the exponentially less cumbersome the PK is, and the exponentially harder becomes Eve’s task.

Generally speaking, Alice’s task becomes exponentially harder with $`s_1`$, too. In practice, it depends very much on whether does she have any good basis of her private ideal, or not. In any case, the speeds of becoming harder of tasks of Alice and Eve are quite different.

### 6.1.

There exist classes of ideals called with doubly exponential ideal membership property \[Swa\]. These are the ideals for which the calculus of a Gröbner basis requires doubly exponential time on the number of variables. It is very interesting to know whether can we employ them in some fashion in this class of cryptosystems. In any fashion, this is the theoretical limit for employing solving of polynomial systems of equations in PK cryptography.

## 7. Some Considerations

The idea of PK was first proposed by Diffie and Hellman \[DH76\]. Since then, it has seen several vicissitudes \[Odl91, Mora, Morb\].

A trapdoor function is a map from cleartext units to ciphertext units that can be feasibly computed by anyone having the PK, but whose inverse function cannot be computed without its knowledge:

* either because (at present, publicly) there is no known way;
* or there are, but the amount of calculi is deterring.

Shannon \[Sti02\] called unconditionally secure cryptosystems those with trapdoor of the first class.

Actually, the aim is to render the trapdoor problems equivalent to time-honoured hard mathematical problems. Being of a problem hard or undecidable implies nothing a priori about the security of a cryptosystem \[Odl91\], however.

Recall that of all schemes ever set up, only two of them, $`RSA`$ \[RSA78\] and ECDL \[Kob99\], are going to be broken (or, at least, are going to become impractical) by solving their hard problems.

The author is very fond of the idea of the PK, and believes howsoever in new developments that will make it fully suffice for all purposes.

Actually, one tendency is that of investigating poor structures, mean, structures with less operations, like groups, semigroups with cryptosystems upon the word problem \[AAFG01, Yam98, Hug02\]. Yamamura’s paper \[Yam98\] can be considered a pioneering USPK. Unfortunately, its scheme is still uneffective.

William Sit and the author are investigating rich structures. We are investigating among other things effective USPK schemes upon differential fields of positive characteristic. We hope that cryptography will arouse new interests on differential and universal algebra, too, as it did in number theory and arithmetic geometry. One reason of optimism is that in universal algebra one can go on further with new structures and hard or undecidable problems forever. Until now we have appealed to only unary and binary arithmetic operations.

## 8. Generalizations on Differential Fields

Differential222Most of considerations given in this section are suggestions of professor Sit through private communications. algebra \[Kol73, Sit02, Rit50, Sad, Kap57\] owes its existence mostly to the efforts of Ritt \[Rit50\] to handle differential equations by means of algebra.

A differential field is a field $`𝔽`$ endowed with a set of linear maps $`\theta :𝔽𝔽`$ called derivatives, such that: $`\theta (ab)=a\theta (b)+\theta (a)b`$.

Kaplansky’s booklet is perhaps the best introduction in the topic.

The schemes given throughout work as well in differential settings. Take $`𝕂`$ to be a finite differential field extension of a differential field $`𝔽`$ of positive characteristic333In zero characteristic numerical analysis tools seriously affect security, or at least constrain us to more careful choices. We shall not dwell on this topic here.. Any such $`𝕂`$ is defined by a system of linear homogeneous differential equations, and there are structural constants defining the operations for the derivations (one matrix for each derivation), as well for multiplication.

One can now replace (5) with a differential polynomial of higher order and degree. Throughout section 6, one can replace ideals with small suitable differential ideals, too. The schemes work verbatim.

The techniques given throughout for polynomials, if applied to differential polynomials, will definitely make it much harder to attack any protocol developed. Any affine transformation (by this is meant a linear combination of the differential indeterminates with not-necessarily constant coefficients, and this linear combination is then substituted differentially in place of the differential indeterminates) will not only even out the degrees, but also the orders of the various partials, and making the resulting differential polynomials very dense.

However, there is one thing to caution about: any time one specifies these structural matrices, they have to satisfy compatibility equations. In the algebraic case, it is the relations between $`P^k=\{p_{ij}^{}{}_{}{}^{(k)}\}`$ in (10) and $`M_{\mathrm{}}=\{m_{ij\mathrm{}}\}`$ in (11). The $`P^k`$ are simply determined uniquely by $`M_{\mathrm{}}`$, given the choices implicitely defined in (11).

It is very interesting to know in the algebraic case whether Alice’s PK is invariant under a change of basis, all the other settings being equal. There is probably some group of matrices in $`GL(n,q)`$ that can do that. Such a knowledge would only weaken all cryptosystems based on equations systems solving.

In the differential case there is a similar action called Loewy action, or the gauge transformation. For ordinary differential equations, two matrices $`A`$, $`B`$ are Loewy similar if there is an invertible matrix $`K`$ such that $`A=\delta KK^1+KBK^1`$. Using this action, one can classify the different differential vector space structures of a finite dimensional vector space. There is also a cyclic vector algorithm to find a special basis, so that the differential linear system defining the vector space becomes equivalent to a single linear $`ODE`$.

If no other problems arise for the differential algebraic schemes, there is however one caution more for them to be unconditionally secure. We have to avoid the exhaustive search. For that, Alice has to publish a finite alphabet where each letter is represented by an infinite set, disjoint sets for different letters. This is possible in differential fields, as they are infinite. Alice renders the sets public parametrically, as differential algebraic functions of elements of the base differential field, and parameters, e.g., in $``$. Bob chooses a letter, gives random values to parameters, obtains one representant of the letter, and proceeds as above. In any case, if $`\mu `$ is the order of public equations, any two elements $`\mathrm{\Xi }`$, $`\mathrm{\Theta }𝔽`$ such that $`(\mathrm{\Xi }\mathrm{\Theta })^{(\mu )}=0`$ must represent the same letter, if any.

In the algebraic case such constructions do not make sense, as the base field is finite. Besides, Gröbner attack is always at hand.

The main care for Alice is that the PK equations must not fall into feasible cases by well-known means, such as linear algebra.

Now the size of the PK is $`𝒪(n^{to+1})`$, where $`o`$ is the order of PK equations. Quite explosive!!! One more reason to take $`q=2`$, so some more monomials reduce to zero.

Anyway, we do not have to increase parameters for better security. The trapdoor problem is simply undecidable. Unlike the algebraic case, we can split cleartext into small strings. Actually, quite good sample values are: $`n=20`$ and $`t,o=2,3,4`$, or so. As of now, $`HDPE`$ trapdoor problem seems undecidable, and the scheme effective.

### Acknowledgments.

I wish to thank Massimiliano Sala and Christopher Wolf for many suggestions and fruitful discussions. I am particularly indebted to William Sit for several comments and improvements on earlier drafts, and to his advisor, Carlo Traverso.


format: text

text:
# One-loop renormalizability of all 2d dimensional Poisson-Lie 𝜎-models

## 1 Introduction

Poisson-Lie T-duality  is the generalization of the world-sheet Abelian T-duality in string theory  and of the traditional non-Abelian T-duality . It works also in situations when a T-dualizable $`\sigma `$-model does not possess a (non)Abelian isometry but only a weaker property called Poisson-Lie symmetry.

The Poisson-Lie T-dualizable $`\sigma `$-models (or, in what follows, the PLT $`\sigma `$-models) are specified by the choice of a Drinfeld double and by the $`(n\times n)`$-matrix of coupling constants where $`n`$ is the half of the dimension of the double. From the point of view of classical field theory, the $`\sigma `$-model and its dual are related by a canonical transformation ; they are therefore dynamically equivalent systems.

The quantum status of the Poisson-Lie T-duality remains a challenging problem. We stress at this point that the word “quantum” does not necessarily suppose that a conformal symmetry is to be required. We shall simply study the duality from the point of two-dimensional field-theory. Whereas for the semi-abelian case the one-loop quantum equivalence of T-dual models has been established for a wide class of models , the same problem for the non-abelian case is far more difficult. The first steps in this direction were undertaken in , where the respective authors established the one-loop renormalizability of certain Poisson-Lie T-dualizable $`\sigma `$-models and the compatibility of the RG flow with the Poisson-Lie T-duality. They did it for a few low-dimensional Poisson-Lie targets and particular choices of the coupling constants.

In this paper, we would like to perform a more systematic study of this issue. However, we miss a classification of all PLT $`\sigma `$-models since it would require a preliminary classification of all the Drinfeld doubles (indeed, the latter project seems as hopeless as the classification of all Lie algebras). On the other hand, low dimensional doubles WERE classified in . Therefore we consider, e. g., all existing two-dimensional Poisson-Lie T-dualizable targets. We do it and show that they are one-loop renormalizable and that the RG flow in the space of coupling constants is always compatible with the Poisson-Lie T-duality.

## 2 Generic 2 dimensional Poisson-Lie models

### 2.1 Four dimensional Drinfeld doubles

A Drinfeld double $`𝒟`$ is a Lie algebra with generators $`T_i,i=1,\mathrm{}n`$ and $`\stackrel{~}{T}^i,i=1,\mathrm{}n,`$ equipped with a symmetric and ad-invariant non-degenerate bilinear form $`,`$ such that

$$T_i,T_j=0,\stackrel{~}{T}^i,\stackrel{~}{T}^j=0,T_i,\stackrel{~}{T}^j=\stackrel{~}{T}^j,T_i=\delta _i^j.$$
(1)
It is moreover required that the linear subspaces $`𝒢Span(T_i)`$ and $`\stackrel{~}{𝒢}Span(\stackrel{~}{T}^i)`$ are respectively the subalgebras of $`𝒟.`$

As shown by  all the four-dimensional non-isomorphic Drinfeld doubles, denoted as $`𝒟(\rho ,\nu ),`$ can be written

$$\{\begin{array}{ccc}[T_1,T_2]=\rho T_2\hfill & [T_1,\stackrel{~}{T}^1]=0\hfill & [T_1,\stackrel{~}{T}^2]=\rho \stackrel{~}{T}^2\hfill \\ [\stackrel{~}{T}^1,\stackrel{~}{T}^2]=\nu \stackrel{~}{T}^2\hfill & [T_2,\stackrel{~}{T}^1]=\nu T_2\hfill & [T_2,\stackrel{~}{T}^2]=\rho \stackrel{~}{T}^1\nu T_1\hfill \end{array}$$
(2)
and are of three non-isomorphic types:

* The fully abelian double $`𝒟(0,0).`$
* The semi-abelian double $`𝒟(1,0).`$
* The non-abelian double $`𝒟(1,\nu )`$ with $`\nu 0.`$

Let us construct the Poisson-Lie $`\sigma `$-models out of these doubles.

### 2.2 The Poisson-Lie models and their T-duals

A general Poisson-Lie T-dualizable $`\sigma `$-model has for action

$$(R(g)+\mathrm{\Pi })_{ij}^1(_+gg^1)^i(_{}gg^1)^j,$$
(3)
where

$$_\pm =_\tau \pm _\sigma $$
(4)
and $`\tau `$ and $`\sigma `$ are the “time ” and “space” coordinates on the world-sheet. The model (3) lives on a group manifold $`G`$ (corresponding to the Lie algebra $`𝒢`$) and it is parametrized by a set of coupling constants assembled into the matrix $`R.`$

In order to determine the $`g`$-dependent matrix $`\mathrm{\Pi }(g)`$ one first defines a triplet of matrices as follows

$$\mathrm{Ad}(g^1)T_ig^1T_ig=a(g)_i^lT_l,\mathrm{Ad}(g^1)\stackrel{~}{T}^i=b(g)^{il}T_l+d(g)_l^i\stackrel{~}{T}^l.$$
(5)
Then

$$\mathrm{\Pi }(g)=b(g)a^1(g).$$
(6)
Note that the matrices $`a,b,d`$ are defined by the adjoint action of $`gG`$ on the Lie algebra $`𝒟.`$

In our two-dimensional case, we may realize the group $`G`$ in the matrix way as follows

$$g=\left(\begin{array}{cc}e^{\rho \chi }& \rho \theta \\ 0& 1\end{array}\right)$$
(7)
and the generators $`T_i`$, $`\stackrel{~}{T}^i`$ are given by

$$T_1=\left(\begin{array}{cc}\rho & 0\\ 0& 0\end{array}\right),T_2=\left(\begin{array}{cc}0& \rho \\ 0& 0\end{array}\right),\stackrel{~}{T}^1=\left(\begin{array}{cc}0& 0\\ 0& \nu \end{array}\right),\stackrel{~}{T}^2=\left(\begin{array}{cc}0& 0\\ \nu & 0\end{array}\right).$$
(8)
Thus we have for the matrices

$$a(g)=\left(\begin{array}{cc}1& \rho \theta e^{\rho \chi }\\ 0& e^{\rho \chi }\end{array}\right),b(g)=\left(\begin{array}{cc}0& \nu \theta e^{\rho \chi }\\ \nu \theta & \rho \nu \theta ^2e^{\rho \chi }\end{array}\right),$$
(9)
which lead to

$$\mathrm{\Pi }(g)=b(g)a^1(g)\mathrm{\Pi }=\left(\begin{array}{cc}0& \nu \theta \\ \nu \theta & 0\end{array}\right).$$
(10)
The matrix $`R`$ is

$$R=\left(\begin{array}{cc}x& y\\ z& w\end{array}\right),\delta detR=xwyz0,$$
(11)
and the right-invariant vielbein

$$dgg^1=d\chi T_1+(d\theta \rho \theta d\chi )T_2.$$
(12)
Then we obtain from the action (3) the resulting target space metric ,

$$G=\frac{b}{\mathrm{\Delta }}d\chi ^2+\frac{x}{\mathrm{\Delta }}d\theta ^22\frac{a}{\mathrm{\Delta }}d\chi d\theta ,\mathrm{\Delta }=(\nu \theta )^2(yz)(\nu \theta )+\delta ,$$
(13)
with the definitions

$$a=x(\rho \theta )+\frac{y+z}{2},b=x(\rho \theta )^2+(y+z)(\rho \theta )+w,$$
(14)
and the torsion potential

$$\frac{\rho \theta (yz)/2}{\mathrm{\Delta }}d\chi d\theta .$$
(15)
Since the target space is two-dimensional, the torsion 3-form vanishes.

The T-dualized model lives on the dual group target $`\stackrel{~}{G}`$ and its action reads

$$(\stackrel{~}{R}+\stackrel{~}{\mathrm{\Pi }}(\stackrel{~}{g}))_{}^{1}{}_{}{}^{ij}(_+\stackrel{~}{g}\stackrel{~}{g}^1)_i(_{}\stackrel{~}{g}\stackrel{~}{g}^1)_j,$$
(16)
where $`\stackrel{~}{R}=R^1`$ and the $`\stackrel{~}{g}`$ dependent matrix is given by

$$\stackrel{~}{\mathrm{\Pi }}(\stackrel{~}{g})=\stackrel{~}{b}(\stackrel{~}{g})\stackrel{~}{a}^1(\stackrel{~}{g}),$$
(17)
where the dual matrices $`\stackrel{~}{a},\stackrel{~}{b},\stackrel{~}{d}`$ are defined similarly by

$$\mathrm{Ad}_{\stackrel{~}{g}^1}\stackrel{~}{T}^i=\stackrel{~}{a}(\stackrel{~}{g})_l^i\stackrel{~}{T}^l,\mathrm{Ad}_{\stackrel{~}{g}^1}T_i=\stackrel{~}{b}(\stackrel{~}{g})_{il}\stackrel{~}{T}^l+\stackrel{~}{d}(\stackrel{~}{g})_i^lT_l.$$
(18)
The elements $`\stackrel{~}{g}`$ of the dual group $`\stackrel{~}{G}`$ are of the form

$$\stackrel{~}{g}=\left(\begin{array}{cc}0& 0\\ \nu \theta & e^{\nu \chi }\end{array}\right)$$
(19)
and one can check that the matrices$`\stackrel{~}{a}(\stackrel{~}{g}),\stackrel{~}{b}(\stackrel{~}{g})`$ are obtained from $`a(g),b(g)`$ by the interchange of the parameters $`\rho `$ and $`\nu .`$ This leads to

$$\stackrel{~}{\mathrm{\Pi }}(\stackrel{~}{g})=\left(\begin{array}{cc}0& \rho \theta \\ \rho \theta & 0\end{array}\right).$$
(20)
Finally, the vielbein is now

$$d\stackrel{~}{g}\stackrel{~}{g}^1=d\chi \stackrel{~}{T}_1+(d\theta \nu \theta d\chi )\stackrel{~}{T}_2.$$
(21)
Inserting all these quantities in the T-dualized Poisson-Lie model (16)gives the same target space metric (13) in which $`R`$ is transformedinto $`\stackrel{~}{R}`$ and $`\rho `$ and $`\nu `$ get exchanged.

From the previous considerations one can check that the abelian model and its T-dual partner are both flat, so we will not consider this trivial possibility and we will take $`\rho =1`$ in what follows.

### 2.3 Isometry and form invariance of the metric

These metrics have the obvious Killing $`\stackrel{~}{K}=_\chi ,`$ with dual 1-form

$$K=\frac{a^2+\gamma ^2}{x\mathrm{\Delta }}d\chi \frac{a}{\mathrm{\Delta }}d\theta .$$
(22)
Besides this isometry, the left group action induces a two parameters group of transformation $`G_L`$ of the coordinates and of the parameters

$$\{\begin{array}{c}\widehat{\theta }=\sigma \theta \tau ,\widehat{\chi }=\chi +\mathrm{ln}\sigma ,\widehat{x}=x,\hfill \\ \widehat{y}=\sigma y+\tau (x1),\widehat{z}=\sigma z+\tau (x+1),\hfill \\ \widehat{w}=\sigma ^2w+\sigma \tau (y+z)+\tau ^2x,\hfill \end{array}\sigma >0,\tau .$$
(23)
Using the relations

$$\widehat{a}=\sigma a,\widehat{b}=\sigma ^2b,\widehat{\mathrm{\Delta }}=\sigma ^2\mathrm{\Delta },$$
(24)
it is easy to check that $`G_L`$ leaves the metric invariant in the sense that

$$G(\chi ,\theta ,R)=G(\widehat{\chi },\widehat{\theta },\widehat{R}).$$

The existence of this group implies that we can get rid of two parameters in the matrix $`R:`$ we can always take $`z=y`$ and $`w=x.`$ Indeed, let us consider a set of the parameters $`x,y,z,w`$ such that neither $`z=y`$ nor $`w=x.`$ Using the transformations laws given above, if we take for parameters

$$\tau =\sigma \frac{(yz)}{2},\sigma =x\left(\frac{t^2}{4}+\gamma ^2\right)^{1/2},t=(x+1)y+(x1)z,$$

we can ensure simultaneously the relations $`\widehat{z}=\widehat{y}`$ and $`\widehat{w}=\widehat{x}.`$ Notice that we have anticipated the positivity restriction on $`x`$ which comes out from the riemannian character of the metric (see (30)). In what follows we will therefore take

$$R=\left(\begin{array}{cc}x& y\\ y& x\end{array}\right),x>0,\gamma ^2x^2y^2>0,y.$$
(25)
For the semi-abelian model, corresponding to $`𝒟(1,0),`$ the lagrangian is

$$B_{ij}(_+gg^1)^i(_{}gg^1)^j,B=R^1,$$

where $`R`$ is given in (25). This metric is flat, so there is no renormalization of the parameters. Its T-dual model is not flat, but as shown in , it is flat up to some diffeomorphism, and the one-loop equivalence between the T-dual pair of models is preserved.

So the remaining open problem is the non-abelian model: since $`\nu 0,`$ appropriate scalings of $`R`$ and of the coordinates allow to take $`\nu =1.`$ As observed in  the full family of Drinfeld doubles $`𝒟(1,\nu )`$ gives rise to a single $`\sigma `$-model with $`\nu =1,`$ the $`GL(2,)`$ model of .

The actual form of the metric is now

$$G=\frac{b}{\mathrm{\Delta }}d\chi ^2+\frac{x}{\mathrm{\Delta }}d\theta ^22\frac{a}{\mathrm{\Delta }}d\chi d\theta ,$$
(26)
with the new functions

$$a=x\theta +y,b=x\theta ^2+2y\theta +x=\frac{a^2+\gamma ^2}{x},\mathrm{\Delta }=\theta ^2+\gamma ^2,\gamma ^2=x^2y^2.$$
(27)
Its T-dual partner is obtained by the change of parameters

$$x\stackrel{~}{x}=\frac{x}{x^2y^2},y\stackrel{~}{y}=\frac{y}{x^2y^2}.$$
(28)
### 2.4 Geometric aspects

Let us check the Riemannian character of the metric (26). This is best done through a calculation of the vielbein

$$G=(e_1)^2+(e_2)^2,e_1=\frac{\gamma }{\sqrt{x\mathrm{\Delta }}}d\chi ,e_2=\frac{xd\theta ad\chi }{\sqrt{x\mathrm{\Delta }}},$$
(29)
The metric will be riemannian iff

$$\gamma ^2>0,x>0.$$
(30)
It follows that $`\mathrm{\Delta }`$ never vanishes. In the sequel we will assume that these conditions hold.

Another interesting point is to find the coordinates which do exhibit the conformally flat character of this metric. Taking for these coordinates

$$U=\chi \frac{1}{2}\mathrm{ln}(a^2(\theta )+\gamma ^2),V=\mathrm{arctan}\left(\frac{a(\theta )}{\gamma }\right),a(\theta )=x\theta +y,$$
(31)
the metric $`G`$ becomes

$$G=\frac{x\gamma ^2}{(y\mathrm{cos}V\gamma \mathrm{sin}V)^2+x^2\gamma ^2\mathrm{cos}^2V}(dU^2+dV^2),$$
(32)
and it will be flat iff the denominator in the pre-factor is some constant. An easy algebraic discussion leads to the conclusion that the non-abelian model is flat iff

$$x=\pm 1\text{and}y=0R=\pm 𝕀.$$
(33)
### 2.5 Frame geometry

The spin connection, defined by

$$de_a+\omega _{ab}e_b=0,$$

is given by

$$\omega _{12}=\frac{1}{2\gamma }\frac{𝒩d\chi +xNd\theta }{x\mathrm{\Delta }},$$
(34)
with

$$𝒩=(a^2+\gamma ^2)^{}\mathrm{\Delta }(a^2+\gamma ^2)\mathrm{\Delta }^{},N=a\mathrm{\Delta }^{}2a^{}\mathrm{\Delta },$$
(35)
where a prime indicates a derivative with respect to $`\theta .`$ One obtains

$$N=2y\theta 2x\gamma ^2,\gamma ^2=x^2y^2,$$
(36)
and

$$\frac{𝒩}{2x}=y(\theta ^2\gamma ^2)+x(\gamma ^21)\theta .$$
(37)
The curvature (in the vielbein basis) has the single component

$$R_{12,12}=\frac{1}{\gamma ^2\mathrm{\Delta }}\frac{(𝒩\mathrm{\Delta }^{}\mathrm{\Delta }𝒩^{})}{2x},$$
(38)
and we have for the Ricci

$$\mathrm{Ric}_{11}=\mathrm{Ric}_{22}=R_{12,12},\mathrm{Ric}_{12}=0.$$
(39)
The explicit form of the curvature component is

$$\frac{𝒩\mathrm{\Delta }^{}\mathrm{\Delta }𝒩^{}}{2x}=x(\gamma ^21)(\theta ^2\gamma ^2)+4y\gamma ^2\theta .$$
(40)
## 3 One-loop renormalizability

The one-loop renormalizability is ensured if the Ricci tensor can be written

$$\mathrm{Ric}_{ij}=(\chi )G_{ij}+_{(i}w_{j)},\chi =\chi _k\frac{}{x_k},$$
(41)
where the $`\{x_k\}`$ are parameters of the lagrangian to be renormalized and $`w`$ is some (non-Killing) vector. In the vielbein basis this becomes

$$\{\begin{array}{c}\mathrm{Ric}_{ab}=(e^1)_b^i(\chi )e_{ai}+(e^1)_a^i(\chi )e_{bi}+𝒟_{(a}w_{b)},\hfill \\ 𝒟_aw_b=\widehat{}_aw_b+\omega _{bs,a}w_s,\widehat{}_a=(e^1)_a^i_i.\hfill \end{array}$$
(42)
Out of these three relations, two involve only the unknown vector $`w`$:

$$\frac{1}{2}\left(𝒟_1w_2+𝒟_2w_1\right)=(e^1)_{a=1}^i(\chi )e_{b=2,i}+(e^1)_{a=2}^i(\chi )e_{b=1,i},$$

$$\frac{1}{2}\left(𝒟_1w_1𝒟_2w_2\right)=(e^1)_{a=1}^i(\chi )e_{b=1,i}(e^1)_{a=2}^i(\chi )e_{b=2,i}.$$

Defining

$$w_1=\sqrt{\frac{x}{\mathrm{\Delta }}}\widehat{w}_1,w_2=\sqrt{\frac{x}{\mathrm{\Delta }}}\widehat{w}_2,$$
(43)
we get

$$\widehat{w}_1=\frac{\mu }{\gamma }\theta ,\widehat{w}_2=\frac{\mu }{\gamma ^2}(v+y\theta )+(\theta +y/x)C_2C_1,$$
(44)
where $`\mu `$ is a free parameter and

$$C_1=2(\chi )\left(\frac{y}{x}\right),C_2=\frac{x^2}{\gamma ^2}(\chi )\left(\frac{\gamma ^2}{x^2}\right)$$
(45)
are constants.

Then we are left with the single relation

$$\mathrm{Ric}_{11}=𝒟_1w_1+2(e^1)_{a=1}^i(\chi )e_{a=1,i}.$$
(46)
The parameters to be renormalized are $`x`$ and $`y`$, so we define

$$\chi =\chi _x_x+\chi _y_y.$$
(47)
The relation (46) gives only two relations (instead of three expected):

$$\{\begin{array}{c}\gamma ^2\chi _x=xy\mu +x^2(\gamma ^21),\hfill \\ 2y\chi _x+2x\chi _y=x(\gamma ^21)\mu +4y\gamma ^2.\hfill \end{array}$$
(48)
Since we are left with some freedom, let us see what comes out if we impose as a further condition the one-loop renormalizability of the T-dualized model. This is most conveniently done by switching to the parameters $`u=x+y`$ and $`v=xy.`$ Then the transformation (28) becomes

$$u\stackrel{~}{u}=\frac{1}{u},v\stackrel{~}{v}=\frac{1}{v}.$$
(49)
We will define for new renormalization constants

$$\chi =\widehat{\chi }_uu_u+\widehat{\chi }_vv_v,\text{with}\widehat{\chi }_u=\frac{\chi _x+\chi _y}{x+y},\widehat{\chi }_v=\frac{\chi _x\chi _y}{xy}.$$
(50)
Relation (48) implies

$$\{\begin{array}{c}\widehat{\chi }_u(u,v)=+\frac{(1v^2)}{2v}\mu (u,v)+2v\frac{uv}{u+v}+\frac{(u+v)(uv1)}{2uv},\hfill \\ \widehat{\chi }_v(u,v)=\frac{(1u^2)}{2u}\mu (u,v)2u\frac{uv}{u+v}+\frac{(u+v)(uv1)}{2uv}.\hfill \end{array}$$
(51)
Now $`u`$ (similarly for $`v`$) is renormalized by $`u\widehat{\chi }_u(u,v)`$ while $`\stackrel{~}{u}`$ is renormalized by $`\stackrel{~}{u}\widehat{\chi }_u(\stackrel{~}{u},\stackrel{~}{v})`$ so, the T-dual pair will be renormalizable provided that

$$\widehat{\chi }_u(\stackrel{~}{u},\stackrel{~}{v})=\widehat{\chi }_u(u,v),\widehat{\chi }_v(\stackrel{~}{u},\stackrel{~}{v})=\widehat{\chi }_v(u,v).$$
(52)
So, if we define

$$m(u,v)=\frac{\mu (u,v)}{2}\frac{uv}{u+v},$$

the joint renormalizability constraints (52) are equivalent to the single constraint

$$m(\stackrel{~}{u},\stackrel{~}{v})=m(u,v).$$
(53)
The function $`m`$ describes the arbitrariness left over even after imposing the stability of renormalizability through T-dualization.

We have therefore shown that the T-dual pair of Poisson-Lie $`\sigma `$-models is indeed renormalizable, in the strict field-theoretic sense, with the most general structure of the renormalization constants

$$\{\begin{array}{c}\frac{\mu }{2}=m+\frac{uv}{u+v},\hfill \\ \widehat{\chi }_u=+m\frac{(1v^2)}{v}+\frac{(1+v^2)(uv)}{v(u+v)}+\frac{(u+v)(uv1)}{2uv},\hfill \\ \widehat{\chi }_v=m\frac{(1u^2)}{u}\frac{(1+u^2)(uv)}{u(u+v)}+\frac{(u+v)(uv1)}{2uv},\hfill \end{array}$$
(54)
where $`m(u,v)`$ is constrained by (53). These renormalization constants are well defined since, as already stated in (30), the parameters $`u+v=x`$ and $`uv=\gamma ^2`$ never vanish.

## 4 Conclusion

Let us conclude with some remarks:

* Absence of torsion and the dimension 2 for the target space is too poor to produce conformal geometries of interest for string theory. The case of 3d dimensional targets seem to be more promising from this point of view (cf. ).
* Remarkably, the renormalizability works despite the traceful structure constants of the Drinfeld double. However, it is important to note in this context that we work with strictly field theoretic renormalization where the Weyl mode is frozen to a constant value (the same is true for the semi-abelian models). In the stringy framework, where the Weyl mode is coupled, the one-loop quantum equivalence requires that both sub-algebras $`𝒢`$ and $`\stackrel{~}{𝒢}`$ in the Drinfeld double must have traceless structure constants .
* The problem of higher loop corrections to the Poisson-Lie T-duality appears to be more tricky than in the case of the Abelian or traditional non-Abelian T-duality. Of course, one problem to cope with is the fact that a finite one-loop renormalization can change the two-loops divergences . But there is also a structural aspect of the thing: we expect that the two-loops effective action of the model should not probably have the same structure as the classical action (3). Why? Because the Poisson-Lie symmetry should be itself only a semiclassical approximation of a quantum group symmetry and the full-fledged effective action should reflect the latter quantum symmetry rather than the former semiclassical one. This means that, starting from the two-loop level, we do not expect that the criterion of the strict field theoretical renormalizability should be respected but we rather believe that it should be replaced by a sort of quantum group Ward identities to be fulfilled by the effective action. It is only in the semiclassical (or one-loop) limit that these Ward identities would reduce to the strict requirement of the strict renormalizability. Unfortunately, we do not have any hint yet how to write down and test the hypothetical quantum group Ward identities. For the moment we just conclude that our one-loop analysis of all two-dimensional PLT targets indicates a good quantum health of the Poisson-Lie T-duality.