Reversing a known encryption algorithm (4-byte repeating key XOR)

The actual "encryption" is done on this line:

mysecretmessage[i] ^= ((mysecretvalue>>(8*(i%4)))&255);

Clearly, this line XORs every byte (or at least, every element; but it makes sense to assume that this is indeed a byte array) of mysecretmessage with some value derived from mysecretvalue and the byte counter i.

So what does the expression ((mysecretvalue>>(8*(i%4)))&255) actually return?

The counter i only appears in the subexpression i%4, which divides it by 4 and returns the remainder.  So from this we can already tell that, whatever else the expression might be doing, its value will repeat every 4 bytes.  So we're looking for a repeating 4-byte key that, when XORed with the byte sequence given in hex below, will yield a meaningful (and thus presumably the original) message.

(In fact, all that the rest of the expression ((mysecretvalue>>(8*(i%4)))&255) is doing is taking a 32-bit integer mysecretvalue and extracting the i%4-th 8-bit byte from it.  It does this by shifting the bits of mysecretvalue right by 8*(i%4) bits, and then taking the bitwise AND of the result with 255 = 28−1 = 111111112 in binary to extract the lowest 8 bits of it.)

So this is basically XOR encryption with a 4-byte repeating key.  If your message was exactly 4 bytes long, and the key was randomly chosen, then this would be an unbreakable one-time pad.  Since the message is longer than the key, however, it becomes a "many-time pad", which is easy to break.

There are many standard techniques and even automated tools to break this type of repeated-key encryption.  A simple approach is to split the message into 4-byte segments, take the first byte of each segment, and search for a byte that, when XORed with each of these bytes, yields mostly printable ASCII characters, with frequencies approximating those of English text.  Then repeat for the second byte of each segment, and so on.

Another method is "crib dragging".  Basically, you guess an $n$-byte sequence (the "crib") which is likely to occur in the plaintext message, and try to XOR it with each consecutive $n$-byte substring of the ciphertext.  Likely cribs for English text include the most common English words surrounded by spaces, like "the" (5 bytes), "and" (5 bytes), "that" (6 bytes) and so on.

Each crib in each position will yield a candidate key (or a partial key) which you can then use to try to decrypt the message and see if the result makes sense.  (If the crib is longer than the expected key length, you can immediately rule out most positions by checking whether the candidate key repeats as expected.)  This process can also be fully or partially automated using statistical analysis tools.

Once you have the message and the repeating 4-byte key, simply writing out the key bytes in hex, from right to left (since the encryption code starts with the lowest byte), will then give you the mysecretvalue in hex if you want it.


For a given plaintext-ciphertext pair, how many valid AES keys are there?

If $f_k$ is AES the block cipher, then there are $2^{128}$ possible output values for a given plaintext and $2^{|k|}$ possible AES keys, where $|k|$ is either 128, 192 or 256, depending on which AES key size you use.

Assuming AES chooses a random permutation, $g_{PT}(k) = f_k(PT)$ behaves like a pseudorandom function*, so you expect something like $2^{127}$ pairs with AES-128 for a given plaintext, but it is possible that there are none. With AES-192 and AES-256 there are always some colliding keys for every plaintext. You expect every key to have (many) other keys that produce the same ciphertext. Roughly, you expect $2^{255}$ and $2^{383}$ pairs, with multicollisions handled as in the above linked question.

If $f_k$ is AES in some mode of operation, then the answer depends on the length of the message. When message length is close to the key length, you expect a lot of collisions, while if it is higher than twice the key length you expect none  due to the birthday bound.

(The previous ignores IV and possible authentication, which depending on mode may make collisions unlikely even for short messages.)

As for whether the cardinality is "fixed", no, it varies with the plaintext. Without exhaustive search or some kind of break in AES, you can only give the expected value.

* Technically not true, since there are related key attacks on AES. You should not rely on $g$ being PRF, but for the purposes of the math here it is probably close enough.


ECDSA vulnerability related to recovering private key using same r

You are positing that the signer signs two messages $m_1$ and $m_2$ under different private keys $x_1$ and $x_2$, but the same per-signature secret $k$.

\begin{align*}
  s_1 &= (h(m_1) + x_1 r)/k, \\
  s_2 &= (h(m_2) + x_2 r)/k.
\end{align*}

Note that $r = x([k]B)$ where $B$ is the standard base point.  Even if you are given $s_1$, $s_2$, $m_1$, $m_2$, and $r$, this is a system of two equations in three unknowns.  This doesn't even constrain you to a unique solution: for any nonzero value of $x_1$, there is a corresponding value of $(x_2, k)$; likewise $x_2$ and $(x_1, k)$, and $k$ and $(x_1, x_2)$.  Indeed, for, e.g., secp256k1, there are approximately $2^{256}$ possible solutions for $(x_1, x_2, k)$.


ed25519 ssh public key is always 80 characters long?

Is there an option/param like when creating RSA keys that may
  influence the length of the key, or by design will always be 80 (68
  removing the ssh-ed25519) characters?

No, there can't be any such option.
First note that only the last 43 characters of your sample public keys are variable. As this is Base64-encoding, they can at most encode $43\cdot 6=258$ bits of information, which is enough to fit the 255-bit $y$-coordinate and 1-bit for the sign of the $x$-coordinate (this is called point compression).

Next note, that EdDSA (the signature scheme in use here), requires a group to work with and Ed25519 is the variant of EdDSA that fixes this group to the points on the Edwards-25519 curve (which operates on a 255-bit field). Now because your group is fixed and your public key is a point of the curve, it can only possibly have a maximal length of 256-bit (or 80 characters in SSH encoding).

Now there are "more secure" curves (eg Ed448-"Goldilocks") available than the one used by Ed25519 which have longer keys, but the signature scheme wouldn't be called Ed25519 anymore...


Elliptic curve group over a prime finite field $F_p$

The cyclic group over the ECDLP problem is posed is a subset of the set of point of the elliptic curve. That is to say, not all the points in the referred curve will be in the cyclic group. What you've called as $G$ confuses with another notation of the generator of a cyclic group $<G>=\{G,[2]G,\cdots,[n]G=\mathcal{O}\}$.

This is the meaning of what you've may heard as the cofactor ($h$). There is a relation between the number of points in the elliptic curve (the cardinal $|E(\mathbb{F}_p)|$) and the order of the mention cyclic group ($org(G)=n$). Following the P1363, the cardinal of a cryptographically good curve should be prime or "almost" prime.

What this almost mean is to factorize in one big number and another very small. $|E(\mathbb{F}_p)|=n\cdot h$, where $n >>> h$. Back to P1363, $h$ shall not be other than $1$, $2$ or $4$. In a $h=1$ your cyclic group fits with the complete set of points in the elliptic curve. On bigger cofactors, smaller the cyclic group; but don't panic, a $192$ bit curve with a cofactor $2$ can be like a $191$ curve with a cofactor $1$ (despite other issues that suggest to avoid cofactor $1$).


What makes the quadratic residuosity problem hard?

I don't know a full answer to this question (which is why I asked it!), but here's what I've been able to determine so far…

Most of the known solutions and partial solutions to the quadratic residuosity problem are based on the prime factors of $m$. In particular, quadratic residuosity is efficient to check for prime $m$, and a number is a quadratic residue modulo $m$ if it's a quadratic residue modulo every prime factor of $m$, so one important criterion is that the factorisation of $m$ is not known by an adversary. As mentioned to the comments in the question, finding semiprimes that are hard to factorise is a well-known problem, given their use in RSA.

When it comes to the decision problem version of quadratic residuosity, there's also an important criterion on the value of $r$: an efficient algorithm (based on the Jacobi symbol) exists to know whether $a$ is a quadratic residue modulo an odd or even number of prime factors of $m$. If an adversary either knows or can guess the number of prime factors of $m$ (e.g. they know that $m$ is likely to be a semiprime), then around half the possible values of $r$ will be efficiently determinable as quadratic non-residues of $m$ (because they need to be a quadratic residue to every prime factor of $m$, and yet the number of prime factors of $m$ that they are quadratic residues to has a different parity). The conclusion is that $r$ must be chosen to be a quadratic non-residue to an even number of prime factors of $m$ (e.g. if $m$ is a semiprime $pq$, then $r$ must be a quadratic residue to either both of $p$ and $q$, or else neither).

$4n+1$ primes and $4n+3$ primes generally interact with quadratic residuosity problems in different ways, so it's possible that there's a security difference between the two different types of prime. (For example, it is of course easy to intentionally generate a quadratic residue $r$ for every prime factor of any given $m$, even without knowing its factorisation, simply by squaring a random $a$; when using the product of two $4n+3$ primes, it's also easy to intentionally generate a quadratic non-residue for every prime factor.) For Blum Blum Shub, a CSPRNG based on the quadratic residuosity problem, there's a requirement to use the product of two $4n+3$ primes as $m$ (and also to keep $\textrm{gcd}(p-1,q-1)$ small). These requirements appear to be specific to the algorithm in question, in order to ensure that the CSPRNG's period is large, and thus might not be required for the problem more generally; however, more effort has likely been put into breaking the quadratic residuosity problem in this case than in cases with no cryptographic applications, so it may make sense to use such values to benefit from the additional scrutiny they may have been given.

It's also, of course, important to avoid trivial cases, e.g. you wouldn't want to pick $r=0$. One highly important case to avoid seems to be $\textrm{gcd}(r,m)\neq 1$ (both because it makes quadratic residuosity easier to directly calculate, and for the more obvious reason that it reveals a factor of $m$). Apart from that, a random $r$ (that's been verified to have the correct Jacobi symbol, i.e. to be a quadratic non-residue of an even number of factors of $m$) will come up at a random point in a brute-force search for quadratic residuosity, so is likely to be secure.

It's probably worth avoiding the smallest values of $a$ because it's possible to, e.g., efficiently search all the values $0\leq a<\sqrt{m}$ in a single calculation, thus the gain from discarding small $a$ is probably larger than the loss from giving a brute-forcing adversary a smaller search space (even if the adversary knows how many values have been discarded, and thus can start their search higher); however, this is something I'm not sure on, and the optimal number of values of $a$ to discard is unclear. Similarly, it may be worth avoiding values $r$ for which $-r=a^2$ for small $a$ (because the quadratic residuosities of $r$ and $-r$ are related).


AES GCM vs other encryption modes in embedded environment for network traffic

If you are constrained by the embedded environment, you should consider CCM instead of GCM as AES mode.

One of the major constrain when implementing GCM is that the authentication part (the GHASH) is totally unrelated to AES and should be implemented in its own way.
And, to make it reasonably fast, you have to use  key-depended look up tables which will consume RAM.

CCM on the other side uses a variant of AES-CBC-MAC as authentication function and AES-CTR as encryption function, so there is a lot of code reuse and runs at half the speed of a normal AES-CTR (since it needs to process the same block with encryption AND authentication).

That is to say that you could end up in overall better performance (considering both code, ram and speed) with AES-CCM than with AES-GCM, although the latest could be faster if you make use of table in RAM (which is not a problem for PCs implementations but could be a problem in embedded environment).

Some details on the embedded environment could have helped in understading better the trade-offs.


For an elliptic curve, what is the difference between the base field modulus $Q$ and subgroup $r$

You are asking about a subset of Elliptic Curve (EC) domain parameters over $\mathbb{F}_p$ or $\mathbb{F}_{2^m}$

Domain parameters of Elliptic Curves over $\mathbb{F}_p$ is the sextuple:

$$T= (p,a,b,G,n,h)$$

The integer $p$ defines the field $\mathbb{F}_p$,
$a$ and $b$ defines the curve equation in Weierstrass form:
$$E: y^2 \equiv x^3 + a \cdot x + b \pmod{p}$$
$G=(x_g,y_g)$ defines the base point
a prime $n$ which is order of $G$
and an integer $h = \#E(\mathbb{F}_p)/n$

So, first choose an EC, then we choose a $G$ that generates a subgroup of order $n$.

  They are all fields, but what is their relevance to the curve they are defined upon?

EC is an Algebraic Group but it is defined over the Field $\mathbb{F}_p$

  How does this relate to a scalar field?

We have scalar (point) multiplication to represent the $k$ addition of a point $P$ by itself as $kP$.

  Which field is the curve defined upon?

Above $\mathbb{F}_p$, it can be also $\mathbb{F}_{2^m}$, but these are for general Cryptographic purposes. EC's can be defined over the Complex, too.


I want to know the hardness of computing a or b given $g^{b^{-1}}$ and ab in cyclic groups with large prime order

Theorem 1 is not true in general; consider a group where the discrete log problem is easy.
On the other hand, it is true if we assume that the discrete log problem in $G$ is hard (that is, if we can recover either $a$ or $b$ given $g^{b^{-1}}, ab$, then we can use that as an Oracle to recover $x$ given $g^x$)
Theorem 2 is true; for any $b \ne 0$ (and we know $b \ne 0$ if $b^{-1}$ exists), the distributions of $ab$ and $z$ (for random $a, z$) are identical (and hence "hard to distinguish").


Which version(s) of SRP are in ISO/IEC 11770-4:2006?

The multiplier parameter $k$ is different between SRP 6 and 6a. You can see that RFC 5054 calculates it using a hash of the domain parameters (modulus $N$ and generator $g$), so it is using SRP 6a, as opposed to SRP 6 where $k$ is constant.

Likewise, in section 6.2.1 of IEC 11770-4 – the October 2005 draft at least – the equivalent value $c$ is defined as a hash of the domain parameters which it calls $q$ and $g_{q-1}$, so it too is based on SRP 6a.

  Also: ISO/IEC 11770-4:2006 can use an Elliptic Curve setting, with (I guess) shorter cryptograms; is that the case for SRP?

Yes. The protocol in 6.2 is defined for either of the fields in section 5: the discrete logarithm one or the elliptic curve one.


Do ECDH and ECDSA combined solution provide an authenticated protocol exchange solution in MCU environment?

Saying that ECDH does not do authentication is not entirely accurate. If you use ECDH with static, known public keys and both sides prove knowledge of the shared secret, then you do get authentication. However, with ephemeral keys you need some way to authenticate the exchange of public keys. That could be ECDSA or it could be any other authentication.

So yes, if you use ECDSA to authenticate an ephemeral ECDH key exchange, you avoid man-in-the-middle attacks. You still need some way to trust the ECDSA keys, of course.


If you use a fixed salt all your passwords can be attacked concurrently.
Though argon2 is designed to be slow and thus hard to do a dictionary attack I see no reason to give your attacker a speedup factor of the number of users.
This will obviously be on top of any other advantages the attacker may have(e.g superior hardware or cryptographical advancement).
On a system with 100 users, using a salt gives you a 100x advantage over an
attacker doing a dictionary attack on the hashed password. You can use this to slow her down or alternatively tune the security parameter to make your legitimate hashing faster and less resource intensive.
Using a salt is an easy win.


I figured it out. All you have to do is to use Bouncy Castle Java library. All other libraries are absolute garbage.
None of the libraries have docs, but at least this one is not a binding to a thirty-year-old C code.


How do revocation certificates work in PGP?

A revocation certificate is a self-signature with signature type 0x20. It only says anybody with access to the private key has revoked it, you cannot distinguish between the real owner and an attacker that got hold of the private key.

You can read the details of what a revocation certificate contains by executing gpg --list-packets [revocation-certificate.asc]. For a revocation certificate of my key prepared in advance if everything including the regular backup fails, this will print:

:signature packet: algo 1, keyid 4E1F799AA4FF2279
    version 4, created 1356517877, md5len 0, sigclass 0x20
    digest algo 2, begin of digest 39 1b
    hashed subpkt 2 len 4 (sig created 2012-12-26)
    hashed subpkt 29 len 1 (revocation reason 0x00 ())
    subpkt 16 len 8 (issuer key ID 4E1F799AA4FF2279)
    data: [8192 bits]

Be aware that also the issue timestamp can be arbitrarily set by an attacker and does not help at distinguishing him from the real owner.


From SEC1 v2.0 (§4.1, pp. 43–47), a public key is a point $Q \in E$, and a signature on a message $m$ is a pair of integers $(r, s)$ satisfying the signature equation (condensed from several steps):

\begin{equation*}
  r \stackrel?= f\bigl(x([H(m) s^{-1}]G + [r s^{-1}]Q)\bigr),
\end{equation*}

where $f\colon \mathbb Z/p\mathbb Z \to \mathbb Z/n\mathbb Z$ projects the least nonnegative integer representative of an element of the coordinate field onto the scalar ring.  Here $G$ is the standard base point, and $H$ is a hash function mapping messages to scalars.

This equation is invariant under the transformation $\phi\colon (r, s) \mapsto (r, -s)$ because $(-s)^{-1} = -(s^{-1})$, $[-\alpha]P = -[\alpha]P$, $(-A) + (-B) = -(A + B)$, and $x(P) = x(-P)$.  It is also obviously invariant under the transformation $\psi\colon (r, s) \mapsto (r, s + n)$ because $s$ is used only as a scalar.

There are three additional requirements specified:

$r$ and $s$ must lie in the interval $[1, n - 1]$, where $n$ is the order of the group.
If $H$ returns invalid then the signature verification must fail.
$[H(m) s^{-1}]G + [r s^{-1}]Q$ must not be the point at infinity.

The only requirement relevant to strong unforgeability is (1), because it rules out the transformations $\phi$ and $\psi$ individually.  But it does not rule out, e.g., $\psi \mathbin\circ \phi$, equivalent to $(r, s) \mapsto \bigl(r, (-s) \bmod n\bigr)$.

Conceivably the signature scheme could require that $s$ be chosen to be ‘even’ like in ANSI X9.62 point compression, or be chosen to be in the lower half of the interval $[1, n - 1]$.  But such requirements are not imposed by verifiers, and so ECDSA cannot provide strong unforgeability.

There are also other obvious ways that an implementation could fail to provide sEUF-CMA:

The implementation could fail to check the intervals of $r$ and $s$.  (However, I don't know any that do.)
The implementation could allow for many different encodings of a single integer.  For example, it could allow BER or DER encodings in some ASN.1 format—because the standard doesn't specify a byte encoding of integers; the signature scheme is really defined in terms of integers, a mistake avoided by EdDSA.

This is the first source of transaction malleability that was reported in Bitcoin, prompting implementations to accept only the unique DER encodings of signatures and reject other encodings, before someone noticed the negation vector too a year and a half later.  (Exercise for the reader aching for a trip down a rabbit hole: Chronicle the saga of transaction malleability in MtGox and figure out what's up with the bankruptcy proceedings these days.)


what actually the function for e(g,g)^xy

This is a bilinear pairing used in cryptography. More precisely it's an evaluation of an appropriate pairing friendly elliptic curve equation.(1,2,3,4,5)


How to break an unknown ciphertext - transposition of some kind

If you know for sure that it is a transposition of some kind you can chek
the average frequency with which the various letters appear in the natural language of the plain text and then compare them to the frequencies of letters in the cyphertext. You can easily find this data on google, here is the example for english.
This method works only if the transposition of the letters is always the same, for example: letter $n$ of the ciphertext = letter $n$ of the plain text + 10.
If your key use columnar transposition you need to work out the column lengths by dividing the message length by the key length. Then you can write the message out in columns again, then re-order the columns by reforming the key word.


Authenticated DH, what protocols are secure?

There have been a large number of so-called authenticated key exchange (AKE) protocol proposals in the literature since the sigma protocols that could be used to replace them. I know of too many to list. They offer various advantages over the sigma protocols, ranging from various stronger security properties (some interesting ones, some which might be of academic interest only, but certainly more than just various forms of deniability) to increased efficiency.

A good high-end design is (H)MQV, see e.g. Krawczyk's papers in 2005 (Hugo Krawczyk,  HMQV: A High-Performance Secure Diffie-Hellman Protocol, pp. 546 - 566, CRYPTO 2005.) if you are just interested in the design. There certainly was an associated patent, but I don't know what the current status of that patent is; and certainly some of its many later variants may be outside the patent.

I could mention a large number of later protocols, but they are hard to compare to each other and the landscape is quite confused; they end up being mostly incomparable if you look closely enough. I'm confident that at the moment, there is no objective method for comparing such protocols that everybody agrees on.

I'm afraid that the first person that mentions any of the newer ones will effectively start a flame war :) I'd say we'd have to wait until the dust settles down, but I think most people agree that HMQV is a pretty solid design.


Yes, given the following conditions:

A trusts the public key of B belonging to B
B trusts the public key of A belonging to A
A trusts the signing algorithm ECDSA used by B
B trusts the signing algorithm RSA used by A
A trusts the key length of B
B trusts the key length of A

Normally, the condition 3,4 use the same algorithm, but if both A and B put trust in the other's algorithm then there is no reason not to trust the authenticity.

As you said 1,2 and 5,6 are true.


Key Derivation Function (KDF) usage for password storage

Yes and no, depending on what you mean by "storing passwords".
If you mean "storing my own passwords in a password store", then "no", since this is clearly not the goal of a KDF. But if you mean "storing authentication data in a database to authenticate our users", then yes, since passwords stored in that way are really hard to recover.
And "yes", companies do use KDF and will keep using it more and more. Notably because NIST has standardized their usage in their latest publication on password storage: NIST.SP.800-63b which says that:

Verifiers SHALL store memorized secrets [i.e. passwords] in a form that is resistant to offline attacks. Memorized secrets SHALL be salted and hashed using a suitable one-way key derivation function.
Key derivation functions take a password, a salt, and a cost factor as inputs then generate a password hash. Their purpose is to make each password guessing trial by an attacker who has obtained a password hash file expensive and therefore the cost of a guessing attack high or prohibitive.

and also because nowadays, data leakages are extremely damageable to any company's PR.
There are two different kind of KDFs:

those for when you have a poor entropy and are afraid of Dictionary Attacks (typically if you store humanly memorable passwords), e.g. Argon2, Balloon, PBKDF, etc.
those that you use when you have a good entropy, which would for example be the case if you rely on the DH protocol to establish a common key. Like e.g. HKDF which is thought for such need-case.

The type I'm talking about here is of the first sort, when you store passwords in a database in order to authenticate users.
I personally have a preference for Argon2. Since other like PBKDF2, can be implemented on ASIC devices, which makes brute-force attacks using such devices much easier, or have less parameters one can tweak... Plus it was chosen as the winner of the password-hashing competition.
Now regarding whether KDFs are actually used, you can simply take a look at most password authentications out there and I believe you'll see that the most important ones do... For instance, LastPass advertises using PBKDF2 to protect your password-store main password and you can tweak yourself the number of iteration done. The Django's framework documentation also mention PBKDF2 as being its default algorithm.
Finally, Wikipedia has a nice list of things using PBKDF2. (Which is still the most used KDF, despite the existence of theoretically better ones.)


How complex must round constants be to resist slide attacks?

It depends on the actual block cipher and is quite an open problem. For example, SCREAM, iSCREAM and Midori64 use such key schedule (i.e., its absense) with sparse round constants. They were broken with a practical attack on quite large weak key space [1]. Though, the linear layer has some special property.

I would add that its not the slide attack that matters, but symmetries/invariants and these things are not yet well understood.

[1] https://eprint.iacr.org/2016/732


Adi Shamir's secret database of all primes is to cryptography venues what the Dahu is to French summer camps. For why, see the answers to this related question.

The three other future work items in the quoted presentation are in the same vein (Breaking RSA-1024 with Fermat factoring; Breaking RSA-1024 using $1024 = 2*2*2*2*2*2*2*2*2*2$; Breaking RSA-1024 using Intel's new RDRAND_NSAKEY instruction).

Note: serious work and some further progress did occur after Cypto 2013; see these updated slides of Asiacrypt 2013, also linked from DJB's smartfacts page.


Is there a way to create an encrypted email with no third party application

It depends on what email host you use. Hosts like Gmail have built in SSL encryption. There are other standards like the S/MIME encryption feature built into Microsoft Outlook. Check out this post https://superuser.com/questions/25658/gmail-and-ssl-encryption-how-much-is-encrypted


How do voters verify a Helios (v3) election result?

How does an average voter know that his vote actually counted? He doesn't have any way of performing the summation and obtaining the private key to decrypt.

This is not actually true. He does have a way of performing the summation. From the spec, "all captured votes are displayed (in encrypted form) for all to see". Given the encrypted votes, you can do the summation. The summation is deterministic, so the homomorphic tally that you come up with in your audit, should be the same tally that each of the trustees comes up with. So when the trustees publish their partial decryption of the summation (the decryption factors), the decryption proofs, and the proof of knowledge of the private key, you can verify that they indeed know the private key, verify that the decryption factors are correct (given the tally you computed using all the encrypted votes). Do this for all trustees and you know all decryption factors are correct. Given all the decryption factors, you can decrypt the summation. At this point, you know that the decryption factors match the tally you computed, and you have used those to get the plaintext of the summation. You still need to make sure that your vote is in the list.

There are still a number of other things you need to do to really verify everything. See Verifying a Complete Election Tally for the complete information.

If at the end of the election the private key is made public, then is knowing the list of fingerprints alone enough to calculate the result themselves? I assume no, otherwise individual votes would be known after the fact.

According to the spec:

  When a voter generates a ballot, Helios provides the ballot fingerprint, which is the base64-encoding of the SHA256 hash of the  data structure defined above.

Since it is just a SHA256 hash, even having the private key will not allow an attacker to compromise the privacy of votes given only the fingerprints. They would have to have the <VOTE> data structure.

How does the summation process prevent someone from submitting a value outside the range of allowed values, unless they decrypt each individual result... which I thought was the whole point of the homomorphic encryption to not do that?

The documentation you link to describes how this is done at a high level.

  A zero-knowledge proof, denoted , is a transcript of a non-interactive proof that the corresponding ciphertext encodes an integer value between 0 and max. For the overall proof, the ciphertext whose value is being proven to be between 0 and max is the homomorphic sum (element-wise product) of the choices ciphertexts.

I'm sure they specify exactly how the zero-knowledge proofs work somewhere.


How do you represent a compressed point on an elliptical curve over F2m?

There are many different but similar ways to do point compression. To make sure we are all aligned, we need to standardize what we do. Let me summarize the content of the documents you cite:

This is P1636.3, which is meant for Identity-Based Public Key Cryptography using Pairings, as can be seen on the IEEE P1636 homepage. It only considers elliptic curves over fields of odd order, and therefore is irrelevant for curve-based crypto over $\mathbb{F}_{2^m}$.
The presentation by Lopez and Dahab shows distinct ways to do point compression over the field $\mathbb{F}_{2^m}$. They seem to propose a novel method, so this is really a perspective from researchers. On slide 15 they show a particular way to do compression, and they refer to the standard IEEE P1636 which contains it. Note that they refer to the general standard P1636, not P1636.3.
This is the actual SEC1 standard, which among other things shows how to do point compression for elliptic curves over $\mathbb{F}_{2^m}$. This is described, as you say, in 2.3.3 part 2.2.2. They show how to do decompression in 2.3.4 part 2.4.2 and 2.4.3. Judging from Lopez and Dahab's slides (I don't have access to P1636 itself), this is done exactly the same way as in IEEE P1636.

Conclusion: in all your documents there is only a single standardized method to do point compression. This would be the most likely option, although I don't have enough experience "in the field" to guarantee this.


First, note the following:

If one-way functions exist then P!=NP (src)
Pseudorandom generators exist if and only if one-way functions exist (src)

From there the proof is trivial.

Now, I wanted to explain (or at least try as this stuff is not my expertise) why the reduction you have in the question is not sufficient.

NP does not mean not-polynomial time, it means nondeterministic polynomial time. Your reduction argues that there is no poly time algorithm. That says nothing about whether or not there is a nondeterministic poly time algorithm. You would have to first show that there is a nondeterministic poly time algorithm, then show that there is not a poly time algorithm (or vice-versa). There may be other problems with the reduction in the question (again this is not my area of expertise). For example, the argument seems to be circular. Hopefully others can comment on this.


For the private key, it's common to use PKCS#8, which is a container format - a header specifying the type of the key (RSA? ECC? Which ECC curve?) and the key itself. The key itself is specified in section C.4 of SEC 1. Everything here is encoded in ASN.1 DER (DER is a concrete encoding of the abstract ASN.1 encoding), which can be saved in raw binary format to disk, or in an ASCII format called PEM which has the DER encoded in Base64 and a header/footer. Which one to use (DER/PEM) is up to the application.
You can generate a key in this format by using the openssl genpkey command, e.g. openssl genpkey -algorithm EC -out eckey.pem -pkeyopt ec_paramgen_curve:P-256 -pkeyopt ec_param_enc:named_curve. The PEM header will be "PRIVATE KEY".
Other possible formats are:

"The key itself" mentioned above directly, without the PKCS#8 header. There is no official name for this format. You can generate a key in this format with the openssl ecparam command. The PEM header will be "EC PRIVATE KEY".
PKCS#12/PFX which is a container format like PKCS#8, but allows bundling the matching certificate.

The public key usually follows the "Subject Public Key Info" structure (which is a ASN.1 structured used in certificates to include the subject's public key). This is also specified in SEC 1, and you will have the same choice between DER and PEM. It's worth nothing that it's not very usual to store the public key by itself, it's either included with the private key or inside a certificate.
For Edwards and Montgomery curves everything is similar, but the "key itself" is encoded per RFC 8410.


AUTHENTICATE MERKLE TREE: In the passage below how is A able to confirm YB in the public file only knowing R, log2 intermediate values, and YB itself?

Alright past Ben listen up. What you are describing here is Tree Authentication ya dingus. Read a book once in a while - get some sun. To be fair to you it wasn't as well explained in "PROTOCOLS FOR PUBLIC KEY CRYPTOSYSTEMS," you had to read Merkle's Thesis, "SECRECY, AUTHENTICATION, AND
PUBLIC KEY SYSTEMS"... pages 41, 41a, 41b, and 42.

Initial Values & Assumptions:

YB = Y5

Log2 Intermediate Values = H(6,6,Y), H(7,8,Y), and H(1,4,Y)...these values are your authentication path

R (Merkle Root) = H(1,8,Y)

GOAL: Only use these initial values to get to the Merkle Root!

"Therefore, to authenticate
Y5 required only that we have previously authenticated
H(1,8,Y), and that we transmit Y5, H(6,6,Y), H(7,8,Y),
and H(1,4,Y). That is, we require 100 log2 n bits of information
to authenticate an arbitrary Y ..."

If you hash Y5 the output is H(5,5,Y). We can now use our first log2 intermediate value. The first one circled is H(6,6,Y). If we concatenate H(5,5,Y) and H(6,6,Y) and hash them together the output is H(5,6,Y). Now let's use our second log2 intermediate value, which is H(7,8,Y). We can now concatenate H(5,6,Y) with H(7,8,Y) and hash them together which yields H(5,8,Y). For the grand finale, we use out last log2 intermediate value which is H(1,4,Y). If we concatenate H(5,8,Y) and H(1,4,Y) and hash them together we should get the Merkle Root, which is H(1,8,Y).

See ya soon future Ben.


How to perform AES MixColumns as matrix multiplication in GF(2) (boolean values)?

Assume that we have to compute $M\times x$, where $M$ is a $n\times n$ matrix, and $x$ is a $n\times 1$ vector, all entries of $M$ and $x$ are in $GF(2^8)$.

We have:

$$
M\times x = M \times \left( \begin{matrix} x_0 \\ x_1 \\ \vdots \\x_{n-1}\end{matrix}\right)
= M \times \left( \begin{matrix} x_0 \\ 0\\ \vdots \\ 0\end{matrix}\right)
\oplus M \times \left( \begin{matrix} 0 \\ x_1 \\ \vdots \\ 0\end{matrix}\right)
\oplus M \times \left( \begin{matrix} 0 \\ 0 \\ \vdots \\x_{n-1}\end{matrix}\right)
$$

Write each $x_i$ in polynomial format: $x_i = x_{i, 0} x^0 + x_{i, 1} x ^ 1 + \ldots x_{i, 7} x ^ 7, x_{i,j} \in \lbrace 0, 1 \rbrace$, which is equivalent to binary form: $x_i = x_{i,0}x_{i,1}\ldots x_{i,7}$ (little endian notation). We have:

$$
M \times \left( \begin{matrix} 0 \\ \vdots \\ x_i \\ \vdots \\ 0\end{matrix}\right)
= M \times \left( \begin{matrix} 0 \\ \vdots \\
\left(\begin{matrix}
x_{i, 0} \\ \vdots \\ x_{i,7}
\end{matrix} \right)
\\ \vdots \\ 0\end{matrix}\right)  \\
= M \times \left( \begin{matrix} 0 \\ \vdots \\
    \left(\begin{matrix}
    x_{i, 0} \\ 0 \\ \vdots \\ 0
    \end{matrix} \right)
 \\ \vdots \\ 0\end{matrix}\right) \oplus
M \times \left( \begin{matrix} 0 \\ \vdots \\
   \left(\begin{matrix}
   0 \\ x_{i,1} \\ \vdots \\ 0
  \end{matrix} \right)
\\ \vdots \\ 0\end{matrix}\right) \oplus \ldots \oplus
M \times \left( \begin{matrix} 0 \\ \vdots \\
  \left(\begin{matrix}
  0 \\ 0 \\ \vdots \\ x_{i,7}
\end{matrix} \right)
\\ \vdots \\ 0\end{matrix}\right)
$$
(Note that $\left(0, , \ldots x_{i,j} \ldots, 0 \right)^T $ is still interpreted as a byte.)

Now, as $x_{i,j} \in \{0, 1\}$, we can check that:
$$
M \times \left( \begin{matrix} 0 \\ \vdots \\
  \left(\begin{matrix}
  0 \\ \vdots \\ x_{i,j} \\ \vdots \\ 0
\end{matrix} \right)
\\ \vdots \\ 0\end{matrix}\right) =
x_{i, j} \times M \times \left( \begin{matrix} 0 \\ \vdots \\
  \left(\begin{matrix}
  0 \\ \vdots \\ 1 \\ \vdots \\ 0
\end{matrix} \right)
\\ \vdots \\ 0\end{matrix}\right) = x_{i, j} \times V_{i,j}
$$

Hence:
$$
M \times x = \bigoplus_{0\leq i \leq n, 0\leq j \leq 7} x_{i, j} V_{i, j}
$$
$V_{i,j}$ is a $n\times 1$ vector, its entries are in $GF(2^8)$. We can check that writing $V_{i, j}$ in $8n\times 1$ binary format (let's call that $V'_{i,j}$) does not change the result. So we have:
$$
M \times x \mbox{ is equivalent to } \bigoplus_{0\leq i \leq n, 0\leq j \leq 7} x_{i, j} V'_{i, j} \\
= (V'_{0, 0}|| V'_{0, 1} || \ldots || V'_{n, 7}) (x_{0, 0}, x_{0, 1}, \ldots x_{n, 7})^T
$$
Let $MC = (V'_{0, 0}|| V'_{0, 1} || \ldots || V'_{n, 7})$, which is a $8n\times 8n$ matrix formed from $8n\times 1$ vectors, we have:
$$
M \times x \mbox{ is equivalent to } MC \times (x_{0, 0}, x_{0, 1}, \ldots x_{n, 7})^T
$$

Thus, we have transformed a matrix multiplication in $GF(2^8)$ to matrix multiplication in $GF(2)$.

Thanks my supervisor for this answer.


I am making some assumptions as to the context of the question here, but I think I understand why/what you are asking. The term you are using, "file stream", to me means an ongoing encryption operation on a computer, so I will word my answer accordingly.

Assume you are a filesystem filter driver, and you can view data as it is read from/written to the filesystem, regardless of the specific filesystem used, or the application that is accessing it.

In this case, an encryption operation may appear as both a read operation and a write operation to the same file, or it may appear as a write operation to a different file (temporary) which then takes the place of the original once the operation is complete (through delete and rename).

There are of course some ways you can determine if the file is being encrypted. If there appears to be a sequential series of reads on a specific file, followed either by sequential writes to the same file, or to another file, and the data being written appears to be random (through statistical analysis), then you can assume an encryption operation is taking place, and then perform more detailed analysis on all open files to the process that is accessing the file.

If there is not a corresponding write operation, but rather a similar amount of bandwidth over a network, the same logic applies. Reads may be buffered before writes or network transmission, but there should be a similar averaged amount of data (unless encoding occurs after encryption), and the bandwidth will probably be easy to spot on large files or groups of files.

Looking at individual files may get you nowhere, but sequential file access (maybe by name or date) with corresponding writes or network transmission is more likely to raise flags, especially if what you are looking for is the signature of someone encrypting large amounts of data. Encryption on a small individual file will be difficult to spot if you do not have a historical trend of data access for all processes. Building a record of those trends and a method of analyzing them will be very similar to the heuristics used by antivirus programs when looking for something that is not in their signature database.


Different inputs but able to generate consistent outputs across different SHA engines

In short, this will be not be possible, even if we only use one secure hash function rather than two.  You seem to be describing a sort of dual second-preimage attack where we need to find two inputs that clash over two separate hash functions.
A secure hash function will be resistant to such attacks.  As such for either SHA2 & SHA3, it will not be possible to find another input that makes a desired output.
I believe that even SHA1 is only weak in terms of collision resistance.  See here for further details.


Perfect shuffle possible with limited raw entropy?

Is it possible to generate all shuffles with a PRNG that has 64, 128 or 160 bit internal state?

No, for restriction of "possible .. with" to a deterministic procedure using the Pseudo RNG output as sole input, and:

Bound to output a single shuffled sequence per run. To generate all shuffles, $\lceil\log_2(52!)\rceil=226$ bits of PRNG internal state are required.
Or bound to use strictly less than $\lceil\log_2(52!)\rceil-160=66$ bits of memory between output of shuffles (for appropriate account of memory).

This is proven by counting the possible states of the deterministic system consisting of the PRNG plus device running the shuffling procedure.

  Does that mean I cannot generate a true shuffle in most modern programming languages?

No. It means that a single instance of a built-in PRNG with that 160-bit limitation can't be used, should we require that the shuffle generated could be any of the $52!$ shuffles, say because such claim was made. If we used such PRNG, irrespective of how it was seeded and security, it could be rationally proven such claim is untrue. But, for a secure and properly seeded PRNG and shuffling procedure, such proof can't be by examination of the shuffles produced (even with a 128-bit internal PRNG state). The proof must rely on the design characteristics of the PRNG. That could be the case in a code audit.

The difficult problem is not making a PRNG with a large state (virtually all modern languages allow to build one). The problem is seeding it with enough entropy. This is not always possible, much less built "in" the programming language¹. However, many modern programming languages (most if you weight in how commonly used/taught they are) come with libraries or allow using external libraries/services which often conveniently provide entropy without a size limitation, and at a rate way more than sufficient for the application.

For example, on a Unix system, a language allowing file I/O often can read /dev/random, which promises to provide true randomness and pause towards that goal if necessary. Using that should be OK, but historically, it has not always. There are anecdotes of embedded devices which generate a key on first boot and end up with a guessable key.

  Java's SecureRandom only has 128bit internal state

That's a dubious assertion. Things depend both on how SecureRandom is used², and on the environment.

  even /dev/rand uses a SHA-1 based PRNG on MacOS (160bits)

As long as /dev/random appropriately re-seeds itself using true entropy, being based on a 160-bit hash or even having a 160-bit state does not imply the (theoretical anyway) limitation of being a PRNG with a 160-bit state. This generator promises to reseed with fresh entropy as needed, and wait when it lacks entropy. It is not (or not supposed to be) a PRNG, that is deterministic after seeding. From this standpoint, /dev/random gives a stronger insurance than /dev/urandom.

  Even using the "golden standard" cryptographic random source it isn't going to be enough. What are my options?

When a paranoia damper is needed (e.g. to convince a gambler who does not trust that $2^{128}$ is large enough), or in order to formally fulfill a promise that all $52!$ possible shuffles can be generated with (nearly) equal probability, the recommendable way is to combine using XOR [or using modular addition modulo $n$ for a primitive that generates a random integer in $[0,n)$ ]:

The output of the "golden standard" cryptographic random source
The output of a custom RNG that is in no way influenced by 1.

With a flawless implementation of that, the resulting RNG is at least as good as the best of the two. This architecture minimizes the (still very practically real) probability that trying to improve on 1 leads to a disaster. Additionally, 1 should be carefully checked to be a Cryptographically Secure True RNG, or a Cryptographically Secure Pseudo RNG seeded from a TRNG with enough entropy.

Now comes the problem of making the custom RNG 2. One possibility if to make a CSPRNG with a 512-bit state initialized as the SHA-512 hash of multiple sources:

The CPU's built in RDSEED, if there is such thing available in the programming environment, in which case that's a sensible choice as an extra entropy source. Same for RDRAND.
Current time to the highest accuracy available, perhaps at different moments in the execution. Same for the job's CPU usage.
The output(s) of some instance of the "golden standard" cryptographic random source with said instance discarded after use³.
For code with a user interface, keypresses and mouse movements (value or position, and sampling of the above sources at each change).
Whatever is easily available, tends to vary, and is even mildly hard for an attacker to guess: compilation date/time, address of static variable/local variable/code, process id, output of some system command (on Windows, wmic process).

For the PRNG 2 itself, one possibility is HMAC-SHA-512(seed, counter) truncated to 32 bytes, where the key seed is the above hash, and the message counter is incremented for each 32 bytes. Techniques to turn this into a uniform generator in $[0,n)$ are well-known.

Note: I'm not claiming that this will generate all shuffles with the exact same probability, or even that it it is possible to positively demonstrate that it is close to that.

¹ Many if not most modern programming languages have no RNG. For example, there's no RNG in the Java language specification. If we count the JCL APIs as part of Java, SecureRandom is there. It is explicitly specified to deffer to providers that often are part of the underlying OS.

² JCL's SecureRandom supports plenty of providers and RNGs, typically including a provider with NativePRNGBlocking which promises to output continuously reseeded entropy, straight from or equivalent to /dev/random.

³ There is nothing preventing repeatedly creating a SecureRandom object, using it to generate say 16 bytes, then disposing of this object. There is at least the potential that the multiple chunks obtained are independently seeded.


Is computing majority element while doing secure two party computation for inner products ( input of the two parties ) an attack on the protocol?

As shown in the attack you described, computing the majority bit is not an attack in the malicious model. However, it is an attack in the semi-honest model.


What is security of stream cipher against chosen plaintext attack?

Suppose choosing plaintext as all zeroes (dark image), will reveal many keystream bits.

It doesn't matter. When using proper cryptographic cipher the bits revealed should not tell anything about the key or previous / next bits.

  With the sufficiently large amount of known keystream bits, it is possible to obtain the original key.

And this is where the term cryptographic comes to the game. The stream ciphers are designed to resist revealing its internal state so even possessing the complete amount of stream bits (used to encrypt the plaintext) it should be hard to derive the key and next bits.

Indeed the LFSR is very open to produce its internal state is not to be used as a stream cipher.

We already had a discussion on this forum. When using simple LFSR (such as common Random implementations with random seed) it is often enought to have very little of the ouput (in some cases 2 numbers) to reveal big part of the internal state and the rest is feasible to guess.

  Is it possible to make above system cryptographically secure against chosen plaintext attack?

Just use proper cryptographic cipher () and you should be ok (assuming you use keys with high entropy and unique iv).

  Is changing the initiation vector frequently so that attacker can get the limited amount of keystream bits only solution?
  How to use initialization vector in such scenario?

You don't need to change IV often. E.g. Salsa has internal state of 512 bits (key size of 256 bits) so it is prettty much enough to encrypt all you need.

It is more important the IV is unique (or random/unpredictable if you want to play safe) for each key reuse. The stream cipher will take care of mixing IV into its output.

  Is one-time permutation after obtaining keystream bits proper solution?

IMHO it is not necessary. When using simple permutations, it doesn't add any security (from the cryptographic point of view)


Implementations of GCM with 64-bit cipher

This would not be recommended in most cases. Note that AES-GCM fails terribly if an IV repeats. In a 64-bit block cipher, if you want the probability of such a failure to be below $2^{-32}$, then you would be very limited in the number of messages you can encrypt. If you can guarantee a unique IV each time, and are not using a random IV in order to get uniqueness, then maybe it can be OK.


Why is private key chosen to be less than chosen prime in diffie-hellman?

since the public key is calculated as Y=(alpha^private-key)mod(chosen prime) and alpha is a primitive root of prime, when Y becomes public then private key can be calculated easily right?

One certainly hopes that it cannot be calculated easily, at least, for the 'chosen prime' that we pick.

since there is a unique private key less than chosen prime that will satisfy the equation.

There's a difference between showing that the equation has a solution, and demonstrating that solution.  That the equation has a solution can be shown by relatively simple number theory; as for finding that solution, the best known algorithm [1] for solving it for unstructured [2] values of $p$ takes superpolynomial time, that is, it slows down (as larger values of $p$ are considered) faster than any polynomial.  The largest unstructured $p$ for which there is a published solved random discrete log problem is circa 768 bits long; we currently use values of $p$ that are at least 2048 bits long (and sometimes longer).
BTW: we generally don't use values of $\alpha$ that is a primitive root; we prefer values that have a large prime order, as that leaks less data about the private value we picked.

[1]: on a conventional computer (such as what you are using to read this web site).  There is a known algorithm that runs on a Quantum Computer which runs in polynomial time; however we currently don't have a Quantum Computer that's large enough and reliable enough to implement that algorithm).
[2]: it turns out to be an easily problem if $p-1$ doesn't have any large prime factors; we deliberately select the $p$ values we use in practice so that $p-1$ does have a large prime factor.


Is every bytestring a valid Ed25519 private key?

There are a few different formats for the standard parts of an Ed25519 private key, which are usually stored as 32-byte or 64-byte strings, so you need to pay attention to the choices made by the system you use it with.  Everyone agrees on how to compute an Ed25519 signature given a secret scalar, which can be a uniform random 256-bit integer, and a PRF secret, which is a uniform random 256-bit string, but the scalar and PRF secret are stored or derived differently in different contexts.

In some exotic protocols where you share a secret scalar between Ed25519 and the X25519 Diffie–Hellman function, the secret scalar may need to be clamped for DH security.  Some libraries do this automatically, particularly those that use a 32-byte pre-master secret; others do not, particularly those that involve hierarchical key derivation.

For example, in libsodium, crypto_sign_keypair generates a 64-byte secret key consisting of the 32-byte pre-master secret seed and the 32-byte public key, with clamping of the scalar.  crypto_sign_keypair_seed derives that same 64-byte secret key from a 32-byte pre-master secret seed.

For the most part, an Ed25519 private key—meaning secret scalar and PRF secret—really is just a uniform random string of either 32 or 64 bytes.  But different libraries may have slightly different rules, so pay attention to the rules of the library.


What risks are involved when choosing a curve for an implementation of ECC?

Risks of choosing specific curves

Using your own crpytographic scheme (a.k.a. "rolling your own crypto") is extremly bad. Anyone can invent an encryption algorithm they themselves can't break. It's much harder to invent one that no one else can break. It's also bad practice to use a non-open-source API for cryptography because you might not know how exactly it's implemented.

But using specific curves doesn't necessarily imply that it's unsecure. Standardized ECC often uses specific curves that are presumed to be secure.

So in general it's good practice to use standardized ECC (i.e. curves from the safe-curve-project) and open-source implementations that have been vetted and are broadly in use.

Auditing a ECC system regarding specific curves

The first thing you should do is research. If you find a paper that raises concern about the security of a specific EC then you should probably find another one.

How to determine if a curve is backdoored

Like many other cryptographic schemes ECC uses random number generators, specifically CSPRNGs.

The problem is, that such CSPRNGs could potentially have a keltographic backdoor, if certain conditions are met. One example of this is a (former) CSPRNG, the Dual_EC_DRBG.

Many cryptographers (i.e. this PDF) have raised concern about this generator and through the Snowden leaks it is now presumed that the NSA had put a kleptographic backdoor in this generator. This video by Computerphile explains it quite well.

The vulnerability of ECC is not the discrete logarithm problem, this is (very likely) not solved. It's rather the implementation of the ECC scheme and especially the usage of certain CSRNGs. If there is a constant in the CSRNG it should be stated how and why this constant was calculated and chosen.


Authenticated encryption vs end-end encryption

Authenticated encryption is an all-in-one encryption form (algorithm) that provides privacy, integrity, and authenticity together.

End-to-end encryption is a concept where only end-users read the encrypted message. end-to-end encryption aims to prevent man-in-the-middle eavesdrop such as telecom and internet providers. The transit data in the servers are encrypted and the service owners do not have keys and the possibility to decrypt it.

they are totally different.


Differences between Extractors and Privacy Amplification for Quantum Random Generators

Privacy amplification (PA) cannot be done at all with only a QRNG (which I take to be a quantum random number generator).  Privacy amplification resides further along the application stack, and requires two co-operating parties (Bob and Alice) and an opponent (Eve) listening in on their quantum channel within their quantum key distribution network (QKDN) :-

Essentially privacy amplification (pink bits above) in QKDNs aims to allow two parties, Alice and Bob, to distil a secure final key from a partially secure bit string. The degree of security (bits) is governed by the Leftover Hash Lemma (LHL), which also can be applied to simple random number generation for regulating the output bias.
The purple rectangle is where true random numbers are generated within a QKDN.  Clearly within a QRNG that would be the end of the story. A randomness extractor may or may not be incorporated into the output stage of the QRNG as they're not always needed. If you did need a randomness extractor, they're used to alter the probability mass function of the quantized signal into an almost perfectly uniform distribution.
That's a lot of stuff, so an example is probably in order.  See High-speed Privacy Amplification Scheme Using
GMP in Quantum Key Distribution, specifically §2.2.


You would need something to prevent do what you would do if those balances were what you said they are from causing the verifier to accept.

That main way of getting that is the prover and verifier both have a statistically binding encapsulation for each of those balances, as described in the paper Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity-Based Encryption (PDF), and the prover additionally has a decapsulation string for each of those.

If you weaken from proofs to arguments as described in the paper Zero Knowledge and Soundness are Symmetric (PDF), then you could let the encapsulation scheme(s) be only computationally binding or instead have the balances be signed in a suitable format, where the prover and verifier both know the signature verification key(s).


Why use prime number $q$ such $q$| $(p-1)$ in discrete logarithm based schemes?

The group you're working with does not have order $p$. In discrete log schemes, you're not working in a finite field, $F_p$, but rather a multiplicative group $1,...,p-1$, which has order $p-1$. Since $p$ is a prime, $p-1$ is composite (as long as $p > 3$). Group theory tells us that there is a subgroup of size $d$ for every $d$ that divides $p-1$.$^{1}$ By choosing a subgroup of order $q$, where $q$ is prime, we ensure that there are no (non-trivial) subgroups. This avoids small subgroup confinement attacks.

As mentioned in the other answer and comments, there are easy ways to find suitable $p$ and $q$. One is by using primes, $p$ and $q$, such that $p = 2q + 1$. Such a $p$ is called a safe prime. Another is by setting $p  = qr + 1$, where $r$ has (potentially) unknown factorization. The group generated by this $q$ is called a Schnorr group.

$^1$ This claim is not true in general. It is true for the group of a finite field. See this Wikipedia section Existence of subgroups of a given order for the gory details in the general case. This math.stackexchange answer is a nice proof for the group of a finite field.


Semantic Security Active or Passive attacks?

The initial notion of semantic security from Goldwasser and Micali has been shown to be euqivalent to what we call today indistinguishability under chosen plaintext attacks (IND-CPA). Yes, that's the only security against a passive adversary and actually the weakest reasonable security notion that we use today.
The authors of the second paper you link seem to use the term semantically secure in a slightly misleading way in the cited part of the paper. What they actually mean is a much stronger notion which is better known as indistinguishability under adaptively chosen-ciphertext attacks (IND-CCA2), which covers active adversaries.
However, this "wording" the authors are using seems to be used by various authors in the way that semantically secure against is seen to be equal to providing indistinguishability under. Also, it is common that when only saying semantically secure, then one means IND-CPA, i.e., a passive adversary. But if one says semantically secure against (adaptively) chosen message attacks, then (IND-CCA1) IND-CCA2 is meant, i.e., an active adversary.
If you read in some parts of the remainder of the second paper you cite from, you will find the correct use:

Under the assumption that this inverting problem is hard, we investigated, in the random oracle mode, how to convert this hard problem into the hard problem of breaking the indistinguishability of encryption with CCA2.


Solutions to $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ with $|x_i| < \ell$

Are there any clear conditions on $p,\ell$ and $m$ under which the equation $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ has at most one solution with $|x_i|<\ell$, where $\gamma$ and the $\xi_i$ are uniformly random?

For any $\ell \ge 2$, there will be values of $\gamma$ and $\xi_i$ for which there are multiple solutions; one such set of values would be $\gamma = 0$ and $\xi_1 = 0$.  Hence, any condition that forbids multiple solutions would necessarily have $\ell < 2$ (which isn't very interesting)

Perhaps you mean to ask "yields more than one solution with probability $< \epsilon$"; that is a rather harder question, but might give you a more useful answer.


Would using a hash of the site name salted with a master password be a secure password for all sites?

The aim of using salt is having a countermeasure against the Rainbow tables. In your case, we can think of as you are creating a password for each site by using a master password and the URL of the site as salt.

Normally, you will be secure against the rainbow tables. One, however, must consider the case that the master password is compromised. Then all of the sites are easily compromised since your URL is known and the hash algorithm is also known.

A better solution, first, use an off-line system to generate the password for each site using a KDF function ( as Bcrypt, Argon2, PBKDF2) using your master password. For the randomness in KDFs you can use the URL but add other random values, too. Now, save your master password as offline, or delete if you finished.

Then you can use these passwords directly. And, remember you will still need the salt and pepper in your websites against rainbow tables.


Partial Homomorphic Schemes that are probabilistic

Actually, only probabilistic schemes will be of interest, since all other schemes (such as the "plain" homomorphic version of RSA) will not provide semantic security. This is problematic, because for many applications of homomorphic encryption plaintext messages can then easily be guessed by "trial encrypting" potential candidates and comparing the ciphertexts. So you want only schemes that are IND-CPA secure.

Yes, Paillier is probabilistic by nature. ElGamal is also probabilistic by nature and as already said by Chris Peikert in the comments it provides IND-CPA security if used correctly (although the homomorphism may then not be of interest for practical applications anymore).

The impossibility of IND-CCA2 secure homomorphic encryption follows this argumentation: Recall the IND-CCA2 game. In the IND game, the avdersary submits two distinct messages $m_0\neq m_1$ and the challenger flips a random bit $b$, encrypts $m_b$ and gives the ciphertext to $m_b$ to the adversary. Now in the IND-CCA2 setting the adversary has access to a decryption oracle in the pre- and the post-challenge phase. Let us now consider the scheme is homomorphic. Thus the adversary can take the challenge ciphertext and any other message of its choice, say $m'$, compute the corresponding ciphertext and perform the homomorphic operation on the ciphertexts corresponding to $m_b$ and $m'$. Then, the adversary submits the resulting ciphertext to the decryption oracle (it is allowed to do so because the restriction on the decryption oracle is only not to submit the challenge ciphertext). Then, when given the plaintext message from the decryption oracle the adversary simply undoes the operation (from the homomorphism) with $m'$ on the plaintext space and if the resulting message equals $m_0$ it outputs $0$ and $1$ otherwise. Consequently, the adversary wins with probability $1$.

So the best you can hope to get for homomorphic schemes is IND-CCA1 security (so called lunch-time attacks, where the adversary has no longer access to a decryption oracle after seeing the ciphertext corresponding to the challenge message).


One-Time Pad Distribution of Keys Between Two Parties

Let's say Alice and Bob have $c$ bits of pre-shared secret key material.  Alice generates $a$ bits of new key material, concatenates it to a message $M$ that is $b$ bits long, and uses $a+b$ bits of their pre-shared key material to encrypt "message||new-key".  She sends this secure message to Bob, who decrypts it with the shared key.  Now they both have $a$ bits of new shared key-material, but in order to securely send those $a$ bits and the $b$ bit message $M$ they had to burn through $a+b$ bits of the previous key material.  The total key material they now have to encrypt future messages is:

$c-$ (Amount spent to send "message||new-key") + $a$.

The term (Amount spent to send "message||new-key") = $a+b$, so the amount they have left is:

$c-(a+b)+a$,

$= c-a-b+a$,

$= c-b$.

So they are no better off now than if Alice had simply send the $b$ bit message $M$ alone without an appended new key.


Are digital signatures secure for signing lots of small messages?

Yes.  Any good standard digital signature algorithm will be secure in this setting.

Digital signature algorithms are designed to be secure against chosen-message attacks, where the attacker can choose any set of messages and learn the signatures on those messages; the security of the signature scheme means that this doesn't help the attacker at all.  This means that it's safe to sign arbitrary messages; there's nothing dangerous or special about messages that are small numbers.

You should choose the key size based upon the desired security level.  A bare-minimum security level is 80-bit security; that then translates to a key size (in a way that is dependent upon the specific signature algorithm you choose).  Similarly, the size of the signature will depend upon the particular signature algorithm you use.


Symetric key encryption is not Authentication?

Consider a CCA2 secure secret key encryption scheme $\mathcal{E}$ with an exponentially large randomness space. Turn this into an encryption scheme $\mathcal{E'}$ where we extend the randomness space of $\mathcal{E}$ with one more element. Let's think of it as $0$ (we can get there by rearranging the randomness space). For randomness $0$ the encryption in $\mathcal{E'}$ becomes the identity for every element.

Now, I claim $\mathcal{E'}$ is still CCA secure as the probability that for the challenge query randomness 0 is chosen is negligible. However, $\mathcal{E'}$ is not a secure MAC as everybody knows a valid tag for any message.


Well , I think DrLecter's great answer in here can be used to answer this question indirectly. But as you want to prove so I will give a proof.
To prove $QR_N$ is a cyclic group, first, you have to know the order of it. In fact, the order of $QR_N$  is $pq=\phi(N)/4$($\phi$ is Euler function ).Actually, we can show this with the help of this map:$$x\to (x_P,x_Q)$$ from $Z_N^*$ to $Z_P^* \times Z_Q^*$.Denote  $Z_N^* \cong Z_P^* \times Z_Q^*$. It's a one to one map. There is a fact about this map we need to use:

$x$ is quadratic residue if and only if $x_P, x_Q$ are all quadratic residues.

Proof.  if $x$ is quadratic residue then  there is a $y$ such that $x=y^2 \pmod{N}$. So $x_P, x_Q$ are all quadratic residues. If  $x_P, x_Q$ are all quadratic residues, then there are $x_1$, $x_2$, such that $$x_P=x_1^2 \pmod{P}$$ $$x_Q=x_2^2 \pmod{Q}$$ .So we the following equation holds:
$$(x_P,x_Q)=(x_1^2,x_2^2)=(x_1,x_2)(x_1,x_2)$$, then using the Chinese remainder theorem, $(x_P,x_Q)$ and $(x_1,x_2)$ point to two elements say $x, y$ in $Z_N^*$. So vice versa.
So with the above fact, we can get $$QR_N \cong QR_P \times QR_Q$$. So $|QR_N|=|QR_P||QR_Q|=\frac{P-1}{2} \frac{Q-1}{2}=pq=\phi(N)/4$.
In order to prove $QR_N$  is a cyclic group,   then you must show that this is an element in it that has the order of $pq$. We know that $QR_P$ is subgroup of $ Z_P^*$  and 'cause its order is prime $p$, then it must be a cyclic group. So does $QR_Q$. So, we can choose  non-identity elements  $x_P \in QR_P$ and  $x_Q \in QR_Q$, and they must be generator. According to Chinese remainder theorem and the fact above, then  $(x_P,x_Q)$ goes to a element in $QR_N$, and its order is $pq$.
Over...
P.S. Although,  i answer your question, but i agree with DrLecter, it likes like your homework, you should think about it yourself.


Is the SHA1 hash of MD5 hash of a password secure?

Pros: The only pro is that your method is very slightly better than storing passwords in plaintext.

Cons: If an attacker gains access to your database, he will easily be able to recover 99% of passwords with only a bit of work, and he won't even need anything more than a laptop.

The lesson here is the usual one. Never build your own crypto. Use a secure password hasher like Argon2. All the information you could need on secure password hashing can be found in this post.

Also, a minor nitpick: "encryption" is not the term you are looking for. Encrypting a value implies a transformation that is invertible, e.g. the result can be decrypted to recover the original value. Hashing, on the other hand, implies a one-way transformation that cannot easily be reversed (other than trying all possible inputs and checking the result).


Where to find a comprehensive content on security proof systems in cryptography

First, as a heads up "approaches to provable security" or "approaches to security proofs" (which it sounds like you are interested in) means something different than "proof systems" in cryptography. Proof systems are a specific construct that are studied within cryptography (similar to encryption or signatures), of which zero-knowledge proofs are the best known example. The fact that there is a naming collision here is unfortunate, but its best to just keep it in mind and sometimes uses more awkward phrasing to avoid the collision.
There are a number of slightly different competing notions of "proof systems". I don't know a resource that collects them all into one document, but two popular ones are:

Bellare and Rogaway's "Game-playing" model, which you can find exposition on here

The "simulation" proof technique, which you can find exposition on here

As for the random oracle model, I believe chapter 6 from Katz's book Digital Signatures is probably a good pointer, although if you do not have institutional access it may not be freely available.
EDIT: Browsing eprint, I found this chapter on hybrid arguments, which also may be interesting.


Why is triple-DES using three different keys vulnerable to a meet-in-the-middle-attack?

The main difference is that with two 56 bit keys the maximal security level is 112 bit, and thus an attack that has a cost of $2^{112}$ operations is no attack, whereas for three 56 bit keys the maximal security level is 168 bits, and an attack that has a cost of $2^{112}$ operations counts as an attack.

This means that two-key 3DES is still a bit weaker than three-key 3DES, but not as much as we'd expect of an ideal 168 bit cipher.

With meet-in-the middle the cipher gets split into two halves, which are attacked separately. The cost of the attack is the sum of the attacks on the two halves, which is dominated by the more expensive half. So meet-in-the-middle is possible if you can split the cipher in a way that the more expensive half is cheaper to attack than guessing the whole key. (Disregarding memory use)

With two keys, one half has (k1,k2) and the other k1. Attacking the first half costs $2^{112}$ operations, attacking the second half costs $2^{56}$ operations. For a total of $~2^{112}$ operations.

With three keys, one half has (k1,k2) and the other k3. Attacking the first half costs $2^{112}$ operations, attacking the second half costs $2^{56}$ operations. For a total of $2^{112} + 2^{56} \approx 2^{112}$ operations.

So meet-in-the-middle gives us an attack with $2^{112}$ operations against either of them, but it's only better than brute-force when using three keys.


What is the Geometric Generalised T' Method?

T' method was introduced in the paper Cryptanalysis of Block Ciphers with Overdefined Systems of Equations by Nicolas Courtois and Josef Pieprzyk (see section 6.1 and Appendix E).

It is a part of XSL attack on block ciphers (such as Rijndael and Serpent).

During XSL attack cipher is represented as a system of multivariate quadratic polynomials and the goal of T' method is to derive more linearly independent equations form it.

Don Coppersmith criticized this attack but noted that

  The method has some merit, and is worth investigating, but it does not
  break Rijndael as it stands.


Do q-ary lattices have parallelogram kind of structure?

Actually, the matrix $A$ defines a $q$-ary lattice $L$, but it is not a basis of $L$.

Let $m \ge n$, write $A$ in blocks, as follows: $A = \begin{pmatrix} A_1 \\ A_2 \end{pmatrix}$, where $A_1 \in \mathbb{Z}_q^{n\times n}$ and  $A_2 \in \mathbb{Z}_q^{m-n\times n}$. Additionally, let's also write the vectors $x \in L$ as "block" vectors $(x_1 \quad x_2)$.

Now, suppose that $A_1$ is invertible over $\mathbb{Z}_q$.

Then we see that $x \in L \Leftrightarrow x = Az \mod q \Leftrightarrow x_1 = A_1z \mod q \text{ and } x_2 = A_2z \mod q $.

But that means that $A_1^{-1}x_1 = z \mod q$ and $x_2 = A_2(A_1^{-1}x_1) \mod q$.

Therefore, over the integers, there is an $(m-n)$-dimensional vector $u$ such that $x_2 = A_2A_1^{-1}x_1 + qu$.

Thus, it is easy to see that the columns of the following matrix form a basis of $L$:

$$B = \begin{pmatrix} I_n & O \\ A_2A_1^{-1} & qI_{m-n} \end{pmatrix} \in \mathbb{Z}^{m\times m}.$$

If we do $B\begin{pmatrix} x_1 \\ u \end{pmatrix}$ we get exactly $\begin{pmatrix} x_1 \\ A_2A_1^{-1}x_1 + qu \end{pmatrix}$, as expected.

Now, answering your other questions:

  Do these also have the same kind of parallelogram structure?

Yes, all lattices have such structure. The parallelogram in this case is defined by the columns of $B$.

  Why do cryptographers use these lattices?

Those lattices appear naturally in cryptography because of problems like SIS and LWE.

There is plenty of material about that on the internet, for example, this tutorial on lattice-based crypto.


Integer factorization still hard with Hamming weight hypothesis?

I suspect that this might be vulnerable to a combinatorial factoring attack.

In this attack, we look at possible solutions to $pq = n \bmod 2^k$, and then extend $p$ and $q$ one bit to list the possible solutions to $pq = n \bmod 2^{k+1}$

Now, if we have no further information about $p$ and $q$, this turns out to be no more efficient than brute force search (as at each step, the number of possibilities doubles, and we have no way to distinguish likely versus unlikely possibilities).

However, in your scenario, we know that both $p$ and $q$ are strongly biased toward 0 bits, and so it would make sense to order our search to explore the possibilities with $p$ and $q$ being mostly 0 first.  The immediately obvious approach would be to keep a list of possible solutions to $pq = n \bmod 2^k$, ordered by hamming weight of $p$ and $q$ (and $k$ somehow); and explore the long solutions with low hamming weight first.

It would seem plausible that this might quickly find a solution if the hamming weight was sufficiently small.  How well would it work in practice (and how small is 'small')?  I suspect that's something that would need to be experimented with.


Should I use XTS or GCM to encrypt my hard drives?

XTS is designed so that the plaintext and ciphertext sizes are the same. This is "needed" for disk encryption in order to preserve the sector size. However, when you are encrypting your disk at the file level, this is a completely irrelevant issue. Also, XTS is not "ideal" in the sense that it's not truly a wide block cipher (defined as a pseudorandom permutation over the block size). It's a standard which is actually somewhat a compromise.

If you are encrypting at file level, then I would recommend an authenticated encryption scheme. GCM is of course possible, but you need to make sure that you have a unique IV and you need to make sure you keep within the bounds. It is possible to use a nonce-misuse resistant version as well; this is highly recommended since nonce reuse is not disastrous (at the very worst will reveal that two files are identical, but if the file includes the path name then this can't happen). You will probably be concerned about speed, but good implementations are well under a cycle a byte and so cost nothing compared to the cost of reading/writing to disk.


My own answer would be: 2048, 2048, and still 2048 bits.

Why ? Because:

2048-bit is the current "standard recommendation"; it has been so for quite some time, and is likely to remain so for quite some time (decades). See this site for pointers.
There are plans for removing support for keys shorter than 2048 bits in some widespread software, e.g. Firefox. Using shorter keys invites future interoperability trouble and maintenance headaches.
There are widespread systems (in particular hardware, such as smart cards and HSM) which have trouble with keys larger than 2048 bits. Even when longer keys are supported, the computational cost rises quite sharply with the key size, so you don't want to overdo it (if your algorithm is super-secure but too heavy, then people will look for ways not to use it, and so goes security down the drain).
If your enemy has access to a quantum computer, then he has resources which are way beyond your wildest dreams. Remember that hiring a few thugs to break your kneecaps is cheap; an attacker with a budget of more than 10k$ will just do that, instead of trying to unravel your public key with computers. Then an attacker who can afford a machine that does not seem to exist at all... Contrary to a quantum computer, a tiny camera concealed in your own glasses is doable with existing technology, and will reveal all your secrets. Worrying about quantum computers is therefore misdirected paranoia.

Your examiner would probably dislike this answer, though. He probably expects that you answer "don't use RSA" when the attacker has a quantum computer, so that you show that you have understood that a quantum computer will make short work of RSA keys of any size.


Is it feasible to find n hashes that sum up to a given hash?

Let the hash length be $d$. If we consider finite groups, like addition modulo $2^d,$ this problem is well understood. Fix $k=n+m.$ If the vectors are randomly generated and form a list of size roughly at least $2^{d/k},$ there exists a solution with constant probability bounded away from zero. This is because a list of size $M$ contains $$F:=\binom{M}{k}$$ subsets of size $k,$ and thus as
$\{a_1,\ldots,a_n,b_1,\ldots,b_m \}$ ranges over these subsets the function $$f(a_1,\ldots,a_n,b_1,\ldots,b_m):=(a_1+ \cdots + a_n)-(b_1+\cdots+b_m)$$ hits $F$ pseudorandom points from $\mathbb{Z}_{2^d}.$

This is a $F$ balls into $2^d$ bins problem and if $F\geq 2^d,$ the probability that $f$ misses the bin corresponding to  $0 \in \{0,1\}^d$ is roughly $e^{-1}\approx 0.37.$ Taking $M=\Omega((n+m) 2^{d/(n+m)})$ is enough here. However, finding the solution is computationally more expensive.

Wagner (see here ) has a recursive binary tree based algorithm for the $k-$ XOR problem $$x_1\oplus \cdots \oplus x_k=0 \qquad (1)$$ with $k=2^s,$ with time and memory complexity essentially
$$O(k 2^{d/(1+s)}).$$ This algorithm can be applied with addition, and will solve your problem if $k=n+m\geq d,$ since a solution will exist in that case.

Here we have $+$ instead of $\oplus,$ which is not a problem since we can use $-b_i'=2^n-b_i$ and use addition throughout. The upshot is, you need $F\geq d/(n+m).$ So if $d=256,$ and $n=20,$ you need $m\geq 236,$ and you will have complexity $$O(k 2^{d/(s+1)}).$$

Note: For the integer case without modular reduction, this is equivalent to a knapsack problem for which, the best algorithms are of very high complexity. Even though your outputs are in $[0,2^d-1]$ addition means your target set is much bigger. I believe the best complexity for finding a solution (if it exists, no guarantees since there is no finite domain) would then be $O(2^{(n+m)/4}),$ memory and $O(2^{(n+m)/2})$ time, from memory (Shamir Schroeppel?).


Timestamping using a hashed linked list and public known events

Your diagram is not very clear, but XOR is not a good combiner function to use for timestamping, as it may allow backdating in some circumstances.  For instance, see the "time travel" attacks in Section 3.3 of the following paper (e.g., pp.179-180): Cryptanalytic Attacks on Pseudorandom Number Generators.  Depending upon how many inputs you have to the XOR function and the specific details of your scheme (which are not sufficiently clear from your question), generalized birthday attacks may also be possible and might allow backdating.

Instead, you should use hashing.  There are standard constructions for hash-chaining: I suggest you use them.  In particular, if the sequence of documents/data to be hashed is $D_1,D_2,D_3,\dots$, we form a hash chain by the formula

$$H_i = \text{Hash}(H_{i-1} \,||\, \text{Hash}(D_i)).$$

Then we can publish the $H_i$'s as well as each $\text{Hash}(D_i)$.  See a standard reference on hash chaining and timestamping for more details.

Update (after the question was edited):

No, this is definitely not a good idea, because $x \oplus y$ does not uniquely determine $x$ and $y$.

For instance, someone could register $H_{D_i}$ (which gets mixed with $B_{t_i}$), then later claim that they actually registered $H'_{D_i}$ (and it was mixed with $B'_{t_i}$), as long as $H_{D_i} \oplus B_{t_i} = H'_{D_i} \oplus B'_{t_i}$.  How would you detect it?  There's not a fantastic way to do it.

It would be much better to compute $M_i$ as

$$M_i = \text{Hash}(\text{Hash}(D_i), t_i, B_{t_i}).$$

Now $D_i$ and $B_{t_i}$ are uniquely determined, given $M_i$; the collision-resistance of the hash function prevents backdating or lying about how $M_i$ was formed.  This is such a simple fix, and it is so obviously better, that there's not much point analyzing in great detail the exact degree of vulnerability of xor; it's clear that using a hash is better than using a xor, so there's absolutely no reason to use a xor in this context.

So, bottom line: use a hash function, not xor.


I'll use these common definitions and notations:

$a\equiv b\pmod c$ means that $c>0$ and $c$ divides $b-a$
$a\equiv b^{-1}\pmod{c}$ means that $a\cdot b\equiv 1\pmod{c}$
$a=b\bmod c$ means that $a\equiv b\pmod{c}$ and $0\le a<c$
$a=b^{-1}\bmod c$ means that $a\equiv b^{-1}\pmod c$ and $0\le a<c$
$\varphi$ is the Euler totient function (also noted $\phi$)
$\lambda$ is the Carmichael function

I restrict to $N$ product of distinct primes; for two such primes, $\varphi(N)=(p-1)\cdot(q-1)$, $\lambda(N)=\operatorname{lcm}(p-1,q-1)$, and $\varphi(N)=\lambda(N)\cdot\gcd(p-1,q-1)$.

The cryptographic standard PKCS#1 requires that the private exponent $d$ is an integer with $0<d<N$ and $e\cdot d \equiv1\pmod{\lambda(N)}$. The later condition is used because it is precisely the necessary and sufficient condition on $d$ so that textbook RSA works, that is:
$$\forall x\in\{0,\dots,n-1\}, y=x^e\bmod N\implies x=y^d\bmod N$$

Notice that $e\cdot d \equiv1\pmod{\lambda(N)}$, or equivalently $d\equiv e^{-1}\pmod{\lambda(N)}$, does not uniquely define $d$. If $d$ is a valid private exponent, then from a mathematical standpoint $k\cdot\lambda(N)+d$ is also a valid private exponent $\forall k\in\mathbb Z$, and is valid from a PKCS#1 standpoint when $0<d<N$.

It is PKCS#1-conformant to use $d=e^{-1}\bmod\varphi(N)$; that uniquely defines a value of $d$, with $0<d<N$ since $\varphi(N)\le N$, and $d\equiv e^{-1}\pmod{\lambda(N)}$ since $\lambda(N)$ divides $\varphi(N)$. This common choice of $d$ will lead to exactly the same results as using any other valid $d$ when exponentiating to the $d$th power modulo $N$. As far as we know, it is not less safe than using $d=e^{-1}\bmod\lambda(N)$, even when side channel attacks are taken into consideration.

Using $d=e^{-1}\bmod\lambda(N)$ rather than $d\equiv e^{-1}\pmod{\varphi(N)}$ is not a good speed optimization: if one is interested in speed, one does not use $d$ at all! Rather, one implements RSA using the Chinese Remainder Theorem (CRT), where exponentiation is performed modulo each prime $p$ dividing $N$, using an exponent which can be computed as $d_p=e^{-1}\bmod{(p-1)}$ irrespective of which $d$ is chosen.

Update: as pointed in comment, the FIPS 186-4 standard requires $2^{\lceil\log_2(N)\rceil/2}<d<\lambda(N)$. Use of $\lambda(N)$ rather than $\varphi(N)$  restricts to a single private exponent, easing Known Answer Tests used for certification; does that in the most mathematically satisfying way; and happens to simplify the requirement $2^{\lceil\log_2(N)\rceil/2}<d$, intended to repel some dangerous ideas of using $p$, $q$ and/or $e$ crafted for low $d$, which otherwise would need to be expressed as the cumbersome $2^{\lceil\log_2(N)\rceil/2}<\big(d\bmod\lambda(N)\big)$.


What are the quantum relations of four-particle GHZ states?

$\newcommand\ket[1]{\left|#1\right>}$
Since you ask about 4-particle GHZ state, I’ll assume you’re familiar with the more usual 3-particle GHZ state.

The 4-particle GHZ state is $(\ket{0000}+\ket{1111})/\sqrt2$. Like the 3-particle GHZ state, loosing a single particle transforms this state to a mere classical mixture of $000$ and $111$.
The relation between the particles can be expressed by the stabilizer group generated by :
$$\begin{gather}
XXXX\\ZZII\\IZZI \\ IIZZ.
\end{gather}$$
This group contains

the  6 permutations of $ZZII$, meaning, that if you measure any two particle in the $Z$ direction, you will obtain the same result
$XXXX$ : meaning that if you measure all particle in the $X$ direction, you will have an even number of them in each direction (i.e. all in the same direction, or two in one direction, 2 in the other, but never 3 in one direction and 1 in the other)
$YYYY$ : meaning that if you measure all particle in the $Y$ direction, you will have an even number of them in each direction.
$ZZZZ$ : meaning that if you measure all particle in the $Z$ direction, you will have an even number of them in each direction. (This is consistent with 1.)
the 6 permutations of $-XXYY$ : if you measure two particle in the $X$ direction, and two in the $Y$ direction, you will have an odd number of $-1$ results.

I thought combining 2,3, and 5 leads to a contradiction similar to the GHZ paradox, but I didn’t manage to find the correct combination, except that measuring any of the qubit the in $X$ or $Y$ direction project the 3 others in a 3-particle GHZ state.


Looking for feedback on the cryptographic design of my open source project: Bloom

One obvious note is that if someone (possibly someone posing as a server) overhears the client to server message (that is, the client's input to the crypto.verify.password_hash.argon2id function), then he knows enough to register as the client to a valid server.  He might not know the password; however he wouldn't need to.

If that is a problem, it would sound like you need some sort of authenticated key exchange (perhaps Opaque), which addresses this.  And, no, I don't happen to have an implementation of that handy...


Well, the idea behind randomized encryption is that a single plaintext $P$ can encrypt into many different ciphertexts $C_1, C_2, ..., C_n$, and that when we encrypt, we pick one of those ciphertexts randomly.  Of course, because the decryptor has no way to knowing apriori which one we picked, it must be able to map any of those ciphertexts back into the original plaintext.

If the ciphertext $C_i$ was exactly as long as the plaintext $P$, then there would be an obvious problem; if the plaintext was $k$ bits long (and hence there are $2^k$ distinct plaintexts), and there are $n$ ciphertexts for each plaintext, we have $n2^k$ ciphertexts (which must all be distinct), and only $2^k$ bit patterns available to express them.

The obvious solution to this is that the ciphertexts must be longer than the corresponding plaintext.  In particular, if each ciphertext was at least $\log n$ bits longer, then everything fits nicely; we have $n2^k = 2^{k + \log n}$ ciphertexts and $2^{k + \log n}$ bit patterns to express them.

Now, the obvious question is: why does anyone bother?  The answer to that is, well, it provides better protection than deterministic methods.  It is generally the case that we'll send multiple messages with the same key.  If we happen to send the same message twice, deterministic encryption would make that obvious to the attacker (because the ciphertexts will be exactly identical), and that is information we'd rather the attacker not have.  Even if we'll never send the same message twice, we may send related messages.  While it is possible to design a deterministic encryption method that doesn't leak any information when given related messages, it's harder than you'd think.  In contrast, the goal behind nondetermanstic encryption is to make all the messages look perfectly random (even if we decide the send the same message multiple times); that turns out to be a rather easier goal to achieve.

One common way nondetermanistic encryption is implemented with CBC mode; the encryptor chooses a random block (known as an IV; 128 bits if he is using AES), and uses that to encrypt the message.  He sends the IV along with the encrypted message to the decryptor, who can uniquely decrypt the message.  One nice property about CBC mode is that it is easy to prove that if the IV is chosen randomly, and that the underlying block cipher is secure, then an attacker cannot distinguish the encryption from a random source.


I think you have mis-understanding and misconception of how nonlinearity of sbox influences on side channel.

The 112 is nonlinear value of good properties sbox (such as AES) , I have not seen sbox with greater value in my literature.

I will go beyond you question, to evaluate s-box against side channel attack such as differential power analysis (DPA), other parameters are taken : Transparency order (TO) (the lower the TO, provides higher resistance to DPA) and signal to noise ratio (SNR) ( the lower the SNR ,provides  higher resistance to DPA).

Prouff showed in his paper (DPA Attacks and S-Boxes), the highly nonlinear s-box are prone to DPA and   the construction of highly-nonlinear S-boxes with small transparency order (close to 0) is an open problem.

I recommend you download the SET tool from this link and start to play it with different constructions of Sbox to gain more knowledge


Is HMAC-MD5 considered secure for authenticating encrypted data?

Yes, there are currently no known attacks on HMAC-MD5.

In particular, after the first collision attacks on MD5, Mihir Bellare (one of the inventors of HMAC) came up with a new security proof for HMAC that doesn't require collision resistance:

  "Abstract: HMAC was proved by Bellare, Canetti and Krawczyk (1996) to be a PRF assuming that (1) the underlying compression function is a PRF, and (2) the iterated hash function is weakly collision-resistant. However, recent attacks show that assumption (2) is false for MD5 and SHA-1, removing the proof-based support for HMAC in these cases. This paper proves that HMAC is a PRF under the sole assumption that the compression function is a PRF. This recovers a proof based guarantee since no known attacks compromise the pseudorandomness of the compression function, and it also helps explain the resistance-to-attack that HMAC has shown even when implemented with hash functions whose (weak) collision resistance is compromised. We also show that an even weaker-than-PRF condition on the compression function, namely that it is a privacy-preserving MAC, suffices to establish HMAC is a secure MAC as long as the hash function meets the very weak requirement of being computationally almost universal, where again the value lies in the fact that known attacks do not invalidate the assumptions made."

However, this does not mean you should use HMAC-MD5 in new cryptosystem designs.  To paraphrase Bruce Schneier, "attacks only get better, never worse."  We already have practical collision attacks for MD5, showing that it does not meet its original security goals; it's possible that, any day now, someone might figure out a way to extend those into some new attack which would compromise the security of HMAC-MD5.  A much better choice would be to use HMAC with a hash function having no known attacks, such as SHA-2 or SHA-3.


What is $z_b$ in this introduction to Private Information Retrieval?

Long to write as a comment;
Look at the referenced paper 47

The user chooses uniformly at random $t$ numbers $y_1,\ldots,y_t \in Z_n^{+}$
such that $y_b$ is a $\text{QNR}$ and $y_j$ ,
for $j \neq b$, is a $\text{QR}$. It sends these $t$ numbers to
DB (total of $t \cdot k$ bits).

The database, DB, computes for every row $r$ a number $z_r \in Z_N^*$ as follows: It  first computes (in $Z_N^*$)
$$w_{i,j} =  \begin{cases} y_j^2 & \textbf{if } M_{r,j} =0\\
y_j & \textbf{if } M_{r,j} =1
\end{cases}$$
and then it computes
$$z_r \ \prod_{j=1}^{t} w_{r,j}$$

...
Therefore, one needs to look at the references to see them in more detail. Survey authors may skip some steps that may trivial to themself but that is not true for all.


Is a chosen ciphertext attack on PGP still possible?

RFC 4880, OpenPGP (superseded RFC 2440 which was up to date in 2002) contains a chapter on security considerations, which also discusses the decryption oracle attack Jallad et al described:

  In late summer 2002, Jallad, Katz, and Schneier published an
       interesting attack on the OpenPGP protocol and some of its
       implementations [JKS02].  In this attack, the attacker modifies a
       message and sends it to a user who then returns the erroneously
       decrypted message to the attacker.  The attacker is thus using the
       user as a random oracle, and can often decrypt the message.

  Compressing data can ameliorate this attack.  The incorrectly
       decrypted data nearly always decompresses in ways that defeat the
       attack.  However, this is not a rigorous fix, and leaves open some
       small vulnerabilities.  For example, if an implementation does not
       compress a message before encryption (perhaps because it knows it
       was already compressed), then that message is vulnerable.  Because
       of this happenstance -- that modification attacks can be thwarted
       by decompression errors -- an implementation SHOULD treat a
       decompression error as a security problem, not merely a data
       problem.

  This attack can be defeated by the use of Modification Detection,
       provided that the implementation does not let the user naively
       return the data to the attacker.  An implementation MUST treat an
       MDC failure as a security problem, not merely a data problem.

  In either case, the implementation MAY allow the user access to the
       erroneous data, but MUST warn the user as to potential security
       problems should that data be returned to the sender.

  While this attack is somewhat obscure, requiring a special set of
       circumstances to create it, it is nonetheless quite serious as it
       permits someone to trick a user to decrypt a message.
       Consequently, it is important that:

  Implementers treat MDC errors and decompression failures as
       security problems.
  Implementers implement Modification Detection with all due
       speed and encourage its spread.
  Users migrate to implementations that support Modification
       Detection with all due speed.

As a consequence, the OpenPGP packets "Sym. Encrypted Integrity Protected Data Packet (Tag 18)
" and "Modification Detection Code Packet (Tag 19)
" have been introduced, together forming an modification detection system (which is the proposed mitigation by Jallad et al):

  NON-NORMATIVE EXPLANATION

  The MDC system, as packets 18 and 19 are called, were created to
        provide an integrity mechanism that is less strong than a
        signature, yet stronger than bare CFB encryption.

  It is a limitation of CFB encryption that damage to the ciphertext
        will corrupt the affected cipher blocks and the block following.
        Additionally, if data is removed from the end of a CFB-encrypted
        block, that removal is undetectable.  (Note also that CBC mode has
        a similar limitation, but data removed from the front of the block
        is undetectable.)

  [...]

At least GnuPG uses these packets per default, which you can verify through gpg --list-packets or pgpdump:

$ echo "foo" | gpg --recipient a4ff2279 --encrypt | pgpdump
Old: Public-Key Encrypted Session Key Packet(tag 1)(524 bytes)
    New version(3)
    Key ID - 0xCC73B287A4388025
    Pub alg - RSA Encrypt or Sign(pub 1)
    RSA m^e mod n(4093 bits) - ...
        -> m = sym alg(1 byte) + checksum(2 bytes) + PKCS-1 block type 02
New: Symmetrically Encrypted and MDC Packet(tag 18)(63 bytes)
    Ver 1
    Encrypted data [sym alg is specified in pub-key encrypted session key]
        (plain text + MDC SHA1(20 bytes))

In GnuPG, you can enforce usage of the new packets through the --force-mdc option (which can also be applied permanently in gpg.conf). From man gpg:

  Force  the use of encryption with a modification detection code. This is always used with the newer ciphers (those with a blocksize greater than 64 bits), or if all of the
                recipient keys indicate MDC support in their feature flags.


Could use an explanation of the notation for an oracle adversary

This represents the probability over all $K$ that $A$ given an oracle access to $F_K(\cdot)$ outputs 1. You usually compare that to the probability of A ouptputting 1 while having oracle access to a random function and the difference tells you how well $A$ does at telling $F_K$ from random


How does one deal with a negative "d" in RSA?

In modular arithmetic all of $a + k \cdot m$ with modulus $m$ and integral $k$ are equivalent. You need to solve this equation modulo $\phi$. So $-x$ is equivalent to $-x + k\cdot \phi$ with a sufficiently large $k$ to make it positive.

In code you can use something like:

d = d % phi;
if(d < 0)
    d += phi;