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 ...
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,...
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 ...
user avatar
  • 31.3k
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 ...
user avatar
  • 44.6k
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 ...
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 ...
user avatar
  • 6,329
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 ...
user avatar
  • 19.2k
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 ...
user avatar
  • 16.4k
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 ...
user avatar
  • 132k
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 ...
user avatar
  • 7,246
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 ...
user avatar
4 votes

Is the complexity of Pollard rho for discrete logartihm really the modulus?

The complexity of Pollard-Rho is indeed $O(\sqrt{\text{ord}(g)})$, but even though $n$ refers to the modulus, their statement might be correct depending of the context. If the modulus considered in ...
user avatar
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 ...
user avatar
  • 124k
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 ...
user avatar
  • 43.4k
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 ...
user avatar
  • 132k
3 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 ...
user avatar
  • 132k
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....
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 ...
user avatar
  • 5,248
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 ...
user avatar
  • 132k
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 ...
user avatar
1 vote

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 ...
user avatar
  • 3,697
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 ...
user avatar
  • 4,018
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 ...
user avatar
  • 6,109
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 ...
user avatar
  • 11.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 ...
user avatar
  • 85.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 ...
user avatar
  • 355

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