Advantages of bilinear map Consider the pairing $e: G_1*G_2 \to G_t$.

Why we are mapping element from group $G_1$ and group $G_2$ to an element in $G_t$.
How are they used in cryptography?
What advantages do they provide?

If we are to summarize things in one sentence, let's say that pairings allow for three-party mathematical protocols.

Consider for instance identity-based encryption. In a classical public-key cryptography system for encrypting messages (e.g. emails), the sender must know the recipient's public key in order to encrypt the message. Distribution of public keys is a known troublesome problem (less hard than distribution of secret keys, but hard nonetheless). IBE strives to make the recipient's public key actually equal to the recipient's name (or email address), because the sender already knows it. If you want to do IBE with, say, RSA, you usually end up with a centralized system in which there is a central system C through which all messages go. Every user knows one public key, the one of C, and encrypts the message with that public key. C decrypts the message, and reencrypts it with the intended recipient's public key (C knows all user's public keys).

This classical model for IBE does not scale well, because the central system must receive, decrypt, encrypt and send every email. Pairings resolve that by moving the central systems to mere mathematics. With pairings, the central system C still exists, but it needs not be invoked for every email. Things go more or less like this:

The central system C has a private key, and the corresponding public key K is known to every user.
Each user U obtains his private key KU from C.
When sender S wants to send an email to recipient R, he can "somehow" compute R's public key using only R's name (email address) and the central system public key K.
Recipient R uses KR to decrypt the message.

The pairing is what resides in this "somehow". It is a computation involving K, R's name, and some input from U. It moves C out of the physical picture. C is still there mathematically (and, in particular, C knows the private keys of every user, since C computes these private keys), but C needs not do anything in particular at the time the email is sent. This prevents C from becoming a network bottleneck when traffic increases.

In a similar way, pairings are convenient for electronic cash protocols (three-party protocols between buyer, merchant and bank, and we would prefer not to have to actually talk to the bank for each transaction).

Historically, pairings were a mathematical curiosity from the 1950s, shown practical for cryptography in 1986 by Miller, and first used to break elliptic curves. Indeed, a pairing from $G_1\times G_2$ to $G_3$ turns a discrete logarithm problem on $G_1$ into a discrete logarithm on $G_3$. For known pairings on elliptic curves, $G_1$ is an $n$-bit curve, and $G_3$ is a multiplicative subgroup in a finite field of size $kn$, where $k$ is the embedding degree of the curve. Sub-exponential algorithms for breaking DL on finite fields are known, so if $k$ is small, applying the pairing makes the DL problem easier.

Fortunately, for most curves as used in practice, $k$ is astronomically high, so the pairing does not break DL on these curves. Some specific curves (especially most supersingular curves) turned out to have very low embedding degrees, and, for them, pairings are a useful breaking tool.

Constructive uses of pairings (as for IBE) rely on using "slightly weakened" curves, i.e. curves for which the embedding degree is sufficiently small to allow the pairing to be efficiently computed, but not small enough to make DL on $G_3$ too easy. For instance, IBE would use an 800-bit supersingular curve of embedding degree 2; DL on a 1600-bit finite field is still way beyond what is technologically feasible. This still is a rather delicate dance which explains that a lot of cryptographers feel uneasy in the presence of a pairing.


Generating passwords from a master password using rules I realize it's generally considered bad idea to use the same password everywhere.

I can use icloud / lastpass to generate my passwords for me, but that leaves me clueless when I don't have access to these services, or attacks to those services.

Does it make sense to use 1 "master password", but modified for each website / service with set of rules?

For example, let's make my master password foobarone and name of the service is "facebook". My rule is to shift 1st letter X. Where X is number of first letter in service name (facebook, first letter is f, f = 6). Therefore, I am shifting 1st letter by 6, so my final password for facebook is loobarone. In reality, these rules would be more complicated.

Does this provide me layer of security, or is my thinking out of line and the only solution is to have random password for every service?

The reason reusing passwords is a bad idea is that the security of all your accounts relies on the security of the weakest account which uses the same password. If you sign up for PNC Bank and [favorite show here] Fan Club using the same password, one of them being compromised will compromise them both.

That being said, under the assumption that one of these services will be compromised eventually, the security of them relies on the security of your scheme, rather than the master password itself. If all you're doing is changing the first letter, then it is trivial to guess it given a leaked password.

A better method could be using some variant of HMAC to combine your master password with the website's domain name.

HMAC_MD5("foobarone", "facebook.com") = "b5bda098afd19b1f7992abfa9ab7d710"

You could then use "b5bda098afd19b1f7992abfa9ab7d710" as your password for facebook. For convienience, you could truncate it to "b5bda098afd19b1f" and still have a relatively strong (64 bit) password.

Using LastPass (or some other manager for that matter) is better than using a homemade system, though.


How to get the keyword from a keyword cipher? I was given a ciphertext and now I am trying to break it via looking for the keyword.
This is a keyword cipher. So:

PlainEnglish: ABCDEFGHIJKLMNOPQRSTUVWXYZ

If keyword is HELLO,

CipherLetters: HELOABCDFGIJKMNPQRSTUVWXYZ

So, I had done a little frequency analysis where I've managed to get the percentage of most frequent letters used and I've made a table of letters that I've arranged in a descending manner and compared it to the normal expected English letter frequencies.

Well I could carry on and try and match the text one by one, but I read that there is a possibility that a keyword can be found as well. I'm looking for a little idea on how I can start off with this task.

English on the left and cipher letters on the right:

e   12.702      o   10.772
t   9.056       k   10.611
a   8.167       t   9.003
o   7.507       d   8.521
i   6.966       n   8.039
n   6.749       j   6.913
s   6.327       q   6.431
h   6.094       r   4.984
r   5.987       c   4.823
d   4.253       h   3.939
l   4.025       l   3.617
c   2.782       s   3.617
u   2.758       u   3.296
m   2.406       i   2.894
w   2.36        w   2.492
f   2.228       a   2.412
g   2.015       b   1.849
y   1.974       m   1.688
p   1.929       y   1.367
b   1.492       v   1.125
v   0.978       e   0.884
k   0.772       g   0.241
j   0.153       p   0.161
x   0.15        z   0.161
q   0.095       f   0.08
z   0.074       x   0.08

So I arranged it back according to normal ABCDEFs. Just trying to make sense out of it more. I sort of have a clue. I thought the keyword might be TVSHOW, but it can't be, as I tried deciphering using it already, and W is like way down in the chain. Any ideas on how I can solve the keyword?

abcdefghijklmnopqrstuvwxyz
tvshoabrnpglijdyfcqkuewzmx

Let's start by considering which cipher letters should correspond to the most common letters E and T.  According to your frequency analysis, the most likely candidates are O, K, T and maybe D and N.

Now, E is the fifth letter of the alphabet, so unless your keyword is very short, it's going to encrypt to some letter in the keyword (and if the keyword is very short, E would likely encrypt to A or B, which doesn't seem likely in this case).  So let's ignore E for now.

However, T is the twentieth letter in the alphabet, so unless your keyword has twenty or more (unique!) letters, T will encrypt to one of the "left-over" letters.  Thus, the encryption of T will tell you how many letters in the range T to Z the keyword contains.

So let's consider the possibilities.  We can rule out T encrypting to K entirely — that would require the keyword to contain nine letters in the range T to Z, but there are only seven letters in that range!  The same goes for D, and N, while barely possible, doesn't seem plausible either.  Even O, at four positions before T in the alphabet, seems rather unlikely, given that most of the letters after T in the alphabet are fairly uncommon. So my guess would be that T — and thus also every letter after it in the alphabet — encrypts to itself.  Looking at your letter frequencies, that seems plausible.

That leaves O and K as plausible encryptions for E; the other one of those then probably stands for A, which would mean that both of them occur in the keyword (and, in particular, that one of them is the first letter in the keyword).  Alternatively, K might stand for O, and D or N for A.

What about P, Q, R and S, then?  Well, there's no way Q encrypts to itself — the frequency of Q in English pretty much never exceeds that of U.  However, Q (nominal freq. 0.095) might well encrypt to P (ciphertext freq. 0.161); it certainly doesn't encrypt to Z, F or X, which are the only less frequent letters in the ciphertext than P.  That means that one of Q, R and S must occur in the key; the ciphertext frequency of S (3.617) is far enough from its nominal frequency (6.327) that we might guess that it's in the key, which would give us the following partial cipher table:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
????????????????PQRTUVWXYZ    key letters: S, (O/K)

We might also guess that P (nominal freq. 1.929) encrypts to M (ciphertext freq. 1.688) – it certainly can't encrypt to N (freq. 8.039) or O (freq. 10.772), unless your message is about peppy popping pepper pips or something.  Could O (n.f. 7.507) then encrypt to L (c.f. 3.617)?  Maybe, but K (c.f. 10.611) seems more likely.

That would  mean that E encrypts to O and that L and N also occur in the key.  Which plaintext letters could they stand for?  Well, looking at the frequency table, N might stand for A and L for C or D.  That gives us the following partial cipher table:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
N???O?????????KMPQRTUVWXYZ    key letters: L, S

Presumably, L and S stand for C and D in either order, but it's hard to tell from the frequencies which.  What letter could stand for B, then?  Well, E looks like a plausible choice — the frequencies are pretty close, and E is common enough to be likely to appear in the keyword.  Guessing that L might stand for C, that makes the cipher table look like this:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
NELSO?????????KMPQRTUVWXYZ

Could the keyword be NELSO(N)?  If so, A would stand for F, B for G and so on:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
NELSOABCDFGHIJKMPQRTUVWXYZ

Looking at the frequencies, I see no obvious mismatches, so I'm going to guess that that's the solution.  Of course, examining the actual ciphertext could either confirm or refute this, but based on the frequencies alone it looks plausible.


How is the PKCS #10 signature generated? I'm generating certificate signing request in iOS, which does not provide proper ready-made API for CSR generation. Now the library I have used for CSR generation produces the different signature for CSR compared to openssl with the same private key.

How is the signature generated and do you think there is an error somewhere, if the signature generated by openssl and the library I'm using does not match?

The signature over PKCS#10 is defined in RFC 2986, specifically section 4.2 (on page 7).

  The signature process consists of two steps:

  The value of the certificationRequestInfo component is DER
         encoded, yielding an octet string.
  The result of step 1 is signed with the certification request
         subject's private key under the specified signature
         algorithm, yielding a bit string, the signature.

The signature is over all the significant information in the request and includes all the DER-encoded attributes in the PKCS#10 signing request.

If there are any missing or additional attributes in the PKCS#10 certificate request, or if any of the attributes differ by even one single bit, then the signature will be completely different. This could include using a different string encoding (printable ASCII string vs UTF-8), but also different dates etc.

If you want to find the difference, you can decode your certificate request here. You might have to strip your request in PEM format or convert your request in DER format to base 64 before using this tool. You could also use openssl asn1parse functionality for this.

Finally, it could also be that a different signing algorithm is used, e.g. PKCS#1 v1.5 padding vs PSS padding. They would both generate the same amount of bytes. PSS is non-deterministic (uses a random bytes) by the way; if it is used the signature would be different each time regardless of the input. Normally PKCS#1 v1.5 padding is still used though.

As Dave mentions,  the best way to validate the correctness of a signature is not to compare it but by verifying the signature and validating the attributes, possibly by using other software. That way non-significant changes won't play a role within the validation.


Is there something wrong with my decryption using key=9, mod 26? I am new to cryptography and have started looking at some basic encryption. I have the following question to answer:

Decrypt the the following encrypted quotation using key = 9, mod 26:

fqjcb rwjwj vnjax bnkhj whxcq nawjv nfxdu mbvnu ujbbf nnc

So far I have decrypted the message to the following:

Whats in a name arose by any other name would smell as sweet

However, this doesn't seem to make sense as a complete decrypted message - have I done something wrong in my decryption or is my answer correct?

Your punctuation is slightly off:

  What's in a name? A rose by any other name would smell as sweet.

It's a reference to Romeo and Juliet


Does mixing two derived keys make a stronger key? And if so, how would I mix? I have to generated a secure key from some meta data and a password, and I'm free to choose among a dozen of key derivation functions (KDFs). The problem is, I'm not too happy with either one. Some are well known and proven to be secure but they are not expensive enough to really survive a massive brute force or dictionary attack (e.g. bcrypt or PBKDF2). Others claim to be prepared against such attacks, but they are not so well known yet, they are rather new and have not been studied for years, so it's still possible that someone finds a weak spot or a backdoor (e.g. scrypt or Argon2, and scrypt already turned out to be weaker than people initially thought it would be). Using just a single KDF seems out of question to me if you really need secure and hard to attack keys, it's like betting all your money on a single horse: if it loses, you've lost it all.

Remembering the Intel random number generator fail? The Linux kernel hackers said that this problem doesn't really affect the random number generator of the Linux kernel as the CPU generator is only one among many random sources and

  Random + Not-Random = Random

so as long as at least one of these sources is able to provide good random numbers, the result is still random, even if an attacker can control the quality of the other sources.

Wouldn't the same apply to mixing derived keys?

Good-Key + Bad-Key = Good-Key (???)

So if I use two derivation functions, one that is known to be secure but a bit weak and one that is very strong but not (yet) known to be secure, wouldn't this lead to better keys than just relying on one method?

And if this assumption is correct, how would I mix the two keys? What would be a good, secure method for that? Treating them as big numbers and then just doing add + modulo? Concatenating them and hashing the result? I'm a bit afraid that using a bad "mix function" will weaken the final result when the mix function becomes the weakest link of that chain.

Update

Mixing the keys is just "an idea", of course, maybe instead of mixing it would be better to use the output of one KDF as the input for the other one. At least that makes the whole thing less parallelize-able and thus harder to attack for number crunchers. But maybe that's not true, maybe it makes it much easier to attack if one of both KDFs fail as now you have a chain and as I said above, a chain is often only as strong as its weakest link. Also interesting, if I use two KDF, A and B, and it is more likely that A is weak than B, would it be better to do A(B(x)) or B(A(x))?

Another idea I had was using an HMAC for mixing, one key would be the data and one key would be, well, the key. Calculating an HMAC if you only have one of both, the key or the data, is still extremely hard, so if just one KDF fails, that shouldn't be a problem. Of course, the final key depends on the security of the HMAC function but the HMAC algorithm is in use for decades, one could say it has been proven to be secure. And that is true even when using such a poor hash function as MD5. MD5 itself has been broken long ago, it's totally useless for cryptography today, yet, so far nobody ever managed to break HMAC-MD5, which means HMAC is a good function and maybe HMAC-SHA2 would be a good way to mix two keys?

This seems such an obvious problem that I'm pretty sure all these questions have been asked before and even answered before, I'm not here to invent anything new, no way(!), I just haven't been able to find the answers, that's what I'm here for, finding answers.

This answer is part answer, part comment requesting refinement of the language in the question.

There is an assumption in the question that is not necessarily valid.

  Using just a single KDF seems out of question to me if you really need secure and hard to attack keys

There is a counter example to the intuition that using more functions will make it more difficult: Suppose you are allotted 1 second of time per evaluation of the key derivation function. If you use scrypt for .5 seconds and then bcrypt for the next .5 seconds (or vice versa), your key derivation function uses less memory then just using scrypt for the entire 1 second. So if memory hardness was the goal, then mixing two functions does not necessarily improve security. Which leads to the next point:

  So if I use two derivation functions, one that is known to be secure but a bit weak and one that is very strong but not (yet) known to be secure, wouldn't this lead to better keys than just relying on one method?

First, there is a contradiction: What exactly is a method that is known to be secure, but is weak? How can we know it's strong if we do not know it is secure? If "strength" is somehow separate from "security", your definitions for the two terms would be appreciated.

Secondly, you have to define "better" keys: better in regards to what?

  How would I mix the two keys? What would be a good, secure method for that

You have to define "secure": Combining hash functions is not trivial.

If you can assume that at least one of the outputs is psuedorandom, then there is little reason not to use the simplest method possible, namely, XOR. The output of $x \oplus y$ is at least as random as the more random of the two (otherwise a OTP would not work).

Unless for some reason, you want order to matter, then you could use a non-commutative operation such as concatenation and hashing. Unless you have an explicit reason for needing the properties of some other mixer, it is probably best to use the simplest tool for the job.


How many iterations for Pollard's $p-1$ with $p = r^k + 1$ for prime $r$? $p$ and $q$ are large primes.
What is the lowest upper bound for the number of iterations for Pollard's $p-1$ algorithm for factoring $N = pq$, provided that $p = r^k + 1$, for a prime $r$, and $r^k + 1 < q < r^{k+1}$?

What is the lowest upper bound for the number of iterations for Pollard's $p-1$ algorithm for factoring $N = pq$, provided that $p = r^k + 1$, for a prime $r$, and $r^k + 1 < q < r^{k+1}$?

Assuming that $p$ is prime, and that $N$ is smaller than 8 billion bits in length, then step 3 of the referenced algorithm will take at most 17 iterations before exiting via condition (a) or condition (b).


Why discrete logarithm modulo composite moduli not popular and not defined in standards? The classical discrete logarithm problem is to find $x$ such that $g^x\equiv h\bmod p$ where $p$ is a prime and $g$ is generator of multiplicative group modulo $p$.
The demerit of this approach seems to be knowledge of $\lambda(p)$ where $\lambda$ is Carmichael Lambda function.
Supposing instead if we had $g^x\equiv h\bmod q$ where $q$ is composite $\lambda(q)$ is hidden since factorization is difficult.
One can still perform Diffie-Hellman at both Alice's and Bob's side since $(g^x)^y\bmod q$ can be computed without knowledge of $\lambda(q)$ and thus without knowing factorization of $q$.
Such a scheme includes factorization as an additional barrier in case discrete logarithm modulo primes is broken and so why is this not popular and defined in standards?
Note if discrete logarithm modulo primes is broken there is no way to use $q$ to be same length as $p$. We will only get smaller security if we use same length. $q$ has to be larger in length but the point is it cannot be prime. Perhaps $q$ is product of $\log p$ primes each of length $\log p$ bits.
Another phrasing of the problem is "Assuming an oracle solving the DLP modulo a prime, can we solve the DLP modulo a composite that's too large to factor?" as stated in a comment with each factor also reasonably large.

Such a scheme includes factorization as an additional barrier in case discrete logarithm modulo primes is broken and so why is this not popular and defined in standards?

Actually, it would not be an "additional barrier", instead, it would be an additional avenue of attack.  After all, the standard attacks against a discrete log problem still work in a composite modulii; in addition, the attacker has the possibility of factoring the modulii, and then solving the discrete log problem modulo each prime factor.  The primes are considerably smaller than the full modulii, and hence those subproblems are comparatively easy to solve; the difficulty is dominated by the factorization effort.
You state in your rephrasing "what if we had an Oracle that solved the discrete log problem modulo a prime (but not a composite)", well, since we have no indication that such an Oracle exists, we don't worry too much about it.
In any case, your construction to change that to "what if we had an Oracle that solved the factorization problem" (because once we've factored, solving the discrete log modulo the smaller prime factors is comparatively easy).
On the other hand, that really doesn't answer the question "why don't standards do that?"  Well, I didn't write the standards, so I can't give an authoritative answer there; however I would note that it makes it considerably harder to come up with a Nothing-Up-My-Sleeve group; that is, a group that we are pretty sure is actually secure, and that no one has a backdoor to.
For prime modulii, it is fairly easy to design a deterministic process that, at the end, generates a "good" prime number; that is, one where we know the large prime subgroup, (and which is not vulnerable to the Special Number Field Sieve algorithm); with that, we are fairly confident that it was not designed with a special vulnerability in mind.
In contrast, we don't have such a good way to have a deterministic process that generates a composite number of unknown factorization (and which is known to be hard to factor), and also has a large rough [1] subgroup with a known generator.  What we are likely to do is rely on some trusted authority to generate one for us.
Well, the "trusted" part is a deal-breaker for quite a few; there isn't anyone which everyone would agree should be trusted with coming up with our crypto parameters.  And, yes, "trust" is the right word; there are a number of ways a dealer can generate a composite modulus for which they can solve the discrete log problem, but other people can't (essentially by using different prime factors for which they can solve the discrete log problem, and then multiplying them together to hide things).
[1]: By rough, I mean one with no small prime factors.  This is not standard terminology (hence this footnote); this is the obvious antonym to "smooth" (consists only of small factors).


How many bits are needed to commit one bit non-interactively in the standard model? I'm wondering the state-of-art result about how many bits are needed to commit a single-bit non-interactively? I noticed in the paper of Naor's bit commitment: http://www.wisdom.weizmann.ac.il/~naor/PAPERS/bit.pdf
this paper says assured amortized O(1) bits of communication per bit commitment. However, it seems Naor's bit commitment has interactive commitment phase. Thus I'm wondering the state-of-art result about this research direction. How many bits of communication per bit commitment should be sent non-interactively in the standard model?

I'm only interested in non-interactive bit commitment assuming one-way function not assuming DDH like Pedersen commitment.

The state of the art regarding non-interactive bit commitment from OWF is quite simple: it is known to be impossible (at least using black box reductions) to build non-interactive commitments from one-way functions (see e.g. this paper).

Are you specifically interested in constructions from generic one-way function, or are you ok with more structured assumptions, such as one-way permutations (which do imply non-interactive commitments)? If you are also interested in OWP (or even one-to-one OWF), then I think the state-of-the-art generic construction of a NIBC is the direct application of the Goldreich-Levin theorem: to commit to $b$, given any OWP $f:\{0,1\}^n\mapsto \{0,1\}^n$, pick random $(x,r)$ and return $(f(x), r, \langle x, r\rangle \oplus b)$. The communication is $2n+1$ bit per bit committed. If you want to commit to a single bit, I do not know of any better solution. When amortizing, however, there might be better approaches - for example, you can at least commit to $\log(n)$ bits at once using a single $x$ and $\log(n)$ different $r$'s, lowering the communication to $n(1+o(1))$. I don't know if there is anything better generically (getting more hardcore bits from the Goldreich-Levin construction seems hopeless, but perhaps a completely different approach can help).

From collision resistant hash functions, at least, this papers provides a construction of a non-interactive commitment with $O(1)$ amortized communication - but their construction still requires a one-time interactive setup phase, the commitment scheme only becomes non-interactive after that.


Which elliptic curves are quantum resistant? If I want to learn about quantum resistant crytography what are the best resources? Which type of elliptic curves should I be studying?

Post-quantum crypto is a very young field and is still changing quite rapidly. If you just want a reading list to introduce you to the topics, I would recommend the March 2015 report released by the EU's PQCrypto Project, and the April 2016 report from NIST.

As of today, here's an (incomplete) list of candidate algorithms for post-quantum cryptography with a link to the best reading material I could find for each:

Hashes: everything we have now is fine, you just have to double the output size against a Grover search:

SHA-2 256 and up
SHA-3 256 and up (aka Keccak)

Hash-based Signatures:

XMSS
Sphincs

Symmetric Encryption: everything we have now is fine, you just have to double the key size against a Grover search:

AES 256

Asymmetric Encryption (some of which also include signature schemes, but why would you when hash-based sigs work so well?):

NTRU (lattice-based cryptography)
McEliece (code-based cryptography)
Ring Learning with Errors (R-LWE) (lattice-based cryptography)
Multivariate polynomials (no specific algorithm yet)
Isogenies on supersingular elliptic curves (no specific algorithm yet)

Since you specifically asked about elliptic curves, you'll notice that ECC in its current form is not on this list. That is because the discrete log problem of reversing elliptic curve point multiplication is easily solved by Shor's algorithm on a quantum computer.

That said, elliptic curves do appear on the list in the form of isogonies: transformations mapping a point on one curve to a point on a (potentially) different curve are conjectured to be hard to invert on both classical and quantum computers.

Personally this is my favourite algorithm from the list above for two reasons:

The keys are smaller and the runtime faster than the other approaches
The other approaches all have the flavour "do some linear algebra which is possible for Eve to invert, so sprinkle in some error that both Bob and Eve have to guess in order to widen the computational gab between them. This fundamental approach makes me kinda uneasy.

The more future-proof answer to this question is to watch NIST: they are gearing up to run a competition-like thing over the next 18 months to select the best post-quantum encryption primitives.


Why use CCM instead CBC-then-MAC? Is there any reason why CCM was created with encryption/decryption being done with a counter versus using CBC-then-MAC?

CTR mode was previously considered a relatively brittle scheme, and in a sense it is. Repeating the nonce will repeat the counter, and repeating the counter will repeat the key stream. This means that the security of the plaintext is broken rather spectacularly on nonce reuse.

However, using CTR has many advantages over CBC:

You can use a nonce instead of a randomized IV (deterministic vs random);
You don't need to bother with padding or ciphertext stealing (no expansion of ciphertext above plaintext size);
Because of above it is not vulnerable against padding oracle attacks (decryption before verification is not vulnerable);
You only need to use the block cipher in one direction (simplification of the encryption scheme, less hardware required);
Online encryption/decryption is perfectly possible (immediate encryption / decryption without caching);
Ciphertext streams may be cached for efficient, byte oriented encryption / decryption (low latency);
As the counter values can be generated in advance, pipelined AES implementations may offer (much) higher performance - see the comment from Yehuda for a description (speed).

So nowadays about every AEAD cipher uses CTR mode underneath. And that's fine, as long as you do indeed provide it with a nonce.

The fact that you can also search within the ciphertext (skip to a specific offset) is of little interest for AEAD ciphers as you would generally not use the data without first verifying the authentication tag. So although it is an advantage of CTR mode, it doesn't make much of a difference within an AEAD cipher such as CCM.

One problem with CTR is that the construction of the counter itself isn't well specified (location of the IV, additional data, etc.). But within an AEAD cipher this is not an issue as the AEAD algorithm itself will specify the precise construction of the counter.

The question is more why the archaic CBC mode is still used that much. It's not as brittle as CTR mode when it comes to the IV, but that comes at a very high price, including additional requirements for that same IV.

Also note that the use of a CBC mode together with a CBC based MAC may not be such a good idea if the same key is used for both; it is easy to introduce conflicts between the two, threatening the security of a scheme providing both confidentiality and integrity of messages.


Multiply by 3 problem with MixColumns in AES I have problem with multiplying bytes by 3 in MixColumns (as in Cryptography And Network Security)
$$\begin{bmatrix}02&03&01&01\\01&02&03&01\\01&01&02&03\\03&01&01&02\end{bmatrix}\times\begin{bmatrix}87\\6e\\46\\a6\end{bmatrix}\mapsto \begin{bmatrix}47\\37\\94\\ed\end{bmatrix}$$
87 = 10000111 => SHL = 00001110 => 00001110 XOR 00011011 = 00010101
6e = 01101110 => SHL = 11011100 => XOR it with the byte ibtself 11011100 XOR 01101110 = 10110010
(If XOR it with 0x1b then XOR it with the byte the answer won't be correct)
4e = No changes (Multiply by one)
a6 = No changes (Multiply by one)
00010101 XOR 10110010 XOR 01001110 XOR 10100110 = 01000111 = 0x47
Next One:
87 = No changes (Multiply by one)
6e = 01101110 => SHL = 11011100 => 11011100 XOR 00011011 = 11000111
46 = 01000110 => SHL = 10001100 => XOR with 0x1b = 10001100 XOR 00011011 = 10010111 => XOR with the Byte itself 10010111 XOR 01000110 = 11010001
(for this one I should XOR with 0x1b first to get right answer)
a6 = No changes (Multiply by one)
10000111 XOR 110000111 XOR 11010001 XOR 10100110 = 00110111 = 0x37
As you see for the first one if we XOR it with 0x1b we wouldn't get the right answer but for the second one, we have to do it to get the right answer. why does this happen?
same problem with this case (used in AES Rijndael Cipher explained as a Flash animation)
$$\begin{bmatrix}02&03&01&01\\01&02&03&01\\01&01&02&03\\03&01&01&02\end{bmatrix}\times\begin{bmatrix}d4\\bf\\5d\\30\end{bmatrix}\mapsto \begin{bmatrix}04\\66\\81\\e5\end{bmatrix}$$

The issue is that the "XOR with 0x1b" step is performed when it must not.
That "XOR with 0x1b" should be performed after a LSL if and only if LSL dropped a 1 on the left (that is, if LSL started from a byte with bit 7 at 1).
Equivalently: LSL drops nothing, we "XOR with 0x11b" if the result of LSL has bit 8 set.
Yet another equivalent alternative: we convert the argument to a polynomial of degree at most 7 with binary coefficients, multiply that polynomial by $x$, and if the result has degree 8, we reduce it by adding the reduction polynomial $x^8+x^4+x^3+x+1$. Then we convert back to bits to get the result.
Minimally fixing the question's "Next" One (second row of the first matrix multiplication):
87 = No changes (Multiply by one)
6e = 01101110 => SHL = 11011100
46 = 01000110 => SHL = 10001100 => XOR with the Byte itself 10001100 XOR 01000110 = 11001010
a6 = No changes (Multiply by one)
10000111 XOR 11011100 XOR 11001010 XOR 10100110 = 00110111 = 0x37


FHE: What is the difference between multiplicative depth and multiplicative level? I have seen the terms multiplicative depth and multiplicative level while reading

Faster homomorphic encryption is not enough: improved heuristic for multiplicative depth minimization of Boolean circuits by Aubry et. al, 2019.

Is there a difference between the term multiplicative depth and multiplicative level?

In Fully Homomorphic Encryption (in short FHE), we have a noise that increased with every operation, and it is almost doubled with the multiplication. When preparing the circuit $\mathcal{C}$ to $\texttt{EVAL}$ on the cloud we have to consider various parameters to deal with the noise of which the FHE scheme provides. Minimizing boothstrapping calls, which is very costly, number of modulus switching and linearization, etc. According to parameters, the FHE scheme may provide more than 1 multiplication without bootstrapping.

Multiplicative depth (From your reference) :

  The multiplicative depth is the maximal number of sequential homomorphic multiplications which can be performed on
  fresh ciphertexts such that once decrypted we retrieve the result of these multiplications.

What is multiplicative level?

This cannot be easily understood if you don't implement some problems. Here is a simple explanation from Efficient Fully Homomorphic Encryption from (Standard) LWE

  During the homomorphic evaluation, we will generate ciphertexts of the form $c = ((v, w), \ell)$, where the tag $\ell$ indicates the multiplicative level at which the ciphertext has been generated (hence fresh ciphertexts are tagged with 0). The requirement that $f$ is layered will make sure that throughout the homomorphic evaluation all inputs to a gate have the same tag.

Here is the trick, if you need to add a fresh ciphertext $c_i$ into a level $l$ (that can be quite common as encryption of 1 or 0 1), you need to increase the level of $c_i$ to $l$. Otherwise, the operations will fail.

Example: Let we want to multiply $p_1,p_2, p_3$ with FHE. Let $c_i = Enc_{k_{pub}}(p_i)$, and clearly they have 0 multiplication level. You need to send $$\texttt{EVAL}(\mathcal{C},k_{pub},c_1,c_2,c_3)$$ The server first calculates3 $$c_4 = c_1 \cdot c_2.$$ Now, the $c_4$ has multiplication level 1. To multiply $c_4 \cdot c_3$ we need to increase the multiplication level of $c_3$ to 1. Once they are equal, we can multiply.

In short: multiplicative depth is how much multiplication can be performed and multiplicative level is how many multiplication is performed on a ciphertext2.

For the comment: While implementation we want to keep track of the current level of the ciphertexts so that if the scheme doesn't allow multiplications of different ciphertext we can adjust or we make sure that the level on any ciphertext doesn't exceed the depth. So, it is a quite useful definition for a variable.

1 The Private Information Retrieval article Bandwidth Efficient PIR from NTRU is implemented as Mux and the selector bits needs to have the same multiplicative level.

2Multiplcative level cannot exceed the multiplicative depth, otherwise you cannot decrypt.

3The calculation performed according to your circuit $\mathcal{C}$.


Is frequency analysis the only attack on a simple substitution cipher? I understand that "anagramming" is often used after frequency analysis of a traditional substitution cipher, but anagramming requires prior frequency analysis to provide a starting point. Is there any technique other than frequency analysis for a cipher-text only attack on a traditional substitution cipher?

Yes, there are many. Here are the few that I know:

Brute-Force: Simply trying all possible keys.
Kasiski examination: Exploiting the repeated words in the ciphertext to figure out the key length in Vigenere Cipher.
Friedman test aka Kappa Test: Measures the unevenness of the cipher letter frequencies to break the Vigenere cipher.
Key elimination: Eleminate the key by XORing two plaintexts with the same key.


Invalid challenge-ciphertext in IND-CPA and IND-CCA games Consider the IND-CPA game between a challenger $C$ and an adversary $A$ for  a given public-key encryption scheme $PKE$:

$C$ generates a key pair $(pk,sk)$ based on some security parameter $n$, and publishes $pk$ to $A$. $C$ retains $sk$.
$A$ may perform a polynomially bounded number of encryptions or other operations.
Eventually, $A$ submits two distinct chosen plaintexts $m_0,m_1$ to the challenger $C$.
$C$ selects a bit $b \in \{0, 1\}$ uniformly at random, and sends the challenge-ciphertext $c=E(pk,m_b)$ (the encryption of $m_b$ using the public-key $pk$) back to $A$.
$A$ is free to perform any number of additional computations or encryptions. Finally, it outputs a guess $b'$ for the value of $b$.

The advantage of $A$ is $Pr(b=b')-1/2$.

The IND-CCA2 game is the same except that, in phases 2 and 5, $A$ has access to a decryption oracle, with the condition that $A$ can not ask for the decryption of the challenge-ciphertext.

My question is: Suppose that there is an adversary $A$ that has a non-negligible advantage in one of these games. Suppose that, in phase 4, the challenger $C$ sends an invalid ciphertext to $A$ (i.e., $C$ sends a ciphertext that is not the encryption of $m_0,m_1$ or any other message $m$). In this situation, what does $A$ answer? Does $A$ knows that the challenge ciphertext is invalid?

Thanks in advance!

$A$ outputs a bit depending on whether it thinks you gave it an encryption of $m_0$ or $m_1$.

If you cheat and give it something completely different it has no usable information but still needs to output a bit.

If your PKE scheme has invalid ciphertexts $A$ might be able to detect that or not depending on the specifics.

So if you want to exchange your encryption of $m_0$ or $m_1$ for something else in a proof you have to show that $A$ cannot distinguish between these two situations.

Intuitively you can think about it this way:
If $A$ had some way to distinguish between the real security game and your simulation it means that your simulation looks different. So how do you know that whatever $A$ did to attack the original game will work on your simulation if it doesn't look the same to $A$?


Rabin cryptosystem decryption when p=q I'm currently trying to implement the Rabin Cryptosystem when I realized something when gave p and q the same value:

So my values are as follows:

Original message = 20

p=11

q=11

Encrypted message = 37

After decryption I get four values

99, 99, 22, 22

None of the values are my original message. Why is that, and how can I still get the original message?

I implemented the algorithm following the wiki article found here: https://en.wikipedia.org/wiki/Rabin_cryptosystem

Thank you in advance!

Rabin, like RSA, requires $p\ne q$. Basically, this is because the rings $\mathbf{Z}_{pq}$ (for $p\ne q$) and $\mathbf{Z}_{p^2}$ have fundamental differences. Crucially, $\mathbf{Z}_{pq}$ is isomorphic to $\mathbf{Z}_p \times \mathbf{Z}_q$, and your decryption algorithm depends on that property. On the other hand, $\mathbf{Z}_{p^2}$ is not isomorphic to $\mathbf{Z}_p^2 = \mathbf{Z}_p \times \mathbf{Z}_p$, so your decryption algorithm doesn't work.


XMSS^MT private key size I'm doing some comparison on hash-based signature schemes. I am reading about one of the most recent schemes, XMSS^MT, and trying to figure out its actual public and private key sizes for concrete parameters.

I found this paper which has some numbers for a variety of parameters, however it does not say what's the size of the private key (even in terms of XMSS parameters). Has anyone figured this out?

The problem with talking about XMSS private key size is that there is a fairly large number of size/performance trade-offs, and so there's no one answer.

At the minimum, the private key needs to have the value used to generate the WOTS+ private keys ($n$ bits), the $n$ bit public seed, and current leaf index (20, 40 or 60 bits, depending on the parameter set).  In addition, if you follow the recommendations of the RFC, you also have an $n$ bit SK_PRF value (to do randomized hashing), as well as the $n$ bit root (although you could recompute that on the fly if you had to).

If you do this (including the recommendations), this translates to a private key (for $n=32$) of 136 bytes (assuming a parameter set with a hypertree of 60 levels).

On the other hand, if you just did this, this would imply that, with every signature you generated, you would need to reconstruct every XMSS tree involved; that's not cheap.

Now, the obvious thing to do is also include the internal contents of each XMSS tree; this makes things fast, but vastly increases the size of the private key.

As a compromise, you can save a handful of internal Merkle tree elements, and use a tree walking algorithm, such a BDS to generate the next authentication path incrementally (and don't forget, if you're doing XMSS^MT, to start work on building the next Merkle tree while you're traversing this one, if you want to avoid having to build the entire next XMSS tree when you exhaust this one.  There are a number of tree walking algorithms known, with various trade-offs (and tweakable parameters).

In addition, you may also want to include other things in your private key.  For example, if you are interested in detecting fault attacks (where a miscomputation of a lower level XMSS public key causes the next higher WOTS+ signature to sign two different messages over two different signature operations), you may want to store the signature (or public key) of the current lower level tree (or, alternatively, the hash of the signature); that way, either you never actually sign with the same WOTS+ private key twice (or, alternatively, you catch it if a miscompute causes you to generate two different signatures).

All this leads to the fact that there are a number of different trade-offs you can make, and hence, no simple answer to 'how big is the private key is'

You asked for an example using BDS; lets lay out some assumptions:

We'll assume that the private key contains the various central information I listed above, a BDS tree for each Merkle tree in the hierarchy, a place to construct the next Merkle tree (for all Merkle tree levels except the top), and nothing else
We'll use the BDS algorithm with the internal variable $k=2$ (note: the BDS paper stated that the algorithm works only if $H-B$ was even; a simple modification to the algorithm makes it work in all cases).

Then, the central information takes $4n+h$ bits.

And, if we denote $H=h/d$ as the height of each Merkle tree, each BSDS tree (both the current and the next one being constructed; total of $2d-1$) takes up no more than $n(\lfloor 3.5H \rfloor - 4)$ memory (actually, it uses a bit less, however a characterization of how much less is nontrivial).

In addition, each of the active BDS structures (total of $d$ of them) need some auxiliary information to track what's stored in their stacks (we don't need to store auxiliary information for Merkle trees we are in the process of building).  I don't feel up to examining precisely how much memory this takes up; I'll just estimate it as $8H$ bits.

This gives a total of $n(4+(2d+1)(\lfloor 3.5h/d \rfloor - 4)) + 9h$ bits

Different assumptions give different numbers (and could be higher, could be lower...)


What is the meaning for a vector mod a matrix in a lattice? I'm reading about the lattice recently.In the paper, it gives a method of a vector mod a matrix:

⃗c mod B as ⃗c−⌊⃗c×B^(−1)⌉×B = [⃗c×B^(−1)]×B.

I know that a integer A mod the other integer B is A+-kB, to make A in the defined field B.

Can anyone tell me what is the meaning of a vector mod a matrix and the mid term ⌊⃗c×B^(−1)⌉ means?:(

Tks.

A vector u mod a matrix B is  u ± Bv .    We are modding an element of the vector space's

additive group by the range of the restriction of B to vectors whose entries are all integers.

The parallelepiped given by B's columns is a fundamental domain for the range of that restriction.

⌊⃗c×B−1⌉ is probably rounding each entry of c×B−1 to the nearest integer.  If that's correct, then they are using the lattice representation, which corresponds to using [the translation of the parallelepiped I mentioned which sends its center to the origin] as the fundamental domain.


How can the Stern's algorithm be used to attack McEliece? I'm reading about the attacks of the McEliece cryptosystem. I needed to work out a lot of things because most descriptions I have found so far on the internet seems to be quite hand-wavy about the details. So I wrote down what I understand or I think I understand then I have some questions at the end.
In a McEliece cryptosystem the public key consists of a $k×n$ key matrix $K$ and and the number of errors $t$ to introduce into the ciphertext. To encrypt we take a $k$ element long message $\mathbf{m}$, an $n$ element long error vector $\mathbf{z}$ with $t$ non-zero elements, and finally we get the ciphertext $\mathbf{y} = \mathbf{m}K + \mathbf{z}$.
The attacker can decode the plaintext using information set decoding (ISD). In which we choose $k$ random linearly independent columns from $K$ to form an invertible $k×k$ square matrix $A$, also we choose $k$ elements from the same positions as the columns to form the vector $\mathbf{a}$.
In an attempt to get the plain text we compute $\mathbf{q} = \mathbf{a}A^{-1}$, if all elements in a are error free this should give us the plain text.
Verify the result by computing $\mathbf{y} - \mathbf{q}K = \mathbf{m}K + \mathbf{z} - \mathbf{q}K = (\mathbf{m}-\mathbf{q})K + \mathbf{z}$.
If $\mathbf{m} = \mathbf{q}$, then the result is $\mathbf{z}$ which has $t$ non-zero elements and we are done.
If $\mathbf{m} \neq \mathbf{q}$, then our guess was wrong. The Hamming distance between two codewords is it least $2t+1$, so $(\mathbf{m}-\mathbf{q})K$ is a vector that has at least $2t+1$ non-zero elements. $\mathbf{z}$ has $t$ non-zero elements so even if $\mathbf{z}$ happens to cancel exactly $t$ elements from $(\mathbf{m}-\mathbf{q})K$, then the result still has $t+1$ non-zero elements. So having more than $t$ non-zero elements in the result means failure.
The McEliece cryptosystem chooses the parameters such that finding error free sub sequences is unlikely.
Then I read that there are other attacks. One that turns the problem into a shortest codeword finding problem. And does so by changing the linear code to such that message is mapped like this: $\mathbf{x} \mapsto \mathbf{x}K - \mathbf{y}$. So this translates the codewords in the code defined by $K$ and this preserves the minimum Hamming-distance requirements so it's still an error correcting code. In this code there is no zero element and the shortest codeword is $-\mathbf{z}$ with $t$ non-zero elements (when $\mathbf{x} = \mathbf{m}$). Since the minimum distance is still $2t+1$ all other codewords have at least $t+1$ non-zero elements. So if we can find this shortest codeword, then we can remove errors from the ciphertext making the ISD succeed on first try.
Now here is one thing I got stuck at: the code obtained by translation isn't a linear code because translation isn't linear transformation. The linear combination of codewords in it isn't necessarily another codeword, and doesn't contain an all-zero codeword. Right?
But still most descriptions I saw proceed by adding $\mathbf{y}$ as a new row into $K$, then compute the parity check matrix of this modified code and feed it into a minimum-length codeword searching algorithm such as Stern's algorithm. How and why does this work when the code isn't linear?

Forgive me if I missed something.
Is $K$ a generator matrix? I believe yes, which means the original code is linear.
The translate of the original code by subtracting $y$ is a coset, sometimes called affine subspace. It has almost all the nice properties of a subspace.
In particular sums of elements of the translated code are codewords in the original code (characteristic two means sum is the same as difference).


Recovering 3 private keys if Eve knows that the keys are shared prime numbers and knows their public keys, How would this be done? okay so here is the original question:

Alice Bob and Carl are generating public keys for RSA, but they are lazy and decide to
share some of the work of generating prime numbers. They find 3 large prime numbers
p,q and r, then Alice uses the modulus $n_A = pq$, Bob uses the modulus $n_B = pr$ and Carl
uses the modulus $n_C = qr$. The prime numbers used are much to large factoring to be
feasible, but Eve learns that they shared prime numbers (and knows their public keys)
how does she obtain p, q and r?

My thinking or possible reasoning for this question.
Since Eve knows the public keys and that the keys share prime numbers she can compute the GCD of n or factorize n in order to calculate or find the private keys. In this case she would first use Euclid's algorithm for $n_A = pq$ & $n_B= pr $ which we know is p because both n's share a common prime $p$. She would use the same process for computing $q$ which is $n_A = pq$ & $n_C = qr$. Shes does it a third time for $r$ which $n_B = pr$ & $n_C = qr$.

I want to know If I am thinking about this the right way or if I have the right idea. If I am on the right track, how do I mathematically represent this?

Yes, your thinking is correct! Using a "shared prime" when calculating $n_A$ and $n_B$ is disastrous for security simply through the fact that it reveals $p$, $q$, and $r$ with a few calls to the $gcd$ algorithm.

Luckily this incredibly unlikely to happen with the use of good randomness. In the case of 512-bit RSA, there are roughly $2^{503}$ 512-bit primes which, when using the birthday bound, equates to about $\sqrt[2][2*2^{503}log(1/(1-0.5)] \approx 6.02520 * 10^{75}$ generated primes needed to achieve a 50% probability of a collision.

Source: http://www.loyalty.org/~schoen/rsa/


What is the purpose of the "Explicit Nonce" in TLS for AES-GCM and AES-CCM? TLS uses an explicit (secret) 32-bit nonce in combination with the 64-bit sequence number to create the IV for AES-GCM and the nonce for AES-CCM. However, I wonder why TLS needs the explicit nonce.

In general, the sequence number is used to prevent the reuse of the IV in AES-GCM, or nonce in AES-CCM. The sequence number does not wrap (RFC5246) since the keys have to be renegotiated if the sequence number would exceed its limit. Thus, it should not happen that a sequence number is used twice under the same key.

So why is there an additional 32-bit nonce added to the sequence number?

This additional 32 bit nonce acts as a salt, and makes multicollision attacks $2^{32}$ times harder.

In this attack, the attacker collects a huge number of TLS sessions, each with a record encrypted with the same nonce.  He then selects a random key, and generates the counter mode keystream for the key (and the fixed nonce); he then checks if that key stream allows him to decrypt any of the records (and he can do this considerably more efficently than individually checking each one, if we assume that he knows the plaintext for each one, or even if he knows a number of linear equations that holds for each one).  If he finds such a random key that matches, he then has the key for that TLS session, and can decrypt it in its entirety.

If the attacker collects $2^n$ sessions encrypted with AES-128, he needs to check an expected $2^{128-n}$ random keys before being able to decrypt one; this is likely still infeasible for any plausible value of $n$, but still is easier than we'd like.

By setting 32 bits of each nonce randomly, this attack becomes more difficult.  The attacker needs to select not only random AES keys, but also random 32 bits of the nonce settings, and he'll find a valid decryption only if all those bits are correct; this makes the attack require an expected $2^{160-x}$ random keys.  Another way of looking at it; this multicollision attack doesn't make any sense unless an attacker collects at least $2^{32}$ seperate sessions; if he has less, it'd be more efficient for the attacker to select one session, and just brute force that (the 32 bit nonce doesn't make a brute force attack on a single session appreciably more difficult).

Also, it's not really important that the 32 bit nonce is secret; the same sort of logic would work if the nonce was public.  However, there's no reason not to make it secret, and it was more convenient in the protocol.


What is the use of Mersenne Primes in cryptography There is an international search for Mersenne Primes. The project is huge. But what is the use of Mersenne Primes in cryptography? Do they have any other properties other than the $2^n-1$ form?

I can think of two places where we use a Mersenne Prime within cryptogaphy:

As a modulus within a prime elliptic curve.  $2^{521}-1$ is a prime, and so we can define an elliptic curve using $GF(2^{521}-1)$, which is in moderately common use.  One reason we use such a modulus (rather than another prime of approximately the same size) is that the special form of the prime makes computing $x \bmod 2^{521}-1$ easy.
In the (rather obscure) Carter Wegmen Counter mode, we use the fact that $2^{127}-1$ is prime; we use that prime, rather than another value, because it is approximately the correct size, and (as above) computing $x \bmod 2^{127}-1$ is easy.

In both cases, the special property that we take advantage of is that they make computing the modulo operation cheap (by using shifts and adds).


Can error be bigger - as in uniformly random? (Learning with Error) Sketch of some basics of lattice signature schemes.

KeyGen: AS=T; S: private; A, T: public.

Signing:

Y <- random distribution.
C <- Hash(AY|message).
Z <- Y+SC.
Rejection sampling on Z, possibly restart. (Note here)

Verifying: Accept iff

Z is reasonably small.
c == Hash(AZ-TC|message).

What I know:

Rejection sampling is for making sure Z is independent of S so as to not leak info about secret key like NTRUSign. That's also why we need Y over a pretty wide range.

(Discrete) Gaussian distribution is used in BLISS to reduce signature size.

What I want to know:

What if the coefficients of S, A, Y are like one-time pads? Sampled uniformly within {0,1,2,..,q-1} - the full range of $Z_q$ where $q$ is the modulus of the coefficients?
Would we be able to eliminate rejection sampling then?
Would we be able to have smaller dimension with smaller coefficients?

Reason for asking.

Curiosity I had when working on the precision of BLISS sampler.

In fact you can sample $Y$ from uniform in $Z_q^n$. An example of such schemes is the NTRU modular lattice signature scheme [1] but it is not the case here. There are mainly 3 reasons that BLISS family of schemes [2] uses discrete Gaussian distribution.

Firstly,  the signer need to prove that he knows the trapdoor (a short basis) namely

$[S, -I],$

to the lattice

$L = \{(u,v): uA+vT = 0 \mod q\}$

Anyone can find vectors of length $q$ for this lattice, i.e., $(q,0,0,...,0)$; but only the signer can find vectors significantly smaller than $q$. This is known as the Ring Short Integer Solution (R-SIS) problem.

Now, if
the vector $Z$ has uniform coefficients in $Z_q$, an attacker is able to find a large vector in $L$, namely $U$, that is a multiple of $C$, i.e., $U = S'C$ for some $S'$. This $U$ is large but it doesn't matter to the verification procedure now, because every legit signature has large $SC$. If required, he can repeat it enough times to ensure that $Z' = Y+S'C$ is uniform in $Z_q^n$. Then $Z'$ will look like a legitimate signature.

In a nutshell, the signer is not able to prove the knowledge of the trapdoor if $Z$ is large. And if both $S$ and $A$ are uniform in $Z_q^n$, there is in fact no trapdoor in the lattice to authenticate the signer.
On the other hand, this attack will not be possible, if $Z$ and $Y$ are small and discrete Gaussian, in which case $SC$ must be small too.

(NTRU modular lattice signature uses a different approach to prove the knowledge of the trapdoor so $Z$ doesn't need to be short.)

Secondly, you still need to perform rejection sampling even if $S,A,Y$ are uniform in $Z_q^n$. Because even if $Y$ is uniform in $Z_q^n$, $Z = Y+SC$ will be somewhat uniform in a different range, which is more or less $Z_q^n$ shifted by $SC$. So if you publish $Z$ with out rejection sampling, each transcript will leak partial information on $SC$.

The third reason of using discrete Gaussian distribution, as you have mentioned, is that $Z$ is also a discrete Gaussian which allows for compression. For example, in BLISS [2], to store an discrete Gaussian vector in $Z_q^n$, you only require $n(log q-2)$ bits, rather than $nlogq$ bits as if the vector were uniform in $Z_q^n$.

[1] https://eprint.iacr.org/2014/457.pdf

[2] https://eprint.iacr.org/2013/383.pdf


Is a hash a zero-knowledge proof? I’m trying to wrap my head around zero knowledge proofs, but I’m having trouble understanding it.

In my current understanding, zero-knowledge proofs prove to the recipient that the sender has a certain knowledge without disclosing it. Like trying to say your password without actually giving it.

Many sources go at it with a convoluted method like a tunnel where there’s a hidden gate, and Bob is trying to know if Alice can go through the hidden gate. But then it starts saying that Bob should not see Alice enter. Wouldn’t it be easier for Bob to just see Alice go in one tunnel and come out the other? That would not disclose the secret way of opening the tunnel, right?

In that line of thinking, given a one-way function like a hash, couldn’t the other person just hash their secret and let the other see that the hashes compare?

I must be missing something (as there’s a lot of research going into it and hashes are well-known), but I can’t wrap my head around it.

Can someone tell me what’s wrong with my understanding of zero knowledge proofs?

There are three issues in your proposal, which I'll go over one by one; I hope this will clarify the concept.

The first issue is that the purpose of a zero-knowledge proof is not only to prove knowledge of some information without disclosing it, but something much, much more powerful: the goal is to prove that you know some information$^1$ without disclosing anything at all beyond the fact that you know this information. The point here is that you have no idea what your opponent is going to do with the information you leak about your secret value. It might well be that even some apparently harmless leakage can allow your opponent to do something unexpected and bad. Consider the authentication protocol you suggest, with a hash function $H$: here, given a secret value $v$, you leak $H(v)$. This is clearly not "no information", and you have no guarantee that this $H(v)$ cannot be used to do something bad. So, the way we define zero-knowledge proofs aims at anticipating every possible scenario, as follows: we say that the protocol is zero-knowledge if there exist an efficient algorithm that could produce an interaction with the verifier which is indistinguishable from an honest interaction, but without knowing the secret value. The intuition between this definition is that if the transcript of the interaction cannot be distinguished from something that could have been produced without even knowing the secret value, then it cannot convey anything useful about this value to the verifier (of course, defining that formally requires some care). Your protocol clearly does not satisfy this.

The second issue is the generality of the functionalities we want to consider in general. In your example, you actually assumed that you were only proving that you know the same value as the one already held by your opponent (since she must hash the value herself to compare). But this is not a very useful situation in general. A much more general setting would be for example the following: some public ciphertext $c$ is known, and you want to prove to an opponent that you know its plaintext, but without disclosing the actual plaintext. Here, your hash-then-send simple approach does obviously not work at all. In fact, zero-knowledge proofs deal with even much more general situations than this, allowing to prove wide classes of statements about secret values, which can be hashed, committed, encrypted, signed, or whatever you like.

Eventually, the third issue is that a zero-knowledge proof of knowledge must, well, prove knowledge. A protocol proves knowledge of a value if given the code of the prover, it is actually possible to extract this value efficiently (this is the formal definition of "knowledge" in cryptography). This is also clearly not possible in your example. In fact, your protocol does not prove knowledge of the secret value $v$ at all, since the prover would just have to know $H(v)$ to complete it - which, as you pointed out yourself, does not imply that he knows $v$, since $H$ is one-way.

Let's go over an actual example, to make all of that more concrete.

Take a finite group $G$ of prime order $p$ (I assume some familiarity with basic algebra here). Fix a generator $g$. Consider now another group element $h$. The goal of the prover is to demonstrate to the verifier that he knows a secret value $x$ such that $h = g^x$ (note that such an $x$ exists since $g$ is a generator, but finding it given $h$ might be hard - it's the discrete logarithm problem). This is very useful for authentication: $h$ will be the "public identity" of the prover, and demonstrating knowledge of $x$ such that $g^x = h$ can be used to authenticate him as the owner of the "private identity" associated to $h$ (its exponent in base $g$). Take one second to convince yourself that no simple "hash based" solution does work here.

Here is a protocol that actually works:

The prover picks a random exponent $r$ and sends $R = g^r$ to the verifier.
The verifier picks a random exponent $e$ (the challenge) and sends it to the prover.
The prover computes and sends $d = ex+r$ to the verifier.
The verifier checks that $h^e\cdot R = g^d$.

Take a few seconds to check that the protocol is correct, meaning, if the prover plays honestly, the check of the verifier will succeed.

Why is this zero-knowledge$^2$? Because one can generate a transcript that is perfectly indistinguishable from an honest transcript of this protocol, but without knowing anything about $x$: pick $(e,d)$ at random, then set $R \gets g^d/h^e$, and output the transcript $(R,e,d)$. Note that this can be easily checked to give a transcript uniformly distributed over all transcripts satisfying $h^e\cdot R = g^d$ - i.e., uniformly distributed accross all honest transcripts. Therefore, interacting with the prover in this protocol does not convey any information at all about $x$ (since a transcript following the exact same distribution could have been generated without knowing $x$).

Why does this prove knowledge of $x$? To show this, I must show that given the code of a prover that succeeds in this proof, I can efficiently recover $x$ - hence showing that this prover actually knows $x$. I do it as follows: I run the prover code, to get $R$. Then, I put a breakpoint in the code, fork it, and run it twice on two random different challenges $(e_0,e_1)$ that I choose. The first copy of the code outputs $d_0$, and the second copy of the code outputs $d_1$. Since this is the code of a successful prover, I know that the check passes$^3$, hence I have $(R, e_0, e_1, d_0, d_1)$ such that:

$h^{e_0}\cdot R = g^{d_0}$

$h^{e_1}\cdot R = g^{d_1}$

which gives after a few easy manipulations $g^{(d_0-d_1)\cdot(e_0-e_1)^{-1}} = h$

Therefore, the value $x$ we are looking for is just $(d_0-d_1)\cdot(e_0-e_1)^{-1}$, and we have successfully extracted it. This concludes the proof.

(1) actually, that's only for the specific case of zero-knowledge proofs of knowledge; in full generality, there are two variants of zero-knowledge proofs, which can be used either to show that some statement is true (existential proof), or that you know a proof of some statement (proof of knowledge). I focus on the latter since it seems to be the one you read about.

(2) in fact it's not truly zero-knowledge, formally it only satisfies a weaker definition known as honest-verifier zero-knowledge, but I omitted this point to simplify.

(3) I'm again hiding some technicalities here, since usually we can only assume that the prover succeeds with some noticeable probability, but it does not make a major difference.

EDIT - Answering questions from the comments

From MechMK1:

  Perhaps my understanding of the matter is not good enough, but I am intrigued by the question asked "Why can Alice not simply enter one end of the tunnel and come out the other?". As far as I can tell, this is not directly answered.

First, note that this cave illustration is not meant to be a real zero-knowledge proof, but is rather a scenario given for illustration purpose that conveys some intuition about a zero-knowledge proofs. There will always be some way in which the intuitive scenario does not properly explain all of the concept.

That being said, let's answer "Why can Alice not simply enter one end of the tunnel and come out the other?" (edit: as I noticed afterward, my explanation below basically expands upon the comment to OP's question made by Roman). Recall that to prove that a zero-knowledge proof convey no knowledge, we have to simulate a valid-looking transcript without knowing the actual secret witness. How can it be done with the cave experiment? An answer is given in the actual paper this illustration is taken from: How to Explain Zero-Knowledge Protocols to Your Children, which I encourage you to read for more discussions about this. Basically, you can record a video tape of someone being asked a random side of the tunnel to show up from; the person doing it, who cannot pass through the door, will just have initially picked a side at random and went there. When the person is lucky and just get out from the right side, keep the recorded video; when he is not, delete the video and try again. In the end, what you have is a recording which is perfectly indistinguishable from an actual recording of people doing the real zero-knowledge experiment.

Now, you could argue that this is a bit fishy, perhaps we could craft a valid-looking video of someone entering from one side and leaving from the other side using video editing, hence the alternative proposal can be "simulated" as well. This is were we reach the limit of this illustration. Actually, the original protocol which inspired this illustration is the zero-knowledge protocol for graph isomorphism. It goes as follows: you are given two graphs, $G_0,G_1$ (the "entries of the cave"), and you claim that they are isomorphic (i.e. "you are able to walk from one to the other"). The protocol works as follows:

The prover knows a secret permutation of the vertices of $G_0$ that maps to the vertices of $G_1$, that's his witness. He picks a bit $b$ at random, and a random permutation $\pi$, and sends $G = \pi(G_b)$ (i.e., he "enters the cave through a side picked at random")
The verifier picks a bit $b'$ and sends it (i.e., she "asks the prover to come out of some random side that she picks")
The prover must reveal a permutation $\pi'$ that maps $G_{b'}$ to $G$ (this is either $\pi$, or $\pi$ composed with the secret permutation). I.e., he uses his secret witness ("the key of the door") to "arrive" at the side chosen by the verifier.

Now, this video-recording illustration is actually an intuitive explanation of how to prove that the above is zero-knowledge - you can create a valid-looking transcript by replaying the protocol many times, and discarding the runs where $b' \neq b$. At the same time, "Why can Alice not simply enter one end of the tunnel and come out the other?" is clear here: that would correspond to revealing the path from one side to the other -- i.e., giving away the secret permutation. But again, it's obviously much less clear that this is not a valid solution in the illustrative example, which is a limitation of this example (and one of the reasons why I do not like it much).

From NieDzejkob:

  "The intuition between this definition is that if the transcript of the interaction cannot be distinguished from something that could have been produced without even knowing the secret value, then it cannot convey anything useful about this value to the verifier". The prover establishes a TLS tunnel with the verifier, and sends the secret through it. Nobody can learn anything from the transcript, and yet this will clearly let the verifier learn the secret. Am I missing something?

A comment related to my footnote (2): actually, the transcript guarantees that nothing leaks not only to external people, but also to the verifier himself, if it is indistinguishable from a transcript that could have been produced as the result of an interaction with this verifier. In the proof I've given, the transcript was simulated assuming that the verifier samples the challenge $e$ honestly, which he might not do in reality. Hence, the proof I've given does in fact only show that the protocol is zero-knowledge against verifiers that honestly sample $e$ at random. But general techniques exist to transform this protocol into one that can actually be proven zero-knowledge against arbitrary verifiers, even cheating ones.

Now, back to your question: when doing so, the simulated transcript would not  look indistinguishable from an honest transcript from the viewpoint of the verifier himself, since the simulated transcript would not include this TLS channel transmitting the secret value. An actual proof of zero-knowledge property must produce a simulated transcript that the verifier himself cannot distinguish from a transcript that could have been produced as a result of an interaction with himself. Hence my previous comment on the fact that, for simplicity, what I had in fact proven previously does only guarantee zero-knowledge against verifiers who sample their challenge $e$ honestly, since it's how it's done in the simulated transcript. But as I said, there are methods to simulate against arbitrary verifiers.


Why is there only one keypair in FrodoKEM? use pqcrypto_frodo::frodokem1344aes::*;
let (pk, sk) = keypair();
let (ss1, ct) = encapsulate(&pk);
let ss2 = decapsulate(&ct, &sk);
assert!(ss1 == ss2);

In the above code, only one keypair is generated. The public key is then used to 'encapsulate', which returns a ciphertext and a shared secret. I'm going to assume that the shared secret is used to do symmetric encryption with AES or something.

Since there is only one keypair, doesn't that mean anyone can compute the shared secret with the public key?

Since there is only one keypair, doesn't that mean anyone can compute the shared secret with the public key?

No, because the secret ss1 is randomly chosen each time from a space large enough that there will never be a collision.


How to have a bound (upper or lower) of Gaussion distribution over lattice based crypto> In lattice-based crypto, we always need to sample 'noise' from Gaussian distribution, but how to measure the bound the noise? For example, if the Gaussian distribution is D_{u,\sigma}, where u is the meaning value and \sigam is the standard deviation, and we sample e \gets D_{u,\sigma}, then how to get the bound of e, i.e., |e|? Similarly, if \sf{e} is an n-dimension vector, what it the bound of \sf{e}, i.e., |\sf{e}|? I am confusing how to use the meaning value u here?

The point $u$ here means that instead of sampling a point from the lattice $\Lambda$, you're sampling a point from the coset of the lattice $u + \Lambda$.
This is a "shifted copy" of the lattice (shifted by precisely $u$).

Generically though, you're looking for tail bounds of gaussian mass on lattices. You can find these a variety of places in the literature. They originate with Banaszczyk's New bounds in some transference theorems in the geometry of numbers, where Lemma 1.5(i) states:

  For any $n$-dimensional lattice $\Lambda$ and $s > 0$, a point sampled from $D_{\Lambda, s}$ has Euclidean norm at most $s\sqrt{n}$ except with probability at most $2^{-2n}$.

This citation/statement of the lemma come from another paper (so may not be exact), as I don't have institutional access to download Banaszczyk's work. If you want to see a derivation, you could look at a generalization of this bound, for example this one, which is on eprint. This includes the coset bound you want, which is stated as:
$$
\sum_{\substack{\lambda\in\Lambda\\\|\lambda + u\|_2\geq r}}\exp(-\pi \|\lambda + u\|_2^2) \leq (2\pi en^{-1}r^2)^{n/2}\sum_{\lambda\in\Lambda}\exp(-\pi\|\lambda\|_2^2)
$$
The left-hand side is the gaussian mass in the tail of the coset, which is upper bounded by the gaussian mass on the lattice.
This doesn't directly turn into the tail bound yet (for example, it doesn't include the standard deviation at all), but I imagine transforming the above inequality into a tail bound would be a quite reasonable exercise to do.


Random Number Generator based on AES CTR I've just about done tinkering with an open source DRBG, and I sure would appreciate a bit of advice from this community. Here's the link to the project, hosted at codeproject.com.

It is written in C#, the code is clean and well commented.

The design criteria:

The same seed must generate the same random output each time.
It must be fast.
It must be extremely difficult to unwind.
It must produce excellent random output.

In its simplest form, it is an AES CTR using block chaining. To address criteria #3, I have added methods that reset the state of the key/iv/counter by whitening them and then using the SHA256 hash value.
An example of 'whitening' the data:

private byte[] ExtractArray32(byte[] SubBuffer)
{
    UInt32[] tmpNum = new UInt32[8];
    UInt32[] arrNum = new UInt32[16];
    byte[] data = new byte[64];
    Int32 ct = 0;
    // copy first array in
    Buffer.BlockCopy(SubBuffer, 0, tmpNum, 0, 32);
    // get the first buffer table index
    UInt16 iter = ExtractShort(tmpNum[0], 10);

    // randomize the bits
    for (int i = 0; i < 8; i++)
    {
        arrNum[ct++] = ~tmpNum[i] ^ SEED1024[iter];
        iter = ExtractShort(arrNum[ct - 1], 10);
        arrNum[ct++] = tmpNum[i] ^ SEED1024[iter];
        iter = ExtractShort(arrNum[ct - 1], 10);
    }

    // copy it to byte array
    Buffer.BlockCopy(arrNum, 0, data, 0, 64);
    // get the hash
    return ComputeHash64(data);
}

I know some people don't like it when someone posts code here, but it makes it so much easier to explain with a visual representation…

So what's happening here, is a 32 byte value, say the original key, is copied to a uint32 array (8 * 4 bytes), then copied into a new uint32 array (16 * 4 bytes), on the first interval, the value is reversed, on both, the value is XORed with a uint32 from a 1024 * uint32 table of random values. The table index is the last 10 bits of the previous value (0-1023). This is how I whiten and expand the array so that it aligns with the 64 byte block size of SHA256. The return is the hash value, which becomes the new value.

Questions:

Is this a good way to whiten the data? Is there a better way?

I do realize that flipping a single bit will give me a completely different hash value, but this goes towards criteria #3, make it difficult to unwind.

There are 4 different prototypes, their primary difference being how and when a state reset occurs; one is configurable via a property (10Kib default), another resets after every 4 block transforms (64 bytes), another resets at random.
Is there an ideal interval at which an AES CTR generator should be reseeded? Is reseeding too often introducing patterns that might be exposed by some form of differential analysis?

I think the best way to get a handle on what I've done, is to just check out the article, nothing too complex, but it really could do with some scrutiny before people start using it in the wild, which leads me to my last question..
How can this be made stronger? How would you improve upon this? ..and are there any serious flaws in the implementation?

I think the most important criteria is that, should an attacker get a portion of the random output, say message data from an xor cipher, it must be as difficult as possible for the attacker to unwind it back to the initial state, given that any changes do not seriously impede upon the other criteria..

Here's the new algorithm:

First, the obvious advice is not to use this in practice. Rolling your own is fine for learning, but you should use standard primitives when you need actual security. E.g. one from SP 800-90A which poncho linked in comments.

Now, some observations. I haven't read all your code, so I may misunderstand things.

  Is this a good way to whiten the data? Is there a better way?

Looks unnecessarily complex. AES output is already white, unless AES is broken, so you shouldn't need to do any whitening on the output. The massive table which you use for stretching doesn't seem very secure. For example, you are using secret array indices, which may allow for timing attacks.

  Is there an ideal interval at which an AES CTR generator should be reseeded?

A normal AES generator should be reseeded after $2^{48}$ blocks of output at the latest, according to NIST. That number prevents the attacker from having more than a $2^{-32}$ probability of an advantage.

  Is reseeding too often introducing patterns that might be exposed by some form of differential analysis?

If you have a good source of numbers to feed it, you can do it often, but then why not use those numbers directly? (Performance, maybe, in which case you want relatively infrequent reseeding, but much more often than required is possible.)

Seeding with bad input should only hurt if you use an update system that overwrites previous state and can lead to identical key & IV.

  How can this be made stronger? How would you improve upon this? ..and are there any serious flaws in the implementation?

I would rip out the whitening stage, for the reasons I mention above, and use AES output as the random output. If you want frequent reseeds and don't have access to a fast TRNG, you could leave an SHA-256 loop for updating the AES key.

Alternatively, if security is the objective, decouple the hash based RNG from AES and run them independently, e.g. XORing the outputs.

A couple more things that seem unnecessary: you are XORing two halves of an SHA-256 output together – using one would be as strong unless SHA-256 is broken; you are XORing the AES counter into the IV, when I think you would be better off treating it as a single counter with a longer period.


Changing the public key in an MD5 certificate Given a valid, signed X.509 certificate using the MD5 digest algorithm and an RSA public key, how feasible would it be to generate a public key which would, all other parts of the certificate being identical, not invalidate the existing digital signature when substituted into the certificate?

Given an existing certificate, it isn’t practical.

MD5 is preimage-resistant, so it is not practical (given $x, y: x = \text{MD5}(y)$) to find $z: z \neq y \land \text{MD5}(z) = x$

But MD5 is still a TERRIBLE choice

MD5 allows for trivial collisions.  This has been used by malware to forge code-signing certificates.


Can I use computational diffie hellman problem in the following scheme? Suppose $$X=mnrP , Y=\frac{1}{n}Q, R=e(P,Q)^m$$

$X,Y,P,Q$ are randomly chosen from $G_1$.And only $X,Y$ is given in public.
$m,n,r$ are randomly chosen from $Z_q$.
Anybody who knows $(1/r)$ can easily get $R=e(X,Y)^{\frac{1}{r}}$.
Can I use computational diffie hellman problem by assuming
 $$X=g^x, Y=g^y$$, then finding $g^yx$.
Because in authenticated identity-based encryption by Ben Lynn, authenticated key
$$K= e(H(ID_A),H(ID_B))^s$$
is assumed to be secure if the CDH problem is hard.In this case, $H(ID_A),H(ID_B)$ is declared as public.

Which one is better, guessing problem or computational diffie hellman problem?

Well, the problem "given $X, Y$, recover $R$" is impossible, even to a computationally unbounded adversary.  The reason is that any value of the form $e(X, Y)^k$ is possible; for any set of nonzero values for $X, Y, n, m, k$, there exists values for $r, P, Q$ that is consistent with the observed $X, Y$ values, and which $R=e(X,Y)^k$

However, that is unlikely to be the only way to attack this system; as stated, your system is informationally secure (in that the attacker literally doesn't have enough information to attack the system), and that is quite rare in cryptography.  Most likely there is some additional information that is available to the attacker; what this information is is vitally important in deciding on the security of the system.


How many bits of symmetric security does RSA-3072 actually provide? I know that the sizes are standardized to $1024$, $2048$ etc. but they actually provide different security than $128$, $256$... for example $\texttt{RSA-}2048$ is actually $112$ bits of security and $128$ bits would be $2304$, so how many bits of security is $\texttt{RSA-}3072$ actually providing?

The https://www.keylength.com/en web site summarizes reports from well-known organizations to give cryptographic key length recommandations for different kind of algorithms. Also note that

  The lengths provided here are designed to resist mathematic attacks;
  they do not take algorithmic attacks, hardware flaws, etc. into
  account.

Plus, there is a feature which allows you to enter the modulus size to synthetize the results: https://www.keylength.com/en/compare/

So by entering $3072$ as the modulus size, according to all the different organizations mentioned on this web site, it is assumed that the $\texttt{RSA-}3072$ security level is equivalent to a $128$-bit symmetric key.

Note that there can be some discrepancies according to the different organizations. For example, for a $2048$-bit modulus size, ANSSI claims that it has the same security level as a $100$-bit symmetric key while NIST says it is $112$.


Which groups to use for Pedersen Commitments I have been reading about Pedersen Commitments, and have come across some  contradictory examples, which is confusing.

Just focusing on simple commitment of scalars (not EC points or vectors), then I have read this:

Why is the Pedersen commitment perfectly hiding?

which states:

  Public parameters - 2 primes , such that =2+1, and 2 elements 1,2∈ℤ∗ of order  (i.e 1,2 are generators of a q-ordered sub-group of ℤ∗).

  Secret parameter - ∈ℤ

  The scheme -  chooses ∈ℤ at random and sends the commitment =12(mod). Then  reveals ′,′ and  accepts iff =′1′2(mod).

and then I have read this version of the scheme:

https://tlu.tarilabs.com/cryptography/bulletproofs-protocols/MainReport.html#pedersen-commitments-and-elliptic-curve-pedersen-commitments

which states:

  Let q be a large prime and p be a large safe prime such that p=2q+1

  Let h be a random generator of cyclic group  such that h is an element of ℤ*q

  Let a be a random value and element of ℤ*q and calculate g such that g=ha

  Let r (the blinding factor) be a random value and element of ℤ*p

  The commitment to value x is then determined by calculating C(x,r)=hrgx
  , which is called the Pedersen Commitment.

  The generator h and resulting number g are known as the commitment bases and should be shared along with C(x,r), with whomever wishes to open the value.

My question is this:

p and q seem to be the same in each example.

In the first example, notice how the secret value is modulo q, the subgroup, whereas in the second example, the secret value, x,  is not modulo anything. Which is correct?

Also, in the first example, the blinding factor, r, is modulo the subgroup q, but in the second example, r is modulo the larger group p.  Again, which is correct?

I've also seen another variant where everything is modulo the larger group, not the subgroup.

Which variant is correct and does it matter?

In general, the second explanation is a bit sloppier, however both appear to gloss over a crucial detail:

  In the first example, notice how the secret value is modulo q, the subgroup, whereas in the second example, the secret value, x, is not modulo anything. Which is correct?

Pedersen commitments only work if $x$ is in the range $(0, q-1)$; given an opening for a value $x$, it is trivial to open it as the value $x+q$.  In practice, this is not important (if we need to commit to a large value, we just commit to the hash); however in this case the first one is more correct.

  Also, in the first example, the blinding factor, r, is modulo the subgroup q, but in the second example, r is modulo the larger group p. Again, which is correct?

The proof that Pedersen commitments is perfectly hiding relies on the idea that the value $r$ is chosen uniformly in the range $[0, q-1]$.  Now, it turns out that both examples do this; the first example makes this explicit, while the second example selects $r$ randomly in the range $[1, 2q-1]$; the computation $h^r \bmod p$ will effectively perform a $r \bmod q$ operation (as $r$ is the size of the subgroup that $h$ generates), which will map the effective value of $r$ to the range $[0, q-1]$, with each effective value having precisely two preimages, and since all preimages are equiprobable, the effective $r$ will be chosen uniformly in the desired range.  This is correct, but not as straight-forward as one would hope (and also a tiny amount less efficient than needed).

Now, the crucial detail that both examples gloss over (unless they cover it in parts of the text you did not quote); it is essential that the committer does not know the discrete log $h$ (or $g_2$) with respect to $g$ (or $g_1$); that is, he does not know the value $x$ s.t. $h = g^x \pmod p$.

If he does know that value, then he can open the commitment to any value he wants; this is less than ideal for a commitment scheme.

The first example just says "there are two generators $g_1, g_2$" without saying where they came from, or who selected them.

The second example says "pick a random $a$, and set $g = h^a \bmod p$ without saying who picks $a$.

This needs to be spelled out; perhaps by either:

Specifying that the verifier picks $g$ and $h$, or
Specifying that they are selected via an appropriate public process; for example, compute $g = (\text{hash}(\text{'g'})) ^2 \bmod p$ and $h = (\text{hash}(\text{'h'})) ^2 \bmod p$ (for an appropriately long hash function)


What is the runtime complexity of the `BLAKE2` hash function? Assume you want to calculate the blake2 hash function for an arbitrary input of $n$ bytes. I am wondering about the runtime, in particular:

Does the runtime of scale linearly with the input length, i.e., can the runtime of blake2 be estimated as O(n)?
Is the landau even something that is sensible here, given how optimized cryptographic operations are on modern day processors (say on an intel-i7)

Blake2 takes (in either variant) the input, processes it in fixed-size blocks, padding the last block with zeroes to the full block size if required. The processing operation happens in constant time (it takes a constant number of cycles, big-O notation is meaningless since the input size is fixed). The initialization and finalization steps also take constant time. Therefore, the overall operation takes $O(n)$ time.


Is steganography valid only for digital images or also for printed images? If I embed some information in an image using steganography and then I print that image, will I be able to retrieve information from the printed image or not?

It depends on the steganography method you're using, and on how the image is printed.

Most steganography methods designed for digital images probably won't survive printing and scanning the image, or at least doing so will introduce a significant amount of noise into the concealed data that will exercise the error correction pretty hard and significantly limit the maximum payload capacity.

However, there are also steganography and watermarking methods that are designed to survive printing, or even designed specifically for printed images.  Indeed, you may have already unknowingly included such watermarks in your prints, if you've printed them on a printer that embeds a machine identification code in its output.


Is it absurd to estimate entropy from a sample? To tell the exact entropy of a source, all I need to do is to use Shannon's formula $\sum -p(i) \lg p(i)$, where $i$ is the $i$-th element of the alphabet emitted by the source.  Therefore, the only thing that keeps me from telling the exact entropy is not knowing $p$.  So, the problem of estimating entropy reduces to the problem of estimating $p$.
I have studied Reid's answer to this question.  Reid seems to say that you get the sample 1011 you could have 0 to 4 bits of entropy.  Why would it be absurd to estimate the probability distribution from this sample?  It turns out we get three ones and one zero.  Is it absurd to guess that $p(1) = 3/4$ and $p(0) = 1/4$, therefore an estimate for the entropy of the source is $0.8111 = 1/4 \times (-\lg(1/4)) + (3/4 \times (-\lg(3/4)))$, and the amount of information in the sample is $3.244$ bits.

Theoretically, you can break down the question of estimating the entropy of a given collection of (assumed to be independent and identically distributed) samples into two steps:

Estimating the distribution of the underlying random variable

Computing that random variable's entropy

Generally you can do the first by "counting". If you see the collection of 4 samples $0, 0, 0, 1$, you can set $\Pr[X = 0] = 3/4$, and $\Pr[X = 1] = 1/4$ (this is generally known as the "empirical distribution"). You can then easily compute the entropy.
Note that the rest of the question has a large caveat, in that you need a source of independent and identically distributed samples to apply it.
If you see $1011$, is this a single sample, or four independent, identically distributed samples?
To answer this you need to think carefully about how the samples are generated, but regardless I'll continue with discussing things assuming you can generate i.i.d. samples.
How accurate the entropy computation is therefore reduces to how close the empirical distribution is to the "true" underlying distribution.
For "large enough" sample sizes, it will converge to the true distribution, but quantifying the rate of convergence becomes important.
There are various ways to do this, a few are summarized in the empirical distribution function wikipedia page.
One particularly useful way to quantify this is via the DKW inequality.
Let $\mathcal{X}$ be the underlying (unknown) distribution, and let $X_1,\dots, X_n$ be $n$ i.i.d. samples from $\mathcal{X}$.
Let $F(x)$ be the cumulative distribution function of $\mathcal{X}$.
We define the empirical cumulative distribution function of the samples $X_1,\dots, X_n$ via:
$$F_n(x) = \frac{1}{n}\sum_{i = 1}^n \mathbf{1}_{X_i \leq x}$$
Here $\mathbf{1}_{X_i \leq x}$ is an "indicator function", which is 1 if $X_i \leq x$, and 0 otherwise.
So $F_n(x)$ counts how many of the $X_i$ are less than $x$ (and then normalizes it to be in $[0,1]$ by dividing by $n$).
The DKW inequality then states that for any $\epsilon > \sqrt{\frac{\ln(2)}{2n}}$:
$$\Pr[|\sup_{x\in \mathbb{R}} (F(x) - F_n(x))| > \epsilon] \leq 2\exp(-2n\epsilon^2)$$
This gives a "Chernoff-like" bound on how far the cumulative distribution function can be from the empirical cumulative distribution function.
After estimating the empirical cumulative distribution function, you can convert this into estimates for the various probabilities.
This is because $p_i = \Pr[X = i] = \Pr[X \leq i] - \Pr[X \leq i-1] = F(i) - F(i-1)\approx F_n(i) - F_n(i-1) \pm 2\epsilon = \tilde{p}_i \pm 2\epsilon$.
More formally, by applying the DKW inequality we will get that $|p_i - \tilde{p}_i| \leq 2\epsilon$ with probability all but $2\exp(2n\epsilon^2)$.
We can then compute the entropy of this:
\begin{align*}
\mathbb{H}[\tilde{X}] &= \sum_{i\in\mathsf{supp}(\tilde{X})} \tilde{p}_i(-\log_2(\tilde{p_i}))\\
&= \sum_{i\in\mathsf{supp}(\tilde{X})} (p_i\pm 2\epsilon)(-\log_2(p_i\pm 2\epsilon))
\end{align*}
From here you could try to bound how close this is to the true entropy.
Unfortunately the only ways I currently see to do it are rather handwavy --- $-\log_2(x)$ is convex so $-\log_2(2(x+y)/2) \leq -1 -\log_2(x)/2 - \log_2(y)/2$, but $\pm\epsilon$ may be negative, so you start running into issues along those lines.
Anyway, you can proceed as you mention, but to get an accurate estimation of the entropy:

You need to be able to "break" your random source into independent and identically distributed samples
You need a large sample size (so the probability an estimate falls outside of the DKW inequality, $2\exp(-2n\epsilon^2)$, is "small").


Decentralised blind leader election I am looking for a decentralised leader election protocol where each node knows whether or not they were elected leader, but nothing else. In particular, this "blindness" property means a node that was not elected leader does not know which node was elected leader.

Do you know of a decentralised blind leader election protocol?

You just want to pick a leader so that only the leader knows? Do you need it to.be at random? By votes?
If you only want to pick a leader at random. Each party picks a large random number and a random index of a party.  Using multi party computation we output the random number matching the modular sum of the indices.
Whoever recognizes his number is the leader. The others just get another random number not their own.