23

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 structure is not a field. Also: don't forget RSA! RSA works in a ring, not a field.


16

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, Benaloh, Okamoto-Uchiyama, Naccache-Stern, Paillier, Damgard-Jurik, BCP, and many other related cryptosystems. This also includes all works based on composite-...


7

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 or finite fields.)


6

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 states: Given a finite group $G$, sample $a,b\in G$ uniformly at random and provide $g^a,g^b$. The problem is solved if you can find $g^{ab}$. Proof: CDH is at ...


6

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 chosen from $S$." and to quote SEJPM from the comments: If $p\in \mathbb P$ (with $\mathbb P$ being the set of all primes) then the notations $GF(p);\...


6

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 you've fixed $p$, there are $\sim2p$ isomorphism class of elliptic curves defined over $\mathbb{F}_p$, which grants you a big set where you are supposed to find a ...


6

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 public key, which can be used to create a randomized encryption of 0 that can then have the message added to it. The cipher operates over integers, but does ...


5

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 represent the elements of the elliptic curve group $G$. If the eliptic curve group is carefully chosen, that is. So, avoid anomalous curves, for example.


5

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 a constant time modulo operation, it's constant time...


5

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 performing field multiplication. Because otherwise the carry bits need to be handled by subsequent additions, which slows down even modern CPUs. So according to ...


5

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 are even more efficient, like Koblitz curves. However, in general, our confidence in the security of these curves is less than for prime-field curves. Thus, in ...


4

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 your situation is a "classical" modulus in crypto (e.g. $n = (2q+1)^k$ for a prime $q$ and a small $k$, etc), as the modulus will be in general chosen so that ord$...


4

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 space can be any domain. Note that the secret $s$ is from the domain, too. The note simply says that whatever the domain $\mathscr{D}$ is we can simply impose an ...


3

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 or FRI. Binary fields allow the use of XOR rather than addition with carry, and carry-less multiplication. That makes computations of field arithmetic easier, ...


3

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 probability at most $2^{-64}$, you need your parameter $k \ge 64$ I would imagine that the proportion of $x \in \mathbb{F}_q$ that do not result in quadratic ...


2

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 chooses one at random and solves the puzzle. The solution to each puzzle reveals a (unique) session key and identifier. Alice sends the identifier (in cleartext) ...


2

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 very few primes are) there will always be some bias. $p$ is not a divisor of $2^{512}$, and hence some values will have more 512 bit preimages than others (and ...


1

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 not specifically relevant to the strength of a curve over $\operatorname{GF}(p)$. Now, it is quite relevant to the strength of the group $\mathbb{Z}_p^*$; ...


1

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 assumption. Therefore, since STARKs don't use ECC and use hashing and bit-shifting instead, it (somewhat) doesn't matter which field characteristic is chosen, so ...


1

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. I have a prime $p$ and random strings with length $n$. Let $S = \{0,1\}^n$ and define the function $H : S \rightarrow F_p, ~~~ H(x) \mapsto x \bmod p$ ...


1

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 following condition: For all $i\neq j$ it holds that $\alpha_i - \alpha_j\in R$ is a unit.* The way you prove this is exactly the same as you prove it for the ...


1

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 then the hash value is fed in the signing/verification algorithms. Therefore the fact that the shares are in $F_p$ will not affect signature generation and ...


1

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 resistant to timing attacks (i.e. no need to handle carries); For the same reason, are easier to implement in hardware; Some processors have support for binary ...


1

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 subgroup of a finite group $G$, then $\lvert H\rvert$ divides $\lvert G\rvert$.


1

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 curves and gave them separate names from the SEC curves by the Certicom corporation. I'll show you the Bouncy Castle code for the NIST curves: defineCurve("B-571", ...


1

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 as follows, taken from this document from ETH Zurich. The theorem is: Let $q$ be an odd prime power, and $a \in \mathbb{F}_q$, then: $a \in QR(q), \iff a^{(q-...


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