72

First things first, I would not have described BearSSL as being "bignum-free". However, it is true that it does not have a generic implementation of big integers; what it contains is a generic implementation (actually several) of big modular integers. And it matters. About low-level multiplications Software libraries run on some hardware and cannot use ...


38

It just means that BearSSL was implemented without using any third-party bignum libraries. According to the BearSSL website: BearSSL's current implementation are less than optimal with regards to performance; they are in pure C, with only 32-bit multiplications. Better implementations shall be added in subsequent versions. Avoiding the use of external ...


23

I recently wrote a big page on how big integers are implemented in BearSSL. There are several ways to represent integers in RAM and compute operations on them; also, note that for cryptography, we usually need big modular integers, which is not the same as big plain integers. BearSSL's code is constant-time, thus nominally immune to timing attacks (subject ...


16

There's at least 5 reasons why multiply is not more often used in symmetric ciphers and hashes: For use as mixer, multiplication requires more hardware/energy/time than other hardware constructs of comparable cryptographic interest. This is an argument mostly for hardware implementations, but many ciphers (and a few hashes) are designed so as to be fast in ...


5

So is there any method of doing this properly? Here's the most obvious method: Iterate through the lower 14 bits of $y$, that is, you'll perform the below steps for each of the 16384 possible settings of the lower bits of $y$ Compute what the lower 14 bits of $x$ are, using $x = A - y$ (because the subtraction is modulo $2^{64}$, we can ignore everything ...


4

So, I don't see how can I measure the complexity of Chinese remainder theorem in term of the number of multiplication in G of order N. Any ideas? Well, the standard way to solve for $x$ (given that $n_0, n_1$ are relatively prime) is to compute: $$x = n_1 ((a_0 - a_1) n_1^{-1} \bmod n_0) + a_1$$ (where $n_1^{-1}$ is computed modulo $n_0$) It is ...


4

In your setting this is assumed to be hard. It is exactly the task of producing a forgery for message $s$ of the weakly secure Boneh-Boyen signature scheme (Sec. 3.1) under public key $g^{e_1}$ (note that the scheme is presented in the asymmetric setting but can equally be instantiated in the symmetric setting under the $q$-SDH assumption). In other words, ...


4

Firstly, $|\mathbb Z_n|=n$, whereas $|\mathbb Z_n^*|=\varphi(n)<n$. So, by the pigeon-hole principal there cannot be a mathematically invertible function $f:\mathbb Z_n\to\mathbb Z_n^*$. So, lets relax our idea of what 'invertible' means a bit. How about ensuring every element of $\mathbb Z_n^*$ has a preimage? Yep, we can do that. To use a couple of ...


4

If I understand what you're looking for correctly, that would completely destroy the security. First off, if an attacker can compute the difference between her value and the mean, it is trivial to find the actual mean. Simply encrypt the number $0$ and then compare it to the mean. If she can compute the mean of any subset, it's pretty trivial to recover ...


4

Here is a specialization of this answer that is efficient in term of average entropy loss, and easily implemented. Let $n$ be the number of faces on the dice ($n=6$ for a common dice). Let $b$ be the minimum value on the dice ($b=1$ on a common dice). Let $m$ be some large integer with $m≥n^2$. No value used will exceed $m$. Set $r←0$, $s←1$. If $s$ is ...


3

I believe what you are looking for is Functional encryption This will allow you to create a key which will allow limited operation on the ciphertext, in this case the differences to the mean. Obviously from your definition the information leakage is very large if we are looking at scalar values, knowing the set of differences of a set of numbers from ...


3

The first byte is 0x00, because some standards allow RSA key sizes $8b+1, b \in \Bbb Z_+$. Such key would have 0x01 at the first bit, but it is possible for almost all other bits to be zero. Thus, 0x00 as the first byte allows interoperability with all possible RSA key sizes. NIST's recommendations and few other standards actually recommend only few specific ...


2

I would point out three things relating to this question. Normal dice In practice This is a cryptography forum The first two points mean that you might be using biased dice. Normal dice are non homogeneous, perhaps chipped and might even be missing some spots. So their rolls would favour one outcome over another in the long run. They go to great ...


2

Let $a$ and $b$ be the numbers emited rsp. by person A and person B. $E(x)$ means encoded form of $x$. $E(a)$ and $E(b)$ are publicly known, right? Note that if person A knows $a$, $E(a)$, $E(b)$ and person B knows $b$, $E(a)$, $E(b)$ and it is possible to calculate $a+b$ from $E(a)$ and $E(b)$ (that is what you want to do, right? So it must be possible) ...


2

Yes, as @DrLecter said in the comments, that equation holds from the bilinear property. Here is a step-by-step proof. Let $e : \mathbb G_1 \times \mathbb G_2 \to \mathbb G_T$ be a bilinear pairing. The bilinear property states that: \begin{align}e(g_1 ^ a, g_2 ^b) = e(g_1,g_2)^{ab}\end{align} Since you don't seem to distinguish between $\mathbb G_1$ and $...


2

There has been research into Fully Homomorphic Encryption, which can be implemented using lattice-based cryptography. Theoretically, FHE lets you run arbitrary computer programs on encrypted data, including the one you want. It's slow, though. It would take millions of years just to evaluate relatively simple gates using this method. https://dl.acm.org/...


2

Does the following equation hold in bilinear pairings? No, not in general. $g$ is posited to be a generator, and so (for any fixed $D$), we have $H(D) = g^b$, for some integer $b$ (which is hard to compute, but we're not going to have to compute it). So, we have $e(H(D)g^a, g) = e(g^{a+b}, g)$. If we move the $a$ exponent out, we then get $e(g^{1 + b/a}, g) ...


2

Why are arithmetic circuits interesting in the zero-knowledge world? There are two main models of general computation: Circuits and Turing-Machines. Describing the computation path of turing machines is what most mainstream programming languages try to do, however for cryptographic processing there are disadvantages associated with Turing-Machines. Namely, ...


2

This answer tackles mostly the first bullet: How are large numbers handled in cryptography and cryptanalysis? Getting the result Many computer languages and most computer hardware do not directly support variables larger than 64-bit (hence product of larger than 32-bit integers), or double that. Many cryptographic algorithms use much wider integers (e.g....


1

Suppose $L$ is an NP language, and its witness checking algorithm is $R$, so that $L = \{ x \mid \exists w : R(x,w) = 1 \}$. Here is how I can prove to you that $x \in L$: Generate a circuit $C$ such that $C(w) = R(x,w)$. We can both do this because $R$ is a public algorithm and $x$ is also public. This circuit $C$ has the instance $x$ "hard-coded"...


1

(I observe $S=c\cdot P$ for some integer $c$.) Is that always the case? Yes. Proof follows. If $g=P$ then $S=0$. We'll disregard this special case in the following. The set $M$ has $k$ elements, with $k$ the lowest strictly positive integer with $g^k\equiv1\pmod P$. This $k$ is known as the order of $g$ modulo $P$. This $k$ divides $P-1$. $M$ also is $\{g^...


1

I think simply put. However fast multiplication is, simple bitwise operations are even faster - and can be executed sometimes out of order, and in parallel by multiple execution units in the CPU. Moreover - major criteria of any algorithm design is the ability to implement it in hardware. Simplicity and ability to parallelise operation, thus lowering the ...


1

Over $\mathbb{F}_p$ an elliptic curve and its quadratic twist have isomorphic endomorphism rings. If $p\equiv 1 \pmod{3}$, the six curves with $j=0$ all have their endomorphism ring isomorphic to $\mathbb{Z}[\frac{1+\sqrt{-3}}{2}]$ and if $p\equiv 1\pmod{4}$, the four curves $E$ with $j=1728$ all have $End(E)$ isomorphic to the ring of Gaussian integers $\...


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