13 votes
Accepted

Intuitive explanation of the $\varepsilon$ parameter in differential privacy

A colleague gave me the following explanation that I think makes a lot of intuitive sense, so I'm reproducing it here. Skip to the last paragraph it you don't care about the proof. Suppose you're ...
user avatar
  • 968
10 votes
Accepted

Is there a hash tree scheme designed for complex data structures?

The general technique for tree hashing (independently of the issue of partially revealing content) is to define the hash of nodes as the hash of the concatenation of the hash of their leaves, with a ...
user avatar
  • 122k
7 votes

Integrity with anti-confidentiality

Sending information covertly when using legitimate systems is a well-studied field. As another question mentions, key words are covert channel and subliminal channel. Designing systems with no covert ...
user avatar
  • 4,382
7 votes
Accepted

Difference between ε-differential privacy and (ε, δ)-differential privacy

The $\delta$ item is a relaxation of the $\epsilon$-differential privacy notion. The latter is a strong security notion because it requires an algorithm $\mathcal{A}$ to have very close output ...
user avatar
  • 2,625
6 votes

Integrity with anti-confidentiality

RSA with PKCS#1 v1.5 padding for signature genernation would work, as the algorithm is fully deterministic. The random padding is only used for RSA with PKCS#1 v1.5 padding for encryption which is ...
user avatar
  • 84.6k
6 votes
Accepted

Applying machine learning algorithms to homomorphic encrypted data

Homomorphic Encryption on Reals In theory, homomorphic encryption can be done on real numbers. This answer describes two options you have when dealing with real numbers or operations that will result ...
user avatar
  • 37.7k
6 votes
Accepted

Differential Privacy: why $\delta$ negligible on the row numbers?

$\varepsilon$-differential privacy is absolute: for any pair of databases, you cannot gain more than a small amount of probabilistic information about a single individual. When you add or remove an ...
user avatar
  • 968
6 votes

Ensuring integrity and confidentiality together with symmetric encryption

Do not invent your own authenticated encryption mode. Use a standardized one, and use a well-supported library to implement it in your code. AES-GCM, AES-CCM, AES-OCB, and AES-CBC with HMAC-SHA256 ...
user avatar
  • 2,217
6 votes

On the privacy of perfect hash functions

The definition of perfect hash functions do not have any security/cryptographic requirements. For example, the hash function that simply outputs the first n bits of any string is a perfect hash ...
user avatar
  • 2,857
5 votes

Secure multiparty computation of conjunction

They could use 1 out of 2 oblivious transfer. Alice offers the messages $0$ and $a$ and Bob uses $b$ as his choice bit (I.e., choosing the first message if $b = 0$ and the second if $b = 1$.). It ...
user avatar
  • 2,857
5 votes
Accepted

Why the definition in $\epsilon$-differential privacy is multiplicative rather than additive?

In short, with this multiplicative definition, it could be ruled out the possibility that an individual's record would be randomly selected and published. Consider a malicious algorithm $M^*$ that ...
user avatar
  • 2,625
4 votes
Accepted

Disk/File modes of encryption and authentication

Beside XTS and CBC-ESSIV, are there any other modes of encryption that are commonly used? No. Just look at software like Veracrypt (XTS only) or dmcrypt. There was a third notable scheme for ...
user avatar
  • 1,187
4 votes

Hiding identifying data while allowing matching?

Any transformation of the identifier, including those in the question, is bound to have at least one drawback: after a transformation of cryptographic quality, it will be next to impossible to re-...
user avatar
  • 122k
4 votes
Accepted

Is zero IV with AES-CBC safe if CPA is not possible and indistinguishability is not an issue?

Furthermore, is using AES-CBC this way any safer than using AES-ECB? Yes, using CBC mode is (almost?) always safer than using ECB mode. Is using zero IVs with AES-CBC safe[...]? No it is not safe, ...
user avatar
  • 44.6k
4 votes

Data Security and Encryption

What is the "unknown attack" the reviewer is referring to? The reviewer did not say "the unknown attack", but "in front of unknown attacks". That refers to no attack in ...
user avatar
  • 122k
4 votes
Accepted

Prove that $x$ is the sum of digitally signed numbers without revealing the summands

As Mark has said, it's, in theory, a solvable problem (we know how to do it; the known methods are not simple). However, by tweaking things around a bit, we can make this problem easy. My solution is ...
user avatar
  • 131k
4 votes
Accepted

How do we select values for parameters when using Differential Privacy?

In the 2019 paper Differential Privacy in Practice: Expose Your Epsilons!, the authors Dwork, Kohli, Mulligan summarize the state of affairs thusly: We found no clear consensus on how to choose ε, ...
user avatar
  • 10.6k
4 votes

If the symmetric key is stolen; can I key revoke without reencrypted data?

If one's key is correctly used to encrypt data, and the key is stolen (that is all physical media containing it are stolen and thus become unavailable; as in "my last bike lock key got stolen&...
user avatar
  • 122k
3 votes

Differential privacy on multiple queries – what is the behavior?

It would be helpful to have a link to the paper you are referring to. But the basic composition theorem says that each query $i$ an attacker sends to the database will just add its corresponding $\...
user avatar
  • 968
3 votes
Accepted

Understanding the big picture with regard to how anonymous credentials work

I'll try to give some high-level intuition of the used construction paradigms in my answer below. First, note that we distinguish between one-show and multi-show anonymous credential schemes. For one-...
user avatar
  • 1,293
3 votes
Accepted

Government root SSL certificate possible vulnerabilities

First - please REALLY check the certificate, download it, open and have a look into details (4096 bit, 30y validity). I don't think your government wants to be insecure themselves (so other parties ...
user avatar
  • 1,182
3 votes

Hiding identifying data while allowing matching?

In this case there is no need for a rainbow table, since at most the identifier has about 15 bits of information. You can cycle through all possible values (there are $26^2 \cdot 31 \cdot 2 = 41912$) ...
user avatar
  • 31.2k
3 votes

Privacy and Integrity in Public Cryptography

Signing and encrypting together is not secure in this method, at least in the way most would perceive security. For example, Bob would likely interpret this message as being sent from Alice to Bob. ...
user avatar
3 votes
Accepted

What's the meaning of probabilities in differential privacy formula?

No, it means that the functions are chosen from some domain with some probability distribution. This is standard for randomized algorithms. For simplicity, assume there are $N$ randomized functions $...
user avatar
  • 16.1k
3 votes
Accepted

Lemma KL-Divergence (Differential Privacy)

I don't understand why: $$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) = \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=y])$$ Well the domain is partitioned into $T$ and its complement. So the sum over the full domain of the ...
user avatar
  • 16.1k
3 votes
Accepted

Differential privacy noise that scales with $L_p$-sensitivity with $p>2$?

You can measure your sensitivity in an arbitrary norm. The exponential mechanism, that samples from the distribution proportional to $\exp(-\epsilon |z-f(x)|_p / 2)$ will give pure DP. This is more ...
user avatar
  • 46
3 votes

Public-key/asymmetric encryption where you can only leak the decrypted message by leaking your password

Your idea of an encryption method including a nonce, and in a way that Alice cannot recover the nonce is practical; however it doesn't solve your problem. One possibility would be a variant of El ...
user avatar
  • 131k
2 votes
Accepted

Are SSL/TLS used for maintaining data confidentiality?

The answer to the first question is both. TLS uses a custom PRF based on HMAC to generate symmetric and MAC keys from a shared secret. The shared secret is created during the asymmetric key exchange ...
user avatar
  • 12.6k
2 votes

Privacy and Integrity in Public Cryptography

Instead of trying to invent your own protocol, you'd be much better off using something that is already out there. For example, you could use TLS to transport the data. Another option would be to use ...
user avatar
  • 37.7k

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