Is a keyed MAC sufficient for integrity protection?

My question is, does message 3 from client > host need to be encrypted for integrity protection?

Encryption doesn't provide integrity protection at all. Authenticated encryption may provide such protection, but it would provide the same security as the MAC, which is already performed.

  My instinct is no it doesn't, and using a keyed MAC is sufficient, because encryption does not guarantee integrity protection.

You are correct.

However, you are also sending a biometric template unencrypted. This will leak information about the person's biometrics, and may compromise the entity authentication of the system. It is unclear from the question what use the template is to an attacker, but generally just sending out biometric data from a person is not secure in any form.

Leaking biometric data is morally wrong. If you send out biometric data without preserving confidentiality then you may be in violation of various laws and privacy regulations even at the UN-level. Note that even if the template doesn't directly spill biometric information of a person, maybe it can be used for others to perform entity authentication.

In short: you are in violation of the integrity of the person you are trying to protect (if you don't encrypt) rather than violating the integrity of the message; that is indeed covered by the MAC.


With RSA-KEM,* the sender knows a modulus $n$ and a public exponent $e$, and the receiver knows the private exponent $d \equiv e^{-1} \pmod{\phi(n)}$.  To send a message $m$, the sender picks $0 \leq x < n$ uniformly at random, derives $k = H(x)$ for some hash function $H$, computes $y = x^e \bmod n$, and transmits $y$ alongside the authenticated ciphertext $c$ (e.g., AES-GCM) of $m$ under the key $k$.  The receiver recovers $x = y^d \bmod n$, recomputes $k = H(x)$, and recovers $m$ from $c$ using the key $k$.

This protocol is non-interactive in the sense that the sender can package up $(y, c)$ and send it off to the receiver.  There's no authentication of the sender built into the protocol; if you want the receiver to be able to verify which sender sent it, the sender could sign the message $(n, e, y, c)$ giving a signature $s$, and transmit $(y, c, s)$.†

However, like ECIES-KEM, this protocol does not provide a static shared secret between the sender and receiver using their long-term key pairs.  In contrast, in Diffie and Hellman's seminal 1976 public-key cryptosystem, Alice publishes $g^a$ in the telephone book, Bob publishes $g^b$ in the telephone book, and their static shared secret is $g^{ab}$.

This protocol also doesn't provide is deniability—the signature $s$ can be verified by a third party.  In contrast, the Diffie–Hellman public-key cryptosystem does provide deniability because any authenticated ciphertext sent between Alice and Bob under a key derived from their static shared secret $g^{ab}$ could have been created by Alice or Bob: in a symmetric cryptosystem, the power to verify is also the power to forge.

* I would say that this is the RSA analogue of ECIES-KEM, but if anything, I would guess that ECIES-KEM as a concept came after and in response to RSA-KEM as a concept!

† Signing the recipient's key $n$ and $e$ in addition to the ciphertext thwarts Don Davis's misattribution attack on PGP and S/MIME.  If you use the signing key for multiple purposes or contexts, you should make sure to identify the purpose as part of the message you are signing so that a signature used for one purpose can't be abused for an unintended other purpose.  This is sometimes called ‘domain separation’.


Man-in-the-middle attack on text-book RSA PKE

I see four ways how to attack this scheme

1) RSA malleability
Suggested in comments

2) If $e=3$ then
Trivial attack exists. Hint: What is the minimal possible size of $N$?

3) If the attack is active(MiTM)
Cheaper attack exists. Hint: Treat the task as a set of Oracles:

$Oracle0: n \mapsto E(n)$ - If you know $(e,N)$, you can encrypt any $n$.
$Oracle1: \epsilon \mapsto E(R_1)$
$Oracle2: E(n) \mapsto E(R_2*2^{28}+n)$
$Oracle3: E(n) \mapsto E(n*2^{156}+R_3)$ - Are you sure?

4) You treat it as a blackbox
Your solution


The following papers constructs linearly homomorphic signature schemes.

Pairing based signatures:

https://eprint.iacr.org/2006/025.pdf
https://crypto.stanford.edu/~dabo/papers/netcode.pdf

Lattice-based signatures:

https://eprint.iacr.org/2010/453.pdf


Is an elliptic curve over $\mathbb{F}_p$ order preserving for the points $(x,y) \in \mathbb{Z}_p$?

The question as currently stated is true if we assume the equation takes place in $\mathbb{Z}$, since all the values are small integers.

Proof: If $x<x'$, then $x^3<(x')^3$ and $ax<ax'$, so
$$
E(x)= x^3 +ax+b < (x')^3 +ax'+b = E(x')
$$

The problem with trying to answer the more general issue you appear to be considering is working out what it means to say $x<y$ for $x,y\in\mathbb{F}_p$. There isn't a reasonable ordering on elements of a finite field, or indeed on $\mathbb{Z}/p\mathbb{Z}$.  Intuitively, one might wish that $x<y$ if and only if $x<y$ when considered as integers. However, this doesn't work because there is no mapping that will respect the required properties. Consider the following [attempt] at defining this:

  For any $x\in\mathbb{Z}$, let $\bar{x}$ denote the image of $x$ under the projection into $\mathbb{F_p}$. Then,[try to] define an ordering $\prec$ on $\mathbb{F}_p$ by $\bar{x}\prec\bar{y}\iff x<y$.

The biggest problem with this is that it isn't even well defined. For example, let $a,b\in\mathbb{F}_7$, with $a=\bar{3}$ and $b=\bar{6}$. Then since $3<6$ we deduce $a\prec b$, but since $a=\bar{3}=\bar{10}$ we must also have $b\prec a$ (since $6<10$). This would imply $a=b$, which is clearly false.

For more information, this wikipedia page might help.


It is simply a parameter for indicating the length of the keystream in bits. Internally, EEA2 will call AES the appropriate number of times to produce that much output, truncating the last block as needed. It is not mixed into AES inputs or the key, so like you said it has no effect on the output bits themselves, beyond choosing how many are taken.


128 bit hash with least chance of collision?

The two proposals in the question have their advantages and disadvantages.

Using MD5
There are three major types of attacks to worry about.

Preimage attacks: given $h$ find $m$ such that $H(m)=h$
Second preimage attacks: given $m$ find $m'\neq m$ such that $H(m)=H(m')$
Collision resistance: find any $m$ and $m'$ such that $H(m)=H(m')$

MD5 is broken with respect to collision resistance. So, what could an attacker do if you use MD5. They could submit two documents that they created which has the same hash value. Since the attacker would have to create both documents, no private information will be leaked. To learn private information, they'd have to break #1.

MD5's preimage resistance is academically broken. It has not been broken, however, in a practical sense.

Truncated SHA
Since NIST has a truncated mode for SHA-512/256 and SHA-512/224. This should give some credibility to the idea. The link talks about some potential attacks, but all are purely academic at this point.

Now, they do suggest using a unique IV for each truncated length. This is to fix "Issue #1" on slide 7. This issue is very specialized and will not matter for your application as you will always be using the same size output. That said, if you have the ability to modify the IV, I would do it. Modifying the IV could cause problems with interoperability and might break things any time you update software, so you'll have to weigh the options.

The near-collisions is also purely academic as we cannot efficiently find near collisions for say SHA-256 (or 512). This is pointed out on slide 15.

The main disadvantage of truncated SHA is that there are no reduction proofs to the original hash function. Basically this means that the truncated version could be less resistant to preimage attacks, but no known preimage attacks exist on truncated versions.

Xor SHA512 (from comments)
This method seems better than using MD5, but worse than using truncated SHA. Let's look at an example (for this I'm going to split the digest at the byte level to keep it simple and use a short output).

Say I'm looking for a preimage attack and am given a digest of 01001010 00100111. The XOR would be 01101101. If I can find a near collision that looks like 00101010 01000111, the XOR is the same. Thus, this construction is also vulnerable to near-collisions, granted this is more of an academic attack.

Since this is also vulnerabile to near-collisions, and since NIST uses Truncated SHA, I'd go with that instead.


RSA algorithm, relationship of the plaintext $m$ with $p$

So after trying a few examples with small numbers, it turns out that if message $m$ is a multiple of $p$, $m=a\times p$ then $\gcd(y,n)=p$, where y the known ciphertext. The rest is easy to compute.


Two party protocol using only hash function

That is impossible (at least as I understand your question) because:

The ability to privately test whether two strings are equal (even if just 2 bits, even with security only against semi-honest parties) implies oblivious transfer. (Kilian: A general completeness theorem for two party games)
It's impossible to realize oblivious transfer from hash functions alone. More formally, the "Minicrypt" model is that all parties have access to a random oracle and are computationally unbounded -- this model captures all the things you can get from one-way functions, hash functions, "without any other stronger kinds of crypto." Oblivious transfer is impossible in Minicrypt. (OT implies all secure function evaluation which implies key agreement which is impossible in Minicrypt: Impagliazzo-Rudich Limits on the provable consequences of one-way permutations)


disadvantages of combination stream and block ciphers

The security claims for these combination ciphers are impressive. Standard attacks against the stream cipher portion should be thwarted by the block cipher, and attacks against the block cipher should be complicated by the use of unique round keys for each block of cipher text.

This might or might not be correct. You claim that if I combine two insecure ciphers I should get secure cipher. This will often be incorrect. Worse, flaws in one cipher can weaken security of other one. Or feeding random data instead of secure static data can weaken security, as some research shows, for example here.

  The speed of these combination ciphers can be comparable to (or even better than) the block cipher by itself, because the number of rounds in the underlying ciphers can be reduced. (For example, Enchilada runs 12 rounds of ChaCha versus the standard 20, and Eris uses 24 round Serpent, versus the standard 32 rounds).

So now you combine two ciphers and reduce their strength, and claim that I should get double security. This is obviously wrong. Also, ChaCha12 is valid (and somewhat normal) choice of rounds, not a reduced version. Since they do more than just ChaCha12, they can't be faster than ChaCha12. And security might be improved or worsened.

  what are the disadvantages or weaknesses of this combined approach?

Those ciphers are new and haven't had proper cryptoanalysis
Those ciphers are slower than their single (and unbroken) counterparts
Those ciphers have poor implementation support
Those ciphers seem to mess around with basic ciphers in hope of creating something secure and fast. In turn they seem to rely more on obscurity than security.

So to be honest, there is no reason to use those ciphers when we have many unbroken, fast and verified secure algorithms. Those multiciphers (or extended ciphers, like AES with 2048bit keys) often rely on scare that everything broken, and make unfounded promises that they can make it better. Truth is often opposite, because you can't extend key and improve speed at once, as that decreases confusion (and because of that security).

If you are scared of one of ciphers being broken (for example in next 50 years), use multiple ciphers with multiple keys (at cost of speed). Then you at least have security of last of ciphers. Don't combine their cores in hopes of making something secure, as this can reduce security. Messing with design without understanding why choices were made is easy way to reduce security.


I like the features of the second, except for some drawbacks:

I don't believe the drawbacks are as bad as you think.

  1.This reduces the number of valid public keys that exist, and could reduce search space for an attacker attempting in the process of brute forcing public keys.

It doesn't help the attacker; if the attacker sees the public key, the knowledge that the hash is small doesn't help him (as he sees the exact value).  And the additional hashing requirement doesn't help Pollard Rho or Big-Step-Little-Step (two algorithms for computing discrete logs)

  2.This relies on the point addition algorithm being highly efficient, and assumes an attacker may not have some new and better way to perform this operation.

I believe that's a fairly safe assumption; it's hard to see how someone could generate $(x, xG)$ pairs in a manner that is significantly more efficient than your algorithm.  In any case, the most significant threat is an attacker with a bot or DSP farm; that would allow him to generate a number of public keys considerably faster than an honest user.

  3.It's possible that an unprivileged attacker observing the initial POW generation could determine some information about the key.

With your algorithm, the attacker has no knowledge of where you started the search.  If he learns that you took a while, he can deduce that a $(x - \delta)G$ doesn't meet the hashing criteria for a number of $\delta$s, however, as he can see the value $xG$, he could verify that directly if he wanted to, and so it doesn't actually leak any information about the private key.

So, it looks safe; my only concern is that it might not provide as much DoS protection as you hoped (of course, I don't know how much protection you're looking for, and what assumptions you are willing to make about attacker capabilities...)


As far as I know, in a typical RSA encoding process first you transform the whole char string that is the file into a number, to be encrypted, so my assumption is that is not possible in a typical RSA encoding-decoding process.

That's not typical. A typical real world RSA encryption process uses hybrid encryption, encrypting the data with a single-use symmetric key that is then encrypted using the actual RSA algorithms.

Depending on what the symmetric encryption is, you may be able to "seek" within the encrypted file without decrypting other parts. In most cases you'll at least be able to read it from the start and throw away decrypted parts as you go, avoiding excessive memory use.

  However, as I have the file I can encrypt it line by line or char by char, instead of encoding the whole, to decrypt it later again slice by slice. I'm assuming that a line or a char after encryption would have the same length in bytes, which may be a wrong assumption.

  Is this a feasible solution? Am I losing efficiency and would be more exposed to brute force attacks?

Using context-dependent (e.g. lines) blocking could leak data on the plaintext, so I wouldn't recommend it.

If you need to be able to quickly jump within the encoded file, you should use a symmetric encryption algorithm (under RSA if you want) that makes this easy. For example, AES in CTR or CBC modes. You will not be able to safely modify a small part of the file, but for read-only access that would be fine.

  EDIT: Let's complicate things a little bit more: After decrypting through RSA or symmetric key, I'll have to encrypt again the slices of my huge file, this time with a RSA private key. So, first: Encrypting huge file on a custom basis to make it decryptable part by part; second: take each part and encrypt it with RSA.

I.e. the file is read-write?

In that case, I would divide the file into constant-sized blocks that get independently encrypted using any symmetric encryption algorithm that accepts a large nonce (24+ bytes would be good, but 16 at the very least). Generate a single symmetric encryption key, which you encrypt with RSA. For each block generate a random nonce/IV that gets prepended to the ciphertext. When something is modified, rewrite the whole block(s), generate new random nonces.

Block size should be chosen to balance the memory expansion caused by nonces with the write amplification caused by rewriting blocks. Something like 4KiB blocks would probably be OK, I would think.

Instead of random nonces, one could use an incrementing counter, but in that case there might need to be additional safeguards to prevent an attacker feeding you an old version of the file, so random nonces are simpler.


Why is RSA private exponent much larger than RSA public exponent?

Is my guess correct?

Not really; we don't go out of our way to deliberately slow down the decryption operation.  Instead, things are set up that way because that's what's needed for security.

It turns out that if $d$ is small (e.g. less than a fourth of the size of $n$), and we tell people what the corresponding $e$ is, it turns out they can factor $n$ efficiently.  Hence, $d$ needs to be large to ensure security.
There's no similar issue for $e$; telling a people a small $e$ doesn't help them factor $n$ (or otherwise break RSA).  Hence, there's no reason not to select a small value (and make the encryption operation faster).


Simplifying the deleted question: it's given two large distinct prefix bytestrings $p_0$ and $p_1$, and it's asked two suffixes $s_0$ and $s_1$ so that $H(p_0\mathbin\|s_0)=H(p_1\mathbin\|s_1)$ for some $b=80$-bit cryptographic hash $H$ (obtained by truncation SHA-3, but that's immaterial). I concluded

The number of hashes to compute is in the order of $2^{42}$.

The standard technique for this is to define a function
$$\begin{align}f:\{0,1\}^b&\to\{0,1\}^b\\
x\quad&\mapsto\begin{cases}H(p_0\mathbin\|r_0\mathbin\|x)&\text{if the low-order bit of }x\text{ is }0\\
H(p_1\mathbin\|r_1\mathbin\|x)&\text{otherwise}\end{cases}\end{align}$$
where $r_0$ and $r_1$ are short fixed bytestrings of length chosen to align $x$ in a way making multiple evaluations of $f$ as fast as possible.
Observe that if we get $x_0$ and $x_1$ differing in their low-order bit and with $f(x_0)=f(x_1)$, that yields the desired suffixes $s_0=r_0\mathbin\|x_0$ and $s_1=r_1\mathbin\|x_1$.
If we evaluated $f$ for incremental inputs $x$ and looked for all exploitable collisions, for $2n$ hashes ($n$ with each value of the low-order bit), the probability of collision is slightly below $1-(1-2^b)^{n^2}$. Thus for $n=2^{b/2}$, that is $2^{b/2+1}$ hashes, and $b$ of cryptographic interest, the probability is about 63%. It's only 22% for $2^{b/2}$ hashes. That's lower than in pure hash collisions for a given number of hashes, because collisions between inputs with the same low-order bit are worthless, and about half of collisions fall into that category.
We can now answer

shouldn't it be $2^{40}$ considering the root of $2^{80}$ ?

by: No. Even with the best possible collision-detection technique, it's rather unlikely we can solve the problem with $2^{40}$ hashes. We can be cautiously optimistic with $2^{41}$.
Further, that exact strategy would require $O(2^{b/2}\,b)$ memory, which is impractically much; and a lot of its execution time would be search in that memory. The simplest solution to that issue is Floyd's cycle-finding, which reduces the memory requirement to a negligible $O(b)$, but markedly increases the expected number of evaluations of $f$. I don't know the exact factor, which depends on strategy; perhaps $3$, which would put us above $2^{42}$.
There are a number of improvements to cycle-finding. One key idea is distinguished points: we define $g$ iterating $f$ until the output has some characteristic (e.g. has the top 24 bits at zero), and try to find collisions in $g$ for inputs with that characteristic. When we get one, there remains only little work to find a collision for $f$, and it has 50% chance to be usable. That enables a time/memory trade-off which will get us to roughly $2^{41.5}$.
There's also the issue of distributing the work on several machines or execution units of a GPU, which would be a necessity is we use SHA-3 and want the result fast. The trade-off becomes between work and communication, and sometime we are willing to make sizably more hashes than the minimum, say in the order fo $2^{b/2+2}$. The standard reference is Paul C. van Oorschot & Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications, in JOC, 1999.


How hard is to find the operators of an addition knowing the sum of them?

Well, the problem "given a finite set $A$ of integers, is there a subset that sums to a target value $B$" is known as the Subset Sum problem; it is known to be hard.  Specifically, the decisional problem (is there such a sum) is NP-complete, and the computational problem (find the subset) is NP-hard.

That means that if you could solve large instances of this problem quickly, you could use that to solve a lot of interesting problems quickly, including just about any problem in crypto (finding AES keys given plaintext/ciphertext, factoring numbers, etc).

Because of this, assuming this is a hard problem would appear to be a fairly safe assumption.

On the other hand, it's not at all clear problem your problem statement that this is the problem you're relying on.  You are you "add each index of them and construct a table"; what do you mean $n_1[0]$?  If this is bit 0 of message digest $n_0$ and you're adding all the bits 0's from the message digests to form bit 0 of $T$, then you're not relying on subset problem at all; you're relying on the related problem that uses bitwise exclusive or -- that problem is known to be easy.


In SET, Bob the merchant doesnt need to know message is from Alice the cardholder. Bob needs to get paid for the order received. So Bob proceeds on response from Acquirer (running a SET payment gateway) telling him this particular cardholder (whatever the name) has sufficient funds in his account. This would likely mean funds were reserved, according to policy of issuing bank.

Yes, a "dual signature" was introduced in SET, meaning message to be signed is actually just two hashes, one is the order and the other is payment information. Merchant is supposed to receive the order and the hash of payment information, unless gateway would open more details.


$\operatorname{XOR}$ is similar to addition when working on Booleans; by contrast, $\operatorname{XNOR}$ is not a group law if we want to use $0$ as neutral.
Economy for extension: we can build a 3-inputs $\operatorname{XOR}$ from two 2-inputs ones; we can't for $\operatorname{XNOR}$.
Economy for making one: we can build $\operatorname{XOR}$ with four identical 2-input $\operatorname{NAND}$, but that can't be done for $\operatorname{XNOR}$. The construction goes:

$z\gets(a\;\operatorname{NAND}\;b)$;
$x\gets (a\;\operatorname{NAND}\;z)$;
$y\gets(b\;\operatorname{NAND}\;z)$;
$c\gets (x\;\operatorname{NAND}\;y)=(a\;\operatorname{XOR}\;b)$.

Update: the later argument works only because/when $\operatorname{NAND}$ is cheaper, faster, or/and less power-hungry than $\operatorname{NOR}$. That indeed was the case in TTL logic: that source shows 4 NPN transistors for $\operatorname{NAND}$, including one with two emitters, versus 6 for $\operatorname{NOR}$. The same holds for RTL logic made from PNP transistors, which used to be popular when these where made using germanium. However, RTL logic using NPN transistors (typically, on a silicon Integrated Circuit), which favors $\operatorname{NOR}$, has also existed. Famously, the Appolo Guidance Computer was built from 3-inputs $\operatorname{NOR}$ gates, two per IC.


How to verify most appropriate cleartext?

A simple approach is to do char gram frequencies.
There are readily downloadable dictionaries of char-gram frequencies.
You can lookup each set of consecutive characters of the requested length and multiply the probabilities.
For numerical reasons you don't actually multiply probabilities but sum the logarithms. You probably want to use some minimal frequency to prevent multiplying be zero.


Can you find the source material given a hash?

No, doing so would break the preimage assumption which is so far unbroken for sha1. (Assuming the message has sufficient entropy as to make brute forcing impractical)

  Can I find a 2nd document now that Shattered exists?

Yes / no. Yes, you can find many documents based on the shattered examples; but no you cannot create a new document without spending the same computations that the researchers did.

Take the two shattered examples, you can control all bytes after their distinct prefix blocks collide. All bytes after must be equal. So you're not introducing any new collisions, just extending the known collisions.

What is broken then?

Collision resistance.

You can (given lots of computing time) produce collisions just as they did in the paper, but this is still expensive. If a protocol assumes collision resistance and you pass it the two shattered files, it'll break. Likely assuming the second file is redundant, or incorrectly equivalent to the first.


An OTP already provides provable confidentiality in the case that the key is as large as the plaintext, and that the key itself is completely random in an information theoretic sense. Provable security in this case means that even a computationally-unbounded attacker would be absolutely incapable of decrypting the ciphertext if they are not given the key. You can't get more secure than that. Adding another key to an already unbreakable cipher does not make it "more" unbreakable.

Do note that an OTP does not protect the integrity of the plaintext in any way, regardless of how many keys are used on top of each other. An attacker can flip any bit in the ciphertext and know that the corresponding bit in the plaintext will also be flipped. To avoid this, a message authentication code, or MAC, is required. A MAC needs a key of its own, so any extra key material can be used for integrity.


Brute forcing the key simply means iterating over all the possible keys, assuming you know the mode of operation (in this case CTR) and the IV. Then if a likely plaintext is found then you've found your key.
It's always possible you find the wrong key, but the chances of you doing so diminishes with the amount of bits known of the plaintext. Usually you know enough about the plaintext to do so.
For instance, you can use the fact that the highest order bit of ASCII is always zero, most files have specific headers, you can do frequency analysis, etc. etc. If you perform an attack you might as well assume you know, say, 4 blocks of plaintext. In that case you can be next to certain that you found the right key to decrypt the rest.
Note that brute force attacks are very easy to parallelize; just split the key space and perform the decrypt / validation phase in separate threads.


Is it possible to get my x,y coordinates from my "secret exponent"?

I'll answer your question in order of appearance and leave the ones out which are off-topic here.

  For example I know you can get the $x/y$ or $x$ or $y$ from your public
  hexadecimal address, but can you get anything like that from the
  secret exponent?

Not directly. You can use the secret exponent (a.k.a. private key) to calculate the public key (which likely is the same as the "hexadecimal address") and thereby recover these values.

  Is the secret exponent the non-hexadecimal representation of your
  private key or is it the secret exponent in hexadecimal?

The secret exponent is a number. How you represent it depends on the context. For exchange you may represent it Base64 encoded or hexadecimally encoded. For internal use, for the computations by the library, the secret exponents is usually represented using a basis that performs particularly well on the platform you're on, e.g. $2^{64}$ for 64-bit architectures and $2^{32}$ for 32-bit architectures.

  I know it's a random number, but are numbers always converted to hex
  in this situation?

See the previous answer.

  Because I can't imagine graphing a hex number!

I'm not sure what you mean here, but usually nobody ever plots crypto systems used in praxis, because the values and distributions wouldn't show you anything at all (by design) unless it's severely broken.

  So, the $(x,y)$ coordinates are on the curve $y^2=x^3+7$, right?

Yes, indeed. For a pair $(x,y)$ to be considered a point on the curve $E:y^2=x^3+7$, they need to fulfill said equation. Note however that the generic equation for elliptic curves in cryptographic use is $E:y^2\equiv x^3+ax+b\pmod p$.

  How can you graph that?

You can plot elliptic curves over the real numbers and they actually look quite nice, but it's very hard to do so for modular elliptic curves and they don't exhibit any nice visual properties. As for the "how" the plotting is done, in the real case standard methods are used and in the modular case one just tries all $x$ values and the corresponding $y$ values and enlists them in the coordinate space.

  Like, is there a program that can generate a curve and then I can
  actually "see" where my $(x,y)$ coordinates are?

I know for sure that there are programs that can do this nicely for the real case, but I'm not aware of any for the finite field / modular case. You have to ask elesewhere for a better answer on this question.

  Basically, I'm just curious to know what point I am on that curve?

Seeing the point for cryptographic applications is highly useless. You'll just calculate the point using the curve equation and then draw it onto the curve you've already drawn.


Manual detection of such blobs of random bytes is rather easy to circumvent, as soon as the file is either too long or non-human-readable. So for something like this to work, you would need to automate the process.

The problem is, that it's really hard to find a valid ruleset on what is a blob of random bytes and what is valid data.

An automatic detection algorithm would have to understand all file formats that should be checked. So lets say, that program could detect a Python triple-quoted comment. Now you let it check a Java file. Java does not do triple-quoted comments, but instead uses /* do denote multiline comments. So your checker does not understand that. Or you could let it check a JPEG-file, which just looks like random bytes, if your checker does not understand JPEG.

Also, triple-quoted strings with random bytes often serve a real purpose, e.g. if you have a look at get-pip.py, it has a blob of Base64-encoded binary at the end, which contains a full installation of pip. Or any RSA-keys, they also look like random bytes and it would be really easy to put something into these fields, that causes an MD5 collision.


What's the difference between polylogarithmic and logarithmic?

Definitions:

An algorithm is said to run in

logarithmic time if $T(n) = O(log(n))$
polylogarithmic time if $T(n) = O(log(n)^k)$ (also written as $T(n) = O(log^k(n))$)

That means they are the same for $k=1$. Otherwise they are different and your other examples are all polylogarithmic.
I'm not sure how exactly to explain what the difference is but maybe a picture will help you:


Both Ram's and Ilmari's protocols allow forgery.

(The "other party" is either Charlie or Alice, depending on

whether Ram's or Ilmari's protocol is being attacked.)

Mallory receives either "Alice" or $m_{real}$, and sends to Bob either "Alice" or $m_{fake}$, respectively.

Mallory receives from Bob either an RSA public key or

a hash, and sends the same thing to the other party.

Mallory receives a random string the other party, and

sends $\:$ that_string $\oplus \hspace{.02 in}H(m_{fake}) \oplus H(m_{real}) \;$ to Bob.

Mallory forwards the next two messages (without changing them).

(Incidentally, I came up with that attack when I was formalizing the content-deniability proof.)


Anonymity problem after voting with blind signatures

The problem is, that you are actually checking a tautology and this is no danger to deanonymization. Let me explain it to you with a simple example of 2 signatures:

Lets say we want to blindly sign distinct messages $m_1$ and $m_2$ with distinct randomness $r_1$ and $r_2$.

Now during the blind signing you produce the transcripts (I omit $\mod N$):

$m_1'=r_1^e m_1$, $sm_1=r_1 m_1^d$ and
$m_2'=r_2^e m_2$, $sm_2=r_2 m_2^d$

and the final message signature
pairs are $(m_1,sm_1=m_1^d)$ and $(m_2,sm_2=m_2^d)$.

Now, lets apply your strategy:

lets look at one case where you start from one of the final signatures, say $(m_1,sm_1)$ and check it against both transcripts of the blind signing process  (and the second case is analogous due to symmetry):

$sm_1' sm_1^{-1}= (m_1^d r_1) (m_1^d)^{-1} = r_1$ and

$sm_2' sm_1^{-1}= (m_2^d r_2) (m_1^d)^{-1} = r_1'$

now you have two candidates and lets check it with every $m_i'$:

$r_1^e m_1 = r_1^e m_1 = m_1'$ and
$(r_1')^e m_1 = ((m_2^d r_2) (m_1^d)^{-1})^e m_1 = (m_2^d)^e r_2^e (m_1^{-1})^{ed} m_1 = r_2^e m_2 = m_2'$

So, now you have checked all transcripts of the blind signing process against the signature of the first message and with your candidates you have found out
that the first message corresponds to both transcripts with exactly the same probability. So you have learned nothing. As said above, the
same argument (due to symmetry) applies to the other case and you can easily generalise this to more messages.


I'd recommend you to read those two documents:

RFC 6090: Fundamental Elliptic Curve Cryptography Algorithms - describes all the fundamental operations in ECC algorithms (including ECDH), and includes references to further readings with more details.
The security impact of a new cryptographic library - explains design and implementation decisions behind NaCl, an OpenSSL alternative from Daniel J. Bernstein.


RSA Digital Signature vs Elgamal Digital Signature

TL;DR: The main reasons to prefer RSA over ElGamal signatures boild down to speed, signature size, standardization, understandability of the method and historical establishment as the result of a lot of lobby work.

The main technical advantage of RSA is speed.
With RSA you only need to do a small-exponent exponentation to verify a signature, where as with plain ElGamal signatures you'd have to do three full-sized exponentiations to verify a single signature. And if you read this, also think about embedded processors who have a public key hardcoded and have to verify the integrity of security-critical firmware updates and other things sent from a central server.
Another domain where RSA is faster, is key generation. If you do ElGamal naively, you'll generate your own field and generator, which is really slow, especially if you consider that "ElGamal primes" $p$ need the special property that $(p-1)/2$ is also prime. Compare that to RSA where you'd only need to find two (random) half-sized primes without any special property and take into consideration that the workload grows superlinear in bitsize.
Of course, if you use standardized fields and generators, ElGamal key generation becomes much faster as it simply is one exponentation and selecting a random integer.

The next domain where RSA is superior to ElGamal is signature with message recovery.
RSA allows you to sign messages which you don't have to encode outside the signature itself which allows very short messages (less than 1700 bits or so) to be directly embedded in the signature, greatly reducing bandwidth requirements in embedded devices and smartcards.
ElGamal signatures on the other hand require you to hash the message and thus you have to append the message to the signature as there's no way to recover it from the hash 100% of the time.

The third point why RSA is superior to many people is standardization.
RSA is greatly defined and standardized in PKCS#1 allowing any developer to just grab the specification and produce an interoperable implementation without any doubt, as every single step is documented. How to encode the hash? Documented. How to convert integers to byte sequences? Documented. How to transfer public keys? Documented.
ElGamal signatures on the other hand completely lack such a specification and the best you can find are some "ad-hoc" implementations following the original mathematical description. Not exactly ideal for interoperability.
It should be noted however, that the related DSA (which is a variant of ElGamal signatures) does have excellent specifications in the form of FIPS-186 (PDF) or your national equivalent.

One of the less technical but still important points to be noted is understandability.
When it comes to RSA, it's super-easy to understand. You take 5-15 minutes with a developer and you can explain him how they work and he can imagine why they are secure. Signature and verification are straight-forward operations and there isn't an awful lot to be done wrong.
ElGamal signatures on the other hand are more difficult to understand. For example in ElGamal your verification is at best an "consistency check" at a first look and the overall description is much much more complex to read and understand, especially compared to RSA. After all, there's a reason why RSA is taught in (some) schools and not ElGamal.

The final and probably one of the more important reasons is lobbying.
Back in the day when RSA was invented, Rivest, Shamir and Adleman sat together and also founded the RSA company. This company sold the RSA cryptosystem to companies and lobbyied a lot for it's use and ensured it ended up in a lot of standards for data authentication (for example at the IEEE).
ElGamal signatures had no comparable economical interest behind them that supported them. It must be said however that DSA did had a similar interest behind it, as the US government established it specifically to avoid RSA (and the related patent cost) and mandated it for quite some time for official products.


Why must IV/key-pairs not be reused in CTR mode?

Yes, the attacker would have a realistic chance of recovering plaintext, and preventing him from knowing the IV values does not reduce this risk.

The problem is that CTR mode encryption is effectively:

$C = P \oplus F(Key, IV)$

where $P$ is the plaintext, $C$ is the ciphertext, and $F$ is a complex function of its two inputs.

The problem with this is if you encrypt two different plaintexts with the same $Key$, $IV$ values, then the attacker gets two pairs:

$C_1 = P_1 \oplus F(Key, IV)$

$C_2 = P_2 \oplus F(Key, IV)$

Where he can see the values $C_1$, $C_2$.  With those, he can then compute:

$C_1 \oplus C_2 = P_1 \oplus P_2$

and thus deriving the value of the two plaintexts exclusive-or'ed together.

As for how that can be attacked, well, you can find two examples against ASCII-English plaintexts here and here.

And, note that since the attacker didn't actually use the IV value, it doesn't matter to him whether he knows it or not.


Why should we consider the output of the AES s-box as a “sensitive value” in relation to side channel attacks?

I would like to complete poncho's answer by mentioning a point that has not been discussed here.

On top of being an internal state which directly depends on plaintexts (resp. ciphertexts) and the key if you attack the first round (resp. the last one), making hypothesis on S-box output (resp. input) allows to exploit the non-linearity of this operation. Indeed, due to this property, passing the hypotheses through the S-box operation ensures a good distinguishability between the correct and incorrect key guesses.

For example, let's say you are performing a correlation power analysis (CPA) by considering the Hamming weight as leakage model. Then if you choose to focus on the round key addition (which also constitutes an internal state which directly depends on plaintexts (resp. ciphertexts) and the key), then all your key hypotheses which have a small Hamming distance with the good key will also result in a high correlation coefficient. The S-box non-linearity offers the  advantage to reduce the peak for all the wrong assumptions.


GCM optimisation using $M_0$ and $R$ tables - Calculation of $R$

$P$, defined on p. 8, is a representation of a primitive element in $\operatorname{GF}(2^{128})$; specifically, if we represent the field by $\operatorname{GF}(2)[t]/(f)$ where $f = t^{128} + t^7 + t^2 + t + 1$, $P$ represents the polynomial $t$, i.e. $0 + t + 0 t^2 + 0 t^3 + \cdots + 0 t^{127}$.

If $x$ is a byte, represented as some polynomial in $\operatorname{GF}(2)[t]$, then there are only 256 possible values of $x$.  The table $x\cdot P^{128}$ maps each possible byte to the corresponding polynomial $x\cdot t^{128}$ reduced modulo $f$.


Modern encryption can be broken in practice even when the algorithms are theoretically secure. There are a variety of ways this can happen:

Side channel analysis could have played a part.

The accepted answer to the linked question is excellent and provides some very good examples.

Exploitation of implementation bugs could have played a part.
Malware presence on the machine more or less negates any benefits of encryption, as advanced enough malware can simply watch and even modify anything/everything that you do.
Users may simply be coerced into surrendering the password which is used to derive their encryption keys.

More about Side Channels

  General classes of side channel attack include:

  Cache attack — attacks based on attacker's ability to monitor cache accesses made by the victim in a shared physical system as in virtualized environment or a type of cloud service.
  Timing attack — attacks based on measuring how much time various computations take to perform.
  Power-monitoring attack — attacks that make use of varying power consumption by the hardware during computation.
  Electromagnetic attack — attacks based on leaked electromagnetic radiation, which can directly provide plaintexts and other information. Such measurements can be used to infer cryptographic keys using techniques equivalent to those in power analysis or can be used in non-cryptographic attacks, e.g. TEMPEST (aka van Eck phreaking or radiation monitoring) attacks.
  Acoustic cryptanalysis — attacks that exploit sound produced during a computation (rather like power analysis).
  Differential fault analysis — in which secrets are discovered by introducing faults in a computation.
  Data remanence — in which sensitive data are read after supposedly having been deleted.
  Row hammer — in which off-limits memory can be changed by accessing adjacent memory.
  Optical - in which secrets and sensitive data can be read by visual recording using a high resolution camera, or other devices that have such capabilities.


Review of the paper

The paper's goal is to offload to a server the computation of the inverse of a (non-singular) $n\times n$ matrix $X$ of (the floating-point approximation of) real numbers, while keeping $X$ and $X^{-1}$ confidential.

Towards that goal, the paper's method is to

draw a secret key consisting of two random permutations and $2n$ non-zero random real numbers (that key will be used for a single matrix $X$);
transform $X$ yielding $Y$ according to the key by performing rows and columns swaps and scalings:

swap rows according to one permutation;
swap columns according to the other;
multiply each raw by a secret random real non-zero value;
multiply each column by a secret random real non-zero value;

send the result $Y$ to the server
obtain the alleged $Y^{-1}$
transforms the alleged $Y^{-1}$ into the alleged $X^{-1}$ by performing rows and columns scalings and swaps:

multiply each raw by the secret random real non-zero value formerly used for the column of same index
multiply each column by the secret random real non-zero value formerly used for the row of same index
swap rows according to the inverse of the permutation formerly used for columns;
swap columns according to the inverse of the other permutation;

verify the result by recomputing some of the coefficients of $X\cdot X^{-1}$ and checking if that's $1$ for the diagonal and $0$ elsewhere.

The paper

rightly observes that for large enough $n$, the bulk of the work is offloaded to the server (the client has $\mathcal O(n^2)$ work, when the server has $\mathcal O(n^\rho)$ works for $2.373\le\rho\le3$ depending on the matrix inversion technique used by the server);
has a section on Security Guarantee that culminates in the imprecise

  the cloud cannot recover X from Y by trivial means.(..) the security analysis follows an informal approach. A meaningful and challenging future work lies in giving a rigorous proof of security.

claims in the abstract (too optimistically at the very least) that it

  fulfills the goals of correctness, security, robust cheating resistance, and high efficiency

wrongly ignores issues of numerical stability in the verification procedure (as well as underflow and overflow that could occur in the scaling process), and is thus incorrect as described (the cheating resistance test has false positives in any implementation with bounded bandwidth to the server);
is insecure from a cryptographic standpoint for $n>1$, in particular because:

the number of elements equal to zero (or of very small magnitude) in $X$ is the same as in $Y$;
for even $n$ and $X$ with no zero elements, the sign of the product of all entries in $X$ is the same as in $Y$;
at least for moderate $n$, given $Y$ and $2n-1$ out of $n^2$ elements of a random $X$, it is typically possible to determine the $n^2-2n+1$ unknown elements of $X$, and a key equivalent to the original one.

Source and name of the cryptographic algorithm

The algorithm used to transform the matrix belongs to symmetric homomorphic cryptography. It is named disguise by Mikhail J. Atallah, Konstantinos N. Pantazopoulos, John R. Rice, Eugene H. Spafford: Secure Outsourcing of Scientific Computations, Technical report of the Department of Computer Sciences of Purdue University (1999), where it appears in section 1.4.1, with the same notation as the 2013 article discussed (which sadly does not cite this apparent inspiration).

The 1999 paper correctly identifies the security shortcomings of disguises (section 4.1), when the 2013 paper sidesteps theses. The 1999 paper has a section (3.1.2) on matrix inversion using this disguise technique, but what the 2013 article describes is more focused and slightly simpler.

Update: an earlier reference is by Mikhail J. Atallah, Konstantinos N. Pantazopoulos, Eugene H. Spafford: Secure Outsourcing of Some Computations, Technical report of the Department of Computer Sciences of Purdue University (1996); but there the technique is not yet named.


Ed25519 is a typical elliptic-curve signature scheme, in a group of large prime order $\ell \approx 2^{252}$ on a curve over the field $\mathbb F_p$ for $p = 2^{255} - 19$.  A secret key is a uniform random 32-byte string; a signature is a 64-byte string encoding a point $R$ on the curve generated by the standard base point, and encoding a scalar $s \in \mathbb Z/\ell\mathbb Z$.

Since for any fixed message $m$ the key-to-signature function is a map from a 32-byte space to a 64-byte space, it can't possibly induce a uniform distribution on the output space.  In fact, for each choice of $R$, of which there are $\ell$ possibilities, there is a unique choice of $s$, so there are only about $2^{252}$ possible signatures—obviously, some secret keys share a common signature on $m$ (but there are so few collisions it doesn't matter in practice).

Further, the signatures are easily distinguishable from uniform random bit strings: the scalar is always less than $\ell$, and the encoding of $R$ contains an encoding of an integer $x$ such that $(1 + x^2)/(1 + (121665/121666) x^2)$ is a quadratic residue modulo $2^{255} - 19$.

Does the output distribution have approximately the same entropy as the uniform distribution on secret keys?  At best it can have about 252 bits of entropy, because there are only about $2^{252}$ possible signatures—but that's pretty close to the 256 bits of entropy possible in a secret key.  At worst it ought not to have substantially less than 128 bits of entropy, because if not, there would be a random algorithm with substantially better probability of success at forgery than, e.g., Pollard's $\rho$ to recover the secret scalar from the public key, at comparable costs.

As it turns out, we choose between these options more or less uniformly at random: the choice of $R$ is determined by a scalar in $\mathbb Z/\ell\mathbb Z$ chosen by a pseudorandom function of the message, keyed by the secret key.  So, to anyone without knowledge of the public key: Yes, the distribution on signatures has about 252 bits of entropy.

This is why you can make a VRF out of it, though you need a little more work like an output filter to get all the properties of a VRF, so that even knowing the public key is not enough to distinguish outputs from uniform random if you don't have the proof of output too.


ElGamal scheme attack when one message is known and ciphertexts are intercepted

Knowing the message $m_j$ should not help you to get $r_j$. In-fact, ElGamal is assumed to be CPA secure (assuming that DDH is hard). Meaning that even if we choose two different plaintexts and give them to alice and she is encrypting only one of them, we won't be able to know which one she encrypted.

You can easily show that if you could retrieve $r_j$ ElGamal won't be CPA secure, as your can try both messages and try to retrieve $r_j$, you will only succeed when you try the right message.

Moreover, you are right about the messages Eve learns and how she does that.


How is a Caesar (Shift) Cipher represented at Binary level?

A Caesar cipher commonly operates on letters. This is often true for classical ciphers. Modern ciphers instead operate on binary values; most of the time implementations consider bytes instead of bits as atomic values.

The 26 letters form the alphabet of the classical cipher. The alphabet is a sequence of characters; in this case it is simply the English alphabet or ABC. The shift of the Caesar cipher is performed using the location within the sequence, using modular addition. The modulus is the number of characters in the alphabet, in this case of course 26. For this reason it is better to use 0 as starting index for the letter A. Modular addition can simply consist of first adding the shift, and then performing the modulus operation.

Fortunately the characters of the alphabet are already in order within the ASCII table. So instead of doing any binary arithmetic you can simply subtract the value of the letter A from the character you need to encrypt/decrypt. This way you get the location in the sequence of the alphabet. Then you do the shift. Finally you can simply add the value of the letter A to get the ciphertext back.

Creating a larger alphabet, for instance containing letters and digits, is certainly possible. In that case the letters and digits combined are the ciphertext. Determining the index in the alphabet for the cipher will of course get a bit harder (e.g. if x is a digit then the location could be x - '0' + 26 to place it after the letter Z in the alphabet). Alternatively you could write down the alphabet "abcdefghijklmnopqrstuvwxyz0123456789" and then use an indexOf function to find the location in the alphabet string.

So in the end, no binary operations are necessary. Addition, subtraction and modulus are all the operations you need.

Notes

Characters outside the alphabet are often removed before performing encryption for the Caesar classical cipher.
There are multiple ways of handling case, but simply converting everything to upper or lowercase - whichever you decide to use - before encryption should do the trick nicely.
Many languages include a remainder operator rather than a modulus operator. This can be tricky when decrypting as subtraction may result in a negative value.


Why SHA-256 (or any other) is too fast for passwords but "slow" for collisions to be found?

I suspect the answer is related to the fact that passwords are, in general, small.

No, actually, the answer is related to the fact that passwords are, in general, predictable.  Meaning that out of the set of all possible inputs to the hash function, a relative few of them are vastly more likely to be somebody's password than others.  For example, Password1 is vastly more likely to be somebody's password than act chance past language (generated using the XKCD comic method), which is in turn vastly more likely than <Cj{Vm7&Jr5y9< (generated with this page).  And that last one in turn is significantly more likely to be somebody's password than any randomly-selected 14-byte sequence (which is unlikely to even be printable ASCII).

What makes passwords weak is that the fact that some candidate passwords are vastly more likely than others means that the attacker can effectively avail themselves of this strategy:

Prioritize guesses that are very likely to be passwords over guesses that are less likely to be so.
Do this guessing process at very high speed using specialized hardware.

You've probably heard the term "dictionary attack," which is a very simple and effective technique for #1.  Just make a list of likely passwords and try them all.  Or download one from the Internet; this one, which collects "every wordlist, dictionary, and password database leak that [the author] could find on the internet" has 1,493,677,782 entries, which is about $2^{30}$.

The equivalent of this in the collision resistance scenario would be if we had some procedure that was able, for the hash function that we are attacking, to prioritize pairs of inputs that were more likely to collide than others.  There's some knowledge about how to do that sort of thing for broken hash functions like MD5 or SHA-1, but not for SHA-256.  Given the state of our knowledge, there isn't any way we know of prioritizing the search so that we try pairs likelier to collide ahead of unlikelier ones.

Since we don't know of a clever way to prioritize the search, then, generic math (the Birthday Problem) tells us that it should take us about $2^{128}$ guesses to find a SHA-256 colliding pair.  That's a number vastly bigger than the $2^{30}$-entry password dictionary I cited above.  Since SHA-256 is much faster than dedicated password hashing functions, you can test guesses for colliding pairs much faster than you could test password guesses, but definitely nothing even close to $2^{98}$ times faster (about $3 \times 10^{29}$).


There will no problem with using the nonce as 0 but only for once with the same key as the nonce says number used once. Remember we can generate the nonce randomly and at it has $1/2^{128}$ chance to appear.
CTR mode turns a block cipher into a stream cipher. As in all stream cipher, if you use the same stream again it will be vulnerable to crib-dragging attacks. In CTR mode, it is using the same nonce again with the same key.
Never use nonce more than once with the same key. To prevent the reselection of a nonce with a good random number generator, you should stop using the same key much before $\sqrt{2^{128}} = 2^{64}$ nonce generation, that comes from the birthday paradox. Alternatively, you can use an LFSR based solution to generate the nonce deterministically as suggested by the NIST.

so, if I use different keys and zero nonce it will be secure?

With the nonces, you can use the same key for a long time, Using always 0 is no more CTR mode. It is completely a new mode of operation. I don't see a problem with that, except as Maarten commented; the Key Check values:

These are often calculated by performing a single block encryption with all zero's. Please make sure that those are not used or published, or you will be exposing the initial part of your key stream.

It is better to use a HKDF to derive a key and a nonce very easily with your randomly generated key using salt and info
Extract:
$$\text{HKDF-Extract}(salt, IKM) \to PRK,$$where  PRK is a pseudorandom key, IKM is the input key material. If your random source is good, you may not need Extract.
and
Expand:
$$\text{KDF-Expand}(PRK, info, L) \to OKM,$$where OKM is Output Keying Material. L is the desired key length.
Note: Rogaway, in their seminal work: Evaluation of Some Blockcipher
Modes of Operation, in figure 1.2: summaries of their findings — confidentiality modes. CTR:

An IV-based encryption scheme, the mode achieves indistinguishability from random bits assuming a nonce IV. As a secure nonce-based scheme, the mode can also be used as a probabilistic encryption scheme, with a random IV. Complete failure of privacy if a nonce gets reused on encryption or decryption. The parallelizability of the mode often makes it faster, in some settings much faster, than other confidentiality modes. An important building block for authenticated-encryption schemes 1. Overall, usually the best and most modern way to achieve privacy-only encryption.

Therefore stick the expert's findings!

1 : AES-GCM that uses CTR and Even a single AES-GCM nonce reuse can be catastrophic.


Primality testing (deterministic vs. non-deterministic)

The simple answer is that AKS horribly inefficient in the real world.
Even the asymptotic complexity is orders of magnitudes higher than the one of probabilistic algorithms. Here is a comparison of AKS with Rabin-Miller and other probabilistic algorithms.
The following table illustrates the problem nicely (The tested number was $10^{
100}
+ 267$:


As the author of that page I feel that some clarification is necessary:-

Am I running a totally different version of the programs?

Yes. You're running the IID test. You need to run ea_non_iid.  What you've run assumes that the data sample is IID within a p=0.01 certainty.  It then calculates the min. entropy of the dataset using the maximum probability ($H_\infty$). That's easy.
ea_non_iid attempts to measure $H_\infty$ of correlated data.  That's hard.
The reason 90B is pretty useless (and never used) is that code assumes uniformly distributed data.  Well to be honest, no one really knows what the authors were thinking. [Insert appropriate conspiracy theory, but I draw your attention to Federal Information Security Modernization Act (FISMA) of 2014, 44 U.S.C. § 3551 et seq., which is referenced on page 3 of 90B].
Other than a few laboratory binary entropy sources, most generate some form of non uniform distribution.  You can get really weird ones depending on how the source is sampled and packed into bytes. That site has examples, and this is another one from a current project's source:-

The site also says to not trust anything on that site.  Do your own research and have a look at:-
John Kelsey, Kerry A. McKay and Meltem Sönmez Turan, Predictive Models for Min-Entropy Estimation, and Joseph D. Hart, Yuta Terashima, Atsushi Uchida, Gerald B. Baumgartner, Thomas E. Murphy and Rajarshi Roy, Recommendations and illustrations for the evaluation of photonic random number generators.
This is an extract:-

You can see that in some cases $H_\infty$ is underestimated sixfold.  Their various predictors are not very good. From experience and research I trust the LZ78Y compression predictor the most, but still.  This is consistent with my own testing as shown.
John Kelsey is one of the 90B authors and so he criticises himself!


Which values are used for an elgamal cryptosystem public key?

Let $p$ be a prime such that the Discrete Logarithm problem in $({\mathbb Z_p}^*,.)$ is infeasible, and let $\alpha \in {\mathbb Z_p}^*$ be a primitive element.

$$\beta =\alpha^a \bmod p$$

The values $p,\alpha , \beta$ are the public key, and $a$ is a private key. For a secret random number $k$ encryption and decryption are as follow:

$\operatorname{Enc}(x,k)=(\alpha^k \bmod p,x\beta^k \bmod p)$
$\operatorname{Dec}(y_1,y_2)=y_2\cdot{({y_1}^a)}^{-1}\bmod p$


Are there any industry standards for PRFs?

HMAC is the standard way to construct a PRF from a hash function.

FIPS PUB 198-1 - The Keyed-Hash Message Authentication Code (HMAC) (NIST standard)
RFC-2104 HMAC: Keyed-Hashing for Message Authentication (informational RFC)
ISO/IEC 9797-2:2011

(Unfortunately the above standards only describe it as a MAC, not as a PRF)

It's also very popular in practice. For example it's used in SSL/TLS, SSH, HOTP/TOTP.

I recommend using it with SHA-2 as the underlying hash function. Though technically the known weaknesses of MD5 and SHA1 don't apply to keyed use in HMAC, so even those obsolete hashes could still be used as PRF in the HMAC construction.


Purpose of signing the signed prekey in X3DH?

section 4.5 of the spec:

It might be tempting to observe that mutual authentication and forward secrecy are achieved by the DH calculations, and omit the prekey signature. However, this would allow a "weak forward secrecy" attack: A malicious server could provide Alice a prekey bundle with forged prekeys, and later compromise Bob's IKB to calculate SK.

in other words:

you want to talk to Bob for the first time
you ask me (the server) what are Bob's keys
I give you:

his real identity key
an unsigned prekey of my own
no one-time prekey

you do the X3DH with this information, and send Bob messages (making use of the output of X3DH)
unfortunately, Bob won't be able to decrypt any of these because the X3DH is not using an unsigned prekey he knows.
later on, I manage to compromise Bob's identity key, I get to decrypt the messages you had sent him at the time. Thus, there is no forward secrecy for these messages that Bob couldn't decrypt (thus, "weak forward secrecy").


Which precautions to protect against side-channel attacks on ARX ciphers?

Side channels

Essentially, side channels tell something about the secret data by using properties (e.g. timing, power consumption) of the algorithm itself. If an algorithm executes in a different way for different messages/keys, the attacker can deduce information about the message/key from the properties of the execution.

Even if the attacker only gains a little information about the key in one execution, they can do statistical analysis on arbitrary many measurements and thus still get a lot of information.

Where I come from I have learnt that you must assume that the attacker:

Can query the device an arbitrary amount of times with their own chosen messages/ciphertexts.
Knows every instruction (and branch) as they are executed  (by using timing attacks/power traces).
Knows the execution time of every instruction (by using timing attacks/power traces).
Knows every address that is looked up during the execution of the algorithm (by using cache timing attacks).

Solution: All crypto algorithms must run deterministically. In other words:

Do not branch on secret data.
Do not do any memory lookups dependent on secret data. I.e. you can do memory lookups, but only if the algorithm does exactly the same lookups each time it executes.
Only use instructions that execute in constant time. (For example, div-instructions often do not execute in a constant amount of cycles.)

ARX ciphers

ARX ciphers limit themselves to only three basic operations which all run in constant time on pretty much all platforms. Because of their design, there are not really that many precautions to be taken, as long as you adhere to the rules above.

But know that, while you will be ok most of the time, it just really depends on the implementation and on the platform. As Squeamish notes: hardware implementations of ARX ciphers can just as easily be vulnerable against DPA/EM attacks, even if you follow all the rules above.


Comparing a brute force attack on DES (with $2^{56}$ operations) to a birthday attack on CMAC (with $2^{64}$ operations) would appear to be an apples-to-Volkswagen comparison; they are assuming two things are similar, when they really aren't.

The brute force attack on DES involves obtaining a single plaintext/ciphertext block pair, and then going through the possible DES keys, and looking for a key that encrypts that plaintext block into that ciphertext block.  The key here is that, once the attacker does have that plaintext/ciphertext pair, he no longer needs anything else from the attackee Alice -- he runs all these trial encryptions on his own hardware, and if he feels the search isn't going fast enough, he just buys more hardware.  The speed of the attack is limited only by the attackers budget.

On the other hand, the birthday attack on CMAC involves asking Alice for the MAC of a huge number of messages (and then digging through those MACs to find a duplicate).  The key point is that we need a great deal more from Alice; it is not sufficient to obtain a limited number of bits, instead if we need to generate the MAC of $2^{64}$ messages, that means that we need to present those $2^{64}$ messages to Alice, and we need her to compute the MACs of all those messages.

That's the key point: Alice will compute those MACs only so fast, and the attacker cannot speed it up by parallelism or anything.  If Alice is able to generate only 1 MAC per nanosecond, that means that it'll take over 500 years to generate the MAC for all $2^{64}$ messages.

In summary: any attack that requires $2^{64}$ exchanges with Alice cannot be considered "somewhat trivial"; even if a brute force attack with the same abstract effort would be.


For question (1):

This page gives some hints on IVs and CBC: https://defuse.ca/cbcmodeiv.htm

I copy-paste the part about IVs "predictability"

  Chosen-Plaintext Attacks

  Randomness is not enough, though. IVs have to be unpredictable,
  too[2].

  Suppose there is a CBC-mode encryption system that selects a random
  IV, publishes it, asks the user for a one-block plaintext to encrypt,
  encrypts it with that IV, then gives the ciphertext to the user.
  Suppose Alice uses the system to encrypt two distinct messages A, and
  B, to get ciphertexts C and D. Alice gives Mallory the plaintexts and
  the ciphertexts and offers Mallory \$1000 if he can tell her which of
  the two ciphertexts is the encryption of plaintext A. If he can't, he
  has to give Alice \$1000.

  If Mallory made a random guess, he would be right with 50%
  probability, because either C corresponds to A, or D corresponds to A.
  If the system is secure, Mallory shouldn't be able to do any better
  than this.

  Mallory doesn't have to guess, though, because he can use a
  chosen-plaintext attack on the CBC-mode encryption system to figure
  out if C corresponds to A, or D corresponds to A. Mallory knows that
  the IV Alice used to encrypt A was IVA, and he knows that the input to
  the block cipher was A XOR IVA. Mallory just needs to know whether the
  block cipher encryption of A XOR IVA is C or D. Mallory asks the
  encryption system for the next IV, IVN, and sends it the plaintext A
  XOR IVA XOR IVN to encrypt. The system follows CBC mode, XORing
  Mallory's plaintext with IVN and passing the result to the block
  cipher. IVN XOR IVN is 0, so the system passes A XOR IVA to the block
  cipher, and gives Mallory the ciphertext. What Mallory gets back is
  either C or D, whichever one corresponds to plaintext A. In this case,
  Mallory gets back C, tells Alice that C corresponds to A, and wins
  $1000 with 100% probability.

  Mallory would not have been able to do this if he could not predict
  the IV, since the plaintext he sends to the system depends on the next
  IV.

For (2):

Although the IV must be unpredictable (for each key), it doesn't need to be kept safe once the ciphertext was generated. Generally it is send (prefixed) to the ciphertext. It's certainly not part of the key.

For (3):

If there are separate encryptions, then see 1. If there is just one long stream then you only need one IV.


Your problem is equivalent to solving $m^3 \equiv c \pmod n$. This corresponds to breaking RSA for $e=3$. We know no efficient way for doing that without factoring $n$.

If you know the factors of $n$ you can compute the private exponent $d$ as $e \cdot d \equiv 1 \pmod{\varphi(n)}$ using the extended euclidean algorithm and then compute $m$ as $c^d$.


A Bitcoin address is computed as follows, according to the Bitcoin wiki:

A private key is a 256-bit integer $k$ below 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141, the order of the group $E(\mathbb F_p)$ of $\mathbb F_p$-rational points on the curve secp256k1, $E/\mathbb F_p: y^2 = x^3 + 7$ where $p$ is the prime $2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$.
A public key is the standard encoding $\underline P$ of a point $P = [k]B$ on secp256k1, the scalar multiplication by $k$ of the standard base point $B \in E(\mathbb F_p)$.
An address is the ‘base58’ encoding of the string $\text{‘1’} \mathbin\Vert h \mathbin\Vert c$, where $h = \operatorname{RIPEMD160}(\operatorname{SHA256}(\underline P))$ and $c$ is the first four bytes of $\operatorname{SHA256}(\operatorname{SHA256}(\text{‘1’} \mathbin\Vert h))$.

If you could find $\underline P$ given $h$, you would be given top billing in a top-tier cryptology journal.  This is because it would tear down the widely held conjecture that both RIPEMD160 and SHA256 are preimage-resistant.

If you could find $k$ given $P$, you would also be given top billing in a top-tier cryptology journal.  This is because it would tear down the widely held conjecture that discrete logarithms are hard to compute in well-understood elliptic curves like secp256k1.

You would alternatively be able to make money from exploitation of much more lucrative markets than your own private blockchain or cryptology journals.  But there are lots of very very smart people in cryptology who aren't doing that, and it's not just because they're all paragons of morality.


CCA2-secure encryption based on LWE/Ring-LWE

If you don't mind relying on random oracles, the simplest approach is to apply a generic transformation such as Fujisaki-Okamoto to the (Ring-)LWE based scheme you start from. See for example Peikert's PQCrypto'14 paper for a concrete instantiation, and the TCC 2016 paper of Targhi and Unruh for a proof of security of this type of transform in the quantum random oracle model.

Lattice-based CCA2-secure encryption in the standard model is usually obtained using lattice trapdoors. The state-of-the-art construction is due to Micciancio and Peikert (section 6.3 of this EUROCRYPT 2012 paper).


How to calculate entropy of output of a PRNG

TL;DR: The applied thought process was wrong. Entropy is a function of random variables and not of arbitrary integers. The fact that the PRNG doesn't increase entropy follows from the fact that the input space is limited and there's no other input to the algorithm and thereby entropy can't be increased.

First, let's recall the formal definition of "entropy" (as can be found in the Handbook of Applied Cryptography, chapter 2.2, PDF):

  Definition The entropy or uncertainity of $X$ is defined to be $H(X)=-\sum_{i=1}^np_i\lg p_i=\sum_{i=1}^np_i\lg (\frac{1}{p_i})$ where, by convention, $p_i\cdot \lg p_i=p_i\cdot \lg (\frac{1}{p_i})=0$ if $p_i=0$.

Notation: $\lg a$ is the binary logarithm of $a$. $X$ is a random variable that takes each value $x_i$ (from a finite set if size $n$) with the correspdoning probability $p_i$.

Now let's model the $m$-bit string as the random variable $X$. The $m$-bit string can take $n_X=2^m$ values, each of which has the probability $p_i=\frac{1}{n_X}=2^{-m}$. Thereby the entropy $H(X)$ is $$H(X)=\sum_{i=1}^np_i\lg (\frac{1}{p_i})=\sum_{i=1}^{2^m}2^{-m}\lg (2^m)=2^m\cdot(2^{-m}m)=m$$ as expected.

The next step is to properly model the "PRNG". I will model it as a pseudo random generator (PRG), because I assume that's how you meant it.

  In short: A pseudo random generator (PRG) is a deterministic algorithm that takes a fixed length input and returns a longer output.

(not a full formal definition and the usual definition would restrict to polynomially sized outputs, but we don't need one here)

By this we can model our PRG $\mathcal G: \{0,1\}^m\rightarrow \{0,1\}^{2^m}$. As $\{0,1\}^m$ can only take $2^m$ states and this is the only input to the function, we know that there can be at most $2^m$ different outputs of the PRG.

If we model the PRG output as a random variable $Y$, we know that (in "best case") $p_i=2^{-m}$ for $2^m$ different $y_i$ and $n_Y=2^{2^m}$. We further know that for the remaining $2^{2^{m}}-2^m$ possible values $y_i$, $p_i=0$ holds. With this information, we can compute the upper bound of the entropy of the PRG:

$$H(Y)=\sum_{i=1}^np_i\lg (\frac{1}{p_i})=\sum_{i=1}^{2^m}2^{-m}\lg (2^m)+\sum^{2^{2^m}-2^m}_{i=1}0\cdot\lg(\frac{1}{0})=2^m\cdot(2^{-m}m)+(2^{2^m}-2^m)\cdot 0=m$$

Note that $0\cdot \lg(\frac{1}{0})$ is, by convention, $0$.

As we have modeled $Y$ using as an optimal "PRG", it may be very well the case that there aren't $2^m$ different outputs. So we can conclude with $$H(X)\geq H(Y)$$ as expected and thereby that the PR(N)G doesn't increase entropy by itself.


Can Fully Homomorphic Encryption do comparisons?

This is simply not true. The above function can perfectly be homomorphically computed on FHE ciphertexts encrypting the inputs. There is no such "obvious limitation", and I wonder where your certainty comes from.

Asking whether FHE is Turing complete does not really make sense: FHE is a cryptographic primitive, not a general computing device. If this is what you meant, yes, we can evaluate any (polysize) function on encrypted inputs using the FHE evaluation algorithm. More precisely, we can evaluate any polysize boolean circuit on the input, in a private way (i.e. the inputs and the outputs are not leaked). If you want to evaluate Turing machines, it is more complicated in general (and you must give up on hiding the exact running time of the computation for this to be interesting), but it can also be done.

EDIT: from your comments, I now understand your question more clearly. Yes, FHE will never reveal the intermediate computation in the clear. This means that when you run a program on encrypted values, the computation pattern will have to be oblivious of the exact data. This does not make such computation impossible, as you seem to believe, but simply less efficient.

For example, suppose that you must evaluate the following program: if $a > b$, output $f(x)$, otherwise, output $g(x)$. Using FHE, you would proceed as follows: compute the bit $\beta$ which is $1$ if $a > b$, and $0$ otherwise, and output $\beta\cdot f(x) + (1-\beta)\cdot g(x)$. You can compute this on encrypted data, and you never need to know the exact value of $\beta$ to evaluate this program with FHE.

The FHE computation does not need "the plaintext result", it simply must rely on an algorithm which works obliviously of the exact inputs, and it is usually not hard to convert a computation in an oblivious computation (although it's not always obvious either).


There are a few key distinctions to make
Quantum cryptanalysis
This is what you hear all the buzzing about. Specifically, there is something called Shor's algorithm, that when used to break modern crypto, can be devastating. If you've encrypted a zip file and told someone the key you're quite safe. But things like PGP and SSL, where you have to agree to a key online, are vulnerable; quantum algorithms have about an impact of O(n/2) on symmetric crypto decrease the effective key size by half for symmetric crypto. That means AES-256 will be as strong as a pre-quantum AES-128. RSA will be much worse off:

Shor’s Algorithm, which can only be executed on a quantum computer, can factor large numbers in $\log(n)^3$ time, which is drastically better than the best classical attack.  [Normally RSA2048] takes about $10^{41}$ units of time ...  Using Shor’s algorithm, the same problem only $10^3$

This is not something D-Wave can do yet. As far as we know.

Geordie (chief technology officer of D-Wave) on June 2, 2011, at 3:59 pm
said:
We do have a factoring algorithm that I’m going to do a series of blog posts on (the working title is “Better than Shor” :-) ).

-- https://dwave.wordpress.com/2011/05/11/learning-to-program-the-d-wave-one/
After that they never mentioned this again. Either he was wrong or
someone told him to shut up about it.

Quantum Key Distribution
This is what the other answer mentions, and this is something we can do today, and because of that, there's some hype about it. What it comes down to is that you have a guarantee that the code has not been intercepted in transit, because any observation would affect the quantum state. But it's really slow for now.
Post-quantum cryptography
These are simply crypto schemes designed to withstand algorithms like Shor's. An implementation is McElieces'; some fascinating work based on the hardness of breaking linear error-correcting codes. Other asymmetric implementations are based on lattices.


Encryption / Decryption using AES-256 GCM

Exporting the key is sufficient.

With GCM (and block modes in general), the key and the nonce play very different roles.

The key is secret; it is known by the encryptor and the decryptor and no one else.  And, you can use the same key to encrypt multiple messages.

The nonce (or IV) need not be secret; common practice is to send it along with the encrypted message.  However, one limitation with GCM is that, while you can encrypt multiple messages with the same key, you must use a different nonce for each message that you encrypt with that same key.  And, typically, the encryptor selects the nonce when it encrypts the message.

Because of this, it doesn't make sense to ask Vault which nonce it expects to use to decrypt; the encryptor selects it (and if Vault will be able to decrypt several messages with the same key, it'll have to use different nonces anyways).


Expected entropy in the output of a random oracle

The expected entropy in the output of a $h$-bit random oracle fed with random $h$-bit input is close to $h-0.8272$ bit, for even moderate $h$ (e.g. at least $32$). As $h$ grows, that expected entropy becomes arbitrary close to $h-\eta$ bit with
$$\begin{align}\eta&=\frac 1{e\ln(2)}\sum_{i=1}^\infty\frac{\ln(i+1)}{i!}\\
&=0.82724538915300508343173\dots\text{bit}\end{align}$$
where the sum is given by A193424.

Proof, where I'll be using $a\approx b$ as a convenient shorthand for $\displaystyle\lim_{h\to\infty}\frac a b\ =\ 1$

For a particular distribution implemented by the oracle, let $n_j$ be the number of output values appearing exactly $j$ times among the outputs for all inputs. The exact entropy $H$ for that particular distribution can be computed from the $n_j$ by applying the definition of entropy, giving
$$\begin{align}H&=\sum_{j=1}^{2^h}n_j\;\frac j {2^h}\;\log_2\left(\frac{2^h}j\right)\\
&=\frac h{2^h}\sum_{j=1}^{2^h}j\;n_j\;-\frac 1{2^h}\sum_{j=1}^{2^h}n_j\;j\;\log_2(j)\end{align}$$
where we have (by merely counting what all inputs lead to)
$$\sum_{j=1}^{2^h}j\;n_j\;=2^h$$
thus
$$h-H=\frac 1{2^h}\sum_{j=1}^{2^h}n_j\;j\;\log_2(j)$$
For fixed $j$ and as $h$ grows, by counting of the possibilities, we can establish that for random distribution, odds that any particular value is reached $j$ times is $\displaystyle\approx\frac 1{e\;j!}$. Thus for fixed $j$ and as $h$ grows, the expected $n_j$ is $\displaystyle\approx\frac{2^h}{e\;j!}$.
In the exact expression of $h-H$, all the terms in the sum are non-negative. To obtain an asymptotic of the expected $h-H$ when $h$ grows, we can thus replace $n_j$ by its expected value, and obtain that when $h$ grows the expected value of $h-H$ is $\displaystyle\approx\frac 1 e\sum_{j=1}^\infty\frac{j\;\log_2(j)}{j!}$.
The stated result follows by defining $i=j-1$, and removing the sum's first term, which is zero.

I've been unable to locate a source; the closest I found is an empirical derivation of $\eta$ to 4 decimals by Andrea Röck: Collision Attacks based on the Entropy Loss caused by Random Functions, WEWoRC 2007, slides; with more in her thesis.

My first empirical derivation was using a program which draws $2^h$ pseudo-random $h$-bit values and counts how many values are reached how many times; for $h=35$ (the largest I could do with 20GB RAM), three runs gave:

             run 1                run 2                run 3
  0  12640123427 36.79%   12640183855 36.79%   12640308584 36.79%
  1  12640408212 36.79%   12640365800 36.79%   12640104651 36.79%
  2   6320124091 18.39%    6320013534 18.39%    6320174710 18.39%
  3   2106681541  6.13%    2106762262  6.13%    2106726749  6.13%
  4    526645276  1.53%     526674914  1.53%     526679947  1.53%
  5    105334156  0.31%     105325000  0.31%     105330269  0.31%
  6     17561277  0.05%      17551924  0.05%      17556150  0.05%
  7      2507918  0.01%       2508727  0.01%       2505282  0.01%
  8       313971  0.00%        313943  0.00%        313406  0.00%
  9        34748  0.00%         34553  0.00%         34755  0.00%
 10         3424  0.00%          3542  0.00%          3546  0.00%
 11          291  0.00%           287  0.00%           292  0.00%
 12           31  0.00%            24  0.00%            24  0.00%
 13            4  0.00%             3  0.00%             2  0.00%
 14            1  0.00%             0  0.00%             1  0.00%
 15+           0  0.00%             0  0.00%             0  0.00%
entropy   34.172763 bit        34.172758 bit        34.172751 bit

Application to the question: the entropy for the output of SHA-256 truncated to its first $128$ bits when fed a random $128$-bit input is about $127.173$ bit, down from very close to $128$ bit before truncation (see final note). The truncation does not halve the entropy, because the halves are not independent. The right line of thought is that SHA-256 truncated to its first $128$ bits is a fine $128$-bit hash, and behaves like a random oracle.

Note: if we consider a random function from $\{0,1\}^{128}$ to $\{0,1\}^{256}$, most likely there is a small $k$ (most often $0$ or $1$, sometime $2$, rarely $3$ or more) such that $k$ outputs have exactly two corresponding inputs, $2^{128}-2k$ outputs have exactly one, and $2^{256}-2^{128}+2k$ outputs have none (odds that any output is reached three or more times are negligible).

Therefore, in this most likely case, the entropy on output of that function when fed a random $128$-bit input is $-k\;2^{-127}\log_2(2^{-127})-(2^{128}-2k)\;2^{-128}\log_2(2^{-128})$, that is $128-k\;2^{-127}$.

The best model we have for SHA-256 (not truncated) for $128$-bit input is a particular function chosen at random among functions from $\{0,1\}^{128}$ to $\{0,1\}^{256}$, thus we can conclude the entropy for the output of SHA-256 when fed a random $128$-bit input is likely exactly $128-k\;2^{-127}$ for $k\in\{0,1,2\}$, which is very nearly $128$ bit, down to about the 37th decimal places.


Why "pairings on elliptic curve" are used?

Although the question is a bit broad, I think it's an interesting one.

Giving a bit of context helps with the explanations. In the 80's, many cryptographic primitives have been design, based on group structures (usually relying on variants of the discrete logarithm assumption over this group). The rationale behind the initial introduction of elliptic curves in cryptography was the following: over a group with no additional structure, solving discrete log is hard (we say that discrete log is "hard in the generic group model"). Elliptic curves are groups, yet they seemed to have little, if any, additional structure that one could exploit to solve the discrete log problem (and related problems).

In the 90's, an apparent weakness was discovered in many types of elliptic curves: in some curves, people observed that there was in fact more structure than expected, as there was an operation that could move (in polynomial time) the discrete log problem from the curve, to a target space (as you can guess, this operation is the pairing operation). Therefore, when the target space was a space with a lot of structure (such as a field), this allowed to reduce solving a hard problem (dlog over a curve) to a considerably easier one (dlog over fields). A variety of attacks were developed, based on the computation of these pairings.

Then, in the 2000's, Boneh and Franklin on one side, and Joux on the other, came up with the idea that this apparent weakness could become a feature: intuitively, a pairing allows to "multiply" the exponents of two group elements, while the usual group structure only allows to add an substract exponents. To do so, one had to use a curve where the pairing was not a strong weakness (i.e., a pairing moving the discrete log to a group sufficiently large to make the computation of dlog still infeasible in the target group). Then, they came up respectively with the following applications:

Identity based encryption, which was a long standing open problem. One can obtain very efficient instantiations using pairings. It has recently been shown that standard groups (without pairings) suffice for identity-based encryption; however, pairing-based solutions remain considerably more efficient.
Tripartite non-interactive key exchange. Here, the idea is simple: the standard two-party DH key exchange works by exchanging two group elements, $g^a$ and $g^b$, and letting the two players locally compute $g^{ab}$. If one has a pairing, we can add a third player without further interaction: the players exchange $(g^a,g^b,g^c)$, and can locally compute $K = e(g,g)^{abc}$, where $e$ is the pairing operation.

This last example is perhaps the most useful one for you, because it illustrate on (arguably) the simplest possible scenario the reason why the additional structure given by a pairing allows for new applications. Following the above applications, many more have been discovered, which can be obtained from pairing but not (or not efficiently) without them. This includes:

Non-interactive zero-knowledge proofs
Verifiable pseudorandom functions
Short Signatures

... and many more. In addition to the "multiplication in the exponent" allowed by pairings, another feature which is at the core of many applications is the fact that they allow to build a gap group, i.e., a group in which the decision problem (DDH) is easy, but the search problem (CDH) remains hard. Such gap groups have many applications (e.g. identity-based signatures, undeniable signatures...).


No, DHE is secure and allows to share a common secret between two parties over an insecure channel. But you cannot know, if the one you share the secret with is the one you want (DHE is vulnerable to man in the middle attacks). So DHE-RSA uses DHE to share a common secret and signs the communication with RSA to make sure, that both persons communicate with the right other person.

So in short: DHE does not provide authenticity. DHE-RSA does.


How the condition $s \geq 8$ is determined in Lindner-Peikert cryptosystem?

Note: I edited a lot of my speculation and calculations after comments from Chris Peikert (see comments below).

The smoothing parameter on a lattice, $\eta_\epsilon(\Lambda)$, is roughly the width of a discrete Gaussian $\mathcal{D}_{\Lambda,s}$ above which it is well-approximated by a continuous Gaussian; see the Regev quote on page 17 here.

In particular, for $\mathbb{Z}^n$, there is an upper bound for the smoothing parameter (see page 8):

$\eta_\epsilon(\mathbb{Z}^n) \leq \sqrt{\ln(2n(1 + 1/\epsilon))/\pi}$

Again, on page 17, if $s \geq \sqrt{2} \eta_\epsilon(\mathbb{Z}^n)$, then the sum of the discrete Gaussian $\mathcal{D}_{\Lambda,s}$ and a continuous Gaussian with width $s$ is basically equivalent ("within statistical distance $4\epsilon$") to a continous Gaussian of width $\sqrt{2} s$, and you want this to hide the discrete structure in the continuous noise.

So I thought at first that the critical quantity was $\sqrt{2} \eta_\epsilon(\mathbb{Z}^n)$. However! After a comment from one of the authors of the paper (see comments below!), it's enough to just consider $s \geq \eta_\epsilon$ with $\epsilon \ll 1/2$. Using the formula above with $\epsilon = 2^{-256}$:

$n=128 \rightarrow s \geq 7.63$
$n=1024 \rightarrow s \geq 7.68$
$n=2048 \rightarrow s \geq 7.89$

So $\eta_\epsilon$ doesn't fluctuate that much and you can take $s \geq 8$ for a nice round number.

Of course you can vary $\epsilon$; I used Lemma 4.2 in this paper to justify constraining it $0 < \epsilon < 1$, but it should be a negligible function, like $\epsilon = 2^{-n}$.

Thanks to Chris Peikert for discussion and clarification in the comments!


Converting a number to a member of a multiplicative cyclic group

Use the Legendre symbol in your case.
Explanation: when $p=2.q+1$, the order of the multiplicative group of $F_p$ is p-1=2q.
Then there is no other alternative, when you select a random number, it could be a quadratic Residue with probability $\frac{1}{2}$.
The legendre symbol of any number a, is : $a^{\frac{p-1}{2}}=a^{q}=\pm 1$

Then except the number 1, all the other quadratic residue (Legendre symbol is 1) have order q.


Is this method of encryption theoretically unbreakable?

Ignoring concerns about missing integrity and authentication verification, here is why:

Suppose that the key you used to generate your keystream from your CSPRNG is shorter than your plaintext; if it isn't, you may as well use the one-time pad. Then I know from the pigeonhole principle that there will be some (many, actually) keystreams that will never be generated. Furthermore, I can enumerate these keystreams by simply going through every key (your plaintext has finite length, so there are only finitely many keys I have to check).

Therefore given any ciphertext, I can infer that there are many plaintexts that can never encrypt to this ciphertext, regardless of the key you picked. I have derived knowledge* about the plaintext from the ciphertext alone, therefore your encryption scheme is not information-theoretically secure (what you call "theoretically unbreakable").

Did I mention I was an entity with unbounded (infinite) computational power? If you want truly unbreakable encryption, this is effectively equivalent to your ciphertext conveying zero information about the corresponding plaintext without knowledge of the key. It's a very high bar to set, and one that is virtually useless in the real world, which is why we are perfectly okay with AES and the like.

You cannot cheat information theory by stretching your keys through deterministic processes. You cannot cheat information theory through elaborate encryption schemes involving multiple encryption passes with different keys and liberal sprinkling of hash functions and CSPRNG's - an unbounded adversary will see right through it, unraveling whatever layers of convoluted encryption you have going on, until it all eventually boils down to how much information your ciphertext has, which is itself fundamentally lower-bounded by how long your key is.

Information is given, not created, and your cipher's security is measured in terms of how much computation it takes to extract information out of the ciphertext without the key. If it carries no information, there is nothing to be extracted, and you have information-theoretical security.

* the length of the plaintext is not generally considered "knowledge" as it is more metadata than anything else; it cannot really be relied on as you can always pad your plaintext to a fixed length and communicate through a prearranged dictionary of fixed-length symbols.


Is there a 3-D alternative for elliptic curves?

So, i've just started to figure out how encryption works.

From what you've said, I fear that's not true.

  As i understand the most widely used method to exchange encrypted data over untrusted network is Diffie-Hellman protocol.

Partially true, as DH is used as key agreement protocol to further derive session encryption & MAC key. DH is asymmetric, where as encryption and MAC (message authentication code) are symmetric.

  So, original idea was to use big prime numbers (1 number, 1-D) ... After a while elliptic curves (x and y coordinates, 2-D) was discovered, so now everyone using them.

The original realization of the idea was to use a big prime number, but those numbers that can be represented in binary system have a exploitable structure make possible attacks faster than brutal-force search.

DH is still realized using scalars, except this time, the scalars are points on elliptic curves over finite fields.

  Question is - do elliptic curves have more cryptographic strength than classical approach because of 2 dimensions?

No, they are stronger because they don't have the same exploitable structure as (big) integers.

  Is there researches related to 3-rd (or even more) order polynomes that potentially can provide even more cryptographic strength than elliptic curves?

Yes, one of my questions here attracted this comment, but I haven't thoroughly comprehended it, I advise you read it with care if you have time.


Security of a self-decrypting block-cipher?

As I understand, your question is about using an involutive function $F$ as a block cipher. This function is constructed as $F(x) = D(P(E(x)))$, for some (let's assume secure) block cipher represented by $(E, D)$. I will assume the encryption and decryption keys are equal such that the same holds for $F$.
Below is a generic attack that only uses the involutive property of $F$, there might be additional problems (depending on $E$ and $D$).

It is typically required that block ciphers are secure against chosen-plaintext attacks.
In the example it is trivial to obtain $x$ given $y = F(x)$ and an encryption oracle. We just ask the oracle to encrypt $y$.
In other words, an encryption oracle is equivalent to a decryption oracle.
Practically speaking, the attacker just needs to get his victim to encrypt something that he already encrypted earlier. Do not underestimate this attack; it is often easier to trick the victim into encrypting something than you might suspect.

Note that many block ciphers do use involutions in their structure. This could be useful, for example, to reduce the size of the implementation.

What about stream ciphers?
In a stream cipher, the state of the cipher constantly changes. This effectively means that the function $F$ is variable, so you'd need a much stronger oracle (which can somehow rewind the state).


Send an encrypted question and return answer without decryption

Is it theoretically possible? Yes.

Is it practical? Absolutely not.

In your scenario, there are two approaches, but both are pretty much theoretical only.

First, there is fully homomorphic encryption (FHE). This means, you can do computations like addition and multiplication of ciphertexts and get another encrypted message. To actually have some of your usual search algorithms transferred into an "encrypted mode", you would also need things like checking for equality, etc., where you could use other cryptographic primitives, like zero knowledge proofs, OT, secret sharing, ...

But FHE is not practical, because it has a very high constant factor for the overhead. Basically it means, instead of using a modern top-notch computer, you have the performance of a 30 year old one (or older).

Then, there is searchable encryption... Basically it allows the server to produce a result for your search query. But that is not along the lines of a google search but more "find this string in the database". It is not the semantic search, but more a syntactical one, where you search for specific objects, attributes, etc.

But basically, it suffers from the same weakness as FHE: It is not practical. In cryptography, something is efficient if it is polynomial. But for practical usage this is not enough, because constant factors and exponents matter - even if they are theoretical efficient (e.g. $2^{1000}\cdot n$ and $n^{1000}$ are unusable in practice, but they are polynomial)


Homomorphic encryption - Why does addition not imply multiplication?

There are at least two problems;

The $b$-times addition leaks the $b$. A semi-honest observer can see that you add the $a$ by $b$ times. However, in FHE, the $b$ is also encrypted with semantically secure that leaks no information. The only information available to the observer is the circuit.
In FHE, the $b$ is coming (or may come) from another result, which means that $b$ is also encrypted. In additive PHE, you cannot multiply by $b$ without decryption.

You can look at some example of FHE circuits from this answer to see that some of them are not even possible with additive PHE.


Is there a difference between private key cryptography and symmetric encryption?

Private key cryptography is often used as synonym for symmetric cryptography, that is, cryptography with constructs that use a symmetric key. For instance professor Katz uses this terminology.

Symmetric keys can be used for e.g. a block cipher such as AES, a stream cipher such as RC4. HMAC - which is a keyed hash construct - also uses a symmetric key, and doesn't use a cipher at all. The term "symmetric encryption" is usually limited to constructs that provide confidentiality, although authenticated ciphers may also provide integrity and authenticity of the encrypted messages.

So the question " Are there Private Key Algorithms that do not use Symmetric Encryption?" has the response "yes" for the simple reason that HMAC it does not provide encryption, and it is certainly a private key algorithm. Symmetric encryption which is a goal rather than a construct uses certain private key algorithms to accomplish the goal.


Yes, you are correct.

The modulo operation (in general, not only over polynomials) is defined such that this is always true:

$A \equiv A + B\ \  (\bmod\  B)$

Thus, if $A = X^3$ and $B = X^3+X^2+1$, that implies that $X^3$ is equivalent to the sum of $X^3$ and $X^3+x^2+1$, which is $X^2+1$, which is represented by $101$.


Burmester-Desmedt (BD) key agreement protocols

All this work is done modulo the prime $p$ (which is 11 in your toy example); in this field, addition, subtraction and multiplication is done in the usual way (except you do a modulo $p$ at the end); however division is defined differently.

We define $x = 6/4\  (\bmod 11)$ to be that value such that $x \times 4 = 6\  (\bmod 11)$.

Now, we see that $7 \times 4 = 28$ and $28 = 6\  (\bmod 11)$, hence $6/4 = 7$.  And, yes, if $p$ is prime, and if what you're dividing by is not zero, then it turns out that such division is uniquely defined; there will always be precisely one number between 0 and $p-1$ that meets this criteria.

How do we find such values $x$.  Well, when $p$ is small, you can just test the various possibilities (like I did in this case).  However, if $p$ is large, you can efficiently find such values using the Extended Euclidean Algorithm


If $G'(s)=G(s0^{|s|})$ and $G$ is a PRNG, is $G'$ necessarily a PRNG?

Suppose g is a PRNG. $\:$ Define G by the following pseudocode:

def G(w):
 m = length(w)
 n = ceiling(m/2)
 set x equal to the n leftmost bits of w
 set y equal to the m-n rightmost bits of w
 z = concatenate(g(x),y)
 output z

In this case, G is a PRNG and G' is not a PRNG.