Mixing
Hash to prime numbers?
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Is there some provably secure hash function to prime numbers?
Say, a function $H: 0, 1^* rightarrow e: e in 0, 1^lambda land e$ is prime$$
I'm asking because there are some constructions to be used only on prime numbers (for example CL02 Strong-RSA Dynamic Accumulators).
hash accumulators
edited 3 hours ago
kelalaka
890217
asked 4 hours ago
oleiba
607
add a comment |Â
up vote
3
down vote
favorite
Is there some provably secure hash function to prime numbers?
Say, a function $H: 0, 1^* rightarrow e: e in 0, 1^lambda land e$ is prime$$
I'm asking because there are some constructions to be used only on prime numbers (for example CL02 Strong-RSA Dynamic Accumulators).
hash accumulators
edited 3 hours ago
kelalaka
890217
asked 4 hours ago
oleiba
607
Take a secure hash function, correspond to the result as the n-th prime number. So, you have to know (list) as $2^128$ or $2^512$ or ... prime numbers. and, link to free version of the article?
– kelalaka
4 hours ago
1
Are you interested in a theoretical answer (ie "do such hash functions exist") or how this would be solved in practice?
– SEJPM♦
2 hours ago
1
What's not fulfilled by taking a standard hash $H'$ with $lambda$-bit output, and defining $H(m)$ as the largest prime at most $H'(m)$, or $2$ if there's none? That's reasonably easy to compute, and with a bound of prime gap security can be proven. If the only issue is that's not uniform, that can be improved.
– fgrieu
2 hours ago
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Is there some provably secure hash function to prime numbers?
Say, a function $H: 0, 1^* rightarrow e: e in 0, 1^lambda land e$ is prime$$
I'm asking because there are some constructions to be used only on prime numbers (for example CL02 Strong-RSA Dynamic Accumulators).
hash accumulators
edited 3 hours ago
kelalaka
890217
asked 4 hours ago
oleiba
607
Is there some provably secure hash function to prime numbers?
Say, a function $H: 0, 1^* rightarrow e: e in 0, 1^lambda land e$ is prime$$
I'm asking because there are some constructions to be used only on prime numbers (for example CL02 Strong-RSA Dynamic Accumulators).
hash accumulators
hash accumulators
edited 3 hours ago
kelalaka
890217
asked 4 hours ago
oleiba
607
edited 3 hours ago
kelalaka
890217
asked 4 hours ago
oleiba
607
edited 3 hours ago
kelalaka
890217
edited 3 hours ago
kelalaka
890217
edited 3 hours ago
kelalaka
890217
890217
asked 4 hours ago
oleiba
607
asked 4 hours ago
oleiba
607
asked 4 hours ago
oleiba
607
607
Take a secure hash function, correspond to the result as the n-th prime number. So, you have to know (list) as $2^128$ or $2^512$ or ... prime numbers. and, link to free version of the article?
– kelalaka
4 hours ago
1
Are you interested in a theoretical answer (ie "do such hash functions exist") or how this would be solved in practice?
– SEJPM♦
2 hours ago
1
What's not fulfilled by taking a standard hash $H'$ with $lambda$-bit output, and defining $H(m)$ as the largest prime at most $H'(m)$, or $2$ if there's none? That's reasonably easy to compute, and with a bound of prime gap security can be proven. If the only issue is that's not uniform, that can be improved.
– fgrieu
2 hours ago
add a comment |Â
Take a secure hash function, correspond to the result as the n-th prime number. So, you have to know (list) as $2^128$ or $2^512$ or ... prime numbers. and, link to free version of the article?
– kelalaka
4 hours ago
1
Are you interested in a theoretical answer (ie "do such hash functions exist") or how this would be solved in practice?
– SEJPM♦
2 hours ago
1
What's not fulfilled by taking a standard hash $H'$ with $lambda$-bit output, and defining $H(m)$ as the largest prime at most $H'(m)$, or $2$ if there's none? That's reasonably easy to compute, and with a bound of prime gap security can be proven. If the only issue is that's not uniform, that can be improved.
– fgrieu
2 hours ago
Take a secure hash function, correspond to the result as the n-th prime number. So, you have to know (list) as $2^128$ or $2^512$ or ... prime numbers. and, link to free version of the article?
– kelalaka
4 hours ago
Take a secure hash function, correspond to the result as the n-th prime number. So, you have to know (list) as $2^128$ or $2^512$ or ... prime numbers. and, link to free version of the article?
– kelalaka
4 hours ago
1
1
Are you interested in a theoretical answer (ie "do such hash functions exist") or how this would be solved in practice?
– SEJPM♦
2 hours ago
Are you interested in a theoretical answer (ie "do such hash functions exist") or how this would be solved in practice?
– SEJPM♦
2 hours ago
1
1
What's not fulfilled by taking a standard hash $H'$ with $lambda$-bit output, and defining $H(m)$ as the largest prime at most $H'(m)$, or $2$ if there's none? That's reasonably easy to compute, and with a bound of prime gap security can be proven. If the only issue is that's not uniform, that can be improved.
– fgrieu
2 hours ago
What's not fulfilled by taking a standard hash $H'$ with $lambda$-bit output, and defining $H(m)$ as the largest prime at most $H'(m)$, or $2$ if there's none? That's reasonably easy to compute, and with a bound of prime gap security can be proven. If the only issue is that's not uniform, that can be improved.
– fgrieu
2 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
You could use the hash value as seed for a deterministic CSPRNG and then use a prime number generator also used for RSA key pair generation. Note that the size of the prime number must be relatively high (1536 bits for 128 bits of security, e.g. for an RSA key of 3072 bits).
Note that the usual caveats of deterministic RSA key pair generation apply. For instance, the algorithms must remain the same, otherwise a different prime value is calculated for the same hash value.
answered 46 mins ago
Maarten Bodewes
48.8k569181
add a comment |Â
up vote
-1
down vote
Let $H$ be a provably secure hash function $H:0,1^* rightarrow 2^h$, where $h$ is the output size of the $H$.
Now, using this $H$, we will construct a provably secure hash function to primes $H'$ as follows;
- Let $L$ be a sorted list of primes contains $2^h$ primes.
- given input $m$, calculate $d = H(m)$
- output $L(d)$
$$H'(m) := L(H(m))$$
Since this is just a bijection, $H'$ is a provably secure hash function.
as noted by @sejpm; this will be impractical. Since the cryptographically interesting values, such as $ h geq 256$, must contain a list near to the number of particles in the universe, that is $10^86$.
answered 3 hours ago
kelalaka
890217
One may want to note that this is ver much unpractical because of the list of size $2^h$ especially if $h$ should have cryptographically interesting values such as $h=256$.
– SEJPM♦
3 hours ago
@SEJPM Exactly,
– kelalaka
3 hours ago
1
$i$ is computed but not used, unless we change $L(d)$ to $L(i)$. What's this "base 10"?. It that a reference to the old joke that there are 10 types of people: those who understand binary and those who don't?
– fgrieu
3 hours ago
@fgrieu thank you, $L(i)$. Well if removing the base 10 conversion will be enough to integer based addressing, I can remove the base 10.
– kelalaka
2 hours ago
@kelalaka: ths question's definition already assimilates bitstring $e$ to an integer, presumably per binary (with unspecified endianness, which customarily is taken to imply big-endian when that matters) , and I see no reason to invoke base 10.
– fgrieu
2 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
You could use the hash value as seed for a deterministic CSPRNG and then use a prime number generator also used for RSA key pair generation. Note that the size of the prime number must be relatively high (1536 bits for 128 bits of security, e.g. for an RSA key of 3072 bits).
Note that the usual caveats of deterministic RSA key pair generation apply. For instance, the algorithms must remain the same, otherwise a different prime value is calculated for the same hash value.
answered 46 mins ago
Maarten Bodewes
48.8k569181
add a comment |Â
up vote
3
down vote
You could use the hash value as seed for a deterministic CSPRNG and then use a prime number generator also used for RSA key pair generation. Note that the size of the prime number must be relatively high (1536 bits for 128 bits of security, e.g. for an RSA key of 3072 bits).
Note that the usual caveats of deterministic RSA key pair generation apply. For instance, the algorithms must remain the same, otherwise a different prime value is calculated for the same hash value.
answered 46 mins ago
Maarten Bodewes
48.8k569181
add a comment |Â
up vote
3
down vote
up vote
3
down vote
You could use the hash value as seed for a deterministic CSPRNG and then use a prime number generator also used for RSA key pair generation. Note that the size of the prime number must be relatively high (1536 bits for 128 bits of security, e.g. for an RSA key of 3072 bits).
Note that the usual caveats of deterministic RSA key pair generation apply. For instance, the algorithms must remain the same, otherwise a different prime value is calculated for the same hash value.
answered 46 mins ago
Maarten Bodewes
48.8k569181
You could use the hash value as seed for a deterministic CSPRNG and then use a prime number generator also used for RSA key pair generation. Note that the size of the prime number must be relatively high (1536 bits for 128 bits of security, e.g. for an RSA key of 3072 bits).
Note that the usual caveats of deterministic RSA key pair generation apply. For instance, the algorithms must remain the same, otherwise a different prime value is calculated for the same hash value.
answered 46 mins ago
Maarten Bodewes
48.8k569181
edited 14 mins ago
answered 46 mins ago
Maarten Bodewes
48.8k569181
answered 46 mins ago
Maarten Bodewes
48.8k569181
answered 46 mins ago
Maarten Bodewes
48.8k569181
48.8k569181
add a comment |Â
add a comment |Â
up vote
-1
down vote
Let $H$ be a provably secure hash function $H:0,1^* rightarrow 2^h$, where $h$ is the output size of the $H$.
Now, using this $H$, we will construct a provably secure hash function to primes $H'$ as follows;
- Let $L$ be a sorted list of primes contains $2^h$ primes.
- given input $m$, calculate $d = H(m)$
- output $L(d)$
$$H'(m) := L(H(m))$$
Since this is just a bijection, $H'$ is a provably secure hash function.
as noted by @sejpm; this will be impractical. Since the cryptographically interesting values, such as $ h geq 256$, must contain a list near to the number of particles in the universe, that is $10^86$.
answered 3 hours ago
kelalaka
890217
One may want to note that this is ver much unpractical because of the list of size $2^h$ especially if $h$ should have cryptographically interesting values such as $h=256$.
– SEJPM♦
3 hours ago
@SEJPM Exactly,
– kelalaka
3 hours ago
1
$i$ is computed but not used, unless we change $L(d)$ to $L(i)$. What's this "base 10"?. It that a reference to the old joke that there are 10 types of people: those who understand binary and those who don't?
– fgrieu
3 hours ago
@fgrieu thank you, $L(i)$. Well if removing the base 10 conversion will be enough to integer based addressing, I can remove the base 10.
– kelalaka
2 hours ago
@kelalaka: ths question's definition already assimilates bitstring $e$ to an integer, presumably per binary (with unspecified endianness, which customarily is taken to imply big-endian when that matters) , and I see no reason to invoke base 10.
– fgrieu
2 hours ago
add a comment |Â
up vote
-1
down vote
Let $H$ be a provably secure hash function $H:0,1^* rightarrow 2^h$, where $h$ is the output size of the $H$.
Now, using this $H$, we will construct a provably secure hash function to primes $H'$ as follows;
- Let $L$ be a sorted list of primes contains $2^h$ primes.
- given input $m$, calculate $d = H(m)$
- output $L(d)$
$$H'(m) := L(H(m))$$
Since this is just a bijection, $H'$ is a provably secure hash function.
as noted by @sejpm; this will be impractical. Since the cryptographically interesting values, such as $ h geq 256$, must contain a list near to the number of particles in the universe, that is $10^86$.
answered 3 hours ago
kelalaka
890217
One may want to note that this is ver much unpractical because of the list of size $2^h$ especially if $h$ should have cryptographically interesting values such as $h=256$.
– SEJPM♦
3 hours ago
@SEJPM Exactly,
– kelalaka
3 hours ago
1
$i$ is computed but not used, unless we change $L(d)$ to $L(i)$. What's this "base 10"?. It that a reference to the old joke that there are 10 types of people: those who understand binary and those who don't?
– fgrieu
3 hours ago
@fgrieu thank you, $L(i)$. Well if removing the base 10 conversion will be enough to integer based addressing, I can remove the base 10.
– kelalaka
2 hours ago
@kelalaka: ths question's definition already assimilates bitstring $e$ to an integer, presumably per binary (with unspecified endianness, which customarily is taken to imply big-endian when that matters) , and I see no reason to invoke base 10.
– fgrieu
2 hours ago
add a comment |Â
up vote
-1
down vote
up vote
-1
down vote
Let $H$ be a provably secure hash function $H:0,1^* rightarrow 2^h$, where $h$ is the output size of the $H$.
Now, using this $H$, we will construct a provably secure hash function to primes $H'$ as follows;
- Let $L$ be a sorted list of primes contains $2^h$ primes.
- given input $m$, calculate $d = H(m)$
- output $L(d)$
$$H'(m) := L(H(m))$$
Since this is just a bijection, $H'$ is a provably secure hash function.
as noted by @sejpm; this will be impractical. Since the cryptographically interesting values, such as $ h geq 256$, must contain a list near to the number of particles in the universe, that is $10^86$.
answered 3 hours ago
kelalaka
890217
Let $H$ be a provably secure hash function $H:0,1^* rightarrow 2^h$, where $h$ is the output size of the $H$.
Now, using this $H$, we will construct a provably secure hash function to primes $H'$ as follows;
- Let $L$ be a sorted list of primes contains $2^h$ primes.
- given input $m$, calculate $d = H(m)$
- output $L(d)$
$$H'(m) := L(H(m))$$
Since this is just a bijection, $H'$ is a provably secure hash function.
as noted by @sejpm; this will be impractical. Since the cryptographically interesting values, such as $ h geq 256$, must contain a list near to the number of particles in the universe, that is $10^86$.
answered 3 hours ago
kelalaka
890217
edited 2 hours ago
answered 3 hours ago
kelalaka
890217
answered 3 hours ago
kelalaka
890217
answered 3 hours ago
kelalaka
890217
890217
One may want to note that this is ver much unpractical because of the list of size $2^h$ especially if $h$ should have cryptographically interesting values such as $h=256$.
– SEJPM♦
3 hours ago
@SEJPM Exactly,
– kelalaka
3 hours ago
1
$i$ is computed but not used, unless we change $L(d)$ to $L(i)$. What's this "base 10"?. It that a reference to the old joke that there are 10 types of people: those who understand binary and those who don't?
– fgrieu
3 hours ago
@fgrieu thank you, $L(i)$. Well if removing the base 10 conversion will be enough to integer based addressing, I can remove the base 10.
– kelalaka
2 hours ago
@kelalaka: ths question's definition already assimilates bitstring $e$ to an integer, presumably per binary (with unspecified endianness, which customarily is taken to imply big-endian when that matters) , and I see no reason to invoke base 10.
– fgrieu
2 hours ago
add a comment |Â
One may want to note that this is ver much unpractical because of the list of size $2^h$ especially if $h$ should have cryptographically interesting values such as $h=256$.
– SEJPM♦
3 hours ago
@SEJPM Exactly,
– kelalaka
3 hours ago
1
$i$ is computed but not used, unless we change $L(d)$ to $L(i)$. What's this "base 10"?. It that a reference to the old joke that there are 10 types of people: those who understand binary and those who don't?
– fgrieu
3 hours ago
@fgrieu thank you, $L(i)$. Well if removing the base 10 conversion will be enough to integer based addressing, I can remove the base 10.
– kelalaka
2 hours ago
@kelalaka: ths question's definition already assimilates bitstring $e$ to an integer, presumably per binary (with unspecified endianness, which customarily is taken to imply big-endian when that matters) , and I see no reason to invoke base 10.
– fgrieu
2 hours ago
One may want to note that this is ver much unpractical because of the list of size $2^h$ especially if $h$ should have cryptographically interesting values such as $h=256$.
– SEJPM♦
3 hours ago
One may want to note that this is ver much unpractical because of the list of size $2^h$ especially if $h$ should have cryptographically interesting values such as $h=256$.
– SEJPM♦
3 hours ago
@SEJPM Exactly,
– kelalaka
3 hours ago
@SEJPM Exactly,
– kelalaka
3 hours ago
1
1
$i$ is computed but not used, unless we change $L(d)$ to $L(i)$. What's this "base 10"?. It that a reference to the old joke that there are 10 types of people: those who understand binary and those who don't?
– fgrieu
3 hours ago
$i$ is computed but not used, unless we change $L(d)$ to $L(i)$. What's this "base 10"?. It that a reference to the old joke that there are 10 types of people: those who understand binary and those who don't?
– fgrieu
3 hours ago
@fgrieu thank you, $L(i)$. Well if removing the base 10 conversion will be enough to integer based addressing, I can remove the base 10.
– kelalaka
2 hours ago
@fgrieu thank you, $L(i)$. Well if removing the base 10 conversion will be enough to integer based addressing, I can remove the base 10.
– kelalaka
2 hours ago
@kelalaka: ths question's definition already assimilates bitstring $e$ to an integer, presumably per binary (with unspecified endianness, which customarily is taken to imply big-endian when that matters) , and I see no reason to invoke base 10.
– fgrieu
2 hours ago
@kelalaka: ths question's definition already assimilates bitstring $e$ to an integer, presumably per binary (with unspecified endianness, which customarily is taken to imply big-endian when that matters) , and I see no reason to invoke base 10.
– fgrieu
2 hours ago
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f63013%2fhash-to-prime-numbers%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Take a secure hash function, correspond to the result as the n-th prime number. So, you have to know (list) as $2^128$ or $2^512$ or ... prime numbers. and, link to free version of the article?
– kelalaka
4 hours ago
1
Are you interested in a theoretical answer (ie "do such hash functions exist") or how this would be solved in practice?
– SEJPM♦
2 hours ago
1
What's not fulfilled by taking a standard hash $H'$ with $lambda$-bit output, and defining $H(m)$ as the largest prime at most $H'(m)$, or $2$ if there's none? That's reasonably easy to compute, and with a bound of prime gap security can be proven. If the only issue is that's not uniform, that can be improved.
– fgrieu
2 hours ago