Why is the Domingo-Ferrer cryptosystem not used in practice?

TLDR: The scheme is symmetric only, its "provable security" argument is flawed, and it is practically insecure when even a modest amount of plaintext is available to attackers.

I'm commenting on the scheme in: Josep Domingo-Ferrer, A Provably Secure Additive and Multiplicative Privacy Homomorphism, published in proceedings of ISC 2002. I ignore the 1996 scheme, which in some sense is a subset.

The paper introduces a symmetric encryption system allowing computation (addition, subtraction, multiplication of plaintext) performed on the ciphertext without key, provided that the results remain below a certain bound ($10^5$ to $10^{20}$ in the proposed parametrizations).

Provable security is claimed for arbitrarily powerful adversary, but under the assumption that only a small number $n$ of plaintexts (including computed results) are known to an adversary: $5$ to $50$ in the proposed parametrizations.

This is an extremely serious limitation. Combined with the fact that it is a symmetric cryptosystem (encryption requires a secret, which also allows decryption of any plaintext or computed result known in ciphertext form), that greatly reduces the practical interest of the system.

In particular I see no credible case for offloading computation to a party with cheaper computational power, for the cost of encryption is going to be prohibitive compared to calculations of practical interest. And if we assume that all ciphertext is public, any party that encrypts of decrypts in legitimate use can get at all the plaintext.

Update: Worse, the information-theoretic security argument is flawed. In a nutshell, it shows that the adversary can't find the key under the assumption that limited information about plaintext is available, but fails to account for

equivalent keys, allowing to decipher without knowing the actual key
considerable information about the plaintext made available merely because it must be small enough that the homomorphic property is usable without overflow.

ACM DL shows 35 papers under cited by. Two notable ones are

Ueli Maurer and Dominik Raub, Black-box extension fields and the inexistence of field-homomorphic one-way permutations, in proceedings of Asiacrypt 2007: credit is given for having shown that there would be practicals applications to the objects which existence is disproved.
A 2018 self-citation in Anonymous and secure aggregation scheme in fog-based public cloud computing, acknowledging that the scheme is

  only secure against ciphertext-only attack

Sadly absent from that citation list are two specific refutations of the paper:

David Wagner, Cryptanalysis of an Algebraic Privacy Homomorphism, in proceedings of ISC 2003. The author's paper page has readable slides, and the article (ps).
Feng Bao, Cryptanalysis of a Provable Secure Additive and Multiplicative Privacy Homomorphism, accepted at WCC 2003 (I could could not locate that one).

On my first glance at the paper, I found it less than fully satisfying from a modern academic perspective:
- The security proof gives no quantitative bound of the advantage for adversaries (the claim is that parameters can be made big enough that this advantage is negligible).
- Parameter $s$ is said to be secret, but its is a small integer from $5$ to $53$ in the proposed parametrizations, and can be estimated from ciphertext size and plaintext bound. The academically correct thing to do is to consider $s$ public.
- It is considered that the system could remain secure when the number of leaked plaintexts exceeds $n$. But the argument boils down to: our analysis does not demonstrate that the secret key is computationally easy to find.


Can you still decrypt XTS if half of the cipher text is deleted?

It depends. (Usual answer to this kind of questions. We would need more details about the data damage to answer)

XTS encryption mode is short for XEX-based tweaked-codebook mode with ciphertext stealing, and XEX stands for Xor-encrypt-xor.

Let's look how the XEX mode is defined:
 (image from wikipedia)

XTS definition changes only how the last block is encrypted, iff the size is not a blocsize multiple.

This mode is a tweakable mode designed to efficient process of consecutive blocks within one data unit. The tweak is represented as a combination of the sector address and index of the block within the sector.

The mode could be defined a tweakable-ECB, so there is no chaining between different blocs. So, you're supposed to recover all sectors that contains no-damaged data. The tweak is given by the sector number and allows to avoid that the same block is encrpyted in the same way if it is stored in different disk sectors, but this mode is deterministic, same data in the same place are always encrypted in the same way.

The problem is that stored and damaged data could be necessary to read the remaining part of the file (a file header, for example).

The ability to decrypt non-damaged sectors is due also to the lack of integrity. Usually if ciphertext has been modified you should not decrypt it at all. And good encryption libraries enforce this binary behaviour.

An image can show how this mode behaves with data modifications:
 (image from this interesting page)

The same page explains how the presence of a diffuser could break your ability to decrypt data for the whole sector even if only a block is damaged.
As far as I know neither dm-crypt nor bitlocker implement a diffuser at the present moment.

So, my final answer is that you're able to recover all sectors containing no-damaged data. If damaged data are all in a small portion of the disk you'll recover the rest of the disk woth no problem, but if the damaged data are sparse, you (probably) will not able to read your data.


Understanding Public key and Private key

If I encrypt a message with public key, I can only decrypt with private key.

True, except that public/private keys must match, and there might be several equivalent private keys (as in many definitions of RSA). We should thus say:

In a secure asymmetric encryption system, a message encrypted with a public key can only be decrypted with a matching private key.

  If I encrypt a message with private key, I can only decrypt with public key.

Encrypt with private key and decrypt with public key is infeasible in many cryptosystems, including those based on the Discrete Logarithm Problem, where public and private keys are fundamentally different. Encrypt with private key is also impossible in many implementations of RSA, and with many asymmetric encryption programs like PGP/GPG.

In an RSA encryption system, it is indeed can be mathematically defined how to to apply the encryption operation with the public exponent $e$ in the public key $(N,e)$ replaced by the private exponent $d$ from the private key. But if this heresy is performed, then anybody can decrypt with the original public key (which is public, see 6), and that goes against the primary goal of encryption. Don't do that.

In cryptosystems that perform signature rather than encryption, it is possible to sign a message with the private key, but that's not encryption. RSA can do both signature and encryption, but usual secure RSA-based signature and encryption cryptosystems have more differences than exchanging the role of public and private key.

  I can generate public key (derived key) from private key (base key).

Not in general. Cryptosystems based on the DLP indeed derive the public key from the private key (and the definition of the group, either public and fixed, or part of the private key). But that applies less to RSA.

In RSA as in the original article, the private key can be considered to be $(N,d)$, where $d$ is chosen essentially at random. It is impossible to find the public key $(N,e)$ from the private key $(N,d)$ alone (for proper choice of $N$): it is also needed the factors of $N$, which are not necessarily part of the private key.
In modern RSA, it is typically first chosen a small public exponent $e$, then drawn secret random prime factors $p,q$, forming $N=p\,q$, with $(N,e)$ the public key. Only then is the private exponent $d$ and the rest of the private key derived from $e,p,q$. So part of the private key is derived from data including a part of the public key.

What always holds it that a public/private key pair is derived from secret base data (output by a Random Number Generator), but the details of that derivation depend on the cryptosystem.

  I can not generate private key from public key.

True. Generating a private key matching a given public key would be a total break of any asymmetric cryptosystem.

  Private key name comes (from) how I handle the key: I keep it in secret, so I call it private key.

True. Notice that secret key is preferably reserved to symmetric cryptography, where the secret key is shared between cooperating parties; and private key is used for asymmetric cryptography, and assumed a secret that is not shared with anyone unless otherwise specified.

  Public key name comes (from) how (I) handle the key: I publish it, anybody can use it, so this is the public key.

True. There typically are additional differences beyond naming. That's the case with DLP, and often in RSA.

  If I publish the base key, I can call it public key.

No. The base key should not be published, if the base key is the private key, or is the secret base data that was used to generate a public/private key pair. Doing so would make the key pair useless, by revealing the private key matching the public key. Private keys must be kept secret, because knowledge of a private key allows to decipher, or forge signature.

  If I keep in secret the derived key, I can call it private key.

Not in general. In particular, not with DLP, where the "derived key" is bound to be the public key.


Your "secret algorithm" is now effectively the key.

If the algorithm stays fixed for all messages, you now no longer have a one-time pad. So let's make your algorithm be tweakable by, say, accepting as input a string that describes its exact operation. Now we have the benefit of being able to publicize the "secret algorithm", since the actual secret details are contained in this input string. Except now that input string is the key, and now you have to find a way to transmit it... which is the problem you were trying to solve in the first place.


Factor RSA modulus given many valid encryption decryption exponent pairs?

Given multiple such tuples, is there a more efficient way to compute p and q?

Possibly, however given how efficient the standard probabilistic method is, we generally don't bother.  Now, someone did find a nonprobabilistic algorithm to do so (proving that the problem is in P, not just in RP); however, it's less efficient in practice, and so that isn't used.

  It seems like we could set up a system of equations using the Chinese Remainder Theorem and then could solve for Euler's totient directly.

It's a little trickier than that; one issue is that we may have $ed \not\equiv 1 \pmod{(p-1)(q-1)}$; hence what such a series of equations would give might not be $(p-1)(q-1)$, but instead $\text{lcm}(p-1, q-1)$.  Now, in practice, $(p-1)(q-1)$ is extremely close to $N$, and hence it should be possible to give a good guess of $(p-1)(q-1)$ given $\text{lcm}(p-1, q-1) = (p-1)(q-1)/\gcd(p-1, q-1)$; however, it is nontrivial to write up an algorithm that will work in general.  In contrast, the standard probabilitic method always works (ok, half the time...)


Do I really need to use the same private/public key pair in RSA?

I've been suggested to digitally sign it, thus, I have my private key, and I ship my application with a public key, and the application then uses the public key to check the QR code

As long as you can live with the requirements for RSA (signature size, computation), that sounds like an excellent idea.

  Am I encrypting the whole message using the private key? or I just generate some separate signature that sits next to my message?

You're generating some separate signature that sits next to your message.  That is, the RSA signature algorithm (which you run) takes the message (and the private key), and spits out a 'signature'.  Then, the RSA verify algorithm (which runs on the phone) takes the message, the signature, and the RSA public key, and then outputs either "signature valid", or "invalid".

You would put into the QR code your message and the signature.

  As far as I know, with RSA, for example, everytime I encrypt a message, a new private and public key are generated, right?

Nope.  There are things known as 'one-time-signatures" where a public/private key can be used only once, but RSA isn't one of them.  Instead, a single RSA private key can sign as many messages as you want.


If an eavesdropper intercepts their conversation and gets the value of $c$ (namely, $m^e \bmod n$) and knows $e$ and $n$, could he not just brute-force different values of $m$ to see which works?

Yes!

This is part of why we do not use the function $x \mapsto x^e \bmod n$ to encrypt messages directly.  Instead, a sensible sender will pick $x$ uniformly at random from all positive integers below $n$, use $k = H(x)$ to encrypt a message $m$ with their favorite symmetric-key authenticated cipher like NaCl crypto_secretbox_xsalsa20poly1305 or AES-GCM, and then transmit $x^e \bmod n$ alongside the ciphertext, so that the receiver can recover $x$ and derive $k$ to decrypt the ciphertext.

This system is called RSA-KEM.  There are also more complicated systems like RSAES-PKCS1-v1_5 and RSAES-OAEP, where we pick $k$ up front and then shoehorn it into something that's close to a uniform random positive integer below $n$, but invariably we use a symmetric-key authenticated cipher to encrypt the actual message.

A little more generally, this goes beyond RSA: any public-key encryption scheme is necessarily randomized, because otherwise anyone could verify a guess about what plaintext is concealed in a ciphertext $c$ is simply by testing whether $c \stackrel?= E(m)$ for a candidate message $m$ where $E$ is the public-key encryption function.


Small generator for classical Schnorr signatures?

FIPS 186-4 appendix A.2 gives an algorithm to generate $g$. They are not talking about Schnor signatures but apparently DSA uses just the same kind of finite cyclic groups.

The algorithm really just tries random $1 < h < p-1$ until it finds an $h$ that fulfills $h^r \not\equiv 1 \pmod{p}$. Apparently the probability to find such an $h$ is not too small.

Fermat's little theorem states that $a^{p-1} \equiv 1 \pmod{p}$ for any prime $p$ and $a \in \mathbb{Z}^+$ with $p \nmid a$.

Thus, with $h<p$ you automatically get $p \nmid h$ and therefore $g^q \equiv h^{rq} \equiv h^{p-1} \equiv 1 \pmod{p}$.

I guess the goal cannot be to find a $g$ with a small bit width to save data. As you calculate $g = h^r \text{ mod } p$ with $r$ being random (uniformly distributed), the possible values for $g$ should be uniformly distributed as well.


Origin of the Chi-Squared test statistic for serial test (two bit test)

This is an interesting question. According to page 3-18 of  available at NIST here it is a common mistake to think the variance statistic is a traditional chi squared statistic. It is not, due to dependence of the overlapping length 2 windows, so a differential statistic is used.

This statistic has been shown to converge to chi squared by I.J. Good, see the reference on the following page of the linked document, who was involved in the enigma decryption effort with Turing. Thus one must take at least a bitstring of 21 bits.

Here is the discussion


Why do two Argon hashes with the same password differ?

ArgonHashString calls the libsodium function crypto_pwhash_str which automatically generates a salt value that is part of the result.


Decryption of a file encrypted by pseudo-random number generator (The Linear Congruence rand()

Short answer: Just replace the srand(time(NULL)); with srand(<epoch
  seconds when encrypted>); and then "encrypt" the encrypted file again
  to decrypt.

Long answer: The unserlying priciple of this programm is a stream cipher, as you already mentioned in your tags, which means the plaintext $P$ is xored with a random keystream $K$. To undo this operation, you simply need to xor the ciphertext $C$ with the same keystream again, which is proven by $C \oplus K = (P \oplus K) \oplus K = P \oplus 0 = P$.

So to reconstruct the plaintext, we need to reconstruct the keystreams to which can be achieved in two ways:

Using the time of encrytion: As you can see in the second line of the main method, the seed of the rand-function is set to the current time in secconds. Since all the following outputs of the rand-function depend on that seed only, one can reconstruct the keystream by setting the seed to the seconds since the unix epoch.
Using a known plaintext:
Let's take a look at how the keystream is generated: $K_{i+1}=(1103515245 \cdot K_i + 12345)\ /\ 65536\ (mod\ 32768)$ This may look complicated at first, but there is one simple property which can easily be exploited: The next state only relies on the previous state. This allows us to compute all the following states using only one state. To get this, we simply xor the ciphertext with the plaintext since $K_0 = C_0 \oplus P_0$ and use it as seed for $K_1$. You can then go on and use the rand-function to get the keystream.

Finally, you need to know the endianness of the encrypting source, so that your decrypting program can match and correctly decrypt.


What is the purpose of the middle-man actor in chaffing and winnowing?

Ron Rivest proposed this technique as a way of dealing with export restrictions as well as giving some protection to the parties communicating. It was roughly at the time of the Clipper chip debate. It is not encryption but gives confidentiality.

Pre shared symmetric keys is assumed to exist between Alice and Bob so the MAC tags can be checked at the destination to verify what's chaff.

Charles adds chaff independently so that confidentiality is achieved but Law Enforcement can't obtain "keys" from Alice or Bob to break the confidentiality.

Note that the keys supply authentication (NOT confidentiality) as is the normal purpose for the MAC.

Read more at Rivest's homepage


How to anonymously transfer ownership where sender cannot resend

After some thought, I have devised one possible solution to the problem (I am definitely open to other ideas too).

Rather than proof of ownership being used solely for the purpose of a subsequent transfer, instead there can be an additional step added to the process whereby the recipient claims ownership of the goods.  The system would not allow multiple claims of ownership for the same transfer request -- only the first claim would be validated, and subsequent claims rejected.  Any time goods are transferred, both proof of ownership and proof of claim would be required.

Once a recipient identifies that he is the recipient of the goods (using the process I outlined above), he would broadcast his intent to claim ownership of the goods.  At this time, he would use the encrypted random private key to verify that he is the intended recipient, and generate a new random public/private key pair.  He would broadcast the new public key as part of his claim, and use the private key to later prove that he claimed ownership of the goods.

Of course, the sender would also have the ability to broadcast a valid claim of ownership after broadcasting the original transfer message (because sender and recipient are both obscured), but that is not a problem as long as the system only validates one claim.  If the sender uses this to reclaim ownership, then the recipient will know that he has not received the goods and can respond accordingly.

This basically allows the sender one opportunity to change his mind before he relinquishes ownership of the goods.  It also allows the sender to reclaim his goods if he accidentally sent them to the wrong address, or if the recipient does not respond in some reasonable amount of time.  So definitely seems to be positive feature of the system.


Deriving 2 shared secrets from one private key and 2 different public keys

Yes, you can use a (semi) static key pair for (Elliptic Curve) Diffie-Hellman. If you want to check for sure that you use ECDH correctly take a look at the NIST SP 56A which shows the various way that key agreement can be used. In this case you'd probably look for 6.2.2.2.

Note that you should check the public keys for validity. Furthermore, this describes a key agreement protocol. If the static public key can be trusted by the two other parties then the party holding the static key pair has been authenticated. You may require additional authentication for the other two parties. Finally, you probably want to use a MAC to validate that you've both generated the correct secret keys in your key agreement protocol rather than afterwards. This probably means that you need a KDF to derive the various session keys. You may want to use different keys for each direction of  communication as well.


Is 2 a safe generator for elgamal encryption

As far as we know, any generator of a given subgroup of $\mathbb Z_p$ is about as safe as any other one for ElGamal encryption; and $2$ is no exception. Argument (this is not a proof): ElGamal encryption is closely related to (and not harder than) the Discrete Logarithm Problem in that subgroup, and consistently solving the DLP with generator $2$ in the subgroup of $\mathbb Z_p$ that it generates is not much harder than solving the DLP with any other generator $g$ of the same subgroup. Close-to-a-proof of the later: If we could consistently solve the DLP with generator $2$ in that subgroup, and knew that subgroup's order $r$, we likely could solve $2^y\equiv g\pmod p$ for $y$, and then for $a$ in the subgroup we could consistently solve $g^x\equiv a\pmod p$ for $x$, by first solving $2^z\equiv a\pmod p$ for $z$ using the hypothetical method, then solving $z=x\,y\bmod r$ for $x$ which is easy.

However if would be wrong to conclude that $2$ can safely be used as the generator for any large enough $p$. Common wisdom is to use a subgroup which order $r$ is a large prime $q$ of at least $2b$ bits for security against effort $O(2^b)$ (and otherwise sound choices). It is not enough that the order of the subgroup is large: if $r$ was smooth, the Pohlig-Hellman algorithm would apply, and allow plaintext recovery for any ciphertext.
Note: I defer making a statement as to what exactly are the necessary conditions on $r$ and messages to reach IND-CPA security until I'm sure of what I write!

Update: a stronger argument in favor of the first assertion in this answer is given by poncho: being able to recover plaintext encrypted by ElGamal with generator $2$ (always, or extremely consistently) implies ability to do so with any generator $g$ of that same subgroup (heuristically always, or with possibly sizable odds), even if the DLP itself was insurmountable.


Why is the Lovász condition used in the LLL algorithm?

The issue with the length-reduction criterion alone (and the reason the Lovász condition is included in the LLL algorithm) is that the following basis satisfies it:

(The grey arrow is the projection of $b_2$ to the orthogonal complement of $b_1$.)

Clearly, this basis is not very short, nor is it close to being orthogonal (i.e., note that length reduction alone does not imply almost-orthogonality!). The Lovász condition is suited to detect such a situation: If the order of the vectors is swapped, another length reduction can easily be performed, yielding the following LLL-reduced basis:

It seems that Lenstra, Lenstra, and Lovász have noticed that a situation in which length reduction alone is stuck with a very bad basis — as depicted in the first image — always has vectors which are in the "wrong" order comparing their lengths and which are far from being orthogonal, and that it helps in this case to exchange them and continue length-reducing.¹
That is really the core idea of the LLL algorithm.

I think of the Lovász condition mainly as a technical construction that just "turned out" to work well, but by rearranging the terms, one may get a feeling for why it enforces close-to-orthogonality:

$$
(\delta-\mu_{i+1,i}^2)\lVert b_i^\ast\rVert^2 \;\leq\; \lVert b_{i+1}^\ast\rVert^2
$$
(In your formula, $\delta=1$ is "hardcoded".)

The Gram-Schmidt coefficient $\mu_{i+1,i}$ measures the angle between $b_i^\ast$ and $b_{i+1}$; the angle is small iff $\mu$ is close to $1$, and it is large (i.e. almost orthogonal) iff $\mu$ is close to $0$.
Note this talks about the angle between the orthogonalized vector $b_i^\ast$ and the lattice vector $b_{i+1}$, but $b_i^\ast$ is in turn forced to be "quite close" to $b_i$, hence this also bounds the angle between the lattice basis vectors depending on the orthogonalized vectors' lengths relative to each other.

In short: The Lovász condition is fulfilled if the vectors are close enough to being orthogonal, or if they are roughly ordered by length. Both of these properties lead to length reduction being quite effective.

¹ The procedure of changing the order of some vectors and length-reducing approximates another basis reduction concept, weight reduction, but there is no efficient algorithm to compute that one.


AES-CTR vulnerability to cryptographic oracle

In general, CTR mode is not secure against chosen-ciphertext attacks.  (The same goes for the other classic block cipher modes of operation too; to get security against chosen-ciphertext attacks, you need authenticated encryption.)

In your stated attack scenario, the attacker can obviously use the decryption oracle to decrypt any ciphertexts they intercept, which (assuming there are indeed no limitations on the attacker's access to the decryption oracle) is as good as having the key.  Since this is kind of a boring scenario (the attacker always wins and there's nothing we can do about it), I'll assume that there are at least some messages that the attacker would like to decrypt, but for which they cannot directly query the decryption oracle.

For example, the attacker might only have access to the decryption oracle up to some time limit ("lunchtime attack"), but would like to decrypt messages intercepted after this time limit.  Unfortunately, with CTR mode (or any synchronous stream cipher), the attacker can still do this if they can predict (with reasonable accuracy) the nonces used for future messages: for each likely future nonce, they can ask for the decryption of a message consisting of a long sequence of null bytes using that nonce.  This will give them the raw keystream corresponding to that nonce, which they can then save for later, allowing them to decrypt any future message encrypted using that nonce.

Making the nonces unpredictable thwarts this particular attack, but still does not provide full IND-CCA2 security since the cipher remains malleable.  To make CTR mode non-malleable, you'll need to combine it with a message authentication code using the encrypt-then-MAC construction (i.e. first encrypt the message using CTR mode, then calculate the MAC for the IV + ciphertext).

Note that including the IV in the MAC calculation is essential; if you don't, the attacker can just intercept any legitimate message, change its IV, submit it to the decryption oracle and XOR the returned plaintext with the ciphertext to get the keystream for that IV.


Does one time pad randomness help brute force attacks?

There is no such thing as a random key.  There are only randomly generated keys.

What I mean by that is that randomness is not a property of the key (or message, or number, or whatever), but of the process that generates it.  For example, it is not meaningful to ask whether the number 5 is random, or whether it is somehow more or less random than the number 4.  However, if I pick up a die and roll it, and it lands with the "5" face up, then I can meaningfully say that I have just randomly selected the number 5 (and we can also meaningfully discuss just how random or not the way I rolled the die may have been).

In English we often do use "random" as an adjective to describe a thing (as opposed to an action), when we really should be saying "randomly chosen" or something similar.  But this needs to be understood as just a linguistic shorthand.  "A random number" really means "a randomly chosen number", and that's all there is, or can be, to it.

Why am I stressing this point so much?  It's because when you ask something like:

  If key TQURI is "measured" as less random than XMCKL, ...

you're revealing a fundamental confusion about what "a random key" really means.  As I wrote above, randomness is not a property of the key string itself, so there's no way to assert that, say, the string "TQURI" is somehow more or less random than "XMCKL" or, for that matter, "ABCDE".  Even trying to make the comparison is meaningless.

All that we can meaningfully ask is how likely it is that each of those key strings would appear if we, say, randomly picked five letters from a bag containing each letter of the alphabet and wrote them down (returning each picked letter to the bag before picking the next one).  And the answer to that question is that each of those strings (yes, even "ABCDE") is equally likely to be the result of that process.

Thus, if our one-time pad was generated using the method I described (or by any other equally random means), then none of those proposed keys is any more likely to be the correct one than any other, and so examining them yields no information about the message.

Ps. Yes, this also means that randomness testing is, strictly speaking, a fool's endeavor: a truly random process is equally likely to output any string of a given length, so no such string can be said to be any more or less random than any other in that sense.

The best we can do is to look for distinctive features that may appear disproportionately more often in the results of certain kinds of non-random (or incompletely random) processes, and declare the observation of such features as evidence that the process that generated the output may not be perfectly random.  In that sense, it would be more appropriate to call any such tests "non-randomness testing".

Even then, in doing so, we must necessarily accept the possibility of "false positives", i.e. the possibility that even a perfectly random process can, and will, occasionally generate outputs that look like the output of some non-random process.  A perfectly random 5-letter string generator must, necessarily, generate the string "AAAAA" with probability $1/26^5 \approx 0.00000008$ — and if it did not, it would not be perfectly random.


Realize a MAC using a Pseudo-random function?

If you have a PRF (with larger input than output), you can use it as compression function in a Merkle-Damgård structure, yielding a hash function which you can subsequently turn into a MAC with HMAC. Indeed, the security proof of HMAC relies on indistinguishability of the compression function from a PRF.

There are still an awful lot of details, though. And the PRF assumption is quite strong.


How does mutlivariate crypto schemes work?

UOV

The first thing you need to know about UOV is that the input variables are partitioned into vinegar variables $x_1, \ldots, x_v$ and oil variables $x_{v+1}, \ldots, x_{v+o}$. The number of vinegar variables is roughly twice the number of oil variables: $v = 2o$. The name oil and vinegar comes from the fact that oil variables do not mix with other oil variables in the secret polynomials. In fact, every polynomial of the secret key can be described as a quadratic form. For example, let $v=4$ and $o=2$ and $\mathbf{x}^\mathsf{T} = (x_1 \, x_2 \, x_3 \, x_4 \, x_5 \, x_6)$. Then every secret polynomial can be described as:
$$ f_i(\mathbf{x}) = \mathbf{x}^\mathsf{T} \left( \begin{matrix}
* & * & * & * & * & * \\
* & * & * & * & * & * \\
* & * & * & * & * & * \\
* & * & * & * & * & * \\
* & * & * & * &  &  \\
* & * & * & * &  &  \\
\end{matrix} \right) \mathbf{x} \enspace .$$
Where the $*$ indicate randomly chosen elements, but the blank spaces indicate zeros. The oil variables, $x_5$ and $x_6$ are not mixed with themselves or each other.

Now, it's also important to know that there are exactly $o$ secret polynomials. The vectorial function whose components are $f_i$ is denoted by $\mathcal{F}$:
$$ \mathcal{F}(\mathbf{x}) = \left( \begin{matrix}
f_1(\mathbf{x}) \\
\vdots \\
f_o(\mathbf{x}) \end{matrix} \right) \enspace .$$
(In our example there are just two components in $\mathcal{F}$.)

The public key $\mathcal{P}$ is generated from $\mathcal{F}$ by composing it with a random invertible linear transformation $S \in \mathsf{GL}_{o+v}(\mathbb{F}_q)$, which is really a square matrix whose inverse exists: $S \in \mathbb{F}_q^{(v+o)\times(v+o)}$. The public key is then
$$ \mathcal{P} = \mathcal{F} \circ S \enspace .$$

In order to sign a document $d$ with hash $\mathbf{h} = \mathsf{H}(d)$, the signer does the following. First, choose a random assignment to the vinegar variables $x_1, \ldots, x_v$. Then the system of polynomial equations $\mathcal{F}(x_{v+1},\ldots,x_{v+o}) = \mathbf{h}$ is a linear $o \times o$ system. Solve it to obtain $x_{v+1}, \ldots, x_{v+o}$ and at this point the signer has the entire vector $\mathbf{x}$. Next, compute the signature $\mathbf{y}$ as $\mathbf{y} = S^{-1}\mathbf{x}$.

In order to verify a signature $\mathbf{y}$, the verifier evaluates the public key in $\mathbf{y}$, and checks if the result is equal to the hash of the document, i.e.,
$$ \mathcal{P}(\mathbf{y}) \stackrel{?}{=} \mathsf{H}(d) \enspace .$$

Notice how UOV uses a linear $o \times o$ system as a step in generating signatures, but how this step generalizes to any quadratic (!) system for which it is possible to find an inverse efficiently. For instance, you can level down recursively and put another UOV system there. This multi-layer approach is called Rainbow.

HFE, HFE-, and HFEv-

HFE-type systems are very different. The first thing you should know about them is that they use univariate polynomials over the extension field. So $\mathbb{F}_q$ is the base field (like in the UOV case). Then pick any irreducible polynomial $f(z) \in \mathbb{F}_q[z]$ of degree $n$, and then you can identify the set of polynomials $\mathbb{F}_q[z] / \langle f(z) \rangle$ of degree smaller than $n$ as a new field, the extension field $\mathbb{F}_{q^n}$, whose operations are polynomial addition and polynomial multiplication modulo $f(z)$. Whenever you have a vector of $n$ values over the base field, say $\mathbf{a} \in \mathbb{F}_q^n$, you can embed this value in the extension field using the canonical embedding $\varphi : \mathbb{F}_q^n \rightarrow \mathbb{F}_{q^n} : \mathbf{a} \mapsto A = \sum_{i=1}^na_iz^{i-1}$. In particular, you can do this with the vector of variables: $\varphi(\mathbf{x}) = X$ and then you have a single variable $X$ over the extension field. Any list of $n$ multivariate polynomials in $\mathbf{x}$ over the base field maps to one univariate polynomial in $X$ over the extension field, and vice versa.

In order to generate a HFE secret key, choose a random univariate polynomial over the extension field $\mathcal{F}(X) \in \mathbb{F}_{q^n}[X]$ with degree at most $D$ and of the form
$$ \mathcal{F}(X) = \sum_{i} \sum_{j} \alpha_{i,j} X^{q^i + q^j} \enspace .$$
In other words, choose the coefficients $\alpha_{i,j}$ uniformly at random from $\mathbb{F}_{q^n}$ as long as $q^i+q^j \leq D$, and set $\alpha_{i,j}=0$ otherwise. Following this structure for $\mathcal{F}$ will guarantee that it maps to a list of multivariate quadratic equations over the base field. In the old days they recommended $D \approx 1000$ but now we understand how to make HFE secure with much smaller $D$, e.g. $D \approx 10$ -- and that will only make the scheme faster! Next, choose two random invertible linear transformations $T, S \in \mathsf{GL}_n(\mathbb{F}_q)$ which are once again really invertible square matrices in $\mathbb{F}_q^{n \times n}$. The secret key consists of $(\varphi, \mathcal{F}, T, S)$. The public key is found by composing these transforms:
$$ \mathcal{P} = T \circ \varphi^{-1} \circ \mathcal{F} \circ \varphi \circ S \enspace .$$

In order to sign a document $d$ with hash $\mathbf{h} = \mathsf{H}(d)$, the signer proceeds as follows. First, he computes $Y = \varphi(T^{-1}\mathbf{h})$. Then he uses Berlekamp's algorithm to factorize the polynomial $\mathcal{F}(X)-Y$ and find the roots $\{X_i\}$ that make it zero. He chooses one of these roots as $X$ and proceeds to compute the signature $\mathbf{z} = S^{-1}\varphi^{-1}(X)$.

In order to verify a signature, the verifier evaluates the public key $\mathcal{P}$ in $\mathbf{z}$ and checks whether he obtains the hash $\mathbf{h}$ of the document:
$$ \mathcal{P}(\mathbf{z}) \stackrel{?}{=} \mathsf{H}(d) \enspace .$$

Unfortunately, HFE as described up until here turns out to be insecure. In particular, it is vulnerable to a direct algebraic attack involving efficient Gröbner basis algorithms. That's why you need at least one of the modifiers - (minus) or v (vinegar). It makes sense to use both. A good right-hand rule is $a + v + \mathsf{log}_2 D \geq 15$.

Minus means that some polynomials are dropped from the public key. In particular, the decomposition now involves a forgetful operator $\pi : \mathbb{F}_q^n \rightarrow \mathbb{F}_q^{n-a}$ that leaves the first $n-a$ components intact but drops the remaining $a$ ones:
$$ \mathcal{P} = \pi \circ T \circ \varphi^{-1} \circ \mathcal{F} \circ \varphi \circ S \enspace .$$
In order to generate a signature, the signer has to choose the value of the missing polynomials. This is no problem as a random choice will suffice.

Vinegar consists of adding $v$ vinegar variables. During signature generation, the value of these vinegar variables is also chosen at random, after which what's left to do is to invert the regular HFE system. Instead of finding a solution to the linear $o \times o$ system (as was the case for UOV), now one must find the preimage by factorizing the HFE polynomial.

Reading Materials

In terms of accessible reading materials, I can recommend two things. One, Ding and Yang have a chapter in the 2009 book "Post-Quantum Cryptography". Two, Ding, Gower and Schmidt have a book called "Multivariate Public Key Cryptosystems". Aside from that, the relevant papers good reads because they contain all the necessary information, for example to estimate security. On the other hand, they are a lot denser.


Text messaging application - AES with or without message authentication

Non-authenticated symmetric encryption is malleable, meaning that an attacker who intercepts an encrypted message can modify it in ways that result in (at least partially) predictable changes to the decrypted plaintext even if they do not know the encryption key.

The exact ways in which this can be done depend on the mode of operation used, but the most obvious examples are streaming modes like CTR and OFB, where simply flipping any bit of the ciphertext will flip the corresponding bit of the plaintext.  Thus, an attacker who could guess a part of your encrypted XML message could manipulate it in nearly any way they like by replacing characters with different ones — replacing authorized user IDs with a different ID, changing ="false" to ="true" , altering the XML markup itself, etc.

Other non-authenticated encryption modes like CBC are malleable in less obvious ways, such that modifying the ciphertext will, as a side effect, typically garble at least some of the nearby plaintext in unpredictable ways.  However, it may still be possible to modify messages encrypted using these modes, if the attacker can arrange their modifications so that the garbled parts of the resulting plaintext will be ignored by the recipient (e.g. by wrapping them in an XML comment).

The point of all this is that, if you want your encryption to be secure against active attacks (i.e. attacks that may involve the attacker constructing their own messages, possibly by modifying intercepted ones), then you need some form of message integrity protection.  This can be achieved by applying a MAC on top of a traditional non-authenticated encryption mode, or by using an authenticated encryption mode that handles both confidentiality and integrity protection.  You could even achieve it e.g. by digitally signing all your messages with some public-key signature scheme.  But if you allow an attacker to actively send forged messages and don't have some way to detect it, they can do a lot more than just "sending a random stream of characters".


Why are stream ciphers based on linear-feedback shift registers so popular?

There were popular once upon a time;

They were very easy to implement in the hardware. Think about you only need latch and $\oplus$. For combining functions some $\wedge$ operation.
Their periodic properties are well studied, the minimal polynomial and characteristic polynomial etc. You can see a glimpse in the classical book of Solomon Golomb.
They are insecure, as Fgrieu said in comments. Single LFSR can be breakable by Berlekamp-Massay algorithm. You need only $2L$ keystream if the LFSR's length is $L$. Interestingly, this algorithm was invented for decoding the BCH codes.
Many people tried to use LFSRs to produce secure stream ciphers. To see the attacks on them look at the links.

Combining LFSRs with non-linear combiner broken by the novel attack of Siegenthaler
Irregular clocking as Alternating step generator
Shrinking Generator
Filtering the LFSR

Some recent (date back to 1999) algorithms based on LFSR

A5/1 and A5/2 used in GSM phones, E0 used in Bluetooth. If you look carefully on their usage you will see that there were a second design factor for this ciphers. That is; using smaller hardware. And, this reduces the power consumption.

Note 0: Definitions:

Shift Register : cascaded flip-flops that the out od each is connected to the next one's input. At each clock cycle, the data shifts one. As in 'C' code  x << 1
Linear-feedback shift register, LFSR is a shift register where the input is the linear combination of previous states.
Nonlinear-feedback shift register, NLFSR is a shift register where the input is the non-linear combination of previous states.

Note 1: The following from eSream project are using LFSR or NLFSR or both:

Trivium uses 3 NLFSRs.
Sosemanuk uses LFSR with a maximal period $2^{230}-1$
Grain uses both LFSR and NLFSR
MICKEY uses both LFSR and NLFSR

Note 2: They have other applications as @bmmo6 said in the comments.

Note 3: I barely remember a product advertisement in Cryptologia. They were claiming that they combined 5 LFSRs to generate a secure cipher.


Paillier: guessing the message when knowing the cipher and the random number

You don't need to guess, you can find $m$ for sure.

If you know $c,r,n,g$, then you can eliminate $r^n$ from the ciphertext and get $c'=g^m \bmod n^2$.

In $Z_{n^2}^*$, we have $(n+1)^x = 1+nx \bmod n^2$ ($x\in Z_n$). Therefore:

If $g=n+1$ is used, then $c'=g^m \bmod n^2 =1+mn$, then you can find $m=(c'-1)/n$.
If $g\ne n+1$, since the order of $g$ must be a multiple of $n$, we have $g= (1+n)^a=1+an \bmod n^2$ for some $a$, then we can find $a=(g-1)/n$. Then $c'=g^m \bmod n^2 =1+amn$, and we can compute $m=(c'-1)/an$.

Added based on Bruno's comment: the general forumula (for all $g$) is $m=(c'-1)/(g-1)$.


Yes, this is fine, at the record level.  (What you've built would be classified as a "Encrypt-then-Authenticate" scheme in the literature, and there are standard provable security results for such schemes.)  Well done on constructing a solid, well-engineered cryptographic scheme.

An AEAD mode would spare you from having to invent such a scheme, but what you've got is fine, and there's no reason why you need to change.

There's no reason to switch to a stream-cipher mode of operation.

As others have mentioned in the comments, this would be more secure if you included an identifier in the input to HMAC that identifies the table, row, and column where this appears, so that a ciphertext cannot be replayed from one position to another.  There will still be the risk of rollback attacks, as fgrieu explains; that is more challenging to defend against, so if you need to stop them, you might want to elaborate on the specific application situation.


Using Keccak permutation as a block cipher

First, this is a slightly silly exercise because most applications are not well-served by a block cipher in particular but rather by things built out of them, such as authenticated encryption schemes.  Probably the most widely used authenticated encryption scheme today built out of AES, AES-GCM, doesn't even use the inverse direction, and would provide better security bounds if AES were a pseudorandom function family rather than a pseudorandom permutation family.  And there are already perfectly good authenticated encryption schemes built out of Keccak, such as Ketje and Keyak, both submitted to CAESAR.

But let's take the exercise at face value and suppose you really do want a block cipher.  The obvious way to get a block cipher out of Keccak is with a single-key Even–Mansour construction analyzed by Dunkelman, Keller, and Shamir.  Specifically, for a $b$-bit permutation $F$ (standard SHA-3 has $b = 1600$, but there are shorter variants, such as $b = 200$ used by Ketje for environments with tight resource constraints), we can define, for $b$-bit keys $k$, the $b$-bit block cipher $$E_k(m) = F(m \oplus k) \oplus k.$$  Since collision-resistance is not relevant to this application, instead of the standard $\operatorname{Keccak-\mathit{f}}[b] = \operatorname{Keccak-\mathit{p}}[b, n_r]$ permutation where $n_r = 12 + 2\log_2 (b/25)$ is the standard number of rounds, we might consider a much smaller number $n_r$ of rounds, as you will find Ketje and Keyak use.

Maybe a 1600-bit key seems excessive for a standard 128-bit security level.  Maybe you could make do with a smaller key, padding it with zeros, $$E_k(m) = F(m \oplus (k \mathbin\Vert 0^{b - 256})) \oplus (k \mathbin\Vert 0^{b - 256}).$$  I haven't done the analysis of a padded-key variant of Even–Mansour; maybe if you read the Dunkelman, Keller, and Shamir paper you'll find an obvious answer.  But we can always derive longer keys from shorter keys using standard functions like HKDF, or even Keccak-based ones like SHAKE256 or KMAC.  So unless you have an amazingly constrained application requiring (a) squeezing out those last few cycles, and (b) a novel Keccak-based block cipher, those cycles are probably not worth the effort to figure out the detailed security analysis!  Thus I leave it as an extra-credit exercise for the reader which will not affect your standard grade.


Let's recall how discrete logarithms are solved in strong elliptic curve groups. The basic idea is to iteratively walk through many combinations of the form $x_i = a_iP + b_iQ$ until we find a distinguished one, i.e., one that shares some common property (like the lowest $k$ bits of $x_i$ set to 0). We accumulate enough distinguished points until we find a collision.

When we find two distinct pairs $(a_1, b_1)$, $(a_2, b_2)$ that evaluate to the same value $x_1 = x_2$, we recover the logarithm by finding $Q = dP = \frac{a_2 - a_1}{b_1 - b_2}P$, which follows from $a_1P + b_1Q$ $=$ $a_2P + b_2Q$. We expect this to happen after $\sqrt{\pi n / 2}$ elliptic curve group operations.

Since by the time we get to the second discrete log we already know the first one, we can reuse the distinguished points found during that log computation. This slightly increases the chances of finding a collision. Suppose we have a hit $a_1P + b_1Q_1$ $=$ $a_2P + b_2Q_2$, where $Q_1$ was the first discrete logarithm target, and $Q_2$ is the current one. Rewrite this as $(a_1 + b_1d_1)P$ $=$ $a_2P + b_2Q_2$, where $d_1$ is the first discrete logarithm. Now we have $d_2 = \frac{a_1 - a_2 + b_1d_1}{b_2}$.

This accelerates the second logarithm by a factor of $2$, the third one by a factor of $8/3$, and the $i$th one by a factor $\approx \sqrt{i}$ compared to if they were solved independently. So as you see, the benefits of precomputation exist, but are much more limited than in the number field sieve case.


How to simplify a the signing process in an elliptic curve signature scheme that involves a quadratic verification equation?

Is there a way to create a signature passing the above verification process that does not involve a square root in $\mathbb{F}_p$?

Well, one obvious thing to try is setting $R=0$ (the point at infinity); assuming the code doesn't have any protection against that (and the pseudocode doesn't), you compute $h = H_{c_2}(M || R_x || R_y )$ (where $R_x, R_y$ is whatever representation the point-at-infinity has), set $s=0$, and you're done...


If the primes $p$ and $q$ are:

appropriately chosen (see abstract of original paper here) and
large enough (use NFS factoring complexity to determine how large they should be)

then to distinguish non uniformity one basically has to factor $N=pq.$ However, as stated by @Maeher in the comments this holds only asymptotically.


Which is the correct duration of an AES execution?

The duration will depend on the chip and on the implementation.

In a good implementation, the duration of encryption is independent of the combination of the secret key and the message to encrypt (otherwise a so-called timing attack to gain knowledge on the key and/or the message is possible).

You need a model of the chip and its cache and the assembly code to do some real estimates (usually giving you a range of minimal and maximal cycles needed). For tight bounds there are commercial offers, e.g., by Absint. It is a feasible, but not a trivial task.


Are Edon-R 512 and Blue Midnight Wish 512 safe/recommendable?

Edon-R seems broken, in particular by Peter Novotney and Niels Ferguson's Detectable correlations in Edon-R and (in secret-prefix MAC mode) Gaëtan Leurent's Practical Key Recovery Attack against Secret-IV Edon-R. These attacks got no rebuttal (and attacks only get better; they never get worse); the design did not make it to the SHA-3 competition's second round; a project's archive appears unchanged since November 2008. I thus recommend against using Edon-R.

Blue Midnight Wish, in the variant that made it to the SHA-3 competition's second round (archive), is not broken as far as I can tell. The closest thing to an attack seems to be Gaëtan Leurent and Søren S. Thomsen's Practical Near-Collisions on the Compression Function of BMW (in proceedings of FSE 2011); but they admit that "it does not weaken the security of the iterated hash function" (that is, full BMW); and the rebuttal raises the argument that BMW's double-pipe construction should make it nontrivial to turn a partial collision for the compression function into an attack on the hash. I'd say that if speed was worth living dangerously and far from the mainstream, using Blue Midnight Wish (irrespective of size) could make some sense.

Here's how BMW's elimination from the final SHA-3 round (making BMW history) was justified:

  Although BMW has very good software performance, and good potentials for pipelining and area-efficient high-throughput values, a disadvantage of the algorithm is its irregular and not-well-understood design. Since the compression function of BMW does not have a conventional iterated-round structure, there appears to be no obviously simple way to adjust the security margin, or to trade performance for security. Moreover, the attacks on the algorithm, even after an extensive tweak, did not provide confidence in the security of the algorithm. For these reasons, BMW was not selected as a finalist.

Footnote: I second the recommendations in that other answer.


How does the challenger choose the message randomly in the one-wayness security game of PKE?

Generally in cryptography papers, if a distribution is not specified, either it's uniform, or the results are essentially determined by characteristics of the distribution like its min-entropy.*

In the Fujisaki–Okamoto paper, $\mathtt{MSPC}_k$ (corresponding to $\mathcal M_k$) could be taken to be a set of cardinality $2^{\operatorname{poly}(k)}$ sampled uniformly at random, or it could be a more generally distribution itself with min-entropy $H_\infty = \operatorname{poly}(k)$.  It's not clear from the paper but the results hold either way.
In the Galindo–Hasuo paper, the notation is explicitly defined as such in §2.

Obviously the upper bound on advantage is at least $2^{-H_\infty}$, or $1/\!\left|\mathcal M_k\right|$ in the uniform case.

It is true that OW-CPA (or ‘OW-Passive’ as some authors call it, because there's no oracle involved) does not imply IND-CPA—for example, the RSA trapdoor permutation $x \mapsto x^3 \bmod n$ has OW-CPA security but not IND-CPA security.  This is why, e.g., RSAES-OAEP exists: to shoehorn a message $m$ from some nonuniform distribution into a nearly uniform random ‘message representative’ $x$.

(A simpler generic approach, of course, is to choose $x$ uniformly at random and then use $H(x)$ as a secret key for a symmetric authenticated cipher, as RSA-KEM does, and as is the modern paradigm for new cryptosystems like the NIST PQC submissions; this is what the Fujisaki–Okamoto paper is about.)

* This is a rule for readers, not for authors.  Authors: Please say ‘uniform’ if that's what you mean!


Do well-known hash functions have any "impossible" output values?

No, it is not known that any cryptographic hash in common use has impossible output values (that is a bitstring of the appropriate size to be an output, but that is not reached by any input message). That's at least for MD5, the SHA(-1/-2) family of FIPS 180-4, SHA-3 of FIPS 202, RIPEMD-xxx, Blake/2, Tiger/2, Whirlpool.

In fact, it would be surprising that such impossible output value exists, and even more that it could be exhibited:

For a hash modeled as a random function, the probability that there is such value is lower than $1/2$ for a $n$-bit hash when there are more than $n\,2^n$ inputs; and that probability lowers with larger message input sets. See this for details.
For a Merkle-Damgård hash with Davies-Meier round function, the message block at most twice as large as the output, and the length padding at most about a quarter of the block size (like MD5 and direct larger successors are), under the assumption that the underlying block cipher is a Pseudo Random Permutation, and by an adaptation of the above reasoning, it is very probable that all outputs are reached with a single message block; and even more probable that they all are reached with two message blocks. Anything else seems to require a severe defect of the underlying block cipher, and any known such defect seems considerably lesser.
For the sponge construction of SHA-3, a similar argument can be made that a severe defect of the sponge function would be required to have some output values unreachable.


The generated private key is same for both client and server is it true?

No, that's not true. The key pairs and thus the private keys will be different. They will only be the same if the random number generator creates 521 identical bits for both the server and the client when the key pairs are generated.

  Client send its public key first or Server?

That doesn't matter, whatever is more efficient.

  The public key should be send plain or it should be signed?

Plain will do, if you perform authentication afterwards. TLS signs and verifies all the packets send, after the key agreement. You do need to check if the public key represents a valid point on the curve though.

  If signed then what will be the mechanism?

Depends on the protocol. Anything that can perform signing or MAC authentication really.

  I want to reuse my public/private key on server where I store that keys in application exe?

Whereever they are most secure. If you use them in software then for OpenSSL the PKCS#12 format probably makes the most sense. It doesn't matter if the PKCS#12 key store is stored as PEM or DER format.

Unless you need an ultra lightweight protocol using TLS itself makes an awful lot of sense. If you really must design your own protocol, then first learn and understand TLS.


Protect the original message of a hash from brute force

First of all, even the entropy is 50-bit, it is not easy to list all possible string to execute an attack on the data set.

Using hash function can hide the data itself due to pre-image resistance, however, the same data can have the same hash since the hash functions are deterministic. Therefore, it can reveal information, especially there is also side frequency information about the data. This is a modern frequency attack[*] and also applies the ECB block cipher mode [‡] of operation. Also, collisions in hash functions are inevitable due to the pigeonhole principle, to reduce the birthday attack probability use SHA3-512 so that the probability will be so small $\mathcal{O}(2^{256})$ for finding a collision with %50 probability. Of course in the adversaries advantage, 50% is too big. This is not a problem for 512-bit hash output, however, one must consider it in the other cases.

In the case that you have only 50-bit space (not 50-bit entropy), it is quite possible to build a rainbow table to attack your hash values, i.e. finding pre-images. If you consider that the bitcoin miner calculates $2^{67}$ double SHA-256 hash values in a second, then 50-bit space is quite accessible. The mitigation against the rainbow table attack (The rainbow tables are dead) is using salt, however, that you want to avoid.

You should use HMAC-SHA3 so that you will have a keyed hash that also provides unforgeability. Since HMAC requires a key, the attackers cannot find the original message or forge a new one, that we expect computationally infeasible. The rainbow table doesn't apply since the attackers don't know the key.

However, even with HMAC, frequency attack condition still applies if the same data occurs multiple times that can leak information. Meaningful possible mitigation is using salt that prevents you from directly comparing the values, or in another term separating the domains of the user.

In short, yes use HMAC-SHA3 or HMAC-Blake2.

update per comment:

  Can I assume the data be secure if the key is not leaked?

HMAC is not encryption, it is a keyed hash function for message authentication. The real security issue for message authentication is unforgeability. No, the attackers cannot find. Even if, they are able to find out out one to forge, it doesn't mean that they found your message, actually they need to find another one to forge because there is already one.

[*] Read from this question How can frequency analysis be applied to modern ciphers? or the below articles.

Inference Attacks on Property-Preserving Encrypted Databases, by Naveed et. al. Applied frequency attack on electronic medical records.
On the Difficulty of Securing Web Applications using CryptDB, by Akın and Sunar, example how to infer the data form Hospital records.

[‡] One might not even call it a block cipher mode of operation.


Homomorphic Evaluation of Pseudo Random Function

There is an Eurocrypt'15 paper published by Albrecht et al. which creates a cipher minimizing the number of multiplications needed to produce an encryption. This cipher is called LowMC and it can also be used as a PRF with almost same parameters as in the block-cipher - check out LowMC section in this paper.

Fortunately, there is open-source code which evaluates LowMC homomorphically with HElib. To evaluate the cipher homomorphically is to compute $\mathsf{Enc}_{\mathsf{k}}(\mathsf{LowMC}(x))$ from $\mathsf{Enc}_\mathsf{k}(x)$.

So you can plug in the PRF parameters given by Grassi et al. (for 128 bit PRF security) in the script provided by Albrecht and there you have it: LowMC becomes a PRF and your question is solved - compute $\mathsf{Enc}_\mathsf{k}(\mathsf{PRF}(x))$ from $\mathsf{Enc}_\mathsf{k}(x)$. And I think this is the state of the art for computing PRFs in HE land.


Is there any correlation in between two AES with a key differ only by one bit? (ECB mode)

This is called a related-key attack. There are many types of related-key attacks and the AES key schedule is vulnerable to some of them, but not the one you describe. From the linked answer:

The key owner can somehow be persuaded to compute three other keys $K_B$, $K_C$ and $K_D$, from $K_A$, using a specific derivation algorithm ($K_B$ is equal to $K_A$ XORed with a constant that the attacker chooses; $K_C$ and $K_D$ use a more complex but equally deterministic derivation algorithm).

There are some ciphers which would be vulnerable to such a trivial related-key attack as the one you describe. The TEA block cipher has equivalent keys. Each key has two others which select the same permutation. The RC4 stream cipher is even more vulnerable. When used multiple times with keys which differ by a small number of bits, it becomes possible to calculate the key.
Even though AES is not vulnerable to such a trivial related-key attack, it is still a good idea to re-key it with independent keys (e.g. by passing a master key through HKDF), for two primary reasons:

So the security of your scheme is not dependent on the particular cipher being used.
To protect from future attacks against AES' relatively simple key schedule.


LFSR: finding the period for an irreducible Polynomial

Actually the property you mention

  $p(x)$ of degree $n$ cannot be factored, and divides $x^k-1$ for the first time when $k=2^n-1$

means the polynomial $p(x)$ of degree $n$ is primitive. If $p(x)$ cannot be factored into a product of polynomials of lower degree then it is irreducible. It is enough to consider irreducible polynomials of lower degree (like prime numbers) as possible factors.

Therefore one could check whether $p(x)$ factors by methods similar to checking whether a number is prime. However, the following helps:

  For $i ≥ 1$ the polynomial $x^{2^i}-x \in \mathbf{F}_2[x]$
  is the product of all monic irreducible polynomials in $\mathbf{F}_2[x]$ whose degree divides $i$.

So, you could compute $x^{2^n}-x$ modulo $p(x)$ by the division algorithm and declare $p(x)$ irreducible if the answer is zero.


On the hardness of addition when the elements of a field is represented by the powers of generator and possible any existant scheme

The term used for the function $Z(\cdot)$ defined by
$$
g^{x}+g^{y}=g^{x}(1+g^{y-x})=g^x g^{Z(y-x)},
$$
in coding theory literature is Zech's logarithm. So for your formulation $$z=x+Z(y-x)=y+Z(x-y).$$
It is no more than the DL of $(1+g^{x-y})$ and is believed to be as hard as DL.
In coding theory it is normally considered for even characteristic groups $G=GF(2^m)^\ast$ in which case it is actually just the DL composed with a permutation $\pi$ of order 2 in the additive exponent group $\mathbb{Z}_{2^m-1}.$
I seem to recall Odlyzko mentioning it in a survey on DL in early 1990's. In any case, I don't know of it being directly used in cryptographic schemes, but others might.


Is using slow password hashing on the client side easier attackable than on the server side?

There exists something which is one step further than your idea. Look up SRP: this is a Password-Authenticated Key Exchange protocol; the two parties (client and server) who run the protocol end up with a newly generated shared key (which can be used to derive encryption and integrity-check keys), with mutual authentication with regards to a shared statically known secret which can be of relatively low entropy (say, a password).

In your system, this would mean that the password is first derived into the shared secret with something slow (bcrypt), and then use the result as the "password" in SRP. SRP has been designed so that the server stores only what amounts to a hash of the "password", not the password itself, so obtaining a copy of the server database does not allow an attacker to log in; it only makes him able to run an offline dictionary attack on the password, at which point the initial bcrypt hits him hard.

The beauty of PAKE protocols is that they are inherently immune to offline dictionary attacks from eavesdroppers: the protocol can be run "in the clear" and this still does not give a passive or even active attacker any way to learn enough to "try" passwords at his leisure. Only an attacker who hacks into the server may get such data, and even then he does not have the password (the password-derived-value-through-bcrypt, in the setup we envision here), just a hash thereof. So there is no need to establish a SSL/TLS tunnel beforehand. Even better, it is possible to use SRP as the initial handshake for a SSL/TLS tunnel; this is standard, and GnuTLS is an opensource implementation of that. A particular appeal of TLS-with-SRP is that client-server authentication is then mutual with regards to the password, which implies that there is no certificate whatsoever.

A possibly troublesome issue is that the number of iterations in bcrypt must be set so that it is slow (for the attacker) but still tolerable (on whatever machine bcrypt is to be executed). If you want bcrypt to run on the client, and also accommodate a variety of clients, some of which being possibly quite anemic (e.g. a 3 years old netbook, like mine: old mono-core Atom clocked at 800 MHz; also think about smartphones), then you have to tune the bcrypt iteration count accordingly. The patience of the average user being, let's say, somewhat limited, this prevents you from setting a bcrypt iteration count as high as you would like. On the other hand, you can muster 100% of the client CPU resources for that (client might be multitasking, but the user is unitask), which probably compensates much of that effect.

Summary: use bcrypt on the client, then use the result as "password" in TLS-with-SRP.


what kind of hash function can provide a short hash and be collision resistant?

Answer's plan:

re-stating the problem;
explaining its conventional solution, using a hash published in hexadecimal, usually of 32 to 64 characters;
explaining a better (perhaps novel) solution, combining two established cryptographic primitives (a hash and a function originally designed for Password Based Key Derivation), plus a slightly better formatting than hexadecimal, giving a 16-character cryptogram with security comparable to existing practice.

I take the question as: how short can a cryptogram be when used to verify integrity of some data, in the common situation where:

we trust the party that computes the cryptogram from the original data;
an adversary knows everything we or the trusted party knows;
we trust the channel by which we obtain the cryptogram;
an adversary is assumed to be able to alter the data in transit;
perhaps: we trust that the adversary could not inject anything in the original data in order to facilitate later alteration.

The traditional approach to that problem is to have the trusted party hash the data, and publish the hash in hexadecimal. For 128-bit security (that is, resisting an adversary able to perform about $2^{128}$ hash operations), if we do NOT assume 5, it is used a 256-bit (64 hex characters) collision-resistant and (second-)preimage-resistant hash.

One temptation is to just assume 5. Then, we no longer need a collision-resistant hash, and can use a 128-bit hash (or a 256-bit hash truncated to 128 bits). However, that would be unwise in some circumstances. For example, in the distribution of some software, the adversary could be introduced enough in the development team to plant an innocent-looking file, say aardvark.c. With a 128-bit Merkle–Damgård hash, and assuming the adversary knows every bit of data before aardvark.c in the archive of the distribution, she can craft that aardvark.c and a completely different version thereof such that substitution will leave the overall hash of the archive unchanged, with effort comparable to $2^{64}$ hashes; which is a lot of effort, but feasible. Notice that using a 256-bit hash truncated to 128 bits fools that aardvark attack, but not one where the adversary knows all the data except the final zymurgy.c that she injects. This is why standard (and good) security advice is to use a full 256-bit hash.

Can we have a shorter cryptogram without giving-up security? YES!!

I propose to:

hash the data using a traditional hash;
transform that hash into a shorter cryptogram using a random-like function that is purposely slow and costly to compute, similar in design to those used for the purpose of key stretching;
express that hash into a slightly more human-engineered form than hexadecimal.

We could use SHA-256 as the hash; Scrypt with the hash as the P/key/password input, a version identifier "1" as the S/salt input, a 10-byte output, other parameters (to be determined) so as to require 4 seconds of computation on a Raspberry Pi model A, but allow parallelization on a system with 16 cores and 16 times as much available memory; and format the 80-bit output as a 16-characters cryptogram using base-32 encoding with the 23456789ABCDEFGHJKLMNPQRSTUVWXYZ characters.

Assuming 5, an attack is expected to require computing power equivalent to $2^{81}$ seconds of the CPU time of our Raspberry Pi, which is perhaps $2^{100}$ hashes on that hardware (assuming 0.5 million hashes/second), and cost equivalent to $2^{116}$ hashes on dedicated hardware (assumed to beat the BCM2835 CPU of the Raspberry Pi by a factor of $2^{16}$ in price/performance ratio when hashing, thanks to massive parallelization and not having to pay the price of a fair fraction of 256 MB of RAM per instance). Thus we have arguably 101 and perhaps up to 117 bits of security for the size of 80, at the cost of 4 seconds of extra computation per use (or less on more capable hardware).

Without assuming 5, a practical attack is possible with in-advance knowledge of the original data (except for the malleable portion), and computing power equivalent to about $2^{43}$ seconds of the CPU time of our Raspberry Pi (which allows computing cryptograms for $2^{40}$ acceptable and $2^{40}$ rogue versions of the data, among which an exploitable collision has a fair probability); with the same hypothesis as above we have arguably 62 and perhaps up to 78 bits of security. Notice that in-advance knowledge of the original data is a very hard requirement for an adversary, and each unknown bit makes the attack twice as unlikely to succeed.

Addition: A quick search did not locate an earlier suggestion of using a deliberately slow transformation in order to shorten a hash while keeping a good fraction of its security. If I am in a position to name the technique, let that be a condensate, obtained by hash condensation.


KDFs for symmetric encryption master key & serial number

Any standard key derivation function should do.

There are, in general terms, two kinds of KDFs: those that are meant for deriving keys from (potentially) low-entropy passwords, and are thus designed to be deliberately slow (key stretching), and those that are meant for deriving keys from a high-entropy master key / secret, and so can be made much faster.  Your use case falls into the latter category.

One example of a non-key-stretching KDF you could use is HKDF, a nice and versatile KDF based on a cryptographic hash function (used in the HMAC construction).  HKDF is an "extract and expand" KDF, where the output keys are derived in two steps:

in the extraction phase, the master key and an optional non-secret "salt" are used to derive an intermediate "pseudorandom key" (PRK), whose size is determined by the output length of the hash function used; and
in the expansion phase, the pseudorandom key computed in the extraction phase is combined with an optional "info" string to derive one or more output keys of arbitrary length.

In situations (like yours) where the master key is already a uniformly random bitstring, the HKDF standard allows the extraction phase to be skipped, and the master key to be used directly as the pseudorandom key.  Thus, you could simply skip the HKDF extraction phase, and use the device ID as (one part of) the "info" parameter to HKDF-Expand.

Alternatively, e.g. if you wish to derive multiple keys for each device (say, an encryption key and a message authentication key), you could use the device ID as the non-secret "salt" in the HKDF-Extract stage to obtain a device-specific PRK, and then derive the actual device keys from this PRK using HKDF-Expand.

HKDF requires you to choose an underlying hash function to use.  Basically any secure cryptographic hash would do, but Richie Frame's suggestion to use SHA-512 seems fine to me, and at least ensures that the size of the PRK will not be a security bottleneck.

Finally, let me briefly note that the general extract-and-expand construction use in HKDF could also be instantiated with some pseudorandom function other than HMAC; some possible variants are mentioned in the HKDF paper (Krawczyk, 2010).


block cipher algorithms with variable block lengths

Rijndael-128, Rijndael-192 and Rijndael-256 are actually 3 different variants of block cipher that are very similar.

Simon, Speck, Threefish and RC5 also define different block size variants in similar way. Rijndael is not unique in this regard.

Block cipher that really has variable block length is XXTEA as its block length is not limited.


How to create an EC point from a plaintext message for encryption

The standard approach for this goes as follows, which I think is usually attributed to this paper by Koblitz:

Suppose you have a curve over an $k$-bit prime field. Also suppose you want to encode a fixed-length $k-1-\ell$ bit message - the one bit is subtracted to not having to mess with non-power-of-two field sizes. Then iteratively execute the following:

Compute $x=m\mathbin\|0^\ell$
Compute $x'=x^3+ax+b\bmod q$ for the curve's parameters $(a,b)$ and the field prime $q$.
If $x'$ is a quadratic residue, compute $y=\sqrt x\bmod q$ and return $(x,y)$ else increment the last $\ell$-bit of $x$ by 1 and try steps 2 and 3 again. If these fail $2^{\ell}$ times abort with "non-encodable"

Decoding simply ignores the $y$-coordinate and strips away the last $\ell$ bits of the received point.

This should work because the set of quadratic residues modulo a prime has size roughly $q/2$ and so you have roughly a $1/2$ chance of any given $x'$ working and given that you try $2^\ell$ values, you have a chance of $2^{-\ell}$ of none of them working.


Rivest's ring signatures with hashes instead of symmetric encryption

There are two immediate implications.

Now, does it break in practical terms?  Not obviously, but our confidence in the security of the ring signature scheme cannot be understood entirely by studying the security of the underlying ordinary signature scheme—there may be an attack against the ring signature scheme even if the underlying ordinary signature scheme is secure, so there are more targets for cryptanalysis, meaning you can't save work by focusing on one primitive.

The two implications are for two different security properties:

Anonymity of the signer.

The Rivest–Shamir–Tauman scheme guarantees the anonymity of the signer even against an adversary of unbounded computational capacity without even relying on $h$ to be a random oracle.  The proof of this depends on the invertibility of everything involved so that there's a pigeon in every hole and exactly one pigeon to each hole: for every $k$ and $v$, there are exactly $(2^b)^{r - 1}$ possible values of $(y_1, y_2, \dots, y_r)$ satisfying the ring signature equation, all equiprobable if the $x_i$ are drawn uniformly at random.

If you replace the PRP $E_k$ by a PRF $H_k$, then this proof no longer holes: the distribution on solutions may be nonuniform.  Is it so nonuniform you could unmask the dirty traitor and prosecute them under the Espionage Act and pillory them on Fox News?  Maybe, maybe not (although you could doubtless find someone else to pillory on Fox News, such as a nonbinary vulture just trying to use the bathroom, and ratings would go up just the same).
Reduction of security of ring signatures to security of underlying ordinary signatures against forgery.

The proof demonstrates how to build an algorithm to forge ordinary signatures given an algorithm to forge ring signatures.  The algorithm again relies on the reversibility of the encryption function, but it's got more details than I can fit in this feathery head today, so I can't say whether you could adapt the reduction (maybe with a wider tightness gap) to work with the hashing version.

Of course, as you may have observed, $2^b$ must be larger than all the moduli, and there aren't all that many 2048-bit block ciphers lying around.  (1024-bit, yes: Threefish.  But you also don't want to rely on RSA-1024.)  So in practical terms, you don't want to use this scheme anyway!  Fortunately, there is a pretty substantial literature on ring signature schemes in the past fifteen years since the RST paper came out.  I leave it as an exercise for the reader to study newer developments in ring signatures.


Non-trivial examples of a system being a zero-knowledge proof system but not zero-knowledge proof of knowledge

At first, every ZKPoK protocol is ZKP protocol. This is obvious: if you proved that you know a witness, therefore a witness exists, therefore the statement belongs to the language.

The interesting question is whether a protocol exists which is ZKP but not ZKPoK.
It holds for trivial languages, but you're justly not satisfied with this.
My idea in a discrete log settings, similar to Schnorr protocol, is the following:
 take a protocol proving the equality of the discrete logarithms of $y_1$, $y_2$ to
bases $g, h \in G$,
i.e. for a language $\{ g||h||y_1||y_2 : \exists w, y_1 = g^w \land y_2 = h^w  \}$,
where $w\in Z_q$ is a witness. $G$ is cyclic group here.

The classical Schnorr-like protocol for that is the following:

Prover chooses $k\in Z_q$, calculates $C_1=g^k, C_2=h^k$ and sends $C_2, C_2$ to Verifier.
Verifier chooses $e\in Z_k$ and sends it to Prover.
Prover calculates $r = k + ew$ and sends it to Verifier.
Verifier checks: $C_1 y_1^e = g^r$ and $C_2 y_2^e = h^r$.

You can easily build knowledge extractor E which will extract $w$ (just the same as in Schnorr protocol), so this is clearly ZKPoK protocol for a language $L_1 = \{ g||h||y_1||y_2 : \exists w, y_1 = g^w \land y_2 = h^w  \}$.

But, notice that this is also a ZKP for a language $L_2 = \{ g||h||y_1||y_2 : \exists v, h = g^v \land y_2 = y_1^v \}$.
The language is actually the same ($L_1 = L_2 = L$), but it's defined through another witnesses.
And knowing a witness $w$ doesn't help you to find witness $v$.
So, this protocol is not a ZKPoK for $L_2$, while it's ZKP for it.

The trick we did here is in the following. We have a language which could be
independently defined by two types of witnesses. You can use say the witness of the first type to provide a proof, but you could not know the witness of the second type. You can say that it's just a trick and this protocol is still a ZKPoK, just for another type of witness. You're right, but this trick is inevitable: if a prover can provide a proof, and the language is not trivial,
the prover necessarily knows something special (otherwise, anybody can conduct such proofs for himself, and language becomes trivial! ).
And this special thing is a witness! But, this could be another type of witness,
not that one which you initially supposed. This is a core idea of the trick.

WARNING: this is an improvisation and I'm not 100% sure in this, so please wait for endorsement of other people.


Can Key-Encryption Key (KEK) be symmetric?

Yes, and Key-Encryption Keys often are symmetric. When they are, they do not bring the benefits of asymmetric cryptography; in particular, anyone with the KEK and passively eavesdropped ciphertext can decrypt the distributed keys. That does not make use of symmetric KEK pointless:

KEK would typically be distributed, stored and used with more precautions (procedural checks, maximum volume encrypted..) than the keys they encipher. Therefore, even if compromise of one of the distributed key was likely (e.g. because some attack has a low probability to recover a distributed key, and many keys are distributed), that won't compromise the other distributed keys or the material they protect, thanks to the key distribution under KEK.
KEK can be long-lived (year) when the keys it enciphers can be short-lived (day). Therefore, the serious inconvenience of secure distribution of the KEK (e.g. by trusted courier) needs to occur only seldom, and other keys can be distributed electronically, and frequently. Frequent change of keys not only reduces the impact of a key leak (see above), it might drastically reduce it's probability to occur (e.g. in attack scenarios that requires many uses of a given key to succeed).


Advantages of Montgomery Ladder-based Scalar Multiplication

Synthetically, the advantages of the Montgomery ladder are that it is simple and fast.

If you look at X25519, the Diffie-Hellman algorithm applied to Curve25519 and described in RFC 7748, you will see that for an n-bit Montgomery curve, multiplying a point with an n-bit scalar, you will need to compute about 10n multiplications of field elements. In more details, there are n iterations of a loop, each of them implying:

4 multiplications with two varying field element values
4 squarings
1 multiplication with a fixed and usually small constant (called a24 in the RFC)
1 multiplication with the base point "u" coordinate (fixed throughout the algorithm, but may vary between invocations)

To that, a final field inversion must be added, which is normally done with a modular exponentiation. If the field modulus is well chosen, that inversion will add a bit more than n squarings. So the value of "10" given above is an estimate that depends on how squarings and multiplications by constants can be optimised; in practice, overall cost will be between 8n and 12n.

Now, with "classic" curves with Weierstraß equation y2 = x3 - 3x + b (for some constant b), the usual implementation method is to use Jacobian coordinates, in which a point (x, y) is represented by the triplet (X, Y, Z), with:

x = X / Z2
y = Y / Z3

With that representation, a point doubling costs 8 multiplications (4 of them are squarings), while a point addition which is not a doubling uses 16 multiplications (4 of which being squarings). A basic double-and-add algorithm would then need an average of 16 multiplications per multiplier bit, but in fact 24 if you want a constant-time implementation (which is recommended), therefore not leaking information about which scalar bits are 0 and which are 1. An extra n multiplications in total are to be added, for the final inversion of Z to get back to affine coordinates (there again, classically with a modular exponentiation).

Things can be sped up with a window optimisation in which, for base point P, you precompute small multiples of P; for instance, with a 5-bit window, you compute kP for all k from 0 to 31 (which involves 15 doublings and 15 point additions), and then you only make one point addition every five doublings. This requires some extra implementation care (for instance doing a constant-time lookup in the window, if constant-time execution is sought) but can bring down overall cost to about 13n field multiplications, i.e. 30% more than for a Montgomery curve. Some further speedups are possible when the base point is known in advance, as is the case for the first half of Diffie-Hellman (using the conventional base curve), because the addition formulas in projective coordinates when one of the point has Z = 1 (called "mixed additions") are a bit simpler (11 multiplications instead of 16).

So, in practice, Montgomery curves get a speed advantage, but not really because they are Montgomery curves:

As shown above, the advantage is slight (about 30%). It must be said, though, that implementation of Montgomery curves is much easier and it shows up as smaller code and less room for tricky bugs.
A much bigger speedup of Curve25519 over NIST curve P-256 comes from the definition of the base field. NIST P-256 uses integers modulo p = 2256 - 2224 + 2192 + 296 - 1. Curve25519 uses p = 2255 - 19. Both are integers chosen because they allow for faster modular reduction; however, NIST's choice is optimised for computer hardware of the late 1980s, while Curve25519 shoots at mid-2000s hardware, with much cheaper multiplication opcodes, and superscalar architectures. On modern hardware (and this includes modern "small" embedded CPU), the latter choice seems to be roughly twice faster than NIST's modulus.
An extra interesting feature of Curve25519 is that it is not one curve, but two curves. Every possible source value for the "u" coordinate will define either a point on the curve, or on the "twisted" curve, which is also cryptographically good (its order is a big prime multiplied by a very small cofactor). This allows X25519 to be safe without performing any validation of the incoming point, which again makes for simpler and shorter code. There again, that feature is not intrinsic to Montgomery curves; classic curves in short Weierstraß form can exhibit the same property, but the NIST curve does not.
Conversely, there is a complication that comes from Montgomery curves, which is that their order is necessarily a multiple of 8; hence, it cannot be prime. This means that a valid curve point is not necessarily a point on the prime-order subgroup on which we perform most operations. The X25519 specification accommodates that issue by forcing scalars to be multiple of 8. When Curve25519 (or its derivative edwards25519) is used in other, more complex cryptographic protocols, this property can be problematic and must be side-stepped appropriately (usually by the same methods of multiplying things by 8 or forcing multipliers to be multiple of 8). In a way, this is a trade-off: implementation is more simple, but at the expense of a bit of extra complexity in the protocols.

To summarise: the Montgomery ladder makes for a somewhat faster algorithm which is easier to implement, especially if you aim for constant-time code. But modern standard curves, that are Montgomery curves, also come with a few extra features that are quite nice to have, and yield even greater speedups; these extra features are not reserved to Montgomery curves, but NIST curves don't offer them because they had not been invented or at least noticed at that time.

As an historical note: Montgomery curves were first invented and used for the elliptic curve factorization method in which raw speed is of paramount importance, but the curves themselves don't have any actual cryptographic relevance.


As a hint, suppose we pick a random $h$, and compute $g = h^3 \bmod N$.  We then find the minimal value $x$ where $g^x \equiv h \pmod{N}$ (and, yes, such an $x$ will exist, assuming $p, q > 7$).

What can we deduce from such a value of $x$?


Is generating public key inevitably slow in classic Diffie-Hellman if the private key is large?

If $g$ is not in the order-$q$ subgroup, then one can easily calculate the last bit of $x$ from $g^{\hspace{.01 in}x}$.
-
If $\: g=2 \:$ or $\: g=4 \:$ then you can very easily compute small powers of $g$.

You could have a large lookup table for powers of $g$.

For example, you could store $\:g^{\hspace{.01 in}2^{\hspace{.01 in}2\cdot m}}\hspace{-0.02 in},g^{\hspace{.01 in}2^{\hspace{.01 in}(2\cdot m)+1}}\hspace{-0.02 in},g^{\hspace{.01 in}2^{\hspace{.01 in}2\cdot m}+2^{\hspace{.01 in}(2\cdot m)+1}}\:$ for each relevant value of $m$.

However, such a lookup table would make the benefit from

three sentences before this sentence mostly redundant.

You could choose $x$ so that there is a relatively short addition chain from $1$

(and any powers you have stored in a lookup table) to $x$, although this idea may well be vulnerable

to attacks that are similar to attacks on RSA private exponents with low Hamming weight.
-
You do that as long as $g$ is in the order-$q$ subgroup. $\:$ If, for whatever reason, you choose a

$g$ that is not in the order-$q$ subgroup, then you select some $\:(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}n)\hspace{-0.02 in}+\hspace{-0.03 in}1\:$ bit value for $x$ instead.


Security of a sha-256 based stream xor cipher?

The stream cipher part is cryptographically fine given a uniform random key and a unique nonce per message, since SHA-256 shows no evidence of failing preimage resistance, but it's stupidly slow because SHA-256 is designed for the much more expensive collision resistance.  There's no reason to prefer it over, for example, XSalsa20.

The password-based key derivation function is problematic if you ever use passwords chosen by a process with entropy much below 128 bits, like most people do, because the cost to the adversary of testing a guess for the password is negligible.  You should use a modern password-based key derivation function like scrypt or argon2 to derive the key.

Overall, when you're composing things like this, you should be concerned more with what you're actually trying to protect here.  Don't mess with inventing your own stream cipher—that's a solved problem.  To do this you need to articulate what you're trying to do in your application with what resources, how the adversary can manipulate those resources, and what you want to make sure the adversary can't do in spite of that.  Then you can decide how to use crypto to prevent the adversary's shenanigans—and you'll almost certainly need some authentication in there beyond encryption.


The security of Hidden Field Equations - sentence

Random oracles are used in cryptographic proofs as a way to abstract away a complex function, making the analysis easier (ie "ignore the actual function, and model it as a random oracle instead").

In the paragraphs before the sentence you highlighted, they propose to measure the "complexity" of an equation / function by the degree of its multivariate polynomial representation over $GF(2)$.

In the context of the surrounding paragraphs, I would interpret that sentence to mean

  The random oracle paradigm abstracts away the complexity of the function, which renders our complexity metric useless.


How many of primitive point on the elliptic curve?

In a group of size $n$ (e.g. an elliptic curve), the order of a subgroup generated by a group element necessarily divides $n$. We usually choose curves so that their order $n$ is prime; in that case, the order of a point must be either $1$ (the point is the "point at infinity") or $n$ (all other points). Thus, if $n$ is prime, then every non-zero point is necessarily a generator for the whole curve.

In general, if $n$ is not prime but you know its factorization, then you can test whether a point $P$ generates the whole curve in the following way: for every prime $k$ that divides $n$, compute $(n/k)P$. If none of these points is zero, then $P$ generates the whole curve.

(All of this applies to every finite group, not just elliptic curves.)


Use of shared secret "other" than key creation

Shared secrets can also be used for authentication. He who knows the shared secret, is trusted.
For instance, this is used in IoT scenarios, where nodes communicate via DTLS and use the secret as a PSK instead of a certificate and a keypair.

Of course, this only makes sense if the shared secret has been preshared or calculated via some algorithm. The result of an online key agreement like DH cannot be used for that.


Would it be secure to use SHA-3 (or SHAKE) to hash the key, and then distribute the hash as the public ID for the secret key?

Sure; SHA-3 and SHAKE are effective uninvertable.  Now, I suppose someone could try various AES keys and see which hashes to the public identity; on the other hand, they could try various AES keys and see which one decrypts the ciphertext properly. We believe that the second is infeasible, and so the first (which requires no less effort) is also infeasible.

  Is there an advantage or disadvantage to using a larger or shorter hash length relative to the key length?

The only disadvantage to using a shorting hash length is that it increases the probability that two different keys that you actually use will end up with the same public identifier (hash).


Does the prime modulus have to be bigger that the generator?

I suppose there is really no requirement to have $a <b$. But then again, if you are using an $a>b$ why not reduce it modulo $b$ and save space?


Do I need to know the curve for ECIES decryption?

This awfully looks like homework, but hey, here we go. Each curve has an order, which is the number of points on the curve (specifically, the number of points into a subgroup of prime order of the curve, but in the case of the Brainpool curves, the subgroup is the whole curve). A private key is a non-zero integer modulo the curve order; i.e. if the order is $n$, then the private key is a number between $1$ and $n-1$. In practice, the size of the private key, expressed in bits, will be close to the size of $n$ (the size in bits of an integer $x$ is the integer $k$ such that $2^{k-1} \leq x \lt 2^k$).

Curves brainpoolP256r1, brainpoolP320r1, brainpoolP384r1 and brainpoolP512r1 have orders of size 256, 320, 384 and 512 bits, respectively. Thus, look at the size of your private key; this should allow you to infer which curves you are talking about.

(Technically, a 255-bit integer, for instance, could be a valid private key for all four curves, since it would be in the accepted range for all four curves; however, probability that a private key, chosen uniformly in the range for brainpoolP320r1, ends up being a 255-bit integer, while it had a whole 320-bit range to chose from, is less than $2^{-35}$, so it won't happen often. In that sense, your answer won't be absolutely guaranteed to be correct in a mathematical sense, but it can be a good guess nonetheless.)


Is there any encryption system where the sender cannot prove that a specific ciphertext belongs to a specific plaintext

Deniable encryption should provide what you want. In a deniable encryption scheme, in addition to the usual $(\mathsf{KeyGen},\mathsf{Encrypt},\mathsf{Decrypt})$ algorithm, you have an algorithm $\mathsf{Explain}$ that takes as input a ciphertext $c$ (which can be any ciphertext) and a message $m$, and outputs a random coin $r$ such that the triple $(m,r,c)$ is indistinguishable from the distribution obtained, given $m$, by sampling a uniformly random coin $r$ and constructing $c$ as $\mathsf{Encrypt}(m;r)$. That is, even though a ciphertext can be correctly decrypted given the secret key, for any plaintext you can find a random coin which "explains" the ciphertext as an encryption of this plaintext.

Given a deniable encryption scheme, a proof that you correctly encrypted a message can never be convincing, because you can always, for any ciphertext $c$ and plaintext $m$, find coins $r$ such that $c = \mathsf{Encrypt}(m;r)$ - and that does not mean that $c$ will necessarily decrypt to $m$. Hence, in such a scheme, if you only know the public key, it is fundamentally infeasible to prove that you encrypted a given message (if you know the secret key, it's a different matter, but that does not seem to be the case in your question).

Note that your requirement 2 can be achieved using any standard authentication mechanism on top of deniable encryption.

Deniable encryption was first constructed in this paper, but this is only of theoretical interest, and does not lead to any efficient instantiation in practice. There exists alternative constructions (see also the many follow ups) that only achieve an inverse-polynomial "deniability", in the sense that it is possible to distinguish "true random coins" from those obtained through $\mathsf{Explain}$ with inverse polynomial probability.


Implementing a one-time pad without binary?

Actually, one-time pad can be implemented on the basis of any finite group operation; with these requirements:

The pad must consist of random group members; that is, each element in this pad must have equal probability of being any specific group member, and there must not be any correlation between different entries within the pad.
The encrypt and the decrypt processes are slightly different; if $\oplus$ is the group operation, $P_i, C_i$ is the i-th group element of the plaintext and ciphertext, $K_i$ is the i-th element of the pad, and $Inverse(x)$ is the group inverse of the element $x$, then the encrypt process is:

$$C_i = P_i \oplus K_i$$

while the decrypt process is:

$$P_i = C_i \oplus Inverse( K_i )$$

Now, when we work in the xor group, the inverse operation is actually the identity (because each element is its own inverse), hence we usually don't explicitly call this detail out.  However when we work in other groups, this distinction becomes important.

As long as the above is followed, the standard security proof for one-time-pads applies.


The number 24 has the curious property that, for any prime $p > 3$, $p^2 - 1$ is divisible by 24.  (In fact, this holds for any odd number $p$ not divisible by 3.)

This follows simply from the fact that $p^2 - 1 = (p-1)(p+1)$; since $p$ is not divisible by either 2 or 3,

the factors $p-1$ and $p+1$ must both be even,
one of them must be divisible by 4, and
one of them must be divisible by 3.

Thus, their product must be divisible by $2\cdot4\cdot3 = 24$.