Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
23 votes
Accepted

Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?

Braid cryptography? Knapsack cryptosystems, like Nasako–Murikami? Lattice-based cryptography tends to work in polynomial rings or modules with coefficients in finite fields, but whose higher-level ...
Squeamish Ossifrage's user avatar
16 votes

Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?

Cryptography over quasi-fields (which are not field, but where non-invertible elements are hard to find) is very common. This includes many cryptosystems such as RSA, but also Rabin, Goldwasser-Micali,...
Geoffroy Couteau's user avatar
7 votes

Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?

Hash-based signatures also seem to fit the bill and have not yet been mentioned. E.g. Merkle signatures and their variants. (For it to qualify the hash function used cannot be based on prime fields ...
otus's user avatar
  • 32.1k
6 votes

Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?

There is a public key cryptosystem mentioned oh so briefly in Fully Homomorphic Encryption Over The Integers, built from a secret key cryptosystem. It operates by distributing encryptions of 0 as a ...
Ella Rose's user avatar
  • 19.6k
6 votes
Accepted

Is the prime P is fixed for an elliptic curve defined over a particular prime field F_p?

In general you start by fixing the field, which translates into fixing the prime, and then you start to look to a suitable (i.e. secure/safe) elliptic curve defined over that field. Note that, once ...
Ruggero's user avatar
  • 7,104
6 votes
Accepted

Does this computation lead to solving DL?

No. Assuming that uniformly random sampling for $x,b$ is applied, this (let's call it E-CDH) is actually equivalent (in terms of hardness) to the Computational Diffie-Hellman Problem (CDH). Which ...
SEJPM's user avatar
  • 46.1k
6 votes
Accepted

Subscript R notation for the finite fields

To quote yyyyyyy from the comments: The $_R$ has nothing to do with the field — it is associated to $\in$! To quote your first link: "For a set $S$, by $a\in_R S$, we mean that $a$ is randomly ...
5 votes
Accepted

How to determine proportion of quadratic residues in elliptic curve group?

I have read that the proportion is close to $\frac{1}{2}$ That is, in fact, correct; it is (for large $p$) extremely close to $\frac{1}{2}$; hence if you need your hashing process to fail with ...
poncho's user avatar
  • 148k
5 votes

Comparing elliptic curves over prime fields against EC over binary fields

Binary fields were developed since they yield more efficient implementations. This is especially true given the Intel PCLMULQDQ instruction. Note, that there are special types of Binary fields that ...
Yehuda Lindell's user avatar
5 votes
Accepted

Randomizing Prime Field Elements

is another method commonly practiced? Sample $\lceil \log_2p \rceil+64$ bits, and reduce its corresponding integer modulo $p$. There will still be a bias, but it is tiny. And, assuming that you use ...
poncho's user avatar
  • 148k
5 votes
Accepted

Questions about the Curve25519-donna implementation

You have 5 limbs because it is based on DJB's papers and as the Ed25519 paper mentions, it's using a $2^{51}$ radix representation for performance reasons. It does so in order to avoid carries when ...
Lery's user avatar
  • 7,699
5 votes
Accepted

Why is the strength of an Elliptic Curve Cryptography (ECC) half the size of the prime field size?

This is essentially because the best known generic algorithms for discrete logarithm, e.g., baby step giant step, have complexity $$O(\sqrt{G})=O(2^{n/2})$$ where $n$ is the number of bits to ...
kodlu's user avatar
  • 22.6k
4 votes
Accepted

Why does libSTARK use binary fields as opposed to prime fields for zk-SNARKs?

Caution: This answer is about the basics of why binary fields $\Bbb F_{2^k}$ are sometime preferred to prime fields $\Bbb Z_{p}$. It does not cover the specifics there may be for zk-STARKs, libSTARK ...
fgrieu's user avatar
  • 142k
4 votes
Accepted

Is linear secret sharing over the addittive group of integers modulo $p$ with $p$ non-prime secure?

What is the most general definition for the domain (I do not get exactly the meaning of the note)? My guess is that $p$ can be any integer. In short, a domain is the input space. As said the input ...
kelalaka's user avatar
  • 48.8k
3 votes
Accepted

Simple: Hash Into a Prime Field

First thing to note is that, if your paradigm is the hash the message into a 512 bit value, and then map that 512 bit field into a value $(0, p-1)$, then (unless $p$ happens to be a power of 2, and ...
poncho's user avatar
  • 148k
3 votes
Accepted

can we modify the prime field by increasing it in secp256k1?

The short answer: No The long answer: No because then the field would not be a prime and things would break horribly. The curve would not be secure anymore. if we keep the double and add operations ...
madhurkant's user avatar
2 votes

Secret sharing over $Z_n*$

You actually have Shamir secret-sharing as long as you have interpolation, and you have interpolation for any ring $R$ as long as your evaluation points $\alpha_1,\ldots,\alpha_\ell$ satisfy the ...
Daniel's user avatar
  • 3,972
2 votes
Accepted

Discrete log of Goldilocks, Babybear, and Mersenne31 fields

The DLP in these small prime fields is quite easy. E.g. for $p=2^{64}-2^{32}+1$, the largest prime factor of $p-1$ is $q=65537$, thus the Pohlig–Hellman algorithm applies, and it's cost is dominated ...
fgrieu's user avatar
  • 142k
2 votes

Randomizing Prime Field Elements

Hi @AryaPourtabatabaie I've been having the exact same problem and would like to find a way to generate a distribution statistically close to uniform on $F_p$. This is my analysis of the above scheme....
Alex Pinto's user avatar
2 votes

Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?

Merkle's Puzzles are often considered to be the first example of public-key cryptography. Bob generates a large number of independent puzzles and sends them all, in random order, to Alice. Alice ...
David Cary's user avatar
  • 5,674
2 votes

can we modify the prime field by increasing it in secp256k1?

NO. With p=2256, which is not prime: If we keep computing with integers modulo p, we no longer have a field, thus we no longer have an Elliptic Curve group. Also the generator would no longer be on ...
fgrieu's user avatar
  • 142k
1 vote
Accepted

Elliptic curve over prime field with high order roots of unity

My question is: does the fact that $\operatorname{GF}(p)$ has "high order" roots of unity make curves defined over this field inherently less secure? Not particularly; the factorization of $p-1$ is ...
poncho's user avatar
  • 148k
1 vote

Why does libSTARK use binary fields as opposed to prime fields for zk-SNARKs?

Short answer: Recall that in EC-based protocols, the security of the protocol depends on the choice of the field characteristic and order of the elliptic curve group, as well as the discrete log ...
user227837's user avatar
1 vote

Secret sharing over $Z_n*$

If you just want to sign the shares like you said, then you don't need the shares to be in $Z_n^*$. You can just share over $F_p$ as usual. To sign a message, usually the message is hashed first and ...
Changyu Dong's user avatar
  • 4,178
1 vote

Comparing elliptic curves over prime fields against EC over binary fields

Binary fields require only xor and shift operations to implement (i.e. no multiplications), and thus are faster in many platforms; For the same reason, they are easier to make their implementations ...
Conrado's user avatar
  • 6,474
1 vote

Order of the curve and generator

The order of any point is a divisor of the curve group order, hence they are never coprime, unless your "generator" is the point at infinity. This follows from Lagrange's theorem: If $H$ is a ...
yyyyyyy's user avatar
  • 12.1k
1 vote

Is the prime P is fixed for an elliptic curve defined over a particular prime field F_p?

The NIST curves as published in FIPS-PUB 186-3 and SEC curves are identical. The P-xxx curves are the same as the secpxxxr1 curves (where xxx is the bit size). NIST just standardized most of the ...
Maarten Bodewes's user avatar
  • 93.1k
1 vote

How to determine proportion of quadratic residues in elliptic curve group?

The answer above is the best explanation but just for reference, the formal proof I was looking for was found quite easily once I realised my question applied to odd-ordered finite fields too, and is ...
bekah's user avatar
  • 365

Only top scored, non community-wiki answers of a minimum length are eligible