7

Given $v_1$ and $v_2$, can the server learn anything about $a$ and $b$? Yes, they can (with high probability) determine whether $a = b$; if $v_2 = 0$, then either $r_1 = 0$ or $a = b$; given that $r_1 = 0$ occurs with probability $1/p$, the attacker can conclude that $a = b$. Now, that's the only thing the attacker can learn; for any observed $v_1, v_2$, ...


6

In a finite field $\mathbb{F}_q$, both maskings are perfectly secure, provided that $x \neq 0$ for the multiplicative masking. This is easy to see. The finite field $\mathbb{F}_q$ defines two groups: the additive group $\mathbb{F}_p^+$ (i.e., $\mathbb{F}_q$ equipped with addition) and the multiplicative group $\mathbb{F}_q^*$ (i.e., $\mathbb{F}_q \setminus ...


5

Alright, let's first agree on a few things: The rsa_private operation is the operation requiring knowledge of the secret RSA key. This operation is required by one of the following processes: RSA signature, to ensure authenticity and integrity of a given message in a way publicly verifiable RSA decryption, to decrypt a message which was sent to you, ...


5

The idea behind a blind signature is that party $\mathcal{A}$ has a message $m$ that they want party $\mathcal{B}$ to sign, but they do not want party $\mathcal{B}$ to learn the value of $m$. Using RSA, where $(e, N)$ is $\mathcal{B}$'s public key and $d$ is it's private key, this may look like: $\mathcal{A}$ computes $x = m*r^e \mod N$, where $r$ is a ...


5

Schnorr signature is a pair challenge-response $(e, s)$ with challenge computed as a hash of message $m$ and initial commitment $r$; signature is verified by re-creating that commitment with challenge and response only. For blind Schnorr signature, one keeps verification equation while randomizing both challenge and response with $\beta, \alpha$ ...


4

Whether multiplicative blinding is drastically worse than additive blinding depends fairly strongly on: The ring are you doing the blinding in Whether you need to blind the value 0 The second is a fairly obvious, as multiplicative blinding doesn't disguise 0 at all. However, it would appear that the slides that you quote the statement from actually falls ...


4

Good blinding requires good randomness. Randomness is a hard requirement, especially for embedded systems. In a similar vein, the DSA and ECDSA signature algorithms require a strongly random integer (called k) for each signature, and several implementations have failed to use random enough values, with hilarious consequences; the most well-known case is Sony ...


3

Would it be a requirement that, given $f(k)$ and $c$, it is hard to rederive $m$? If so, then what you are effectively asking for is a public key encryption system; your public key is $f(k)$, and your private key is $k$. Such a method can be constructed from any public key encryption algorithm (but isn't any more efficient than the underlying pk algorithm). ...


3

First of all, you need to understand what's the point of key blinding in the first place. First of all, you have a server (who has a private key, and who is willing to decrypt messages), and you have a client (who has a value who he wants decrypted, but is unwilling to tell the server what that value is). The client might not want to tell the server what ...


3

If all we know are the blinded values $y_i$ (and the modulus $p$), and if the blinding factors $r_i$ are indeed sampled randomly from the multiplicative group modulo $p$, I don't see any way to recover the secret $x$. This is because, for any list of blinded values $y_i$ and any candidate $x$ value, we can compute a unique list of blinding values $r_i \...


3

It's impossible: Impossibility of Blind Signatures From One-Way Permutations - Katz, Schroder, Yerukhimovich


3

As fgrieu said in comments, $x\to x\cdot b\bmod p$ is just as secure as additive blinding. So we suppose that question is about $x\to x\cdot b$. Here we suppose that factorizations time for $x\cdot b$ is negligible and examine brute force search for finding $b$: In additive blinding let $c=x\cdot b$, we should check all $b$ for meaning $c-b$. So we need ...


2

The adversary can learn whether or not $a$ and $b$ are equivalent (with high probablility). All other information is protected. I asked in the comments whether nor not a finite field was used or if we were working in the integers. This is important, because in the unsigned (positive) integers, the adversary can learn order. Since he has $r_1a+r_2$ and can ...


2

Both constructions are not perfectly secure! In an attempt to express things a bit more mathematically, I'd say you can implement a one-time-pad with a message $m$ and a key $r$, when $m$ and $r$ are elements of $\mathbb{Z}/n\mathbb{Z}$, the additive group of integers modulo n, or when $m$ and $r$ are elements of a group $G$ isomorphic to $\mathbb{Z}/n\...


2

Blinding is usually applied on the whole modulus, and I see no incentive to do otherwise; random is cheap. In RSA, blinding is not always applied as described in the question and article, for efficiency and security reasons: the technique described requires computing $r^d\bmod N$, which is just as costly as the $m^d\bmod N$ operation being protected, and ...


2

Till today, there is no known construction for this. The problem is that standard hash functions do not come with the necessary algebraic properties required for blinding and unblinding.


1

There are at least three possible senses of blinding in crypto in a context involving a hash such as SHA-256. In all cases, the purpose is to hide something (the value, or the true meaning) of some data element manipulated. Blinding with the hash as a tool used as a black box. The exact meaning depends on the purpose. That can further subdivides into we ...


1

Highly suggested paper: Security of Blind Signatures Revisited by Dominique Schröder et al. Especially have a look at Section 3, where the Unforeability and Blindness security games are defined. In case if you don't want to deep dive into the paper, then I give you hereby a high-level description of the corresponding games. Unforgeability: in the ...


1

It (Blind Signature) is unconditionally blind, because if you take a blind message $m\cdot r^e$ and then sign it, you get $m^d \cdot r$ which distributes like a random element in a subgroup of $Z^{*}_{N}$ so even if you have unlimited computational power you can't extract $m^d$ from looking at $r \cdot m^d$. Even if you factor $r \cdot m^d$ you won't know ...


1

You can try to encrypt your sensitive data with a lightweight cipher, like Prince. You encrypt your Prince key with a HE encryption scheme like BGV (HElib implements it) and give the cloud two things: Enc_HE(Key_Prince), Enc_PRINCE(Data). The cloud is able to decrypt homomorphically Enc_PRINCE(Data) using Enc_HE(Key_Prince) and obtain only Enc_HE(Data). The ...


1

Ok, here is a random idea I had; it needs further analysis, especially in regards to the security parameters. It's based on RSA; I believe that there are ways to run RSA as a threshold scheme; I'll assume that you'll use one of those. The public key will be the normal RSA parameters $N, e$, as well as an integer $C$. The private key will be the RSA ...


1

As long $(r_i)_{i=1\dots n}$ is sampled uniformly from the set $Z := \{(z_i)\in(\mathbb Z_p^\times)^n|1\le i<j\le n\implies z_i\ne z_j\}$ and the attacker gets all the $y_i$'s, but no information about the $r_i$'s and $x$ (during the other steps), no algorithm can obtain any information about $x$, as multiplying by $x$ preserves the uniform distribution ...


1

There is no algorithm to find an $x$ only having $y_i$.


1

After those very helpful hints by poncho and yyyyyyy the answers are now obvious and I'll briefly argue why each of the construction is perfectly secure or not. Concerning construction 1: It can't be perfectly secure because it has been proven that perfect secrecy (=perfect security) requires the keyspace $\mathcal K$ to be as large as the message space $\...


1

1) Blinding has been used, for example, to design a version of El Gamal encryption that is resilient to certain side-channel attacks --- see [PK] and the references therein. 2) The goal of the field of leakage-resilient cryptography is to model and study (from a theoretical perspective) what security can be guaranteed against side-channel attacks (...


1

What you are doing is the following: Choose a random number $r$ in $[1,2^n-1]$. Check if $r$ is invertible $\bmod n$ (should be with probability $\approx1-2^{-1000}$, because by random luck you'd have to hit $p$ or $q$), if not go to 1. Check if $(\frac{r}{p})=(\frac{r}{q})=1$($(\frac{a}{n})$ denotes the jacobi symbol), if not go to 1. So in order to speed ...


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