Elliptic curve as a product of 3 cyclic groups possible?
$begingroup$
I'm looking for some kind of 3-dimensional Elliptic curve. As far as I know a normal Elliptic curve like $$y^2 = x^3 + ax + b$$ over $F_p$ consists of one or two cyclic groups $Z_m (times Z_n)$. Given one point and one/two generators you can reach each point with it. Now I'm looking for a product of 3 cyclic groups, given a point and 3 generators let you reach each point in this product.
(btw for cryptography do you mainly use elliptic curves with one ore two cyclic groups?)
So lets say it's $Z_m times Z_n times Z_r$ with generators $g_m, g_n, g_r$ and a point $s$ which lies in there. With $s g_m^i g_n^j g_r^k$ all points can be reached. E.g. $s g_m^m$ would be $s$ again and $s g_m^i g_n^j = s g_n^j g_m^i$ (same for $r$,$m$,$n$). (Best for use case would be $m=n=r=prim$)
I read from Wikipedia about Projective twisted Edwards coordinates with $$(a X^2 + Y^2)Z^2 = Z^4 + d X^2 Y^2$$
It has 3 coordinates but not sure if it's what I'm searching for. Can't find information about the inner structure.
I did some tests with the written algorithm but it was neither cyclic for all points nor closed for all points nor a product of 3 cyclic groups. I did some test with small numbers ($p,a,d$) and found many different cycle sizes. Normal for that kind of Elliptic curves? Did I something wrong? Is it what I'm looking for?
Do you know any other Elliptic curve with an inner structure of 3 cyclic groups (some more also Ok, can ignore those)?
Or something else which produces 3 cyclic groups, with the condition, given two points, starting at one you don't know how to reach the other point. Only way doing this try around until finding him. So you don't know which generator using next. And if you found him you also know the way backward.
elliptic-curves
New contributor
$endgroup$
add a comment |
$begingroup$
I'm looking for some kind of 3-dimensional Elliptic curve. As far as I know a normal Elliptic curve like $$y^2 = x^3 + ax + b$$ over $F_p$ consists of one or two cyclic groups $Z_m (times Z_n)$. Given one point and one/two generators you can reach each point with it. Now I'm looking for a product of 3 cyclic groups, given a point and 3 generators let you reach each point in this product.
(btw for cryptography do you mainly use elliptic curves with one ore two cyclic groups?)
So lets say it's $Z_m times Z_n times Z_r$ with generators $g_m, g_n, g_r$ and a point $s$ which lies in there. With $s g_m^i g_n^j g_r^k$ all points can be reached. E.g. $s g_m^m$ would be $s$ again and $s g_m^i g_n^j = s g_n^j g_m^i$ (same for $r$,$m$,$n$). (Best for use case would be $m=n=r=prim$)
I read from Wikipedia about Projective twisted Edwards coordinates with $$(a X^2 + Y^2)Z^2 = Z^4 + d X^2 Y^2$$
It has 3 coordinates but not sure if it's what I'm searching for. Can't find information about the inner structure.
I did some tests with the written algorithm but it was neither cyclic for all points nor closed for all points nor a product of 3 cyclic groups. I did some test with small numbers ($p,a,d$) and found many different cycle sizes. Normal for that kind of Elliptic curves? Did I something wrong? Is it what I'm looking for?
Do you know any other Elliptic curve with an inner structure of 3 cyclic groups (some more also Ok, can ignore those)?
Or something else which produces 3 cyclic groups, with the condition, given two points, starting at one you don't know how to reach the other point. Only way doing this try around until finding him. So you don't know which generator using next. And if you found him you also know the way backward.
elliptic-curves
New contributor
$endgroup$
add a comment |
$begingroup$
I'm looking for some kind of 3-dimensional Elliptic curve. As far as I know a normal Elliptic curve like $$y^2 = x^3 + ax + b$$ over $F_p$ consists of one or two cyclic groups $Z_m (times Z_n)$. Given one point and one/two generators you can reach each point with it. Now I'm looking for a product of 3 cyclic groups, given a point and 3 generators let you reach each point in this product.
(btw for cryptography do you mainly use elliptic curves with one ore two cyclic groups?)
So lets say it's $Z_m times Z_n times Z_r$ with generators $g_m, g_n, g_r$ and a point $s$ which lies in there. With $s g_m^i g_n^j g_r^k$ all points can be reached. E.g. $s g_m^m$ would be $s$ again and $s g_m^i g_n^j = s g_n^j g_m^i$ (same for $r$,$m$,$n$). (Best for use case would be $m=n=r=prim$)
I read from Wikipedia about Projective twisted Edwards coordinates with $$(a X^2 + Y^2)Z^2 = Z^4 + d X^2 Y^2$$
It has 3 coordinates but not sure if it's what I'm searching for. Can't find information about the inner structure.
I did some tests with the written algorithm but it was neither cyclic for all points nor closed for all points nor a product of 3 cyclic groups. I did some test with small numbers ($p,a,d$) and found many different cycle sizes. Normal for that kind of Elliptic curves? Did I something wrong? Is it what I'm looking for?
Do you know any other Elliptic curve with an inner structure of 3 cyclic groups (some more also Ok, can ignore those)?
Or something else which produces 3 cyclic groups, with the condition, given two points, starting at one you don't know how to reach the other point. Only way doing this try around until finding him. So you don't know which generator using next. And if you found him you also know the way backward.
elliptic-curves
New contributor
$endgroup$
I'm looking for some kind of 3-dimensional Elliptic curve. As far as I know a normal Elliptic curve like $$y^2 = x^3 + ax + b$$ over $F_p$ consists of one or two cyclic groups $Z_m (times Z_n)$. Given one point and one/two generators you can reach each point with it. Now I'm looking for a product of 3 cyclic groups, given a point and 3 generators let you reach each point in this product.
(btw for cryptography do you mainly use elliptic curves with one ore two cyclic groups?)
So lets say it's $Z_m times Z_n times Z_r$ with generators $g_m, g_n, g_r$ and a point $s$ which lies in there. With $s g_m^i g_n^j g_r^k$ all points can be reached. E.g. $s g_m^m$ would be $s$ again and $s g_m^i g_n^j = s g_n^j g_m^i$ (same for $r$,$m$,$n$). (Best for use case would be $m=n=r=prim$)
I read from Wikipedia about Projective twisted Edwards coordinates with $$(a X^2 + Y^2)Z^2 = Z^4 + d X^2 Y^2$$
It has 3 coordinates but not sure if it's what I'm searching for. Can't find information about the inner structure.
I did some tests with the written algorithm but it was neither cyclic for all points nor closed for all points nor a product of 3 cyclic groups. I did some test with small numbers ($p,a,d$) and found many different cycle sizes. Normal for that kind of Elliptic curves? Did I something wrong? Is it what I'm looking for?
Do you know any other Elliptic curve with an inner structure of 3 cyclic groups (some more also Ok, can ignore those)?
Or something else which produces 3 cyclic groups, with the condition, given two points, starting at one you don't know how to reach the other point. Only way doing this try around until finding him. So you don't know which generator using next. And if you found him you also know the way backward.
elliptic-curves
elliptic-curves
New contributor
New contributor
edited 6 hours ago
kelalaka
6,36522142
6,36522142
New contributor
asked 6 hours ago
J. DoeJ. Doe
132
132
New contributor
New contributor
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $mathbb{Z}_{n_1} times mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides the group order, but $r^2$ does not, then there is a field extension of some degree such that, in the field extension, there are $r^2$ points of order $r$, and these points are a subgroup isomorphic to $mathbb{Z}_r times mathbb{Z}_r$. This is probably not what you want.
For an integer $n = pqr$, for three integers $p$, $q$ and $r$ which are prime to each other, $mathbb{Z}_n$ is cyclic, but it is also isomorphic to $mathbb{Z}_p times mathbb{Z}_q times mathbb{Z}_r$. This is what the Chinese Remainder Theorem is about. What this means is that being cyclic does not prevent a group from also being isomorphic to a product of three cyclic groups. In particular, suppose that you have an elliptic curve of cardinal $n$. You can then find points $P$, $Q$ and $R$, of order $p$, $q$ and $r$, respectively, over that curve. Then, the curve will be isomorphic to the product of the three subgroups generated by $P$, $Q$ and $R$, which means that every point $T$ of the curve can be uniquely decomposed as $T = uP + vQ + wR$ for three integers $u$, $v$ and $w$ taken modulo $p$, $q$ and $r$, respectively.
It is unclear whether such a curve is really what you want. In cryptography, a lot of the security relies on a clear distinction between what is doable, and what is not. For instance, in a curve such as the one expressed above, given a point $T$, one can find its component $uP$ (on the first subgroup) as:
$$ uP = ((qr)^{-1} bmod p)(qrT) $$
but obtaining $u$ from $uP$ involves solving the discrete logarithm over the subgroup generated by $P$, which is hard and basically infeasible if $p$ is large enough. Whether these characteristics are appropriate for your use case depends on what you want to use that curve for.
Building a curve with a specific order $n$ is not easy. You can use supersingular curves; e.g. in the field $mathbb{Z}_e$ with $e$ prime and $e = 2 bmod 3$, the curve $y^2 = x^3 + B$ (for some $B neq 0$) has order exactly $e+1$ points. However, discrete logarithm on that curve is relatively easy (you'd need $e$ to have size at least 1024 bits, which means that operations will be slower than what we usually get with elliptic curves). For non-supersingular curves, Complex Multiplication theory can help: given your target order $n = pqr$, if you can find a prime integer $e$ such that $e = 1 bmod 3$, and an integer $g$ such that:
$$ 4e - (e+1-n)^2 = 3g^2 $$
then about 1/6th of curves of equation $y^2 = x^3 + B$ over the field $mathbb{Z}_e$ (for constants $B neq 0$) will have order exactly $n$. Finding solutions to that kind of equation is not easy and I am unsure there is actually a known method for that.
In any case, a first step would be first to define, precisely, the kind of properties that you need, in particular which relations and transformations need to be feasible, and which must not be feasible, in order to ensure the security of whatever scheme you want to build on top of that curve.
$endgroup$
$begingroup$
So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
$endgroup$
– J. Doe
4 hours ago
$begingroup$
Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
$endgroup$
– J. Doe
3 hours ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
J. Doe is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66597%2felliptic-curve-as-a-product-of-3-cyclic-groups-possible%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $mathbb{Z}_{n_1} times mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides the group order, but $r^2$ does not, then there is a field extension of some degree such that, in the field extension, there are $r^2$ points of order $r$, and these points are a subgroup isomorphic to $mathbb{Z}_r times mathbb{Z}_r$. This is probably not what you want.
For an integer $n = pqr$, for three integers $p$, $q$ and $r$ which are prime to each other, $mathbb{Z}_n$ is cyclic, but it is also isomorphic to $mathbb{Z}_p times mathbb{Z}_q times mathbb{Z}_r$. This is what the Chinese Remainder Theorem is about. What this means is that being cyclic does not prevent a group from also being isomorphic to a product of three cyclic groups. In particular, suppose that you have an elliptic curve of cardinal $n$. You can then find points $P$, $Q$ and $R$, of order $p$, $q$ and $r$, respectively, over that curve. Then, the curve will be isomorphic to the product of the three subgroups generated by $P$, $Q$ and $R$, which means that every point $T$ of the curve can be uniquely decomposed as $T = uP + vQ + wR$ for three integers $u$, $v$ and $w$ taken modulo $p$, $q$ and $r$, respectively.
It is unclear whether such a curve is really what you want. In cryptography, a lot of the security relies on a clear distinction between what is doable, and what is not. For instance, in a curve such as the one expressed above, given a point $T$, one can find its component $uP$ (on the first subgroup) as:
$$ uP = ((qr)^{-1} bmod p)(qrT) $$
but obtaining $u$ from $uP$ involves solving the discrete logarithm over the subgroup generated by $P$, which is hard and basically infeasible if $p$ is large enough. Whether these characteristics are appropriate for your use case depends on what you want to use that curve for.
Building a curve with a specific order $n$ is not easy. You can use supersingular curves; e.g. in the field $mathbb{Z}_e$ with $e$ prime and $e = 2 bmod 3$, the curve $y^2 = x^3 + B$ (for some $B neq 0$) has order exactly $e+1$ points. However, discrete logarithm on that curve is relatively easy (you'd need $e$ to have size at least 1024 bits, which means that operations will be slower than what we usually get with elliptic curves). For non-supersingular curves, Complex Multiplication theory can help: given your target order $n = pqr$, if you can find a prime integer $e$ such that $e = 1 bmod 3$, and an integer $g$ such that:
$$ 4e - (e+1-n)^2 = 3g^2 $$
then about 1/6th of curves of equation $y^2 = x^3 + B$ over the field $mathbb{Z}_e$ (for constants $B neq 0$) will have order exactly $n$. Finding solutions to that kind of equation is not easy and I am unsure there is actually a known method for that.
In any case, a first step would be first to define, precisely, the kind of properties that you need, in particular which relations and transformations need to be feasible, and which must not be feasible, in order to ensure the security of whatever scheme you want to build on top of that curve.
$endgroup$
$begingroup$
So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
$endgroup$
– J. Doe
4 hours ago
$begingroup$
Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
$endgroup$
– J. Doe
3 hours ago
add a comment |
$begingroup$
Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $mathbb{Z}_{n_1} times mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides the group order, but $r^2$ does not, then there is a field extension of some degree such that, in the field extension, there are $r^2$ points of order $r$, and these points are a subgroup isomorphic to $mathbb{Z}_r times mathbb{Z}_r$. This is probably not what you want.
For an integer $n = pqr$, for three integers $p$, $q$ and $r$ which are prime to each other, $mathbb{Z}_n$ is cyclic, but it is also isomorphic to $mathbb{Z}_p times mathbb{Z}_q times mathbb{Z}_r$. This is what the Chinese Remainder Theorem is about. What this means is that being cyclic does not prevent a group from also being isomorphic to a product of three cyclic groups. In particular, suppose that you have an elliptic curve of cardinal $n$. You can then find points $P$, $Q$ and $R$, of order $p$, $q$ and $r$, respectively, over that curve. Then, the curve will be isomorphic to the product of the three subgroups generated by $P$, $Q$ and $R$, which means that every point $T$ of the curve can be uniquely decomposed as $T = uP + vQ + wR$ for three integers $u$, $v$ and $w$ taken modulo $p$, $q$ and $r$, respectively.
It is unclear whether such a curve is really what you want. In cryptography, a lot of the security relies on a clear distinction between what is doable, and what is not. For instance, in a curve such as the one expressed above, given a point $T$, one can find its component $uP$ (on the first subgroup) as:
$$ uP = ((qr)^{-1} bmod p)(qrT) $$
but obtaining $u$ from $uP$ involves solving the discrete logarithm over the subgroup generated by $P$, which is hard and basically infeasible if $p$ is large enough. Whether these characteristics are appropriate for your use case depends on what you want to use that curve for.
Building a curve with a specific order $n$ is not easy. You can use supersingular curves; e.g. in the field $mathbb{Z}_e$ with $e$ prime and $e = 2 bmod 3$, the curve $y^2 = x^3 + B$ (for some $B neq 0$) has order exactly $e+1$ points. However, discrete logarithm on that curve is relatively easy (you'd need $e$ to have size at least 1024 bits, which means that operations will be slower than what we usually get with elliptic curves). For non-supersingular curves, Complex Multiplication theory can help: given your target order $n = pqr$, if you can find a prime integer $e$ such that $e = 1 bmod 3$, and an integer $g$ such that:
$$ 4e - (e+1-n)^2 = 3g^2 $$
then about 1/6th of curves of equation $y^2 = x^3 + B$ over the field $mathbb{Z}_e$ (for constants $B neq 0$) will have order exactly $n$. Finding solutions to that kind of equation is not easy and I am unsure there is actually a known method for that.
In any case, a first step would be first to define, precisely, the kind of properties that you need, in particular which relations and transformations need to be feasible, and which must not be feasible, in order to ensure the security of whatever scheme you want to build on top of that curve.
$endgroup$
$begingroup$
So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
$endgroup$
– J. Doe
4 hours ago
$begingroup$
Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
$endgroup$
– J. Doe
3 hours ago
add a comment |
$begingroup$
Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $mathbb{Z}_{n_1} times mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides the group order, but $r^2$ does not, then there is a field extension of some degree such that, in the field extension, there are $r^2$ points of order $r$, and these points are a subgroup isomorphic to $mathbb{Z}_r times mathbb{Z}_r$. This is probably not what you want.
For an integer $n = pqr$, for three integers $p$, $q$ and $r$ which are prime to each other, $mathbb{Z}_n$ is cyclic, but it is also isomorphic to $mathbb{Z}_p times mathbb{Z}_q times mathbb{Z}_r$. This is what the Chinese Remainder Theorem is about. What this means is that being cyclic does not prevent a group from also being isomorphic to a product of three cyclic groups. In particular, suppose that you have an elliptic curve of cardinal $n$. You can then find points $P$, $Q$ and $R$, of order $p$, $q$ and $r$, respectively, over that curve. Then, the curve will be isomorphic to the product of the three subgroups generated by $P$, $Q$ and $R$, which means that every point $T$ of the curve can be uniquely decomposed as $T = uP + vQ + wR$ for three integers $u$, $v$ and $w$ taken modulo $p$, $q$ and $r$, respectively.
It is unclear whether such a curve is really what you want. In cryptography, a lot of the security relies on a clear distinction between what is doable, and what is not. For instance, in a curve such as the one expressed above, given a point $T$, one can find its component $uP$ (on the first subgroup) as:
$$ uP = ((qr)^{-1} bmod p)(qrT) $$
but obtaining $u$ from $uP$ involves solving the discrete logarithm over the subgroup generated by $P$, which is hard and basically infeasible if $p$ is large enough. Whether these characteristics are appropriate for your use case depends on what you want to use that curve for.
Building a curve with a specific order $n$ is not easy. You can use supersingular curves; e.g. in the field $mathbb{Z}_e$ with $e$ prime and $e = 2 bmod 3$, the curve $y^2 = x^3 + B$ (for some $B neq 0$) has order exactly $e+1$ points. However, discrete logarithm on that curve is relatively easy (you'd need $e$ to have size at least 1024 bits, which means that operations will be slower than what we usually get with elliptic curves). For non-supersingular curves, Complex Multiplication theory can help: given your target order $n = pqr$, if you can find a prime integer $e$ such that $e = 1 bmod 3$, and an integer $g$ such that:
$$ 4e - (e+1-n)^2 = 3g^2 $$
then about 1/6th of curves of equation $y^2 = x^3 + B$ over the field $mathbb{Z}_e$ (for constants $B neq 0$) will have order exactly $n$. Finding solutions to that kind of equation is not easy and I am unsure there is actually a known method for that.
In any case, a first step would be first to define, precisely, the kind of properties that you need, in particular which relations and transformations need to be feasible, and which must not be feasible, in order to ensure the security of whatever scheme you want to build on top of that curve.
$endgroup$
Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $mathbb{Z}_{n_1} times mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides the group order, but $r^2$ does not, then there is a field extension of some degree such that, in the field extension, there are $r^2$ points of order $r$, and these points are a subgroup isomorphic to $mathbb{Z}_r times mathbb{Z}_r$. This is probably not what you want.
For an integer $n = pqr$, for three integers $p$, $q$ and $r$ which are prime to each other, $mathbb{Z}_n$ is cyclic, but it is also isomorphic to $mathbb{Z}_p times mathbb{Z}_q times mathbb{Z}_r$. This is what the Chinese Remainder Theorem is about. What this means is that being cyclic does not prevent a group from also being isomorphic to a product of three cyclic groups. In particular, suppose that you have an elliptic curve of cardinal $n$. You can then find points $P$, $Q$ and $R$, of order $p$, $q$ and $r$, respectively, over that curve. Then, the curve will be isomorphic to the product of the three subgroups generated by $P$, $Q$ and $R$, which means that every point $T$ of the curve can be uniquely decomposed as $T = uP + vQ + wR$ for three integers $u$, $v$ and $w$ taken modulo $p$, $q$ and $r$, respectively.
It is unclear whether such a curve is really what you want. In cryptography, a lot of the security relies on a clear distinction between what is doable, and what is not. For instance, in a curve such as the one expressed above, given a point $T$, one can find its component $uP$ (on the first subgroup) as:
$$ uP = ((qr)^{-1} bmod p)(qrT) $$
but obtaining $u$ from $uP$ involves solving the discrete logarithm over the subgroup generated by $P$, which is hard and basically infeasible if $p$ is large enough. Whether these characteristics are appropriate for your use case depends on what you want to use that curve for.
Building a curve with a specific order $n$ is not easy. You can use supersingular curves; e.g. in the field $mathbb{Z}_e$ with $e$ prime and $e = 2 bmod 3$, the curve $y^2 = x^3 + B$ (for some $B neq 0$) has order exactly $e+1$ points. However, discrete logarithm on that curve is relatively easy (you'd need $e$ to have size at least 1024 bits, which means that operations will be slower than what we usually get with elliptic curves). For non-supersingular curves, Complex Multiplication theory can help: given your target order $n = pqr$, if you can find a prime integer $e$ such that $e = 1 bmod 3$, and an integer $g$ such that:
$$ 4e - (e+1-n)^2 = 3g^2 $$
then about 1/6th of curves of equation $y^2 = x^3 + B$ over the field $mathbb{Z}_e$ (for constants $B neq 0$) will have order exactly $n$. Finding solutions to that kind of equation is not easy and I am unsure there is actually a known method for that.
In any case, a first step would be first to define, precisely, the kind of properties that you need, in particular which relations and transformations need to be feasible, and which must not be feasible, in order to ensure the security of whatever scheme you want to build on top of that curve.
answered 5 hours ago
Thomas PorninThomas Pornin
69.2k13183262
69.2k13183262
$begingroup$
So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
$endgroup$
– J. Doe
4 hours ago
$begingroup$
Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
$endgroup$
– J. Doe
3 hours ago
add a comment |
$begingroup$
So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
$endgroup$
– J. Doe
4 hours ago
$begingroup$
Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
$endgroup$
– J. Doe
3 hours ago
$begingroup$
So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
$endgroup$
– J. Doe
4 hours ago
$begingroup$
So as far as I understand the answer is: It's not possible with elliptic curves. editing...more text coming soon
$endgroup$
– J. Doe
4 hours ago
$begingroup$
Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
$endgroup$
– J. Doe
3 hours ago
$begingroup$
Thanks for quick response and description. I did not fully understand all yet but it seems it doesn't work as I wanted. I forgot to mention above an important detail. In my case also the user himself should not know about the factorization. Given this the $T$ above should not work because the user also knows the $u, v, w$. The user should only have the option to find a random solution for the given elliptic curve by (advanced) trial and error (no factorization). He should also get those 3 generators. Unknown should be the exponents of those 3 generators to reach the point of another user.
$endgroup$
– J. Doe
3 hours ago
add a comment |
J. Doe is a new contributor. Be nice, and check out our Code of Conduct.
J. Doe is a new contributor. Be nice, and check out our Code of Conduct.
J. Doe is a new contributor. Be nice, and check out our Code of Conduct.
J. Doe is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66597%2felliptic-curve-as-a-product-of-3-cyclic-groups-possible%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown