If a new hash function were made that simply truncated sha-256 to the first N bits, how much insight would it provide into sha-256?

If this provided any insight, we would consider SHA-256 to be broken.  In general, we expect the $n$-bit truncation of SHA-256 to resemble an $n$-bit uniform random function.  For example, finding a 10-bit partial preimage costs an expected ${\approx}2^{10}$ trials; finding a 10-bit partial collision costs an expected ${\approx}2^5$ trials.

That said, there are often simplified versions of cryptographic primitives for study:

One obvious simplification of SHA-256 is to reduce the number of rounds from 64—for SHA-256 as for most cryptographic primitives with rounds, the first (and, for unbroken cryptosystems, only) attacks published in the literature are on reduced-round variants.
Aside from varying the number of rounds, Keccak supports any power-of-two word size from 1-bit to 64-bits; SHA-3 is based on 64-bit Keccak with a 1600-bit state, but you could study 1-bit Keccak with a 25-bit state (with any number of rounds).
The SHA-3 candidate BLAKE came with several toy versions BLOKE, FLAKE, BLAZE, and BRAKE.


Are sufficiently large key sizes enough to deter quantum attacks for symmetric key ciphers?

Current understanding of quantum cryptanalysis suggests: Generally, yes.

Symmetric crypto tends not to have any mathematical structure that can be exploited by, e.g., Shor's algorithm, so, absent specific quantum cryptanalysis of a specific primitive (which would be a remarkable publication about the specific primitive), the adversary is limited to the generic Grover's algorithm.

Grover's algorithm searches among $n$ possibilities for a preimage under some fixed function in $O(\sqrt{n})$ sequential qubit operations—for example, it should take about $2^{96}$ qubit operations to find $k$ among the $2^{192}$ possibilities given $f(k)$ where $f\colon k \mapsto \operatorname{AES-192}_k(8432715)$—so the conventional wisdom is that you just need to double your key sizes to attain the same security level against a quantum adversary as you had against a classical adversary.

Even better, a recent estimate with more careful attention to realism of cost models suggests that owing to Grover's poor parallelism in contrast to classical brute force, it doesn't take much to thwart generic quantum attacks in more practical terms—if AES-128 is construed to provide 128-bit security against a classical adversary (which is debatable in the multi-target setting!), even AES-192 should provide 128-bit security against a quantum adversary, for example.


Given $P=xG$, prove in zero knowledge that I know $sqrt(x)$

My answer simply extends the comment by SEJPM.

Since the group has prime order (as you said in the comment), and since you assume that it is known that $x$ has a square root, you can simply prove knowledge of $x$ such that $xG = P$, using the standard Schnorr protocol for demonstrating knowledge of a discrete logarithm (see e.g. the wikipedia page, or my description here for a simplified security analysis of this protocol).

Now, since knowing $x$ is equivalent to knowing $\sqrt{x}$ in a group of prime order (each can be computed from the other in polynomial time), convincing the verifier that you know $x$ does also convince him that you know $\sqrt{x}$. Since the proof leaks nothing about $x$, it leaks nothing about $\sqrt{x}$.


Well, one obvious method (which assumes that either there's a point on the elliptic curve with $x=0$, or the verifier doesn't check if $R$ is on the curve) is:
$$m1 = 0$$
$$R1 = (0, y)$$
$$s1 = 0$$
This satisfies the verification equation...


Where can I find useful data for cryptography/coding theory?

Generating prime integers and computing things modulo integers is easy with a programming language which features support for big integers. I usually use Java: it includes java.math.BigInteger, with which one can:

generate prime integers of any length;
do all basic operations, including modular reduction (mod() method);
compute modular inverses (modInverse());
compute modular exponentiations (modPow()).

For irreducible polynomials, things are more complex: Java does not offer a generic method for testing irreducibility of polynomials (or, for that matter, anything related to polynomials). I do have my own library but it is not generally available (I implemented it for a customer). However, my friend Google points out that this library appears to be fairly complete in that area.


How do Alice and Bob perform key exchange through a third-party (server) in end-to-end encryption?

If Alice and Bob have no relevant secret knowledge not known to eve which controls the communication channel between them, it is impossible to create a seecure communication channel.
Any protocol used, including diffie hellman, double ratchet socialist millioner or anything else can still be used with a MITM attack.

Eve takes the role of Bob when talking to Alice and the role of Bob when talking to Alice. Agreeing on two separate keys. The socialist millionaire will do no good because Bob shares a key with Eve.

To make this work we need either a pre shared public key for at least one party or a secondary communication channel to verify same key is used. We could use a public channel which everyone sees but Eve does not control. We could meet IRL and compare keys. We can use a voice channel assuming Eve won't be able to synethesize our voice in real time to recire a key commitment.(Deep learning is rapidly making the last assumption dubious).

Key exchange protocols work great with a passive eves dropper or when we have an authentication mechanism.


What they are calling a "group cipher" is much more commonly referred to as proxy re-encryption. Proxy re-encryption is typically asymmetric but I don't think there is anything prohibiting it being symmetric. It has many applications (see this list) but most of these applications are using the asymmetric variants. I myself cannot point to another application of symmetric proxy re-encryption.

One drawback is that it is almost as expensive as an asymmetric scheme, so there is little reason to prefer it with today's computational abilities.

Another is that it requires a small multi-party computation between the three parties so that the third party learns the ratio key without Alice or Bob learning it, or the third party learning anything other than it. This MPC requires secure channels, which for all scenarios where at least one pair of parties haven't exchanged keys in-person, this means using asymmetric cryptography to setup the channels.


Note: This is not (yet) a full answer, but I'm posting this anyway in the hope that I or someone else might be able to complete it later.  Please don't upvote this yet.  If you can fill in the gaps in the vague proof sketch below, please do so; if you post it as a separate answer, you'll have my vote.

It's pretty trivial to show that, if AES-CBC is secure and the keys are independent, then both of your schemes will also be secure.  Of course, that's not a very interesting result, so, to get something more interesting, we'll need to assume that AES-CBC is somehow not secure enough by itself.

Of course, we could hypothesize all kinds of attacks on AES or on your use of the CBC mode, but, to keep things simple, let's just assume that the security of the AES layer is completely lost because the attacker knows your AES key.  (This assumption also has the advantage that, besides being just about the worst-case scenario imaginable, it also seems a lot more plausible in practice than any hypothetical cryptanalytic attack on AES.)

CBC encryption using a secure block cipher normally provides IND-CPA security, assuming that the attacker cannot predict the IV and that the message length is fixed (i.e. not useful to the attacker).  It's easy enough to show that, assuming that Serpent is a secure block cipher, and that you implement CBC correctly, your first scheme is also at least as secure as Serpent-CBC alone, and thus also IND-CPA secure.

The remaining question then is:

  Assuming that the attacker knows the AES key (but not the Serpent key), and that both AES and Serpent are secure block ciphers, does the construction Serpent-ECB( AES-CBC( $m$ ) ) provide IND-CPA security?

Intuitively, provided that the CBC IV is chosen randomly, it seems that the answer might, in fact, be yes, although I have no proof of this yet.

In particular, we have the following lemma:

  Lemma: If no plaintext block is ever encrypted twice, ECB mode instantiated with a secure block cipher is IND-CPA secure.

(Proof omitted, but it's kind of intuitive: a secure block cipher looks like a random permutation, and two outputs of a random permutation are indistinguishable if you've never seen either of them before.)

So the question becomes whether an adversary who:

a) knows the key,
b) can choose the messages, but
c) does not know the IVs in advance

would be able to force the output of CBC encryption to contain the same block more than once with a non-negligible probability.

Of course, this might happen by chance, if the number of encrypted blocks gets close to the birthday bound, although it's not quite clear whether such random collisions actually provide any advantage to the attacker.  Still, even if they do, we may avoid this issue by assuming that the total number of blocks the adversary can ask to be encrypted is much less than $2^{64}$.

We can also show that, even if the attacker knows the CBC mode encryption key and can choose the plaintext to be encrypted, as long as the IV is uniformly randomly chosen and unknown to the attacker when they choose the message, each of the ciphertext blocks, considered individually, will also be uniformly random.

However, that's not quite enough to show that the attacker would not be able to introduce correlations between the ciphertext blocks, possibly causing them to repeat more often than expected.  Intuitively, that should not be possible, if the block cipher used is, in effect, randomly drawn from a secure pseudorandom permutation family, but I'm getting too tired to be able to show this right now.


Verify product without revealing multipliers

You are asking the wrong question.  You shouldn't do it the way you described (by multiplying or adding random numbers submitted by the participants).  This problem has been well-studied, and there are solutions to it.  Your question assumes a particular approach to the problem, but that approach turns out to be flawed.

Your approach is vulnerable to numerous security problems.  For instance, if you multiply, any one participant can force the final result to be 0 by just submitting 0 as their contribution.  As another example, if you add, any one participant can force the final result to be anything they want, by waiting for everyone else to submit their contributions, looking at their contributions, and then choosing their own contribution so they all sum to the desired result.

Instead, if you want to jointly generate a community random value that none of you can influence, here is what you should do:

Each party picks a random value, and publicly commits to it.  In detail: the party Pi should pick a 128-bit random value ri and broadcast yi = Hash(ri, Pi).
After everyone has received everyone else's commitments (yi values), then each party should open their commitment.  In detail: once party Pi has received all n-1 commitments, he/she broadcasts ri.  Everyone checks that each published ri value is consistent with the earlier commitment yi.  If anyone detects any inconsistency, or if anyone doesn't finish the protocol, you have to call the whole thing off and punish whoever didn't follow the instructions.
Finally, compute R = Hash(r1, r2, ..., rn).  The value R is the random value that everyone has jointly generated.

The security property we get is that no one party, or no coalition of a subset of the parties, can influence the final random number R, except by refusing to finish the protocol.

(You'll have to have a separate out-of-band way to punish parties who don't follow instructions or don't finish the protocol.  The scheme above describes how to detect such parties; it will be up to you to adequately disincentivize such behavior.  If a malicious party Pj is willing to possibly decline to finish the protocol, they can exert modest influence over the final random number R, simply by waiting to be last to reveal their random number rj, checking what R would be if they finished the protocol, and determining whether it is more favorable to them to finish the protocol and end with random number R or to refuse to finish the protocol and leave everyone with no random number.)


The most recent version of the paper indeed seems to be:

Efficient Embedded Security Standards (EESS)
EESS #1: Implementation Aspects of NTRUEncrypt and NTRUSign
Consortium for Efficient Embedded Security
June 20 th , 2003
Version 2.0

(PDF download)

Yet, as you stated, that doesn’t contain any test vectors; just like the previous (v1) paper:

  Appendix B - Test Vectors

  [To be added in future versions]

But you can find test vectors when checking implementations. For example, by looking at the files contained in the directory https://github.com/Yawning/ntru/blob/master/testvectors/

Alternatively, you could take a look at the files contained in the NTRUOpenSourceProject directory https://github.com/NTRUOpenSourceProject/ntru-crypto/tree/master/reference-code/Java/Encrypt/com/securityinnovation/testvectors/ (see NtruEncryptTestVector.java file)


AES is deemed secure because:

Its building blocks and design principles are fully specified.
It was selected as part of an open competition.
It has sustained 15 years of attempted cryptanalysis from many smart people, in a high-exposure situation, and it came out relatively unscathed.

Another reason, which is not as good but felt important by many people:

It was designed by non-American cryptographers.

In asymmetric cryptography we often (try to) reduce security to a "known hard problem", a luxury which is not often encountered in symmetric cryptography, but this does not change the conceptual root of the issue: at some level, there is some "problem" for which no efficient solving algorithm is known, despite decades of research. It is not proven that the problem is necessarily hard, or even that there can exist such as thing as a necessarily hard problem, but we are just stumped when it comes to finding a solving algorithm. With AES, the "hard problem" happens to be the AES itself.


The problem is solving for $x$ the equation $g^x\bmod n=a$, given integers $n$, $g$, $a$, with $n$ a large composite too difficult to factor (which implies $n$ is several hundreds bits). It is not stated how instances of the problem are generated.

That is hard at least for some instances of the problem. In particular, if one of the factor $p$ of $n$ is large (say, at least 1536-bit), and $p-1$ has a large factor $p_0$ (say, at least 256-bit), and the order of $g$ in $\Bbb Z_p^*$ is $p_0$ or a larger multiple, then an instance of the problem where $x$ was chosen at random in $[1,n/2]$ and $a$ computed as $g^x\bmod n=a$ is hard. Argument: ability to solve $g^x\bmod n=a$ for $x$ and knowledge of the factorization of $n$ trivially implies ability of solving $g^x\bmod p=a\bmod p$ for $x$ (modulo $p-1$), which is is believed hard; and lacking knowledge of the factorization of $n$ can only make the question's problem harder.

I conjecture without proof that the condition "$p$ large" can be replaced by the existing "$n$ too difficult to factor"; and that a random instance is hard.

Among the usual Discrete Logarithm methods, Baby-step/Giant-step and Pollard's Rho remain applicable, with cost $O(\sqrt x)$ multiplications modulo $n$ (and moderate memory for Pollard's Rho). That allows to solve instances with moderate $x$ (say 80-bit with a standard PC), but I see no better method to solve a random instance.


Can "Approximate Hashing" work in a Proof-of-Work context?

In the paper the following remark is probably most important:

  For example, observing the frequency-error
  characteristics of Figure 4, the hashing cores corresponding
  to both approximate adders, $\operatorname{GDA}_{(1,4)}$ and $\operatorname{KSA}_{16}$, have negligible error rates at nominal frequency. Also, their nominal
  operating frequencies are higher than their non-approximate
  counterparts, $\operatorname{CLA}$ and $\operatorname{KSA}_{32}$ respectively.

It is further also said that $\operatorname{KSA}_8$ doesn't work because the error rate is so high that the SHA-256 hash is (almost) 100% certain to be wrong.

So it is clear that the double SHA-256 hash still has a large success rate, to be precise the error rate of the "core hash function" is
$7.27 × 10^{−3}$ for $\operatorname{GDA}_{(1,4)}$ and $8.79 × 10^{−2}$ for $\operatorname{KSA}_{16}$. Apparently that is small enough an error rate to be good enough compared to the (estimated / calculated) increased speed and reduced die size. This is not that strange, you should just be able to multiply the success rate of the double hash $(1-\varepsilon)^2$ with the speed increase.

Note that incorrect positive results results are not much of an issue within BitCoin; if you find a hash you can very easily verify the result (a correct hash is currently found every 10 minutes, and an approximate hasher is unlikely to change that frequency).

Obviously there is also the problem with missed, correct hashes. This means that - apart from the higher speed mining - there there is also a small amount of blocks missed that should contain a bitcoin. This should however not matter much; it's not known in advance if a block contains a coin and the amount of blocks missed will be minimal.


Subkey generation in OMAC1/CMAC with XTEA?

Look at how the keys $K_1$ and $K_2$ are used in CMAC (pdf, Section 6.2):

  If $M_n^*$ is a complete block, let $M_n = K_1 \oplus M_n^*$; else, let $M_n = K_2 \oplus (M_n^*||10^j)$, where $j = nb-Mlen-1$.

They are combined with message blocks using XOR. So they must be equal in length to the block size, not the key size (if different), of the cipher.

Similarly, then, $C$ is determined by the block size.


Formal definition of (perfect) forward security/secrecy

Do you have a specific application domain in mind?
I do not know of any formal definition that spans multiple application domains.

A formal definition of Perfect Forward Secrecy for the domain of key exchange protocols is included in this paper:

Beyond eCK: Perfect Forward Secrecy under Actor Compromise and Ephemeral-Key Reveal


What are the random variables in Universal Hash Function?

The random variables are $k_0$ and $k_1$, typically taken to be uniformly distributed in $\mathbb Z/p\mathbb Z$ in this context.

(Sometimes we take $k_0$ to be uniform in $(\mathbb Z/p\mathbb Z)^\times$ instead, i.e. exclude $k_0 = 0$, but as long as $p \gg 2^{100}$ this is not important.)


Is it possible to guarantee a SHA-256 hash will begin with a certain 3 bytes?

Cryptographic Hash functions are deterministic random functions. Deterministic means the same input the same output and random in a sense mean that the output is unpredictable. We expect that the hash functions have avalanche effect that whenever one bit complemented from the input, each of the output bits flips with a 50% probability.

If it is possible to find a specific first 3-byte faster than the hashing random inputs this actually means that someone found a weakness in the hash function. There is no known such weakness in the SHA-256.

Note: By the design of the SHA-256 (or the family), even there is a non-random method for the first 3-byte, with high probability, the other bytes will have, too.


Is there any strong enough pen-and-paper or mind cipher?

"Strong enough" is a broad term. Some things that you need to keep in mind are entropy size and cryptanalysis. "Strong ciphers" are ciphers that have shown to have enough entropy to withstand practical attacks over time from public scrutiny.

With that said, the Solitaire cipher has a keyspace of roughly 238 bits. By comparison, many SSL keys on the internet are 128 bit AES. Distributed.net is currently working on cracking a 72 bit key, via brute force, at a pace of about 300 billion keys per second, and they have well over 100 years before the keyspace is fully exhausted.

So, for the Solitaire cipher to not be taken seriously, it needs to show practical weaknesses outside of brute force searching. So far, the only weakness that has been demonstrated is that the output has a bias of 22.5:1 rather than 26:1 pure random output would have. This isn't severe enough to mount a practical attack.

As such, until other attacks are made known, to Solitaire cipher is a "strong" hand cipher, that doesn't have NSA influence, can be used without incriminating tools and is easy to learn and remember.


So I heard that Twofish is much more secure than AES, because it is not vulnerable to bruteforce and only supports 256 bit .

Neither AES nor Twofish is vulnerable to brute force attack on the key in practical scenarios. Both support key sizes of 128, 192, and 256 bits, which makes them equally resistant to brute force attack.

Also I heard that is not vulnerable to most side channel attacks .

Quoting wikipedia:

Twofish's distinctive features are the use of pre-computed key-dependent S-boxes...

The use of pre-computed tables can be vulnerable to side channel attack. The table(s) contents are key-dependent, so the situation is not exactly the same as it is for AES (where the table(s) contents are known by the adversary), but it's still a cause for concern.
Additionally, side channel attacks target the practical implementation, so the theoretical algorithm is not really inherently more or less secure in regards to side channel attacks (some are just easier to secure then others). There are still concerns such as Power Analysis, Acoustic Analysis, Rubber Hose Cryptanalysis, etc.

And Twofish might be much more secure because there is no known attack to it , while in AES there is a known theoretical attack .

There are theoretical attacks on Twofish. Wikipedia has a section on the side:

Best public cryptanalysis
Truncated differential cryptanalysis requiring roughly $2^{51}$ chosen plaintexts.
Impossible differential attack that breaks 6 rounds out of 16 of the 256-bit key version using $2^{256}$ steps.

So clearly there are attacks on Twofish. They do not constitute a practical break of the cipher; Neither do any of the cryptanalytic attacks on the theoretical AES algorithm (meaning: attacks that do not use side channel analysis).

From what I have heard twofish is not the encryption standard because it is too slow , but has a much higher security index .

This appears to be accurate (as you might know already...)

So are those claims true ? Is twofish really more secure ? Everybody says different things . Would it be the better choice for classified top secret data ?

AES-256 is standardized for use to protect the confidentiality of classified top secret data. Twofish is not. It is not really a choice for people who actually have classified top-secret data to protect: AES-256 is the answer.


How does one calculate the cryptoperiod?

This is all about the question of risk assessment.  Are you willing to risk all devices together so that if one key is compromised, they all have to be returned?  What is the cost of one return, 100 returns, or 100,000 returns?  What is the expense of issuing a master key?  Of issuing ten master keys?  Of issuing a thousand?

Do you have an estimate for how hard it might be for an attacker to compromise a device and extract the key?  Is it a year's effort?  Is the payout worth it to an attacker to spend a million dollars to obtain your keys?  If he breaks it once for a million dollars, does cracking a second key cost him another million, or does it only take him an additional four hours?

Cryptoperiod doesn't enter too much into this discussion, other than you should also consider "time" as one of the factors.  If someone hacks the key out after a year of owning it, does that mean all your 2012 model devices are compromised?  Or if you don't change the keys every period, that means every device you make from 2012-2017 are all equally at risk from a single compromise.

Where time plays a more important role is in the length of protection needed for your secrets.  Consider a DishTV receiver.  The session key is only needed as long as the transmission lasts, because most Dish pirates don't record an encrypted stream in hopes of decoding it next year after cracking the keys - they only want their Dish to work right now.  Those keys don't need the same duration of protection that a long-term valuable (like a credit card number) requires.

The large number/short period vs. small number/long period idea is one way to help you estimate the overall number of exposure per key.  If you're deploying an encrypting radio to 100,000 people, and they're each going to use one session key per radio per day, that's X amount of traffic.  If you deploy encrypting radios to 100 people, but each goes through a thousand session keys per day, it's the same amount of traffic.  If you think you can only afford to risk one million session keys per primary key, your cryptoperiod would be 10 days.


The two conditions indeed represent different things. Consider the function that, given an $n$-bit input, returns $n$ zeroes. This clearly meets the second definition (if you have $n$ zeroes, a randomized algorithm has just a $1/2^n$ chance of guessing the input, because any $n$-bit input returns that output), but it also clearly fails the first ($A$ is just "return $0^n$"). So the first condition is not weaker than the second; in fact, anything failing the second clearly fails the first (you just use the same algorithm $A$, and use $A(f(x))=x$ and so $f(A(f(x)))=f(x)$). So the first is in fact stronger than the second.

The key difference between the two is that the second is just about finding the exact input we fed into the function. If a function meets this condition, then it means an attacker who knows the output isn't going to figure out our actual input. But that's often not what we're concerned about. In many schemes, it's a problem if the attacker can find any input to get a given output, whether or not it's the actual input we used. Condition 2 asks for the inverse; condition 1 just ask for an inverse, and if the function isn't one-to-one there's a difference between the two. In crypto, one-way functions tend to be used where finding an inverse is a problem.

To use a password hash as an example, suppose my password is swordfish, which hashes to ABCDE1234, and the hash function meets condition 2 but not condition 1. Because of (2) you can't efficiently figure out that my password is swordfish, but because it fails (1) you can find something that hashes to ABCDE1234 (say, letmein12). Sure, you didn't get my password, but you found some inverse of ABCDE1234, and it doesn't help me that you didn't get my password - letmein12 works just as well for your purposes.


Can an AES-GCM be cracked if the key is known but the nonce isn't?

You'll have to guess the plaintext of at least one block (128 bits) that is on a 128 bit boundary from the start of the GCM ciphertext. Then you can XOR it to retrieve 128 bits of the key stream.

Now the key stream you can decrypt since you have the key. This will get you a counter value. The counter in GCM mode starts with a 12 byte nonce and the counter as four bytes: 00000002 in hexadecimals. Once you have that nonce you can generate all the other required nonce + counter values.

So yes, it is possible, but only if you can guess at least one block of the plaintext.


how to mathematically prove a key exchange algorithm

I guess the best place to begin is with the paper that started it all: Entity authentication and key distribution, by Bellare and Rogaway. In a nutshell, they define a protocol to be a secure mutual authenticated key exchange if it fulfills the following four criteria (I will explain the term "matching conversation" below):

Matching conversations $\Rightarrow$ both parties accepts, meaning that both parties believe they are participating in an authentic session. Note that this is criteria is basically a simple "sanity check" of the protocol: if there are no adversaries the protocol should "work".
If a party accepts $\Rightarrow$ there should exist some matching conversation out there. This is the first "real" security requirement. What this basically says is that a protocol provides secure mutual authentication if all that an adversary is able to do is act like a wire between the protocol participants. An adversary which faithfully relays all protocol messages between the parties is called a benign adversary.
Benign adversary $\Rightarrow$ both parties obtain the same key and in accordance with the distribution chosen for the key space. Again, this is basically a sanity check of the protocol.
Session key is protected. This means that if the parties managed to agree on a shared key, the attacker should not be able to learn anything about it. This is formalized by a game between a challenger (one of the parties) and the adversary, where the challenger gives the adversary either the real key or a random string (from the same distribution). If the adversary is not able to distinguish these two settings, we say that the session key is protected.

Thus if you are to prove a key exchange algorithm secure you need to show that it provides the four points above. Usually you do this using a reduction to an underlying assumption, like the existence of secure encryption functions and MAC's. The term matching conversation means that if party A sent out ($\alpha$) and received ($\beta$) the following messages: $(\alpha_1, \beta_1), (\alpha_2, \beta_2) ... (\alpha_n, \beta_n)$ (in that order), then B have a matching conversation if he received ($\alpha$) and sent out ($\beta$): $(\alpha_1, \beta_1), (\alpha_2, \beta_2) ... (\alpha_n, \beta_n)$ (in that order). There are some more technicalities to this definition dealing with who sent the first message and so on, but the gist of it is that A and B have matching conversations if they received what the other party sent out (and in the right order).

Note that this is only one approach to this subject and is by no means the right way of defining a secure key exchange. Another common approach e.g. deals with a simulation framework of interactive turing machines, and proves that a protocol simulates an ideal functionality defined in this model. These are in some sense much more elaborate and complex than the simple approach given by Bellare and Rogaway, but are also much more general.


Is a hashing algorithm considered broken if a collision happens under $2^{n/2}$?

If for example we would find a hash collision for SHA256 with $h(x) = h(x')$ …

Yes, pretty much.  Now, I'm not certain what you meant by "$x \land x' < 128$ bit" (total bit length is less than 128 bits, or they disagree in at most 128 bits???), however, it doesn't really matter; finding any collision would demonstrate that SHA256 isn't quite as collision resistant as we had thought.

  Is it then always possible to create more collisions in feasible time or could this hash collision just be considered an "anomaly"?

If $x, x'$ had the same length (or, more generally, used the same number of SHA-256 blocks when hashing), then it's easy to find more collisions; we would have $h(x || Pad_x || y) = h(x' || Pad_{x'} || y)$ for any string $y$ (where $Pad_x, Pad_{x'}$ is the padding that SHA-256 applies when hashing $x, x'$).


I'll expand my comments into a full answer.

Start by examining that you know the value of $r^3$ - this is just $F(r)$.

You know you can express $F(r+1)$ and $F(r+2)$ symbolically. You can do this for any term in the key sequence, but it will be useful to write down $F(r+3)$. Forget any constant terms in the computations because they can be added in at the end.

Do you notice anything about the coefficients of $r^2$ and $r$ in the expressions for $F(r+1)$ and $F(r+2)$? Do they look like the coefficients of any subsequent terms in the key sequence?


Using encryption for authenticating messages (instead of signing)

Since everyone's answers were in the comments and I want to mark this as answered I'm answering my own question based on what I learnt from your comments and further research:

The answer is you simply can not encrypt with a private key. Encrypting with private keys is only possible in theoretical scenarios and only with RSA keys.

And if you try to encrypt with the public key, then you will have to share your private key. And no, they are not interchangeable, most importantly if someone has the private key they can derive both keys from it.

So the only possible way is to sign the message.

This answer could be useful for people like me who have read simplistic online articles about how cryptography works and were led to believe that public and private keys are interchangeable.


Extending key sizes in Salsa20 and ChaCha?

You are correct about extending number of rounds. It is safe to increase number of rounds. In most cases it will increase safety margin.

Removing constants doesn't seem to be a good idea to me, as Salsa20 and ChaCha don't have any round constants. Purpose of constants is also to reduce number of bits that can be controlled by attacker, however key is not assumed to be controlled by attacker. Constants also separate different key lengths. I'm also concerned about sliding attacks, however I don't know, if they are applicable to Salsa20 and ChaCha as they are not a block ciphers.

Setting start value of counter with key will cause same block outputs with different keys at some points as counter will change key.

Even if replacing constants and counter with key is secure, setting 448-bit key into Salsa20 or ChaCha doesn't guarantee 448-bit security. For longer keys cipher (permutation) has to be stronger. Best attack on Salsa20 with 128-bit key breaks 7 rounds, while with 256-bit key it breaks 8 rounds. Also see Keccak permutation distinguishers.

Mouha and Preneel proofed that 15 rounds of Salsa20 is 128-bit secure against differential cryptanalysis. This means Salsa20 with 15 rounds and 448-bit key could possibly be broken with differential cryptanalysis with complexity of about 128-bits.

You could use XSalsa20 to extend key (instead of nonce) by 128-bits. This would be at least as secure as 256-bit Salsa20.


What is the proper way to generate a fixed length key from a variable length password?

Using simply a hash function is not strong enough, even if the key is not stored. We the users tend to choose very crappy passwords, such as "1234" or "password". If you only use a hash function for generating the key, then there are a lot of chances that the generated keys are SHA256("1234") or SHA256("password"). That is, this method is very vulnerable to brute-force attacks. An attacker could simply hash common passwords, similarly to a dictionary attack.

It is also possible to perform brute-force attacks on established key derivation methods, such as PBKDF2 and scrypt, but the probability of success is extremely small. These methods are specifically designed for this, for example by using a salt value (in order to prevent dictionary attacks) and a lot of iterations of the hash function (in order to slow brute-force attacks).


Average number of multiplications in left-to-right k-ary exponentiation

In Algorithm 14.82, you divide the exponent into $2^k$ windows. In the pre-compute stage, you encode those "bit-windows" into products of $x$. All of those bit-windows will be involved in multiplications except the $000...00_2$ window, which will be encoded as 1, hence no multiplication (I'm assuming $x\cdot 1$ is trivial).
Here's the trick: on average you're equally likely to be using the other $2^k - 1$ bit-windows. Another way of saying this is that you have a probability $\frac{2^k-1}{2^k}$ to pick a bit-window that isn't $000...000_2$. How many bit-windows did we split the exponent into? Precisely $\lfloor{t/k}\rfloor$, or $l$.
So the average number of multiplications (that aren't pre-computations or squarings) is $l\cdot \frac{2^k-1}{2^k}$. You don't have to worry about the evenness of the residual bits at all.
Advice
In practice, 14.85 (the sliding window method) is more efficient in practice, even if it's hard to count the number of steps it takes (as noted on page 617). If you're trying to implement something, check that one out. As a real-world example, CPython, the usual C implementation of Python, uses 14.82 for large modular exponentiation. They choose $k=5$ as that seems to work well in practice.
Example
I copied an example from here to count the multiplications.
Looking at Algorithm 14.82 on page 615, let's say I wanted to calculate $x^{250}$ and let $k=2$, or $b=2^2=4$. Write $250 = (11111010)_2$. With a window of $2$, you have $11|11|10|10$.
First, let's make the pre-computation table: even though we only need $11_2$ and $10_2$, let's follow 14.82 anyway:
$00_2\rightarrow 1$
$01_2\rightarrow x$
$10_2\rightarrow x\cdot x = x^2$
$11_2\rightarrow x^2 \cdot x = x^3$
We have four "bit-windows", only $3 = 4-1$ of which will be involved in multiplying something that isn't $1$.
Now, in the algorithm, step 3.1 is the "squaring" step, except we're multiplying by $x^{2^2}$ each time. After each "squaring" step, we have a multiplication step using the table above. So taking the bits two at a time we have:
$11_2: x^3, x^3$
$11_2: (x^3)^4=x^{12}, x^{12}\cdot x^3 = x^{15}$
$10_2: (x^{15})^4=x^{60}, x^{60}\cdot x^2 = x^{62}$
$10_2: (x^{62})^4=x^{248}, x^{248}\cdot x^2 = x^{250}$
The middle column is the squaring step (3.1), and the right column is the multiplication step (3.2).
So that gives us $2$ multiplications in the precompute stage, $6$ squarings (or $3$ "raising to the fourths"), and $3$ multiplications.
In this example, $t=8$, so $l = 4, 2^k = 4$, so the formula gives $4 \cdot 3/4 = 3$.
If you do the same thing with $k=3, b = 8$, you get $6$ precompute multiplications, $6$ squarings, and $2$ multiplications. In that case, our formula gives $l = \lfloor{8/3}\rfloor = 2$, and $2^k = 8$, so we calculate $14/8 \approx 2$ multiplications. Close enough?


Generate key pair deterministically from a particular seed

Of course it's possible; all you need is take your cryptographically secure input, feed it as the key to a CSRNG, and then use the CSRNG output as the source of randomness to an RSA key generation algorithm.  For a concrete example, there are several such key generation methods in FIPS 186-3, with the cryptographically secure input being the 'seed' (and you would fix all the other various parameters).

This is easy; however this is not cheap.  RSA key generation involves testing various large numbers for primality; depending on the hardware you have (and the RSA key size you are attempting to build), this can take multiple seconds.  Depending on the your requirements, this can be a deal breaker.  In contrast, the key generation method for elliptic curves is cheap; that is undoubtedly why the guys on the web-site selected it.


Is it safe to reuse an IV 100 times to a single key with AES CBC?

Given sufficient resources - maybe.  If an attacker knows text that was encrypted and can associate that plaintext with an encrypted string then they can potentially work on figuring out what the other strings encrypted with the same IV are.  Can they simply derive the plaintext using some formula though?  No.  If you're encrypting textual data it's easier to determine than binary data.
You have another problem in that it's generally recommended to limit the total amount of data encrypted with a single key (no matter how many IVs get used).  In the book Cryptography Engineering Ferguson and Schneier recommend a limit of around 64 GB for CBC mode (assuming you're using AES).  So, if your billion records are more than 64 bytes each you'll start bumping into that.  This is a recommendation based on what they believe to be an acceptable risk of leaking data.  You could potentially encrypt 128 GB or 256 GB and be fine.  Or if you want the data to be safe for a number of years in the future without having to re-encrypt the data you might want to take it down to 8 GB or even 4 GB per key.  It just depends on the level of risk you're willing to take.


The RSA encryption that you seem to be using is specified in PKCS#1, I've linked to the latest version, 2.2:

rsaEncryption    OBJECT IDENTIFIER ::= { pkcs-1 1 }

where

pkcs-1    OBJECT IDENTIFIER ::= {
    iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) 1
}

with the description:

  The object identifier rsaEncryption (see Appendix A.1) identifies the
     RSAES-PKCS1-v1_5 encryption scheme.  The parameters field associated
     with this OID in a value of type AlgorithmIdentifier SHALL have a
     value of type NULL.  This is the same as in PKCS #1 v1.5.

So your application is using PKCS#1 v1.5 padding. Attacks on textbook/plain/raw RSA - which you mention in your comment - are therefore not possible.

PKCS#1 is secure for static text, but it may be vulnerable to the Bleichenbacher attack that uses a padding oracle to try and find the message - in this case undoubtedly the secret key that is used to encrypt the actual data.

However, you've indicated that your ciphertext is signed. If we assume that this signature is correctly verified (and you'd be amazed how many times it is not) then this attack is not possible.

Of course, signing the ciphertext also has drawbacks: the encryption is lost for the plaintext message. More importantly, the scheme is not protected against the removal of the signature or the replacement of signatures. So an adversary can try and show that the message is theirs by simply substituting his own signature.

Signature substitution sounds horrible, but it may not be a problem if only signatures are accepted from one or more specific, trusted parties. In that case substituting the signature will simply result in the message being rejected by the receiving party (who hopefully knows what to do when receiving such message).

Conclusion: I would deem the current scheme secure. The fact that RSA PSS is used for signing gives hope that the person creating the scheme knew what she was doing. There seems to be no pressing need to implement OAEP instead.


AES has a 128-bit block size, period. The valid key sizes are 128, 192, and 256-bits.
I am not sure what you mean by that, a "block" is a 128-bit group of data, being the input and output to the cipher, it does not receive anything. Please revise that part of the question, and I will adjust my answer.
CTR, OCB, and ECB are the only modes I know that can run encryption on blocks independent of eachother. CTR is the obvious choice for a fast secure implementation and turns the block cipher into a stream cipher. OCB is a more complex mode built on ECB, where both the input block and cipher output are modified using an incrementing counter generated from a nonce, and provides 1-pass authentication.


Probability of same input as output in AES 256

Normally you don't enter keys at all. Maybe you enter passwords which then get transformed into keys. The only time anyone normally enters keys is during testing and possibly during key management (e.g. backing up a key in multiple parts, printing it on paper).

Even if AES does output the same bytes as the key, it doesn't matter as long as the bytes are random; the attacker would never know about it. So the only reason to even worry about this is when you want to use AES to derive keys. The output of AES is a pseudo random permutation where each result is as likely as the other. AES has no "weak keys" where the output has special properties, so you cannot enter a weak key by mistake.

As already indicated, AES has an output of 128 bits, so it will never output 256 bits by itself. You'd need a mode of operation such as ECB, CBC or CTR to do so. The output of AES with a mode of operation depends on the protocol and mode of operation itself.

To derive keys you'd better use a Key Derivation Function (KDF) though. Password Based KDF's are used to turn passwords into keys. Well known ones are scrypt, bcrypt, PBKDF2. If you want to derive other keys from a master key, you can use a Key Based KDF such as HKDF. If you must use AES, use a counter mode KDF specified in NIST SP-800 108.

One of the good things about KDF's is that you can specify the output size to be 256 bits. There are other properties such as having a label, performing key stretching and optionally using a salt that make them much better than a plain hash or block cipher to derive keys.

Beware to never mix up text and binary. All modern cryptographic primitives operate on bytes. You need character-encoding (e.g. UTF-8) and possibly encoding (e.g. base 64) operations to convert between text and binary.


I believe that, if you make a plausible-sounding assumption on the SHA256 hash compression operation, you can show that the only malleability SHA256 has are length extension attacks.

This plausible assumption is that, for a fixed input state, then the mapping between message block and output state acts like a random oracle [1]

With this assumption, suppose we a message $M_0$ which, after SHA-256 padding, is the sequence $N_0$, and a message $M_1 = f(M_0)$, which, after SHA-256 padding, is the sequence $N_1$, and we assume that $M_1$ does not have $M_0$ as a prefix (if it is, then this is a length extension attack).

If $M_0$ does not have $M_1$ as a prefix, then we can show that, after some integral number of SHA-256 blocks, $N_0$ and $N_1$ differ; at this point, the SHA-256 hash compression operation will map their states to random values, and after that point, the latter SHA-256 hash compression operations will continue to map the states to random values, and so the outputs will be effectively random (and hence you cannot compute one from the other).

And, if $M_0$ does have $M_1$ as a prefix (the attempted attack is a "length shortening attack"), then $N_0$ may have $N_1$ as a prefix; if it does, then the intermediate state of $M_0$ processing cannot be determined by the final $M_0$ output value (as it is effectively random), and $N_0$ doesn't have $N_1$ as a prefix, then the previous reasoning applies.

This argument is a bit hand-wavy; I believe that it's essence is valid.

[1]: Note that we cannot make the assumption that the entire hash compression operation acts as a random oracle, because we know how, given a message block $M$ and a delta $\delta$, we can find input and output states $S_0$ and $S_1$ with $S_1 = \text{Compress}( S_0, M )$ and $S_1 = S_0 + \delta$; this shows that the hash compression operation itself is distinguishable from a random oracle.


SHA-1, like the earlier MD5 and SHA(-0), and the later SHA-2, is built per a carefully devised hierarchical design:

Merkle-Damgård at the outer, building a collision+preimage-resistant hash with a security argument based on a fixed-width compression function.
Davies-Meyer to build that compression function, with a security argument based on a block cipher with strong related-keys security (message blocks are the key).
Iteration of unbalanced Feistel rounds to build that block cipher.
Sort of an Add/Rotate/Xor (ARX) strategy with Shift/AND selectively added to implement the necessary non-linear round functions of the block cipher and of its key schedule.

The only distinctly haphazard aspect is the multiple non-linear functions changing after 20 rounds. That's an idea inherited from MD5, and it did not much help SHA(-0) or SHA-1. It was dropped in SHA-2, in favor of a uniform round function combining several non-linear functions. That was a reasonable move.


Key clamping in curve25519 not evident in generated key's binary representation

The clamping happens as part of the key agreement / signing procedure. The private key itself isn't clamped when stored.

(How did you test the numbers you have provided? None of them seem to be multiple of 8. Also recall that curve25519 keys are in little endian.)


This is actually a special case of a more general property of the Euler totient function: it is a multiplicative function, meaning that, for any two coprime numbers $p$ and $q$, $\phi(pq) = \phi(p)\phi(q)$.

The special case where $p$ and $q$ are (distinct) primes is easy to prove.
By definition, $\phi(n)$ gives the number of positive integers coprime to and smaller than $n$, i.e. the number of integers $k$ satisfying $0 < k < n$ and $\gcd(k,n) = 1$.

Since $p$ and $q$ are the prime factors of $pq$, an integer $k$ is coprime to $pq$ if and only if it isn't a multiple of either $p$ or $q$.  In the range $0 < k < pq$ there are $p-1$ distinct multiples of $q$, and $q-1$ distinct multiples of $p$, and a bit of thought shows that these two sets cannot overlap, as any positive number that was a multiple of both $p$ and $q$ would have to be at least as large as $pq$.

Thus, out of the total $pq-1$ integers $k$ in the range $0 < k < pq$, all but $(p-1) + (q-1)$ are coprime to $pq$, and so $$\begin{aligned}\phi(pq) &= (pq-1) - (p-1) - (q-1) \\ &= pq - p - q + 1 \\ &= (p-1)(q-1).\end{aligned}$$


Why was it easier to decode messages that you had several copies of?

Dooley says that simple substitution or transposition were used by both sides from 1914 to mid-1916--for radio, telegraph, and phone messages. Radio became more important in the summer of 1916, and then cryptanalysis became the name of the game for determining order of battle.[1]  Crystal set radio often required messages to be sent repeatedly due to signal attenuation, interference, operator error, etc.  But this is probably not what he was referring to.

Von Bernstorff was likely referring to the debacle of the Zimmermann telegram, where the same message was sent using two different encryption systems from Berlin to Mexico City.  It was a British intelligence coup.  Both cipher systems were weak, but the older one was almost completely broken.

The Germans did that because their embassy in Mexico City did not have their government's more modern cipher book.  Their people in Washington, D.C., fatefully relayed the Zimmermann telegram using an older cipher system.

Unsurprisingly, we have evidence that Von Bernstorff did employ one cipher which probably worked against the British, and that was the null cipher.
David Kahn says how Bernstorff used null ciphers in press cables to get past British collection.[2]

[1]  Dooley, John, F. (2016) Codes, Ciphers, and Spies: Tales of Military Intelligence in World War I (p. 49). New York, NY: Springer.

[2]  Kahn, David (1967) The Codebreakers (pp. 521 and 1063). New York, NY: The Macmillan Company.


It depends on what exactly you want to achieve. I don't know ORUTA.

But in general:
You have to convert your message to a numerical representation somehow. Then the message has to be short enough to be in Zp.

e.g. in Java:

    BigInteger p = [your p value]
    String message = "test message";
    BigInteger m = new BigInteger(1,message.getBytes(StandardCharsets.UTF_8));
    if(m.compareTo(p)>0) {
        not good, your message is too big!
    }

Usually in signature schemes, you use the hash value of the message instead of the message, because a hash function has a fixed output size and for a suitable p you can be certain it is always < p.

This is also quite simple, but if you say you want to compute a hash, it is probably not what you want to do?


Is there FHE (fully homomorphic encrpytion) for string/text processing?

All encryption methods deal with bit or numbers not strings. You can convert your strings into bits and numbers to process. As I understood from your question you are looking for detection of mail provider on the FHE encrypted data.

One way to this is by encoding your data. You can separate the e-mail as the user_name and domain then encrypt and use integer comparison circuit to check. You can find the circuit in this answer

Of course, you can compare without encoding, however, this circuit will be much complicated and slower.

update for implementation

There can be pitfalls on the implementation design. For example, if you only send the encrypted values of the domain names like gmail and hotmail
you may leak information to the server with the size of the ciphertext. To mitigate the problem, first, determine the maximum possible length of all possible domain, then encode the domain names with leading zeros. After that you can call the comparator circuit $\mathcal{C}$; $$\mathcal{C}(c_1,c_2,p_k^{[1]})$$

where $c_1 = enc_{p_k}(\operatorname{encode}(p_1))$ and $c_2 = enc_{p_k}(\operatorname{encode}(p_2))$ with your public key, $p_k$

Once the server returns you the FHE result bit $r$, either decrypt with your secret key $s_k$,

$$cpm(p_1, p_2) = Dec_{s_k}(r)$$
$$cmp(p_1, p_2) = Dec_{s_k}(\mathcal{C}(c_1,c_2,p_k))$$

or use it with some other circuit that you want to calculate.

Note 1: Your data need not be on your site. You can supply the server with the cloud data.

Note 2: If your data encrypted with AES, and deployed into the cloud, you can still compute the comparison circuit, this time the operation is a bit more complex. You need to run an AES decryption FHE circuit so that after the circuit finishes, you don't have plain plaintext around but the FHE encrypted plaintexts. Now, you can call the $\mathcal{C}$ but this time you may need to compare all e-mail.

[1] : Your public key may be required to during computation by the server, like encryption of zero or one. Therefore, you sent it into your circuit.


What is a formal definition of strong one-time-secure signatures?

It's the usual security game for digital signatures, but the adversary is only allowed to make a single signature query.

In other words:

The simulator generates a key pair, and gives the adversary the verification key.
The adversary sends the simulator a message $m$. The simulator signs the message and sends the signature $\sigma$ to the adversary.
The adversary outputs his forgery $(m',\sigma')$.

The adversary wins if $\sigma'$ is a valid signature on $m'$ and $(m',\sigma') \not= (m,\sigma)$.

In the usual signature game, the second step can be repeated many times.


How does secret sharing solve the partial exposure problem?

A simple partial explanation addressing your "random value added", too long for a comment. This works well for the trivial case of two shares: Given a secret $x$, split it into $r$ and $x-r$, where $r$ is a random number. Having both shares, you can get the secret by as their sum.

Having only one share, you can do nothing at all, assuming there are no bounds on the variable values. This wouldn't work with integers, so some finite field gets used, e.g. modular arithmetic with a prime modulus $p$. As an example, consider $p=101$ and $r=42$. Now each secret $x$ is equally possible, e.g., $x=10$ corresponds with the other share $x-r = 10-42 = -32 = 69$ (computed modulo 101). This is what information-theoretic security means in this trivial example.

It's easy to extend this for an arbitrary number shares where all of them are needed to reconstruct the secret. I hope it can help you to understand the general method described elsewhere.


Why is a Diffie-Hellman key exchange required when RSA is already being used for key exchange in TLS?

What is RSA used for during key exchange?

RSA can be used either (a) for signing the key agreement transcript with some other mechanism of key agreement (ciphersuites TLS_*DH*_RSA_WITH_*), or (b) for the client to encrypt a premaster secret key it sends to the server as an authenticated key agreement (ciphersuites TLS_RSA_WITH_*).

The premaster secret determines the key under which records exchanged by the peers in the session are symmetrically encrypted and authenticated, e.g. with AES-GCM.

In both cases, the server does a private key operation to prove its identity: in (a), it signs the key agreement transcript with the server's long-term public key, producing a signature that the client (and anyone else) can verify; in (b), it decrypts the client's premaster secret key, proving it is able to decrypt messages encrypted to the server's long-term public key.

Note that in TLS 1.3, RSA key agreement is going away.

  What is Diffie-Hellman used for?

Diffie–Hellman, over finite fields or over elliptic curves, can be used for ephemeral or static key agreement.

In the ephemeral case, both parties generate and exchange a fresh key pair and use it to agree on a premaster secret key, which they then authenticate by another means, such as an RSA or ECDSA signature.  (Note that in principle you could use DH for key agreement and authentication, but nobody does this in TLS.)

In the static case, at least one of the parties, typically the server, has a long-term DH public key, which the other party, typically the client, combines with a DH private key to derive a premaster secret.  The server proves its identity by deriving the same premaster secret from its private key and the client's (ephemeral or static) public key.  (Static DH isn't used much.)

  Since RSA already provides authenticity and confidentiality, why is Diffie-Hellman used during the exchange?

Diffie–Hellman provides a fast key agreement procedure, with a small number of rounds trips, that supports fast key erasure: as soon as the session is done, all copies of the DH private keys, the derived premaster secret, the derived master secret, etc., can be erased by the peers.  Fast key erasure means compromising the long-term identity keys does not enable retroactive decryption of the session.

In contrast, with RSA key agreement, future compromise of the server's long-term identity key trivially enables an adversary to retroactively decrypt past sessions, because the session keys were all encrypted to the server's long-term identity key.

  I've heard DH exchanges aren't secure. Is that something to be worried about in an RSA with Diffie-Hellman exchange?

There are lots of security issues one might be concerned about.  Maybe your friend is concerned about historical mistakes in supported ciphersuites; maybe your friend is concerned about timing side channels in finite-field arithmetic over general primes; maybe your friend is concerned about dynamic DH group choices and insufficient validation; maybe your friend is concerned about choices of elliptic curves.  But I can't read your friend's mind: you'll have to be more specific.

  If DH is used for forward secrecy. What's wrong with just generating new RSA key pairs and exchanging keys with that?

You could generate a fresh RSA identity key for every session, ask your certification authority to sign a certificate for that key, and then use that for RSA key agreement.

This would be the most stupidly expensive TLS stack ever, because generating RSA keys is extraordinarily expensive compared to generating DH keys (and takes an unpredictable amount of time to boot), sensible certification authorities store their keys in hardware security modules that you don't want to have attached to your TLS front ends, and sensible certification authorities have elaborate audit trails around certificates including Certificate Transparency logs that you can explore at crt.sh.

You could devise an RSA-based key agreement protocol with ephemeral RSA keys and without involving your CA, but RSA keys are still extraordinarily expensive to generate, and it would take additional round-trips between the peers, and you would still have to find some way to authenticate them.


Where did ChaCha20 and Salsa20 stream ciphers get their names from?

idle speculation, my personal favourite! i always thought it was after the dance...

Salsa dance - see the video (Video demonstrating salsa dancing fundamentals) and jump to ~1min05sec in, the section titled: "side-side-quarter-turns", if you'd prefer to remain seated...

and from (https://en.wikipedia.org/wiki/Salsa20), The Salsa quarter-round function. Four parallel copies make a round.


For security, need a 1-1 crypto-mapping be NP-complete?

NP is about worst case hardness. An NP-hard problem can in fact be very easy to solve for the majority of cases. This would obviously be a poor cryptographic system. Further, some NP-hard problems may even be quite easy to approximate. This could also be bad for cryptography.


Use of orthogonal vectors in lattice-based cryptography

Let $\left\{\vec{b}_1,\ldots,\vec{b}_n\right\}$ ba a lattice basis and $\left\{\hat{\vec{b}}_1,\ldots,\hat{\vec{b}}_n\right\}$ be its Gram-Schmidt orthogonolization. Here are some reasons:

It helps computing a reduced basis (an equivalent basis with shorter vectors) using LLL or BKZ algorithm,
The span of $\{\vec{b}_1,\ldots,\vec{b}_i\}$ is equal to the span of $\{\hat{\vec{b}}_1,\ldots,\hat{\vec{b}}_i\}$ for $1\leq i\leq n$,
It helps you finding the volume of the lattice by multiplying the norms of $\hat{\vec{b}}_i$'s rather than computing a determinant.
It provides you upper and lower bounds on successive minimas and smoothing parameter of the lattice.


Commitment schemes for arbitrarily large integers

A small comments: the Damgard-Fujisaki commitment scheme, which you are referring to, does not depend on the strong RSA assumption. If you instantiate it (for example) over RSA group, it is perfectly hiding, and binding under the factorization assumption. However, the soundness of the zero-knowledge protocol for proving relations between integers committed with DJ relies on the strong RSA assumption.
That being said:

In this work, we reduced the assumption for the proofs of relation between DJ-committed integers to RSA instead of strong RSA.
In an upcoming Eurocrypt paper (not yet online, but hopefully very soon), we build a new integer commitment scheme over class groups. The main difference with DJ is that DJ requires a class group with a hard-to-factor discriminant, meaning that you need a trusted setup to generate the parameters. In contrast, we only need class groups with a prime discriminant, which can be publicly generated from a shared random string.
In the same paper, we also build a bounded integer commitment scheme. Unlike the previous ones, the size of the group grows with a bound on the maximum size of the supported integers. However, the scheme still comes with efficient ZK proof systems for proving relations between the committed integers. Furthermore, the commitment and the proofs are secure under the discrete logarithm assumption.
There is always the option of using bit-decomposition of the integer, and committing to the bits, e.g. with a generalized Pedersen commitment (so that the commitment remains compact for arbitrary integers). While this does not directly come with efficient proofs over the integers, for many statements of interest, one can reduce these proofs to statements involving inner products between the committed bits. This was done e.g. in Bulletproof to construct what was (until our upcoming Eurocrypt paper) and still is for some parameters (very large intervals) the most compact range proofs.

As far as I am aware, there does not currently exist any other candidates.


In short: hybrid encryption.

Encrypt the content with a random symmetric key. And encrypt this key with the public key of each recipient.

Then all you need is a public key from all the people you want to share the content with. It doesn't even have to be the same public key cryptosystem for all the receivers.

  It might be they each come up with their own password or ...

Passwords alone are quite useless, and if you just use a password as key in a crytposystem, you screwed up badly. From a practical point of view, the concepts of a key and a password might be quite similar, from a security perspective they are not.

Of course you can design a system, where the users actually have to enter a password to decrypt their locally stored private key, like it is done for ssh keyfiles. But that is another issue.


How do institutions like banks do RSA with big primes?

First of all to encrypt/decrypt data such institutions as banks use some block or stream ciphers for instance AES (Advanced Encryption Standard), which are very fast compared to RSA algorithm, hundreds times faster to process same amount of data. But block and stream ciphers use symmetric key (which is usually 128-256 bits random number, much smaller than RSA keys), it means that both parties A and B who exchange data encrypted with ciphers need to have same symmteric key and for that they need to share securely this key.

To exchange a symmetric key an asymmetric encryption is used. RSA is an example of an asymmetric encryption system. Most asymmetric encryption systems are much slower than symmetric ciphers, mostly due to usage of big numbers (as you mentioned) in computation.

So to exchange a shared symmetric key, used to encrypt large amount of data, we encrypt this key using RSA public key of recipient. Because only small key (e.g. 256 bits long) is encrypted using RSA, quite small amount of time (e.g. 0.5-1 second) is used for that. After that large symmetrically encrypted data and small asymmetrically (using RSA) encrypted key are send to recipient. On the recipient side the opposite is done - first the symmetric key is decrypted using RSA private key and second large data is decrypted using symmetric key with block or stream cipher like AES.

Also usually some integrity check is done, e.g. by using MAC (Message Authentication Code) - MAC is computed on sender side and checked on recipient side. Or instead of MAC a digital signature (using e.g. DSA, Digital Signature Algorithm) is create on sender's side using sender's private key and verified on recipient's side using sender's public key. MAC is an integrity check value created using symmetric algorithms (e.g. AES, 3DES), while digital signature is created using asymmetric algorithms (e.g. RSA or DSA).

To answer your question about large numbers - in order to compute those large exponents by some large modulus arbitrary length big numbers simulation is done with numbers having thousands of bits, i.e. around one thousand decimal digits. I'll give an example of how exponentiation can be computed in a quite fast way instead of straightforward multiplication (which can take forever). All the multiplications, additions, subtractions and divisions are simulated as a huge numbers arithmetic in the memory using algorithms similar to those that we studied at school to e.g. multiply or divide long numbers on paper. To do a fast exponentiation a technique called Exponentiation by Squaring is used. We will compute value of C = M^E (mod N). This algorithm is proportional to the number of bits in exponent E, i.e. does several big number operations (approximately two multiplies and two divisions) per each bit in number E, so if E is from 1024 to 2048 bits (these lengths are usual for RSA) then algo makes around 1024 to 2048 blocks of 2 to 4 arithmetic operations on big numbers. There are two main versions of that algorithm exist, one is iterating through bits of exponent left to right (MSB-first (Most Significant Bit first) order), another one is iterating right to left (LSB-first (Least Significant Bit first) order) (cited from here):

// LSB Binary Exponentiation Algorithm (scans exponent's E bits right to left)
// Input: Exponent: E of k bits, message M
// Output: Ciphertext: C = M^E (mod N)
C =1 ; S = M;
// Scan E's bits from LSB to MSB (right to left).
for i := 0 to k-1
  begin
    // Multiply by degree of M.
    if (E_i = 1) C = C * S (mod N);
    // Square degree of M.
    S = S * S (mod N);
  end;

// MSB Binary Exponentiation Algorithm (scans exponent's E bits left to right)
// Input: Exponent: E of k bits, message M
// Output: Ciphertext: C = M^E (mod N)
C = 1;
// Scan E's bits from MSB to LSB (left to right).
for i := k-1 downto 0 do
  begin
    // Square result.
    C = C * C (mod N);
    // Multiply by M if E's bit is set.
    if (E_i = 1) C = C * M (mod N);
  end;


As shown in the paper Ricky Demer linked in the comments, HMAC can be secure even when the underlying hash function is not collision resistant. Only PRF-ness of the hash function is required, and SHA-1 is not known to lack it. Or a couple of other conditions can suffice even if it isn't a PRF.

Intuitively, it makes sense that HMAC is secure as a MAC even with SHA-1, because a MAC does not allow a collision search. The only way to find the key would be to compromise the preimage resistance of SHA-1. HMAC in turn prevents length extension attacks and the like that would allow a forgery without knowing the key.

As an aside, even HMAC-MD5 hasn't been broken. However, for the same reason as there – attacks only get better – I would recommend not choosing SHA-1 as the HMAC hash for new applications if you can just as easily use SHA-2.


Why does libSTARK use binary fields as opposed to prime fields for zk-SNARKs?

Caution: This answer is about the basics of why binary fields $\Bbb F_{2^k}$ are sometime preferred to prime fields $\Bbb Z_{p}$. It does not cover the specifics there may be for zk-STARKs, libSTARK or FRI.

Binary fields allow the use of XOR rather than addition with carry, and carry-less multiplication. That makes computations of field arithmetic easier, because carries requires code (for large arguments as used in cryptography, especially for SIMD implementations including SSEn), or circuitry, thus power and time. Removing carries removes the need for a trade-of between simplicity and propagation delay in carry lookahead, which is significant for wide-word hardware implementations.

The estimation of a quotient in modular reduction is simpler for a binary field: it can't be off-by-one as occurs in ordinary multi-digit Euclidean division, which makes constant-time implementations easy, removing a possible side-channel.

Squaring in a binary field can be reduced to bit rotation by using a normal basis representation for the field. This in turn allows more efficient scalar multiplication on Elliptic Curve groups defined on some Koblitz curves over binary fields.


Do all AEAD implementations use symmetric key ciphers in practice?

When people say "AEAD", they have symmetric schemes in mind. But conceptually, authenticated encryption is not restricted to symmetric keys. It is just the case that public key variants have not received much attention both in the literature and in practice. But there are implementations. For example, NaCl has an API for public-key authenticated encryption, based on security notions by Jee Hea An 2001. The construction is based on public-key encryption and MACs. This shows that AE in the asymmetric setting is fundamentally different from simply signing encrypted messages, as explained in the NaCL API docs:

The crypto_box function is not meant to provide non-repudiation. On the contrary: the crypto_box function guarantees repudiability. A receiver can freely modify a boxed message, and therefore cannot convince third parties that this particular message came from the sender. The sender and receiver are nevertheless protected against forgeries by other parties. In the terminology of https://groups.google.com/group/sci.crypt/msg/ec5c18b23b11d82c, crypto_box uses "public-key authenticators" rather than "public-key signatures."
Users who want public verifiability (or receiver-assisted public verifiability) should instead use signatures (or signcryption).

Apparently this API and the formalization in the paper do not include the "additional data" (AD) part of AEAD but I don't think there is a fundamental limitation. AEAD as a single primitive in the symmetric setting became popular only after 2001, so I believe Jee Hea An simply didn't think about "additional data" as a useful feature back in 2001.
I can only speculate but I believe one reason why authenticated public-key encryption has not received much attention is that (even unauthenticated) public-key encryption itself is a rarely used primitive. Public-key encryption is useful in a setting where the sender and the receiver are not online at the same time. The prominent example is e-mail encryption but unfortunately e-mail encryption never took off for various reasons (Johnny Still, Still Can't Encrypt), and protocols for e-mail security such as PGP/GPG and S/MIME conceptually separate confidentiality and authentication and implement them via public-key encryption and digital signatures (and not MACs!). Of course these can be combined ("sign-then-encrypt", "encrypt-then-sign" or "encrypt-and-sign") but the responsibility for doing so correctly is mostly pushed down to the user, and the 2001 paper shows that all of these constructions are insufficient. (One reason why PGP and S/MIME wanted signatures explicitly is that you can still have authentication for public emails, e.g., posts to public mailing lists.)
The success of the idea that we should consider authenticated encryption as single primitive with a single misuse-resistant API whose users do no need to be cryptography experts came only later in the symmetric setting after people screwed up in endless ways with constructions like "encrypt-then-MAC", "MAC-then-encrypt", "encrypt-and-MAC", which are the symmetric counterparts to the modes mentioned above. Note however that the symmetric and asymmetric settings are hard to compare when it comes to authentication, e.g., due to the mentioned subtleties with repudiability and public verifiability. MACs and signatures are very different beasts.


How do I unpack the x and y values from the BITSTRING in a DER ECDSA public key?

The first octet in a DER encoded BITSTRING is the number of unused bits (0 in this case). The remaining 65 octets are the elliptic curve point encoded as described in SEC 1 (http://www.secg.org/collateral/sec1_final.pdf) section 2.3.4. The first octet distinguishes the identity point and whether point compression is being used. Since you have 65=1+32+32 octets, this is an uncompressed point and the first octet should be 04, follows by the X and Y values encoded as described in section 2.3.6 (basically fixed length big endian).


How do I calculate CRC32 mathematically?

The most common CRC32 is borrowed from the 32-bit Frame Check Sequence in the 1988 edition of CCITT V.42, section 8.1.1.6.2, available here, which gives a mathematical definition (note: remove the obviously spurious $1$ after $x^{30}$ in the English edition).

I prefer this alternate definition with some of the math on polynomial replaced by equivalent operations on bits:

Consider the message as a sequence of $n$ bits in chronological order (if the message is structured in words or bytes: with low-order bit first unless otherwise specified).
Append $32$ one bits, forming a sequence of $n+32$ bits.
Complement the first $32$ bits of that sequence.
Form the binary polynomial of degree (at most) $n+31$, with term $x^{n+32-j}$ present (resp. absent) when the $j$th bit in the result of the previous step is one (resp. zero), for $j$ with $0<j\le n+32$.
Compute the remainder of the polynomial division of that polynomial by the binary polynomial $x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1$, forming a binary polynomial of degree (at most) $31$.
Form the $32$-bit sequence with the $j$th bit one (resp. zero) when the term $x^{32-j}$ is present (resp. absent) in that polynomial, for $j$ with $0<j\le 32$.
Append that $32$-bit sequence to the ORIGINAL message (if it is to be converted to bytes: the first bit of that sequence shall be the low-order bit of the first byte unless otherwise specified).

Note: Inserting $32$ bits at step 2 allows a receiver to process bits of the message and $32$-bit sequence uniformly as they are being received, without knowing the frontier between the message and the final 32-bit sequence until after the end of that sequence. Step 3 makes it likely that suppression of bits in the message is detected including for zero bits at the beginning of the message.

Note: In term of binary polynomials (according to the conventions in steps 4 and 6), the combination of steps 2 and 3 changes $M(x)$ to $M(x)\cdot x^{32}+\displaystyle\sum_{i=n}^{n+31}{x^i}+\sum_{i=0}^{31}{x^i}$.

Note: Steps 4, 5 and 6 can be replaced by:

repeat until the sequence has exactly 32 bits:

if the first bit is one:

complement the 7th, 10th, 11th, 17th, 21th, 22th, 23th, 25th, 26th, 28th, 29th, 31th, 32th and 33th bit.

remove the first bit.


Pseudorandom zero-sharing: how does it work?

To your question:

About the HMAC example, maybe the hypothesis that $f^i_A(j)$ is not feasible. Because $f_A(x)$ servers as a role somelike base polynomial while $\psi$ servers as a random scalors of these base polynomials.

$f_A(x)$ is constructed in this way: first, we know $t$ roots of $f_A(x)$, then we assign $f_A(0)=1$. Therefore, $f_A(x)$ is a $t$ degree polynomial whose constant term is 1. Besides, other points like $(j, f_A(j))$ are computed by interpolating. We cannot simply treat $f_A(j)$ as 1.

About reconstructing secret 0. Now that we know the secret is 0, why we need to concern about how to reconstruct the secret. I think maybe the real secret, things we want to hide from is coefficients of non-constant terms in $f_A(x)$, because we usually use PRZS protocol to randomize an existing polynomial whose constant term is a secret.

BTW, there is a simpler version of PRZS:

\begin{equation*}
   f(X) = \sum_{A\subset X\text{, }|A|=n-t}\sum_{j=1}^t \psi_{r_A}(a, j) \cdot X^j \cdot f_A(X)
\end{equation*}

Three observations here:

$f_A(X)$ is a polynomial whose degree is at most $t$ with random constant term.
$X^t \cdot f_A(X)$ is a polynomial whose degree is at most $2t$.
$f(X)$ is divisible by $X$ which means its constant term is 0. Beacause $X^1 \cdot f_A(X)$ contributes $f(X)$'s lowest degree.

Therefore, we come to the conclusion that $f(X)$ is a polynomial that $deg(f) \leq 2t$, and $f(0) = 0$.


Assuming the Hash function is "good" (say it obeys the random oracle model, for concreteness) its restriction to 128 bit inputs should behave as like a random function.

This means that it will "miss" roughly a fraction $(1-e^{-1})$ of the $2^{128}$ binary strings in its range. Also, it will, with high probability have a point $y$ in its range (see, e.g., Mitzenmacher's Probability and Computing book), such that $$|H^{-1}(y)|\approx \frac{\log n}{\log\log n}:=M,$$
where $n=2^{128}.$

In fact, iterating this argument, since the remaining points in the range can be considered to come from a random function on $2^{n}-M$ points which would then have a point in its range with inverse image size $$\approx \frac{\log (n-M)}{\log\log (n-M)}$$ and so on.

This is probably not "almost one to one", but it looks like your attack may work with some fixed probability bounded away from zero, if you use multiple P/C pairs to deduce intersections of possible key sets corresponding to the clustered points in the range.


Fully or partially Decrypting Data with Multiple keys

Functional encryption might fit your description; as far as I know it's still far from practical though.


A binary sequence of period $105$ will have characteristic polynomial
that is a divisor of $x^{105}-1$. Since $x^{105}-1$ has irreducible
factors of degrees $12, 4, 3$, and $1$, it is possible to have an LFSR
of length $4+3=7$ generate a sequence of period $105$, and that is
exactly what has happened here. Note that
$$x^7+x^6+x^5+x+1 = (x^3+x+1)(x^4+x^3+1)$$
where $x^3+x+1$ and $x^4+x^3+1$ are irreducible (in fact, primitive) polynomials of degrees
$3$ and $4$. Individually, the shorter LFSRs generate sequences of
periods $7$ and $15$: the "product" sequence has period
$\operatorname{lcm}(7,15)=105$.


How to run a (provably probably) secure global referendum?

Regarding the 3rd part of your question, "Can and should ordinary, run of the mill elections be conducted online ..." - If one thinks of an election as a problem around the issue of preserving the privacy of many inputs (a people or population's votes) while correctly producing the right result (i.e. correctly tabulating the outcome of the election) and moreover, if you would like to do this without relying on a trusted central authority (like the election commission) - there are some central results in cryptography that prove the possibility of such a thing under different adversarial assumptions, starting with the landmark paper of Goldreich, Micali and Wigderson entitled "How to Play Any Mental Game - A Completeness Theorem for Protocols with Honest Majority" - this result falls under the general moniker of "Multi Party Computation" (MPC), and represents a provably positive result for MPC with honest majorities.
Since this paper, MPC has evolved quite a bit and has been promoted, among other things, as a means for secure voting - the more recent SPDZ protocol of Damgard, Pastro, Smart and Zakarias is secure against "active static adversaries" and is able to tolerate corruption of up to n − 1 of the n parties involved in the computation.
In terms of successful applications, the following outlines one of the first applications of MPC techniques (the Danish sugar beet auction) "https://www.cs.purdue.edu/homes/aliaga/cs197-10/papers/bogetoft.pdf"


Estimate password cracking time given Shannon Entropy

Assuming knowing the entropy in the generation process is meaningful, the relationship between difficulty of brute force guessing an unknown random variable  and entropy (or entropies) is quite a delicate one, and depends on the assumptions about the attack scenario.

In particular, the direct use of Shannon entropy can give misleading results, and the best case brute force number of guesses can be much lower than that implied by shannon entropy (say $H_0$ bits, should imply roughly $2^{H_0}$ guesses in the worst case.

One result on the expectation is that the expected number of guesses to determine a random variable  (for the optimal guessing sequence) is upperbounded by

$$2^{_{1/2}()−1}$$
and lowerbounded by
$$\frac{2^{_{1/2}}()−1}{\log |X|}$$
where $H_{1/2}(X)$ is the Renyi entropy. In general Renyi entropy can be much lower than Shannon entropy, hence Shannon gives a misleading result for this problem. See the answers  to this question for details and references.


Is MAC algorithm same at both sender and receiver end

Yes, the MAC algorithm works the same way on both sides. It is a mathematical function that computes the tag from the key and the message. On the sender side, the message is processed as follows:

Calculate T = MAC(key, raw_message).
Send the raw_message and the tag value T. Many communication protocols append them in this order but anything will do as long as the receiver agrees on the format.

On the receiver side, the processing goes as follows:

Parse the received data is parsed as a raw message and a tag value.
Calculate T' = MAC(key, received_raw_message).
Compare T' with received_T. If the values are equal then the message is authentic, otherwise it is not.

SSL does use a MAC to verify data integrity. Strictly speaking, the MAC itself only ensures authenticity, not integrity: a MAC alone does not protect against replay attacks, whereby an adversary repeats a legitimate message. To protect against replay attacks, protocols such as SSL include a nonce in the authenticated message: if the message is genuine and contains the expected nonce, then it hasn't been modified or switched in transit.


Do identical strings always have the same SHA-256 value?

Yes, if you hash the same input with the same function, you will always get the same result.

This follows from the fact that it is a hash-function. By definition a function is a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output.

In practice there is no seed involved in evaluating a hash-function.

Now, this is how things work in practice.
On the theoretical side of things, we often talk about families of hash-functions. In that case there does exist a key that selects which member of the family we are using. The reason for this is a technical problem with the definition of collision resistance.

The naive definition of collision resistance for a single hash function $H : \{0,1\}^* \to \{0,1\}^n$ would be that for all efficient algorithms $\mathcal{A}$ the following probability is negligible $$\Pr[(x_1,x_2)\gets\mathcal{A}(1^n): H(x_1)=H(x_2)]$$

The problem with that is, that it is impossible to achieve. Given that $H$ is compressing, collisions necessarily exist. So an algorithm $\mathcal{A}$ that simply has one of those collision hardcoded and outputs it, has
$$\Pr[(x_1,x_2)\gets\mathcal{A}(1^n): H(x_1)=H(x_2)] = 1.$$
So the definition is not achievable, since this $\mathcal{A}$ by definition exists even though nobody might know what it is.

To solve this problem, we define collision resistance for a family of hash-functions $\{H_k : \{0,1\}^* \to \{0,1\}^n\}_k$.
We then define that such a family is collision resistant if it holds that the following probability is negligible
$$\Pr_{k\gets\{0,1\}^n}[(x_1,x_2)\gets\mathcal{A}(k): H_k(x_1)=H_k(x_2)].$$

Here we do not run into the same problem, because the exact function $\mathcal{A}$ needs to find a collision for is chosen uniformly at random from an exponentially large family. Since $\mathcal{A}$ could have hardcoded collisions for at most a polynomial number of functions in the family, such hash-function families are not trivially impossible.

Note that this means that there somewhat of a disconnect between the theoretical treatment of hash-functions and their practical use.


Why can't you divide by 0 in an Edwards Curve?

Claim:

Both denominators can never be zero if $d$ is not square in $K$.

Proof:

Let $(x_1, y_1)$ and $(x_2, y_2)$ be on the curve, i.e., $x_i^2+y_i^2=1+dx_i^2y_i^2$. Write $\epsilon=dx_1x_2y_1y_2 \neq 0$ and suppose $\epsilon \in \{-1,1\}$. Then $x_1, x_2, y_1, y_2 \neq 0$ and

\begin{equation}
\begin{split}
dx_1^2y_1^2(x_2^2+y_2^2) & = dx_1^2y_1^2(1+dx_2^2y_2^2) \\
 & = dx_1^2y_1^2 + d^2x_1^2y_1^2x_2^2y_2^2 \\
& = dx_1^2y_1^2 + \epsilon^2 \\
& = 1+dx_1^2y_1^2 \\
& = x_1^2 + y_1^2
\end{split}
\end{equation}

Now we need to show that $\epsilon = dx_1x_2y_1y_2 = \pm1$ implies $d$ is a square. For now we have $dx_1^2y_1^2(x_2^2+y_2^2)=x_1^2+y_1^2$. It follows that

\begin{equation}
\begin{split}
(x_1+\epsilon y_1)^2 &= x_1^2+y_1^2+2\epsilon x_1y_1 \\
& = dx_1^2y_1^2(x_2^2+y_2^2)+2x_1y_1dx_1x_2y_1y_2 \\
&= dx_1^2y_1^2(x_2^2+2x_2y_2+y_2^2) \\
&=dx_1^2y_1^2(x_2+y_2)^2
\end{split}
\end{equation}

$x_2+y_2 \neq 0 \rightarrow d=\left(\frac{(x_1+\epsilon y_1)}{x_1y_1(x_2+y_2)}\right)^2 $

$x_2-y_2 \neq 0 \rightarrow d=\left(\frac{(x_1-\epsilon y_1)}{x_1y_1(x_2-y_2)}\right)^2 $

Now if $x_2+y_2 = 0$ and $x_2-y_2=0$, then it follows that $x_2=y_2=0 \rightarrow$ contradiction to the statement we made above ($x_1,x_2,y_1,y_2 \neq 0)$.


finding the basis of a kernel in a lattice

Let ${\bf A}$ be a $n\times m$ matrix with $n|m$ and rank $n$. Write down ${\bf A}$ as $m/n$ blocks of $m\times m$ matrices as follows:
$${\bf A}=\left[{\bf A}_1|\cdots|{\bf A}_{m/n}\right].$$
If ${\bf x}\in\Lambda({\bf A})$, then
$${\bf 0}={\bf A}{\bf x} = \sum_{i=1}^{m/n}{\bf A}_i{\bf x}_i,\pmod{q}$$
where ${\bf x} = \left[{\bf x}_1^T|\cdots|{\bf x}_{m/n}^T\right]^T$.
Without loss of generality, suppose that ${\bf A}_1$ is invertible. hence the above equation can be written as:
$${\bf x}_1=\sum_{j=2}^{m/n}{\bf B}_j{\bf x}_j,\pmod{q}$$
where ${\bf B}_j = -{\bf A}_1{\bf A}_j$, for $2\leq j \leq m/n$.
Using the above equation and by replacing a standard basis as ${\bf x}_j$, $2\leq j \leq m/n$, one can find ${\bf x}_1$, which fully  describes the lattice $\Lambda({\bf A})$.


Secret key formed by the combination of several keys

A trivial solution would be to encrypt the message under all the different keys and concatenate the ciphertexts. However, this obviously has a large blow-up in terms of ciphertext length.

An idea to decrease the blowup would be to encrypt the message under a new short key $k'$ to get a ciphertext $c$, then encrypt $k'$ under all the IDs $k_1,...,k_n$ individually and concatenate the results to $c$ and broadcast the concatenation.

This may not be great in practice but it has an asymptotic rate of $1$, which is better than the trivial solution's rate of $1/n$.

One caveat for both the above solutions is that there would have to be some ordering on the stations, and the stations would have to know their place in the ordering.


A question about fully homomorphic encryption (FHE)

If we encrypt $m_1$, and send it to the server, can the server "somehow" find $E(m_1)$ and remove it?

Nope; FHE allows a server that knows $E(m_1)$ and $E(m_2)$ to produce a ciphertext which is a representation of the value $E(m_1 \odot m_2)$ (for pretty much arbitrary functions $\odot$); what it doesn't allow a server to do is determine whether $m_1 = m_2$.  If it could, then it could decrypt (by guessing various values $m_2$, producing $E(m_2)$, and then checking if that was the same.

  Is there any other way to remove $m_1$ from the outsourced dataset without leaking any information to the server?

One thing that occurs to me is to produce $E(m_1)$, and have the server replace all values $E(m_i)$ it knows with $E(m_i \odot m_1)$, with $a \odot b = a \cdot (a-b)^{p-1}$ (and, of course, erase all the original $E(m_i)$ values.  In case you don't get the punchline, with this $\odot$, we have $a \odot b = a$ if $a \ne b$, and $a \odot a = 0$; hence any copies of $E(m_1)$ are replaced with an encryption of a fixed constant, while the copies of any other value are unaffected.


What's the utility of the last two messages of Needham Schroeder Symmetric key protocol

Messages 4 and 5 are meant to protect the recipient B from a replay attack. It is a basic challenge response mechanism. Otherwise an attacker could just replay previous messages and have the very same interaction with B again. That is bad, if e.g. the message is just "increase some counter", or another message that has a lasting effect or changes a state.

This doesn't protect from a compromised Alice or if the trusted party is compromised. It only protects from an attacker controlling the network.

More explicitly: Eve has a copy of a past interaction between Alice and Bob. She has message 3, but it is encrypted and she can't extract the content. But she is able to send that same message to Bob. If Bob doesn't have a full record of every interaction in the past (and checks against all those records), he thinks it's a new one. If Eve just replays every message originally sent by Alice, Bob would have no way to detect it isn't really Alice sending those messages. Of course the interaction could be adaptive, and Bob then notices a difference, but the protocol should also work with non-adaptive messages.


Well, for perfect secrecy, we require that for all message distributions over $\mathcal{M}$, all messages $m\in\mathcal{M}$, and all (possible) ciphertexts $c$ it holds that

$$Pr[M=m\ |\ C = c] = Pr[M=m]$$

In particular, that means, if we can find a single counterexample, i.e. a distribution over $\mathcal{M}$, a message $m\in\mathcal{M}$, and a ciphertexts $c$ such that

$$Pr[M=m\ |\ C = c] \neq Pr[M=m]$$

then, by our definition, the encryption scheme does not offer perfect secrecy.

So, let's take the uniform distribution over $\mathcal{M}$. For this distribution, we obviously have $$Pr[M=c]=1/|\mathcal{M}|.$$
Now, given that $0^n$ is not a valid key, what is the probability  $$Pr[M=c\ |\ C = c]?$$ Are the two probabilities equal?


determinant of intersection of two lattices

I know this is really old, but it's still an interesting question that is semi-related to something I am working on.
I will refer to the lattices as $L_0$ and $L_1$, so I can write $L_i$ and $L_{1 - i}$ to refer to both of them without making a particular choices of indices.
I will use $L \leq L'$ to denote sublattice containment.

Let the operation $L_0 + L_1$ be the minkowski (not direct) sum of lattices.
If $L_i = \mathcal{L}(M_i)$ is the lattice generated by the matrix $M_i$, then $L_0 + L_1 = \mathcal{L}([M_0 | M_1])$ is the lattice generated by the concatenation of the matrices.
You can equivalently view this as the sum of all pairs of lattice points, i.e. $L_0 + L_1 = \{l_0 + l_1 | l_0\in L_0, l_1\in L_1\}$.
This operation can be seen as "dual" to the intersection in a formal sense [1], which I will exploit below.

Note that $L_0\cap L_1\leq L_i$, so the quotient $L_i / (L_0\cap L_1)$ is well-defined.
Moreover note that $|L_i / (L_0\cap L_1)| = [L_i : L_0 \cap L_1] = \det(L_0\cap L_1)/\det(L_i)$.
By the second isomorphism theorem (viewing lattices as $\mathbb{Z}$-modules), we have that:
\begin{align*}
L_i / (L_0\cap L_1) &\cong (L_0 + L_1) / L_{1-i}\\
\implies \det(L_0\cap L_1)/\det(L_i) &= \det(L_{1-i})/\det(L_0 + L_1)\\
\implies \det(L_0 \cap L_1) &= \frac{\det(L_0)\det(L_{1})}{\det(L_0 + L_1)}
\end{align*}
This holds for any pair of lattices $L_0, L_1$ such that $L_0 \cap L_1$ and $L_0 + L_1$ are lattices (interestingly, we have not assumed the lattices are integral yet).
This suggests that all we have to do is prove that $\det(L_0 + L_1) = 1$, and we have:

$L_i$ are integral (i.e. $L_i \leq \mathbb{Z}^r$)
The GCD condition

To work with. Note that integral lattices satisfy $\det(L)\mathbb{Z}^r \leq L \leq \mathbb{Z}^r$.
One can show that $L_i \leq L_i'$ implies that $L_0 + L_1 \leq L_0' + L_1'$.
Applying this to the above, we get that:
$$\det(L_0)\mathbb{Z}^r + \det(L_1)\mathbb{Z}^r \leq L_0 + L_1 \leq \mathbb{Z}^r$$
It is not hard to show that $a\mathbb{Z}^r + b\mathbb{Z}^r = \mathsf{gcd}(a, b)\mathbb{Z}^r$, so upon using our GCD condition we get that $\mathbb{Z}^r \leq L_0 + L_1 \leq \mathbb{Z}^r$, and therefore $\det(L_0 + L_1) = 1$.

[1] The submodules of a module form a modular lattice in the sense of order theory, where $\cap$ is the meet, and $+$ is the join respectively. This is to say that $+$ and $\cap$ are "dual" in the same sense that the set union and intersection are "dual".


Are there cryptographical flaws in this e2ee website chat widget?

If the customer sends his public key to the business, then the business creates a new set of keys forwarding the new public key to the visitor then the business now has a way to decrypt messages from the visitor since the visitor is not aware that the public key is not the intended customers public key but the new one generated by the business.  The business now can decrypt all messages from the visitor to the business making any changes they wish and using the customers original public key to re-encrypt the changed message with the customers public key and passing that message along to the customer who is not aware that the message has been changed.  If the business does this with the public key of the visitor passed to the customer as well then messages can be read and changed in the opposite direction as well.  This is a classic man in the middle.  That is what TLS is designed for an encrypted communication channel directly between the visitor and the customer with no relay between the certificates for TLS can be verified through a certificate authority which both parties have to trust for the initial key exchange to take place.  In this scenario the business is trying to act as a trusted man in the middle however it maybe the intention to have the business act as a certificate authority  who signs both the businesses and visitors certificates or public keys to ensure that both parties are receiving the intended keys.  In order to do that both parties should have the businesses certificates installed as trusted certificates authorities on their systems which is not a great idea and can lead to major compromises in practice.


1) Yes. This is the common modulus attack and has actually been answered many times on this forum.

2) Assuming $r$ is prime, yes. $\phi(n)$, (the totient of $n$) can be computed by subtracting 1 from each of $n$'s prime factors and multiplying them together.


What's the main difference between Pohlig-Hellman and RSA?

The main difference is that Pohlig-Hellman is a symmetric cypher, while RSA is a public key system.  This is because, with Pohlig-Hellman, anyone who knows the encryption key $e$ can compute the inverse operation (because the 'decryption' key $e^{-1} \bmod p-1$ is easy to compute), while the RSA, someone who knows the encryption key $e$ (but not the factorization of the RSA modulus) cannot compute the decryption operation.