This is obtained by raising to $\lambda=\lambda(n)$: since the order of any element in $\mathbb{Z}_{n^2}$  divides $n\cdot\lambda$, the second part cancels out:

$$\begin{align}
    g^{x_1-x_2}\cdot(y_2/y_1)^n=1\bmod{n^2} &\Leftrightarrow\\
   g^{(x_1-x_2)\cdot\lambda}\cdot(y_2/y_1)^{n\cdot\lambda}=1\bmod{n^2}&\Leftrightarrow\\
  g^{(x_1-x_2)\cdot\lambda}\cdot 1=1\bmod{n^2}&\Leftrightarrow\\
g^{(x_1-x_2)\cdot\lambda}=1\bmod{n^2}
   \end{align}$$


The distinction is that ECDSA solves a problem that HMAC does not. If you need that problem solved, then you need to do ECDSA rather than HMAC; if you do not, then HMAC works just as well (and is a lot cheaper).

With HMAC, here is what we have: we have an authenticator that has a secret key.  It takes a message, and gives that (and the secret key) to the HMAC algorithm, and that generates a tag.  We send that tag, along with the message, to the verifier.

The verifier also has the secret key. It takes the received message, and gives that (and the secret key) to the HMAC algorithm, and that generates the tag.  It then checks if the computed tag was precisely the same as what it received; if it is, then it knows that the message is precisely as it was when it was originally sent.

With ECDSA, here is what we have.  we have an authenticator that has a private key.  It takes a message, and gives that (and the secret key) to the ECDSA signing algorithm, and that generates a tag.  We send that tag, along with the message, to the verifier.

The verifier also has the public key (which is not the authenticator's private key). It takes the received message and tag, and gives that (and the public key) to the ECDSA verification algorithm, and it checks whether the tag corresponds to the message.  If it does, then it knows that the message is precisely as it was when it was originally sent.

So, what's different?  With HMAC, both sides share the same key; the verifier could (if it wanted to) generate its own tags to messages of its choice, and those tags would validate just as well.  With ECDSA, this doesn't happen; the key that the verifier has (the public key) allows it to check tags, but it does not allow it to generate tags on its own.

So, is this distinction important in your scenario?  I don't know enough about what you're doing to say.  The question you need to answer is: can you trust the verifier not to generate its own tokens?  Can you trust someone who has access to the verifier's keys not to do so?  If that is not something you are worried about (possibly because the verifier is the only one who cares about tags generated by a specific set of keys), then HMAC works just fine (and, as I mentioned earlier, is a lot cheaper).  If you do care (for example, you distribute the verifier code to lots of people, and you have one set of keys), then it doesn't matter how cheap HMAC is - it doesn't solve your problem - you need to go with something like ECDSA


Encrypting user data with their password?

There are a number of considerations here, I'll try to lay them out one at a time for ease of following:

What must the site do with the data?

Oftentimes, we ask web sites to do things on our behalf when we are not actually visiting them.  For example, I may want crypto.SE to email me when there are responses to this post.  The site could not do that without access to my email address, preferences, and the list of which posts I've subscribed to.

Either the site does not ever need to access a user's data (or at least not when the user is not logged in, if we want to do some session management as part of our scheme)...or the benefit of encrypting each user's data with a different key is negated by the fact that the keys need to be stored near the data.

What do you mean exactly by "encrypt the data with the password"?

When an infosec professional says "encrypt foo with bar", we literally mean that bar is being used as the key for an encryption algorithm that will turn foo into encrypted-foo.  When it comes to user-supplied passwords, this is universally a bad idea.  Most users choose terrible passwords.  Even a good password policy might get you a passphrase of 20 characters or so with a digit or uppercase thrown in as a gimmee...at best.  That isn't very much entropy in the grand scheme of things (even less when 42 of your users pick their favorite bands' names or family pets).

OTOH, what one might do to combat the lack of entropy is to use the password to encrypt a decent, randomly-generated encryption key, which is in turn used on the data.  That's much less terrible.  Not perfect (what encryption is perfect?), but markedly less terrible.

As a free bonus, the use-password-to-encrypt-key method helps with the fact that yes, stupid users will recycle passwords, and their accounts on various sites where they have recycled passwords will inevitably have some duplicate content that can be matched up should that ever be relevant to an attacker.

Why are we doing this again?

You ask "Would this work?", but you never actually defined what the problem was that you were trying to solve.  This is one of the first things I advise you un-learn on your path to getting good at crypto and/or infosec in general.  ALWAYS define a goal, a use case, or some sane description of what you mean to accomplish in the first place.  Failing to correctly and adequately define the problem before solving it is how a massively large fraction of screwups happen, in infosec and elsewhere.

"Would this work?" as a proxy for "could I actually code and run something like this?" ->  Yes, you could.  I wouldn't advise it, but it would work.

"Would this work?" as a proxy for "Would this make my database's data less likely to be stolen if my database fell off of a truck?" -> Probably not.  Granted, most DBs sit unencrypted on disk, but they do that for a reason: they're always unencrypted, or the keys stored nearby, when in use.  Also, for your option of directly encrypting data with user-supplied passwords as the key, the likely weakness of the passwords makes offline attacks on most of that data trivial.

"Would this work?" as a proxy for "Would it be a good idea to implement this in a production system?" -> Absolutely not.  The argument that this scheme provides added protection is weak, but the complexity it would introduce into the web application software is significant.  Even if the encryption scheme were somehow useful (which I'm not buying so far), the added complexity is almost certain to result in vulnerabilities of a magnitude greater than the increase from the encryption.

I may be off base, of course...

I did presume some things from your very light specification... I presumed that you are talking about encrypting data at rest in a publicly accessible web application's database.

Related things

I'm not trying to kill all of your aspirations here, just to introduce the harsh reality.  The good news is that you are kinda-sorta dancing around something that IS a viable concept:

In something that's not a webapp, where the service provider doesn't need access to users' data (e.g. a backup service), it IS wise for users to store their data with keys that they (the users) control.  Furthermore, those keys should not be shared with the provider, who's just acting as a warehouse at that point.  This is, in fact, how every responsible cloud backup provider behaves.


Encryption method with master key and user keys

I'll show a scheme with the following presumption:

the game has its own server key, this key is hidden in the game data somewhere (this usually cannot be secured completely, the game has to store the key somewhere);

So what you can do is to encrypt your game data with a randomly generated data key. If you use GCM mode of operation then you can verify if the data was tampered as well during decryption. This data key itself you encrypt (wrap) with the game key and the user key.

Now the game can always access and change the data. But the user needs to supply the user key. However, the user only has a password, so we need to convert that password to a user key. The way to do that is to use a Password Based Key Derivation Function such as PBKDF2, and use the output as the user key (note that you need to supply the PBKDF2 with a random salt that you generated & stored when the user account is created).

In the end you can make it as easy or hard as you want. One very interesting feature would be to let the user sign the game data as well; in that case the game can reject tampered game data.

It may also be a good idea to encrypt game data values separately, you can use a hash of the identifier of the specific data as Initialization Vector for the encryption/decryption.


The hash of a zero-length message is defined for several reasons:

There's no reason not to define it. If (as you assume) it'll never be used, then it doesn't matter whether it's defined and there's no reason to avoid defining it.
Having it undefined would create a weird exceptional case that'd need to be handled by anything that uses the hash, just in case it ever happens. Weird exceptions tend to lead to bugs, bugs tend to cause vulnerabilities, and cryptographers hate vulnerabilities and the design choices that cause them.
In practice, it will be used. One common use of hashes is to create a fingerprint of the contents of files, and empty (zero-length) files are entirely normal.

As for your point that for a given HASHing algorithm, the hash value of a zero length message is essentially pre-defined: that's true, but it's also true of any other specific message. The hash of "a" is essentially pre-defined, as is the hash of "foo", "This is a message", etc.


Why was Vaudenay's original padding oracle attack not exploitable on TLS 1.0?

It's a question of attack model. Vaudenay places himself in a model where the attacker is "outside", and trying to work out the password that a human user enters in a Web site (or another similar password-protected protocol). Both client and server systems are honest and truthfully run the TLS protocol; the attacker can inspect and alter packets, but that's all. Chosen Plaintext Attacks are out of scope.

In that model, in case of repeated errors, the human user will consider things too fishy, and will not persist. Moreover, most alterations meant to check an hypothesis on the last byte of a block also mangle the previous bytes in the record, which contain the MAC, so the ultimate observable behaviour, from the attacker's point of view, is unchanged: an (encrypted) alert record is sent by the server, and the connection is aborted (so we are not talking about the difference between a short error message and a long non-error message, but about two error messages, who have the exact same length).

The 2003 paper "fixes" both issues:

It targets the case of an email client that automatically connects to an IMAPS server, every minute, and will try again and again even if connections abort; the errors are also silently ignored.
The difference between failure modes ("bad padding" vs "good padding but bad MAC") can be worked out by the attacker by measuring the server's response time.

Retrospectively, we may note that the problem about the alert message not being known can be avoided when the padding has the size of a full block and the receiving side does not check padding byte contents, as is nominally the case with SSL 3.0. Also some TLS 1.0 implementation did not check padding byte contents.

Around 2010, researchers made some sort of "mental breakthrough" in which they realised that CPA were a valid model in a Web context. This began with padding oracle attacks on ASP.NET, in which the attacker sits on the sending side, and wants to unravel the "viewstate", an encrypted blob that the server adds to a Web page in order to offload state information storage on the client. This is not a TLS attack, but it still demonstrates the "extra powers" awarded to the attacker: the attacker controls the connection and can decide to try again, repeatedly, with no supervision by a human victim; and he gets access to error messages.

Then, in 2011, the BEAST attack demonstrated an attack which was not about padding (though it was still about CBC in TLS), with a CPA model in a Web browser, and targeting a secret value sent automatically by the client (the cookie). From that point, researchers began to really believe that CPA with low success rate per connection were really practical in a Web context.

The padding oracle attack, Vaudenay-style, combined with BEAST-like attackers using hostile Javascript, to form the Lucky Thirteen attack. In the mean time (and thanks to Vaudenay's 2003 article), TLS libraries had adapted their code:

The same alert message was sent, whether the failure was on the padding or the MAC (also, that error message was not necessarily made available to the attacker).
The MAC was still computed even in case of bad padding, so as to have a constant processing time.

Yet, there was a small remnant of a timing leak, because the MAC computation time depends on the size of the plaintext, which is not exactly equal to the size of the ciphertext, because of the padding. If padding found upon decryption was incorrect, then the library had to choose some pseudo-padding length, which would leak a bit of information. The Lucky Thirteen attack uses that small leak, in a CPA model with hostile Javascript.

Modern TLS libraries implement really constant-time processing which removes this last timing leak, thus making TLS 1.0 CBC cipher suites safe again (but TLS 1.2 with AEAD suites is still largely preferable).

Summary: it took researchers a decade to understand that the Web offered a practical CPA setup. This entailed recognising that Javascript was not only meant to animate a dancing squid on a Web page, but was powerful enough to trigger many silent connection attempts; and, crucially, that each such connection could be made to include a secret value which, while not being the actual human-entered password, was still juicy enough to warrant some attacking effort.


How to convert a set of sequential integers into a set of unique random numbers?

Let $P$ be an arbitrary random fixed permutation of $n$ elements. Each of the desired shuffle can be generated from the previous as follows:

apply $P$ to the previous shuffle (or the initial set/vector, the first time);
rotate the result one to the left;
apply $P^{-1}$ to the result.

This will have the property asked by "if I pick a number at a particular position in the list after each shuffle, I should never get a duplicate". Proof: in applying the shuffle sequentially, the next application of $P$ with cancel the previous application of $P^{-1}$. It follows that the rotation will operate on the result of the previous rotation, thus that the property is met at the output of the rotation. It follows that the property is met after applying $P^{-1}$, thus at the output.

We can iterate this $n-1$ times (if we do it once more, we are back to the original, thus will get something clearly sequential, thus in the context distinguishable from the required "random integers" with great ease and near certainty).

We can use the Fisher-Yates shuffle to generate $P$. Or, if keeping it in memory is an issue because of size, we can use a cipher to implement $P$, and its reverse; that's a standard trick of Format Preserving Encryption.

Any isolated shuffle is indistinguishable from a random shuffle, but even the first two shuffles generated are distinguishable from random shuffles with the required property (which perhaps is undesirable, if not clearly prohibited).

If we remove the requirement that the same operation is iterated to go from one shuffle to the next (we are told that we can), we can do something better: pick three arbitrary random permutations $P$, $Q$, $R$ of $n$ elements, and get the $(j+1)^\text{th}$ shuffle as

apply $P$ to the initial state
rotate the result $Q(j)$ times to the left, where $Q(j)$ is the $(j+1)^\text{th}$ element of the vector obtained by applying $Q$ to the vector of the first $n$ non-negative integers; or, otherwise said, $Q(j)$ is an integer $q_j$ with $0\le q_j<n$, such that $0\le i<j<n\implies q_i\ne q_j$.
apply $R$ to the result.

This time, we can obtain $n$ individually random-looking shuffles, which obviously is the maximum. Again, Fisher-Yates or FPE can be used to implement $P$, $Q$ and $R$. Even knowing the initial shuffle and the rank of any two generated shuffles, I vaguely conjecture (without proof) that they are indistinguishable from two random shuffles meeting the property asked. By a counting argument, three generated shuffles are distinguishable, at least by an unbounded adversary; thus we are far from generating the best randomness possible.

I have asked the question in more academic terms there.

Here is sample code in Java for the second method. Class MyCipher implements a Pseudo Random Permutation of size elements, made using cycling (arguably the simplest efficient FPE technique), and a basic iterated block cipher. Class MyShuffledArray is then a straightforward implementation of the technique that I propose. The code is usable for large parameters, and uses constant memory.

import java.util.Random;
import java.security.SecureRandom;

public class MyShuffledArrayDemo {

    // MyCipher implement a PRP of size elements
    static class MyCipher {
        private static final int R = 40;        // number of rounds
        private final int size;                 // size of PRP
        private final int mask;                 // bit mask for block
        // 0 < size <= mask+1  and mask+1 is a power of 2
        private final int rish;                 // right shift count
        private final int[] rk = new int[R];    // rk for each round

        // Constructor from rng source
        private MyCipher(int size, Random rng) {
            assert size>0 : "MyCipher.size must be positive";
            int i,j;
            // find block cipher width j in bits; and mask
            for (j = 3, i = 8; j<31 && i<size; ++j)
                i += i;
            this.size = size;
            this.mask = i-1;    // one less than a power of two
            this.rish = j*3/7;  // shift count, at least 1
            i = R; do
                rk[--i] = rng.nextInt();
            while (i!=0);
        }

        // Implement PRP, using a basic iterated block cipher and cycling.
        // Input and output are a non-negative integer less than size.
        private int Perm(int x) {
            assert x>=0 && x<this.size : "bad input to MyCipher.encrypt";
            do { // cycling loop; executed on average less than twice when size>4
                int r = R;
                do {// Round loop; each losslessly transforms x by
                    // - multiplying by 0xADB modulo a power of 2
                    // - adding a round key
                    // - XORing x with a right-shifted version
                    // Here, x<= mask  and mask+1 is a power of 2
                    x = (x*0xADB+this.rk[--r]) & this.mask;
                    x ^= x>>>this.rish;
                    }
                while (r!=0);
                }
            while (x>=this.size);
            return x;
        }

    } // class MyCipher

    // MyShuffledArray implement a virtual square array where each line and column appears to be a random permutation
    static class MyShuffledArray {
        private final int size;         // dimension
        private MyCipher P,Q,R;

        // Constructor from rng source
        private MyShuffledArray(int size, Random rng) {
            assert size>0 && size<=0x40000000: "MyShuffledArray.size must be positive and at most 1073741824";
            this.size = size;
            P = new MyCipher(size, rng);
            Q = new MyCipher(size, rng);
            R = new MyCipher(size, rng);
            }

        // Implement the virtual array
        private int Get(int col, int lin) {
            return R.Perm((P.Perm(col)+Q.Perm(lin))%this.size);
            }

        } // class MyShuffledArray

    // Example use
    final static int START_OF_RANGE  = 1;
    final static int END_OF_RANGE    = 9;
    final static int NUMBER_OF_LISTS = 3;
    final static int size = END_OF_RANGE - START_OF_RANGE + 1;

    public static void main(String[] args) {
        MyShuffledArray myShuffledArray = new MyShuffledArray(size, new SecureRandom());
        for (int j = 0; j <NUMBER_OF_LISTS; j++) {
            for (int i = 0; i <size; i++)
                System.out.print(String.format(i==0?"[%d":", %d", myShuffledArray.Get(i,j) + START_OF_RANGE));
            System.out.println("]");
        }
    }
}

This answer identifies that we are generating a latin square. Here is a literature survey.


Structure for an introductory course on cryptography?

I recently read Understanding Cryptography: A Textbook For Students And Practitioners by Christof Paar & Jan Pelzl. I can say without a doubt that it addresses all your bullets and in the meantime it's easy and fun to read.

I have an MSc in Information Security so everything I read I already knew but some of the concepts were so well put that I felt I got a better grasp on how some things work.

As I was a reading it I thought to myself that if I ever teach a introductory course in Cryptography I'll follow this book. You can give it a shot, see if its format suits your needs as a roadmap.


It's impossible:

Impossibility of Blind Signatures From One-Way Permutations -  Katz, Schroder, Yerukhimovich


A simple keyed message authentication code using XOR

Assuming your authenticated message is public (which is reasonable), this scheme seems insecure for the following reason:

Your authentication tag $t$ over message $m$ is computes as

$$t=sha256(salt||key) \oplus sha256(m)$$

This means that any adversary knowing $m$ can compute a new authentication tag $t'$ for a message $m'$ in the following way:

$$t' = t \oplus sha256(m) \oplus sha256(m')$$

This will result in

$$t' = sha256(salt||key) \oplus sha256(m) \oplus sha256(m) \oplus sha256(m') = sha256(salt||key) \oplus sha256(m')$$

This is, by your definition, a valid authentication tag for $m'$.

You need to incorporate the message into the authentication tag in a non-reversible way. For example, HMAC does $h(k \oplus opad || h((k \oplus ipad) || m))$. This way, a new authentication token cannot be created without inverting the hash function $h$. (opad and ipad are fixed values that are used to ensure the keys are different at both positions)

Additionally, you would have to distribute your salt to the recipient somehow, and ensure that the adversary cannot change it. Otherwise, authentication will be impossible because the recipient cannot compute $sha256(salt||key)$.


Unbalanced Feistel network only generates complete permutations with square lengths

I think that this method of yours will not work out. The reason is the way you compute $r = counter$ mod $s$.
Take a simple example of $(counter_1, period) = (3, 11)$ and $(counter_2, period) = (5, 11)$. Here $d=3$ and $s=5$.
You get initial $(q_1, r_1) = (1,3)$ and $(q_2, r_2) = (1,0)$.
After first iteration of the loop, you have $(q_1, r_1) = (3,1)$ and $(q_2, r_2) = (0,1)$.
After the second interation of the loop, you will get $(q_1, r_1) = (1,1)$ and $(q_2, r_2) = (1,1)$.
Now, for the remaining iterations, both $(q_1,r_1)$ and $(q_2,r_2)$ will always go along being equal and will finally result in equal values being returned by the function for 2 different counter values with the same period sabotaging the maximal permutation.
You should get rid of the above mentioned issue by computing initial $r$ as $r = counter$ mod $d$.


ECDSA: What is the purpose of adding a hash of the used certificate to the signed data?

It is probably a countermeasure to multi-user attacks.

In the classic (single-user) attack scenario the attacker wins if she manages to create a valid signature under a given public key, without knowing the private key. (note that a it is not request to obtain the private key, but just one valid signature)

In the multi-user scenario, instead, there are multiple public/private key pairs. And the attacker wins if she's able to create one valid signature under just one of the given public keys (the attacker can choice the target one).

The multi-user attack is believed to be easier than the single-user attack.
The high level idea is that the attacker's computation can be reused against any of the allowed public key, thus increasing its efficiency.

A common countermeasure, introduced in ed25519, is to create a stronger bond between the signer and the signature by including in the hash computation the signer's public key.
What you describe in the car2car scenario looks similar to that countermeasure as the forger needs to create hashes of the messages which include the signer's identity. This most likely remove the multi-user advantage compared to single-user.

Bernstein showed that adding the signer's key in the ed25519 hash computation protected against multi-user attacks.
Klitz et al. later showed a reduction from the multi-user to the single-user. Bernstein, however, disagrees with the paper conclusions.

To summarize, IMHO, adding the signer to the hash is very efficient and seems to provide a generic solution to concerns about multi-user attacks, while the reduction between multi-user and single-user for signatures is still unclear.


Do asymmetric signatures require constant-time verification?

Towards the security of the signature scheme, no precaution against timing attack is necessary when verifying an asymmetric signature. That's because there is no secret involved, thus no information leak to fear.

However it can happen that the message, or the signature itself, is intended to be secret; a leak by timing dependency (during computation of the hash of the message, during verification of message padding..) could compromise this (not the security of the signature mechanism). Except for intentionally leaky implementation of signature verification, the leak would most likely be only of few bits, and thus not to fear for the signature. However sometime any small message leak is important; and repeated leaks on related messages could in the end leak a lot of information about what's common in the messages.


How to prove that a function is not pseudorandom?

Before answering the actual question, I will offer some general advice.

It is important to pay attention, both in class and to the textbook you are reading. If learning how to solve such exercises is a key goal of the course, such solutions have very probably been discussed at length in class. Moreover, your textbook also has proof examples, and in this case it has one which is conceptually identical to the one you have given here (where $G'(k)$ is replaced by $k$).
It is crucial to know and understand your definitions. Here, you want to show that a certain family of functions is not pseudorandom (i.e., does not satisfy the definition of a pseudorandom family of functions), but it is not clear that you understand what this means (you do not articulate it in your question). You must understand this definition if you want to be able to show that a certain construction does or does not satisfy it.
Broadly speaking, you seem to lack what is commonly known as mathematical maturity, which is not knowledge of any specific mathematics, but rather the ability to see how to connect the dots in a mathematical argument between the hypotheses and the conclusion. Indeed, a telltale sign of someone who is not "mathematically mature" is that they balk at the mere sight of the word "proof" and seem unable to make any progress beyond stating the hypotheses. Unfortunately, cryptography is not the best of places to "get your feet wet" in writing proofs because it is a very complicated business (most results in cryptography aim to prove that it is impossible to do something), and you can feel overwhelmed pretty quickly. For this reason, abstract algebra or real analysis are better training grounds, even if you have no intention of studying them for their on sake.

To turn to the main question, we first need to know and undertand the definition of a pseudorandom family of functions. We consider a function $F$ which maps each pair of strings $(k,x)$ of equal length to a third string $y$ of the same length as $k$ and $x$. For any string $k$ of length $n$, we note $F_k$ the function which maps the $n$-bit string $x$ to the $n$-bit string $y$ (i.e., $F_k(x) = F(k,x)$. The string $k$ is called the key. I only state the definition of a pseudorandom function without a lengthy discussion (which can be found in the book).

  The function $F$ defined above is pseudorandom if it satisfies the following two conditions.

  Easy to compute. There is a deterministic polynomial-time algorithm $C$ such that $C(k,x) = F_k(x)$ for any strings $k$ and $x$ of equal length.
  Pseudorandom. For every probabilistic polynomial-time algorithm $D$, every polynomial $p$ and all sufficiently large $n$, we have
  $$\left|\mathrm{Pr}[k \gets \{0,1\}^n : D^{F_k}(1^n) = 1] -
          \mathrm{Pr}[f \gets \mathrm{Func}_n : D^f(1^n) = 1]\right|
< \frac{1}{p(n)}.$$

My notation is as follows:

$\{0,1\}^n$ is the set of all strings of length $n$.
$\mathrm{Func}_n$ is the set of all functions from $\{0,1\}^n$ to itself.
$k \gets X$, where $X$ is a finite set, means that $k$ is randomly and uniformly chosen from $X$.
$D^f$ denotes the algorithm $D$ when given oracle access to the function $f$. That is, $D^f$ can obtain $f(x)$, for any $x$ of its choice, at the cost of only one operation.
$\mathrm{Pr}[A : P(x)]$ denotes the probability that $P(x)$ holds after the execution of $A$.

Here, you want to prove that the given function is not pseudorandom, meaning that it does not satisfy the definition above. In other words, that it satisfies its logical negation. Since the logical negation of the definition is not entirely trivial, it is best stated explicitly. Typically, the "easy to compute" condition will be satisfied, so we only give the negation of the pseudorandomness condition.

  A function $F$ as above which is easy to compute is not pseudorandom if there exists a probabilistic polynomial-time algorithm $D$ and a polynomial $p$ such that for infinitely many $n$, we have
  $$\left|\mathrm{Pr}[k \gets \{0,1\}^n : D^{F_k}(1^n) = 1] -
          \mathrm{Pr}[f \gets \mathrm{Func}_n : D^f(1^n) = 1]\right|
\ge \frac{1}{p(n)}.$$

We can finally define the algorithm $D$ (we denote by $\mathcal{O}$ the function computed by the oracle). On input $1^n$, it proceeds as follows.

Compute $y_0 = \mathcal{O}(0^n)$.
Compute $y_1 = \mathcal{O}(1^n)$.
If $y_0 \oplus y_1 = 1^n$, output $1$. Otherwise, output $0$.

We must determine the probability that $D$ outputs $1$ in each case: when $\mathcal{O}$ is $F_k$ for a uniformly chosen $k$, and when it is a uniformly chosen $f$.

In the first case, regardless of what $k$ is, we have $y_0 = G'(k) \oplus 0^n = G'(K)$ and $y_1 = G'(K) \oplus 1^n$. Hence we have $y_0 \oplus y_1 = G'(k) \oplus G'(k) \oplus 1^n = 1^n$, and $D$ ouputs $1$ with probability $1$.
For the second case, we note that $D$ outputs $1$ if and only if $y_1 = y_0 \oplus 1^n$. If $f$ is a totally random function, $y_1$ is chosen among all $2^n$ strings of length $n$ uniformly and independently of $y_0$, and so it will equal $y_0 \oplus 1^n$ with probability $1/2^n$.

Hence finally we see that for all $n$, the value of the big probability expression in the definition equals $1-\frac{1}{2^n}$. If $n > 0$ this is at least $\frac{1}{2}$, and so we can take $p$ to be the constant polynomial $2$.


What is the chance of a collision when using SHA-3?

Generally, SHA-3 is build to offer $2^{n/2}$ collision resistance (and $2^n$ preimage resistance).

You haven’t specified which SHA-3 you are talking about (SHA3-224/256/384/512), but even when looking at the smallest of them (SHA3-224) and assuming correct implementation, the chance of a collision is more of a theoretical nature.

Talking about implementation: what I don’t really grasp is why you would inject a 50-byte hash before, and another 50-byte hash after the password. Those might just be two individual hashes of some web app related information you’re pulling together there… but in case that’s an attempt to add some kind of security, I would like to advise you to look at HMAC-SHA3 constructions. Yet, even better would be to use solutions that were specifically designed for this kind of task, like bcrypt, scrypt or pbkdf-2.

For further reading:

The new SHA-3 secure hash algorithm has been published in FIPS 202 (PDF).
The HMAC algorithm is described in RFC 2104 (TXT).

It may be helpful to know that the block lengths $B$ to be used in the HMAC algorithm (meaning: the byte-length of the digest input block) is given in Table 3 of FIPS 202… that’s 144 bytes for SHA3-224, 136 bytes for SHA3-256, 104 bytes for SHA3-384, and 72 bytes for SHA3-512.


Can the fingerprint of a PGP key be combined with a phone number?

Given a message space of $10^{10} \approx 2^{33.2}$ different phone numbers and $16^{16} = 2^{64}$ different fingerprints, you should expect to take no less than $\log_{64}(2^{33.2 + 64}) \approx 16.03$ base-64 characters, or $\log_{36}(2^{33.2 + 64}) \approx 18.61$ base-36 characters. Bit concatenation is fine in this case, assuming each fingerprint and phone number in the whole space is equally likely to occur.

However, what stops the carrier from still simply MitM'ing and swapping such an encoded pair of fingerprint and phone number with their own?


I guess you have read the wikipedia page completely, and seen that all of those works mentioned are referenced. And then you have to consider two things from today's point of view:

The sequence of those publications.
The assumpions made. e.g. Practical Byzantine Fault Tolerance (PBFT) by Castro and Liskov assume $n>3t$. But I don't know which other protocols you mean, or what kind of assumpions they are based on. I would speculate they try to get high confidentiality (but no certainty) but allow a higher number of corrupted machines.

So while adressing the same problem, using different assumptions can lead to different solutions. And of course, later works should be aware of the prior ones - which is impossible the other way around.

I don't understand your last question. Yes, that's exactly what it does - under certain conditions. But what are you getting at? A general solution for any number of faulty machines? That's impossible - because what would be the correct result if all are faulty? If all but one are faulty how do we know what is faulty and actually correct? In that case we are wandering into the area of the halting problm as well.


With some modes you can encode then encrypt, specifically stream cipher modes (CTR, OFB). Bit errors during transmission translate to identical bit errors in the encoded plaintext, and error correction will work as intended.

However, with standard block cipher modes (ECB, CBC), the entire block is encrypted, and a 1 bit error in the ciphertext creates many bit changes to the decrypted block due to the avalanche effect. Depending on the type of correction used, this may be correctable, but it is generally better to apply the code to the ciphertext.


Finding discrete logarithm with baby-step-giant-step algorithm

To search for the values $a^x$ in the range $0 < x < k$, what you need to do is set $m = \sqrt{k}$ (rounded up), and then do the Baby Step/Giant Step algorithm for $0 \le i, j < m$.

That is, you generate the values $a^0, a^1, ..., a^{m-1}$ and the values $B\cdot a^{-0}, B\cdot a^{-m}, B\cdot a^{-2m}, ..., B\cdot a^{-(m-1)m}$; if $x<k$, then there will be a colliding pair $a^j = B\cdot a^{-im} = a^x \cdot a^{-im}$ with $x = j +im$


An attack in this context would be being able to compute valid responses to salt challenges while in possession of information lesser than the piece of data (message).

Lets assume the salt is either the same size as that of the hash function's block or is padded to that size. In essence, the first iteration of the hash function is solely computed with the salt.

Each time you challenge with a salt you are challenging with new state values of the hash function. Basically a new hash function (different default values).

To be able to attack this you would need to break the one-way property of the hash function. You would need to create associativity rules for the hash function - compute iterations of the hash function on the message in such a way that the result can be applied to an arbitrary initial state.


Which groups to use for Pedersen Commitments

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

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

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

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

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

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

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

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

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

This needs to be spelled out; perhaps by either:

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


Error-correcting Code VS Lattice-based Crypto

Broadly speaking, it's true that the main difference between "code-based cryptography" assumptions and "lattice-based" assumptions is the noise distribution.
There are of course exceptions, e.g. code-based cryptosystems using the rank metric, or binary LPN, where the noise can be described as either small Hamming weight or small Euclidean distance.

In one case the noise is inspired of the "physical noise", and in the other one, it's more mathematical and consider a more complex distance (euclidean distance instead hamming distance).

I'm not sure about these analogies of "physical" and "mathematical" noise. Both types of noise may be useful mathematical models in different physical scenarios, e.g. low Hamming weight noise can model bits flipped during transmission, while Gaussian noise can model small perturbations in an image from a noisy sensor. In any case, these analogies aren't really relevant to cryptography.

is there a theorem which certify that every cryptographic protocol based on an error-correcting code assumption could be transformed in a more efficient protocol based on lattice (i.e with the same level of security and based on a weaker lattice assumption)?

I don't know of any general theorems like this. While lattice-based protocols are often more efficient, this is not always the case and it very much depends on the cryptographic application.
A natural example where lattices beat codes is key exchange. Here, lattice-based protocols such as Kyber are much simpler and faster than their code-based analogues like BIKE, largely due to an expensive error-correction step in the code-based setting, compared with cheap rounding techniques to correct errors in the lattice setting.
Another example is the challenge of constructing linearly homomorphic encryption schemes. This is quite straightforward using lattices, but still an unsolved problem from code-based assumptions. There is even evidence that this is impossible to achieve using natural "arithmetic" techniques - see the paper of Applebaum, Avron and Brzuska; this work only looks at specific applications, but may contain the types of theorems you are interested in.
On the other hand, there are cases where small-Hamming-weight noise can give efficiency benefits. A fairly recent example is when generating private, correlated randomness (e.g. multiplication triples or random oblivious transfers) for use in secure multi-party computation protocols. Using code-based assumptions, there are efficient techniques for compressing the correlated randomness down to much shorter seeds, which can be later expanded. This compression technique crucially relies on the sparse noise distribution, and analogous methods in the lattice setting are much more expensive. (See for instance, these works)


Possible ECC backdoor and its impact on Internet traffic

If the NSA has chosen the elliptic curve parameters (the "constants") in a way that makes the elliptic curve cryptographically weak, then cryptography using that curve might be, well, insecure and breakable by the NSA.  For instance, it is known that there exist various classes of elliptic curves where the discrete log problem is easy (or not very hard).  If the NSA knows of an additional class of weak curves, and if they were able to influence the choice of parameters, it is plausible they could have chosen the parameters to make the curve weak.  Given that the NSA apparently spends $250 million per year on research, it is not implausible that they might know of classes of weak curves that are not known to the public community.

No one currently knows of a concrete, fully-worked-out way they could have done that with the NIST curves (for instance), but at the same time, no one knows of any proof or argument why this would be impossible.

In this scenario, if the curve is sufficiently weak, then it would let them mount passive attacks: by eavesdropping on traffic that is protected with ECC using those curves, they could break the ECC crypto and decrypt the traffic.  Hypothetically.  Yes, in this scenario, it could let them passively sniff HTTPS traffic that is using an ECC-based ciphersuite.  This is all terribly speculative, but you asked how it could happen, at least in principle.


How can I visually explain M of N encryption (Shamir Key Sharing)?

I've used the following a number of times in lectures, and it always goes over well with a technical audience.

I start by asking them How many points do we need to uniquely define a line? The answer I get back is always 2.
Next I ask If I give you a single point in the X,Y plane, how many lines can you draw through that point? The answer I always get back is infinite.
Finally I say, Let's consider I have some secret (usually I use 42 for the obvious reason) and I want to share this secret with many people so that any two of them could get together and reconstruct the secret.

At this point, depending on the audience, I will either ask how I could accomplish this, hoping they get the idea to somehow encode 42 into the line (e.g., as the y intercept). Or, I will just tell them how it works.

All of this can be shown visually, which I would try to add pictures here, but I don't have time at the moment.

For even non-mathematical audiences, if I start with #2 above (draw a point on the board or in a slide and ask how many straight lines can be drawn that pass through this point), it works well. Then I move to #1, then #3.


Why is the market for cryptographic primitives non-commercialized?

Are there more examples?

About the only other example I can think of is Cryptography Research Inc (now owned by Rambus); however what they sell is methods of implementing primitives (in ways that are resistant to side channel attacks); however those operate just like the standard primitives, so that might not count.

Why do people, scientists not try to commercialize their achievements, despite the fact that they could do so, especially under patent protection.

They could certainly try; however they are quite unlikely to succeed.  A large part of the crypto community is quite allergic to anything patented (unless that patented has been released for all uses); unless what they have is considerably better than the alternatives, it'll not be used at all (and so the patent fees will be for nothing).

I know that a patent can makes it difficult to adopt technology in this market.

Think: close to near impossible.  Consider the case of OCB; it might be a bit better than the competing competitors as a way to do authenticated encryption (e.g. GCM); however GCM was patent free and OCB was not, no one uses OCB.
Yes, if someone did have (say) a practical FHE method (say, with homomorphic multiplication only 1,000 times slower than an unencrypted multiplication), you could make a mint (because there is nothing else able to come close to that); however this side of such a radical improvement, people will look for unencumbered alternatives (and be able to find them)
And, while we're on the subject: I believe Certicom's patenting (and aggressive threats of lawsuits) on some implementation methods for ECC (they certainly did not own the concept of ECC) slowed down the adoption of ECC by several years; certainly, the company I was with refused to touch it until the patent scenario was resolved.  Yes, Certicom did make some money; however I don't believe this was a net plus for the crypto community...


I am literally quoting the paper here. You should really try to read the paper properly first before asking questions.

  In the notion of [22] the adversary does not get credit for finding any old collision. The adversary must still find a collision $M, M'$  but now $M$ is not allowed to depend on the key: the adversary must choose it before the key $K$ is known.

I can't really give an example of this, just as I can't give an example of why I can't produce light with a brick.


I have solved the question by carrying out the Pohlig-Hellman attack for the smaller prime factors and finding that $b \equiv 3 \mod 11$ and $b \equiv 6 \mod 19$, then finding all the integers $< 400$ satisfying this and testing them. The answer is $b=234$.

I am still interested in if anyone has a solution which usesthe order of $g$ though.


Where is defined the fact of having a "learning" and "challenge" phase in cryptography proofs?

You're confused about a few different things here. Assume that you have some cryptographic concept and you need to write down a definition of security. Such a definition can typically be written down as a game. When you write down your definition, you consider what the adversary should be able to do, i.e. it's while writing down the game that you assume whether you want active adversaries or not. This will be reflected in the operations that you allow the attacker to do, i.e. what the oracles will be.

Once you have written down the games themselves, then you typically prove bounds for an adversary being able to distinguish between the games assuming some bound on the number of oracle queries. At this point you don't distinguish between the type of adversary. The adversary can do anything that the game allows.

As an example, assume you have a security definition where you want the attacker to get access to $n$ ciphertexts corresponding to some plaintexts $p_1,\ldots,p_n$. If you want a non-adaptive adversary, you define your game to contain an oracle that will take as input $n$ plaintexts and which will return $n$ corresponding ciphertexts and allow only one query. If you want an adaptive adversary, then you would provide a single oracle that takes a plaintext and returns a ciphertext, but which allows itself to be queried $n$ times.

You might then wonder where real world computational limits fit in. What you normally prove is that if you can distinguish between two games, then you can construct an algorithm for solving say DDH or CDH. This reduction argument then links distinguishing the two given games to something you assume that can't be done and this will give you an estimate of how hard it should be to distinguish between the original games.


Feedback on rolling my own entropy gatherer

You should not remove any part of the pool, or do some more-or-less random selection out of it. Instead, just hash the whole thing with SHA-256. This will get you all the entropy there is to get out of the data, up to 256 bits, which is more than enough.

Once you got 256 bits of entropy, i.e. you accumulated physical measures which should amount, together, to at least that many bits of entropy, and then you hashed all of it, into a single 256-bit value, then you can use that 256-bit value in a good PRNG, which will produce as many random bits that you could wish for (i.e. bits computationally indistinguishable from true alea, which is the best you can practically hope for or actually need).

Now that's exactly what is happening behind /dev/urandom, CryptGenRandom(), java.util.SecureRandom, or whatever name your OS gives to its strong random number generator.


Asymmetric cipher with multiple public keys

Merely receiving a message and seeing that it has a valid signature does not provide any useful information. You also need to know who made the signature, or at least to have some information about them. If you don't know anything about who made the signature, then an adversary can generate their own message using whatever key they like.

In your scenario, there is apparently a group of trusted people. You want these people to be able to sign messages such that:

a recipient can verify that the message is a genuine message from a member of the group (as opposed to a message modified crafted by someone outside the group);
ordinary recipients do not know which member of the group produced a given message.

With just these conditions, you could make all senders use the same private key. However this would usually be a bad idea because it precludes many desirable properties, such as the ability for certain participants to tell who produced a given message, the ability to revoke the credentials of a participant who's defected, etc.

A common, relatively simple way to build such a system is to allow each participant to generate as many private keys as they like (possibly one for each message), and send the corresponding public keys to a certification authority (CA). The CA can choose what information it puts in the certificate. CAs for websites put the website name in the certificate, because that's what website certificates are for. A CA in your scenario would not put any identification in the certificates. The CA is thus an anonymity broker: it knows who is who but doesn't tell.

This scenario occurs with TPM: a TPM needs to be able to generate keys which cannot be tied to a specific TPM, but can be used to identify it with a particular service. What I described above is how multiple identities for TPM version 1 works. TPM 2 adds another method: direct anonymous attestations (DAA). I'm afraid that explaining the mathematics of DAA is beyond me. DAA may be a solution for you.


Real world example of non-interactive zero knowledge proofs?

The argument about Peggy being able to start over is not about NI-ZK proofs, it is about zero knowledge in general.

Zero knowledge does not give you a definite certainty that Peggy actally has the claimed knowledge. In your example, the probability of Peggy being able to cheat is $1/2$ after one round. If we do this for two rounds, the probability that she cheated twice succssfully is $1/4$. This goes on, until there is a satisfying probability, e.g. that Peggy could only cheat with probability of $1/2^{80}$ for 80 rounds.

Now, if we require in a NI-ZK proof that Peggy created a transcript with 80 rounds, she would have to start over for $2^{80}$ times to find such a transcript, if she doesn't have the ability to go back just one round. This has to be enforced, which is done in the Fiat Shamir heuristic by hashing all the previous results. In the CRS model this is achieved by defining the reference string only with a certain distribution and granting no one authority over this choice. This assumption implies, that Peggy can not just go back one step. If she starts over from the beginning, the entire string would change.

From a practical point of view, this is a challenge. The most commonly suggested practical solution would be a trusted third part, like for certificate authorities. But the effort of creating and publishing common reference strings is quite a lot more complex than building a PKI.

For some interesting arguments about this, and a possibly different realization I would suggest reading Cryptography in the Multi-string Model by Groth and Ostrovsky. Especially the introduction is quite interesting and their proposed new setup assumption.

Considering most usages of a CRS in the sense of NI-ZK is that there is usually some property, which is then used in order to prove the ZK property. In regular ZK you give the simulator some kind of advantage, e.g. being able to rewind one step. In this model you use some kind of commitments, which are binding in the real protocol but the advantage of the simulator is that he can decomit his previous commitsments to anything.


Some observations, though I would recommend against inventing your own protocol, at least for real world use:

  When a new Chat group is formed, a random AES Key is generated and encrypted using each users public key.

This means the protocol lacks forward secrecy. Anyone who compromises the private key of a chat participant can decrypt any previous chats they've been a part of. (Perhaps aside from ones where they've created the group.)

  Since this encryption happens on the device of the group creator, the provider of the server storing all keys never knows them.

Where does the group creator get the public keys? If the answer is "from the server", the server could swap one public key for another for which it has the private key. The server would then know the session key and could encrypt it for the real public key of the participant, with neither the group creator nor the spoofed participant noticing.

  Is there any way to recover the chat AES key using the combination of the encrypted keys and the public keys?

Other than the above, the server is also in a privileged position to decrypt the private keys. Since they are randomly generated, no one will be able to generate the same key and compare to the public key (assuming a secure RNG), but the server can try to brute force or dictionary attack the encryption password.

So you'll probably want to require strong passwords, include unique salts and use a password hash.


I wouldn't assume that the NSA has cracked AES ciphers. I would assume that most crypto systems that use AES have implementation flaws that the NSA exploits when they feel it is worth it.

In any case, when the only possible way a state can know something is by breaking a cipher, it's difficult for them to use that information; doing so would reveal that the cipher is broken. So in practice, a broken cipher is more likely to be used as a shortcut to find something that could be discovered (albeit with more difficulty) by other methods.

You might be interested in this recent story and commentary about NSA's crypt analytical capabilities.


Degenerate discrete logarithm in binary field

It is equally difficult (within a factor of 2) for any irreducible polynomial.

Suppose $g$ was your 'cheap' irreducible polynomial, that is, one for which, given $g^n$, you can rederive $n$ quickly.  Then, given an arbitrary pair $h, h^x$, you can quickly find $a, b$, such that $h = g^a$ and $h^x = g^b$, and then immediately deduce that $x = a^{-1}b$


How to compromise the privacy of NaCl encrypted messages, when nonce is reused?

NaCl's public key authenticated encryption uses a stream cipher for symmetric encryption (after key derivation using Curve25519). Like all synchronous stream ciphers, it produces the same keystream when you use the same nonce.

That means you are in the same position as when a one-time pad has been reused. (Having a known plaintext would make things even easier than mentioned in that link, since it would just reveal (a part of) the keystream.)


What is difference between Zero Knowledge proof and Zero Knowledge Proof of Knowledge?

How do you define "having" or "knowing" the witness?

This question, which is much less intuitive than it may seem, is the core reason behind the difference between proofs of language membership and proofs of knowledge. Even though it seems intuitively true, there is no known general reduction from "I can prove that this word belongs to this language" to "I know a NP-witness for this statement". The latter is, in fact, a much stronger requirement - we are asking about a specific piece of information $w$ such that some fixed polynomial-time relation $R$ outputs 1 on $(x,w)$ (where $x$ is the statement). As far as we know, it might be that someone can "prove that $x$ is in the language", in the sense of being able to send the appropriate messages in an interactive and probabilistic proof, without knowing the static and deterministic proof (i.e., the witness). It also often occurs that the language is trivial (every word belongs to the language), yet it is defined by a specific relation such that it is non-trivial to know a witness for a given word, with respect to this relation.

Well, let me give you an example: fix some prime-order cyclic group $\mathbb{G}$ with generator $g$, and consider the language $L = \{x \in \mathbb{G} : \exists w, x = g^w\}$. Yes, this is a trivial language: since $\mathbb{G}$ is cyclic, every element of $\mathbb{G}$ belongs to $L$. This means that the following is a valid interactive proof of language membership: the prover sends nothing, the verifier checks that $x$ is an element of the group $\mathbb{G}$, and accepts if it holds. But now, consider the relation that I used to define this language: $R(x,w) = 1$ iff $g^w = x$. Clearly, knowing a witness $w$ with respect to this specific relation is much stronger than just being able to show language membership: in the first case, we must show that we know the discrete log of $x$ in base $g$, while in the latter, there is nothing to do.

Now, to answer my own initial question: in cryptography, we define knowledge by saying that a party knows some information if this information can be efficiently learned from this party. Formally, this is stated as follows: a proof is a proof of knowledge of a witness $w$ if there exists a probabilistic polynomial-time extractor which, given the code of the prover, is able to extract the witness $w$ from the prover. This property is crucial in many security analysis. Typically, we will want show that a cheating prover allows us to reach a contradiction to some security property, and the extractor will help us in deriving this contradiction.


Definition of soundness (a different approach) in "Witness Indistinguishable and Witness Hiding Protocols"

The soundness definition that you are familiar with is the normal soundness definition of proof systems. The soundness definition in this paper is a definition of soundness for "proofs of knowledge", i.e., the goal of the prover is not only to convince the verifier that the statement is true but also that it knows a witness. This can be a much stronger requirement.
Now, there are two main aspects in which this differs to the notion you're familiar with. The first aspect is related to this question: How can we formalize that the prover "knows" a witness? The short answer in informal words is: if there's a witness in the prover, then there must be some way to get it out of the prover. This extraction process is the job of the knowledge extractor $M$ in the definition you found. The knowledge extractor $M$ is given black-box access to $P$ in order to extract the witness. I could expand on this concept but I believe there are a lot of very good resources with different levels of rigor that elaborate specifically on this point [1,2,3,4] because this is often a source of confusion for newcomers.
The second difference is that this definition relates the accepting probability of $P$ with the probability that $M$ extracts. In other words, whenever $P$ convinces the verifier, then $M$ should be able to extract a witness (with a negligible error). An alternative (but flawed) definition which is closer to the definition you're aware of would require that if $P$ convinces with non-negligible probability, then $M$ can extract successfully.* Variants of this definition have indeed been used early but they're too weak for what we typically need, as Bellare and Goldreich [4] explain in an entire paper that I very much recommend for a deeper understanding. In Appendix A, they explain why the definition you found is better than the flawed definition but still not optimal.
A final remark is that the paper you've found is already pretty old. These were the first days of zero-knowledge when the community was still in the process of finding good definitions for zero-knowledge proof systems, which can be nicely seen from the paper by Bellare and Goldreich [4]. The definitions in newer works may be clearer.
*Note that the condition "if the statement is in the language" would obviously be too weak: just because the statement is in the language does not mean that some $P$ (which could be just a dummy machine outputting only zeros) knows a witness.


"Power of one" as input to functions of a cryptosystem

The notation $1^\lambda$ means a string with $\lambda$ characters all of them equal to 1. For instance, if $\lambda = 3$, then $1^\lambda$ is $111$.

And yes, it typically stands to the security parameter, from which the probability of "breaking" the system is measured (as well as the resources needed to do so and also to execute the cryptosystem's procedures).

The reason to use $1^\lambda$ instead of $\lambda$ is theoretical. The point is that the functions run by the users (KeyGen, Enc, Dec, etc) are supposed to run in polynomial time and the best attacks are usually supposed to take exponential time. But polynomial/exponential time regarding what? Regarding the size (length) of the input. So if you say that the input is simply an integer $\lambda$, what is the input's length? But using $1^\lambda$ as the input, the size is clearly $\lambda$, because the input has $\lambda$ characters (or letters, or bits...).

And about this specific scheme that you've cited, I would say that the authors are probably miss-using the notation. It seems that $\lambda$ measures how many bits the integers used there have. So, the algorithms run in poly$(\lambda)$ as expected. But, as it happens often (e.g. with RSA), for a security level of $\lambda$ bits, the integers used in the scheme must have much more than $\lambda$ bits.


Relationship between Elliptic Curve Discrete Log, Integer Discrete Log, and Integer Factorization

Actually, there are two known reductions among these three problems:

If you can solve discrete logs in $Z^*_n$ for composite $n$, you can use that to efficiently factor $n$
If you can solve discrete logs in $GF(p^k)$, you can compute discrete logs in an Elliptic Curve over $GF(p)$.  That's because there is a known mapping of Elliptic Curves over $GF(p)$ into $GF(p^k)$ (for an integer $k$ that depends on the curve) that preserves the group operation; hence you can solve discrete logs over an Elliptic Curves by mapping the generator and the target into $GF(p^k)$, and solving the discrete log there.  Now, for curves used in practice, $k$ is large enough that, with the current discrete log algorithms, this method is actually slower than just using a generic discrete log algorithm in the elliptic curve.

Of course, neither of the above reductions would apply to the recently discovered algorithms for doing discrete logs over small characteristic fields; for the former, we're not talking about a field at all ($Z^*_n$ is a ring, not a field), and for prime elliptic curves (which is what we use in practice), $GF(p^k)$ has a very large characteristic.


Why exactly is Blowfish faster than AES?

Blowfish has strong points regarding speed because bulk encryption (and decryption) reduce to an alternation of: a 8->32-bit table lookup, and one or two 32-bit operations (addition or XOR). That structure is very well suited to 32-bit CPUs with a short pipeline and a fast cache of at least 4 kByte; and is well suited for a straight C implementation, which generates code that often is very near optimum.

For each byte enciphered, and unless I miscount:

Blowfish performs on average 8 table lookups and 10.25 straight 32-bit operations.
AES-128 performs on average 10 table lookups and 7.75 10.25 straight 32-bit operations (when using a common optimization also requiring 4 kByte of tables).

Table lookups are much more expensive than straight 32-bit operations (most of these come almost for free in practice), and dominate the cost. Thus yes, Blowfish can be a little faster than AES implemented in software; especially if the AES implementation is not optimized to the max, or is AES-256.

Other than that, Blowfish and AES are not playing in the same league, and AES often wins without battle:

Blowfish is a 64-bit block cipher, while AES is a 128-bit block cipher; this is a serious issue in a growing number of applications.
Blowfish key setup is a slow process that produces 4 kByte of table per instance, in RAM. By contrast AES can be implemented efficiently (at least in hardware) with no RAM, and (for encryption, which is the most used) no pre-computation at all (decryption requires a tiny pre-computation).
The 4 kByte table (or 1 kByte, 512 bytes, or even 256 bytes with speed trade-of) used for fast software AES implementation can be shared between instances (or in ROM/flash), it can't in Blowfish.

That makes Blowfish a terrible algorithm when 64-bit block is an issue (e.g. CBC mode with gigabytes of data); or when key agility matters (on occasions the relative slowness of Blowfish's key setup is an asset, see bcrypt); or for hardware implementation; or when 4 kByte is a lot of RAM (e.g. some embedded systems, or a server handling many simultaneous connections).

Also: as rightly pointed in cherio's comment, AES has hardware implementation on many modern CPUs, and that more than offset any speed advantage Blowfish may have (but the question states "AES accelerators are not used").


SHA256_HMAC for deriving session keys using a counter

Sure, that should be fine. It's probably more secure than KDF1 & 2 that use a normal hash method and a 4 byte counter. HKDF however can certainly be used for this, but it seems you only need to differentiate, rather than extract and expand.


Research question: usefulness of newly discovered symmetric key cryptosystem

The unique (we think) property of the cryptosystem offered by this mathematical discovery is that so long as Alice and Bob publicly choose a new particular mathematical object ($T$) to apply their key to before each message sent (of which there is a continuum of choices for $T$), they can use the same initially chosen key to send an arbitrary number of messages, for we can prove that it would be mathematically impossible for Eve to ever determine the key if such a method was used.

Actually, that can easily shown to be impossible, as long as we make a few minor assumptions:

We will assume that the adversary is computationally unbounded (that is, he can perform any finite number of computations)
We will assume that the adversary has access to a number of encrypted messages (along with their corresponding $T$ values); we'll denote these pairs as $(T, C)$ values.
We will assume that the adversary can recognize an incorrect decryption (perhaps he knows the contents of some of the encrypted messages, which is a standard assumption in cryptography)
We will assume that, if some keys act the same (that is, they encrypt and decrypt identically), then finding any key in the same equivalence class as the 'correct' key would count as success for the adversary

So, here is what our adversary would do; he would go through all possible values of the key $K'$, and with each possibility, decrypt every ciphertext $(T, C)$ and see if it results in a plausible plaintext.  If it every $(T, C)$ pair results in a plausible decryption, then the value $K'$ is declared correct.

It should be obvious that, if $K'$ were not the correct key (or in the same equivalence class), then some ciphertext would have decrypted incorrectly; hence this finds the correct key.

Now, the above procedure shows that key recovery is mathematically possible (and we could make the proof less hand-wavy if we shifted to the question of unknown message decryption, which is what the adversary is really interested in).  Of course, if the space of possible keys is large, this procedure is impractical (as we really don't actually have an adversary with unbounded computation), but does leave open the question of whether there are computational optimizations that would make it practical.  That I don't know the answer to, and frankly speaking, neither do you.

And, to answer your questions:

  Does a cryptosystem exhibiting such properties already exist?

Do we have efficient symmetric cryptosystems that are believed to be secure?  Sure, we have quite a number of them.

  Even if not (ie. analogous systems already exist), should we pursue publishing the method in a journal?

Actually, in cryptography, there really aren't many journals (there's the Journal of Cryptology, but that's about it, not counting predatory ones that everyone ignores); all the exciting new work is published in conferences.  On the other hand, I can't think of any conference that would be interested in what you have; the next level down is publishing on eprint (or arXiv), however I'm not certain that even the eprint editors would be that interested in taking this (unless you do some work to show that you've done the basics to ensure that your system isn't trivially weak).

If you do want to pursue your idea, then things to consider:

Is your system still strong even if the adversary knows some of the encrypted messages?  What if the attacker can pick some of the messages (and use what the ciphertexts look like to decrypt other messages of unknown contents)?
How would your system respond if an adversary modifies one of the ciphertexts $(T, C)$, and passes that modified ciphertext to be decrypted?  Will the modified ciphertext be rejected by the decryptor?  That can be handled by other means, however that slows things down (and modern fashion is that encryption and integrity protections should be provided by the same cipher).
You say your system is efficient; what do you mean by that?  For example, if it were implemented on a modern CPU, how long (in CPU cycles) would it do encrypt a message of size L?  If it takes T cycles, what's the size of $T/L$?  If it's more than 5 or so, well, your system wouldn't be considered efficient (by modern standards).


The whole point is that in the Aritmetic Circuit (AC) model we take a field and use field operations (+,*) as building blocks.
Each field operation is represented as a single output multiple input gate.
The total number of gates and the depth of the AC are typical measures of complexity. Size and bit structure of inputs does not explicitly come into it, each operation is considered of some fixed complexity.
The goal is to find the minimum complexity circuit realizing a certain formula.


Combining Random Hashes - avoiding collisions and ensuring randomness

I'd treat your input as one 192 bit input instead of thinking about 5 separate inputs.
If you don't need security, you can always reduce the number of rounds of cryptographic primitives. If you merely need statistically random output, 20% of the usual number of rounds should be fine with many hashes.

A few suggestions:

SipHash has good performance for short inputs. It's pretty easy to implement as well.

The default version of SipHash has 2 rounds for each 64 bits of the input and 4 rounds of finalization, called SipHash-2-4. Sacrificing security you could reduce that to SipHash-1-2 or even SipHash-1-1.

I expect a cost of 200 CPU cycles using SipHash-2-4 on your 192 bit input on a modern 64 bit CPU and 100 cycles with SipHash-1-2.

A round of SipHash:

v0 += v1; v1 = ROTL(v1, 13); v1 ^= v0; v0 = ROTL(v0, 32);
v2 += v3; v3 = ROTL(v3, 16); v3 ^= v2;
v0 += v3; v3 = ROTL(v3, 21); v3 ^= v0;
v2 += v1; v1 = ROTL(v1, 17); v1 ^= v2; v2 = ROTL(v2, 32);

SipHash treats the input as a sequence 64 bit words. You can use A, BC, DE as the three inputs. SipHash as specified applies some padding at the end, which increases the effective input size.

Since you have constant length inputs, you can simply leave out the padding, so the input is only 3 words instead of 4.
Rijndael-256 truncated to 64 bits. This should have great performance when used with AES-NI, but implementing it yourself will be hard.
MD5

While it's not secure against deliberate collisions, accidental collisions are as rare as one can expect. But it will be a bit slower than the alternatives.
A variant of Skein256

Skein is fast on 64 bit CPUs. Use the variant based on Threefish256, not the variant that uses Theefish512 and merely truncates since, the smaller block size doubles performance for short messages. Remove the finalization compression, it's only necessary for some security properties you don't need.

Then you can proceed to reduce the number of rounds to the smallest value that's still random enough for your purposes.

Personally I'd go with round reduced SipHash.


Plaintext message space in Somewhat Homormorphic Encryption scheme?

Answer to question 1

I don't know about any somewhat (or leveled) homomorphic encryption whose plaintext space is the field $\mathbb{F}_p$.

Several schemes work over the ring $\mathbb{Z}_t[x] / \langle f(x) \rangle$, which is isomorphic to the field $\mathbb{F}_{p^n}$ when we chose $t$ to be a prime $p$ and $f(x)$ to have degree $n$. However, for security reasons, we usually are not able to chose $n = 1$.

Schemes based on integers usually have the field $\mathbb{Z}_2$ as the plaintext space and they do not seem difficult to adapt to an arbitrary prime instead of $2$.

Answer to question 2

Yes, multiplying a ciphertext by a plaintext increases the noise.

Ciphertexts in these noisy schemes are (roughly speaking) of the form $f(m) + e$, where $f$ is some function, $m$ is the message, and $e$ is the error. When we multiply a ciphertext $c = f(m) + e$ by another message, let's say $m'$, we end up with something like $f(m) \cdot m' + e\cdot m' = f(m \cdot m') + e'$, and this new error $e'$ is bigger than the original error $e$.

For instance, considerer the YASHE scheme:

Ciphertext format: $c = \Delta m + e + hs$, where $h$ is the public key, $e$ and $s$ are random polynomials.
When we multiply by a plaintext $m'$: $c \cdot m' = \Delta m m' + e m' + hsm' = \Delta m m' + e' + hs'$.

As it is said on page 11 of SEAL's manual, for the FV scheme "plain multiplication increases the noise by a constant factor that depends on the plaintext multiplier".

And I am quite sure it also happens on plain multiplication of BGV scheme.


Are private and public key sizes of Elliptic curve related?

The size of the public key depends on the elliptic curve used. Any private key will produce a point on the curve, which is the same size – approximately 256 bits for 256-bit curves, for example.

Random numbers from a small range could be insecure, however. The secure way to generate the private key is to take it from the range $[1, l-1]$, where $l$ is the order of the base point. So in the end the size of the private key and the public key should be related, though not necessarily equal (if the cofactor is larger than 1).


For data shorter than 32 bytes, is it sure that no collision exists?

I think what you're asking is:

  We know there certainly exist two 33-byte strings $m \ne m'$ such that $H(m) = H(m')$, when $H$ is (say) SHAKE128-256, because there are only $2^{256}$ distinct possible outputs of $H$ and $2^{262}$ distinct possible 33-byte messages.

  Do there exist two <32-byte strings, say 16-byte strings, $m \ne m'$ such that $H(m) = H(m')$?

Suppose the output of the hash function $H$ is $h$ bits long, and suppose the input is $t$ bits long.  If we model $H$ as a uniform random function, then each output for distinct messages $m_1, m_2, \dotsc, m_n$ is an independent random variable $H(m_1), H(m_2), \dotsc, H(m_n)$ with uniform distribution on the $h$-bit strings.  In this case, we are wondering whether there is any collision under $H$ in $n = 2^t$ distinct messages.

By the birthday paradox, the probability of a collision grows quadratically with the number of messages: it is at most $n^2\!/2^h = 2^{2t}\!/2^h$; of course, this bound is not very helpful if $t \geq h/2$, but the probability of a collision rapidly converges to $1$ as $t$ exceeds $h/2$.  So, there's roughly 50-50 odds that there's two 16-byte inputs that collide under (say) SHAKE128-256—but unless you find some amazing cryptanalysis of SHA-3, we'll never know what those two inputs are, if they exist at all.  The same goes for any other unbroken hash function of the same codomain, like SHA-256.


Fixed point of the SHA-256 compression function

SHA-256 is based on a Davies–Meyer compression function. Easy to find fixed-points are a known property of this construction.

A notable property of the Davies–Meyer construction is that even if the underlying block cipher is totally secure, it is possible to compute fixed points for the construction : for any $m$, one can find a value of $h$ such that $E_m(h) \oplus h = h$ : one just has to set $h = E_m^{-1}(0)$. This is a property that random functions certainly do not have. So far, no practical attack has been based on this property, but one should be aware of this "feature".
The fixed-points can be used in a second preimage attack (given a message m1, attacker finds another message m2 to satisfy hash(m1) = hash(m2) ) of Kelsey and Schneier for a $2^k$-message-block message in time $3 \cdot 2^{n/2+1}+2^{n-k+1}$. If the construction does not allow easy creation of fixed points (like Matyas–Meyer–Oseas or Miyaguchi–Preneel) then this attack can be done in $k \cdot 2^{n/2+1}+2^{n-k+1}$ time. Note that in both cases the complexity is above $2^{n/2}$ but below $2^n$ when messages are long and that when messages get shorter the complexity of the attack approaches $2^n$.

(from One-way compression function - wikipedia)
Thanks to Samuel Neves for pointing this out.


Why does the modulus of Diffie–Hellman need to be a prime?

Answer to Martin's and Vadim's comments:

Let $n:=p$ and you want to find $x$ with $g^{x} \equiv y \bmod pq$

Calculate the two easier DL problems:
 ${x_p}$ with $g^{x_p} \equiv y \bmod p$
 ${x_q}$ with $g^{x_q} \equiv y \bmod q$

Note that
$x_p \equiv x \bmod p-1$
$x_q \equiv x \bmod q-1$

With the chinese remainder theorem you can calculate $x'$ from $x_p$ and $x_q$ with
$x' \equiv x \bmod lcm(p-1, q-1)$


Is Schnorr's digital signature a non-interactive zero-knowledge proof?

Yes, and in fact, Schnorr's signature scheme was originally described as a non-interactive protocol. I think the confusion around interactivity comes from the fact that the same paper first described a interactive identification scheme, which can be viewed as a specialization of the signature scheme for empty messages.
In both schemes, challenges can be generated either interactively or using hashes. The non-interactive variant can be viewed as an application of the Fiat-Shamir transform, although Schnorr did not describe it as such.
Note that while more general formulations of the Fiat-Shamir transform involve a random oracle assumption, the Schnorr signature scheme in particular has weaker requirements -- see Navel et al. and Chen et al.


Disclaimer: the only reason to go this way is if you have an 8 bit CPU. Otherwise, select AES.

Sending nextKey in the data packet is silly. What you want is key + iv. Look up the CipherSaber 2 variant of RC4. This covers the attack used on WEP just fine. Bear in mind though this wants a good RNG (probably hardware RNG) and 10 bytes of iv. Unless you can store the iv counter, there's no good way to reduce it. There are other possible attacks on RC4 though, the most worrying is the one that can be used against 1 billion messages to reveal the first 128 bytes of message. A plausible workaround is simply eating the first 256 bytes off the stream (don't bother sending just discard).

Your key length here won't be 64 bits though. That's too small. You need at least 128 bits.

We do have to keep in mind that RC4 and all its variants are weakening. There is simply no good explanation for the fact it is as strong as it is today. It really should not be. The next attack might doom it.

EDIT: Answer no longer good. A recently published attack against RC4 is no longer mitigated by the CS2 variant. I was not expecting this.


What is the role of the round counter in the key schedule of PRESENT?

to prevent self-similarity of key scheduling

The importance of constant addition (not only present cipher) appears in preventing key schedule-based attacks  such as slide attack ,related key attacks and other structural attacks such as: invariant subspace attack , and nonlinear invariant subspace attacks.

paragraph  5.4 Key schedule attacks in original Present Block cipher
answers your questions.


What is the most common encoding of messages to polynomials?

In NTRUEncrypt, a raw message m of octet string of length l octets is encoded through the following steps:

Padded it with a random salt of b byte and a few extra information to form the actual octet string M that is to be encrypted.
This M byte string is then converted to a binary string Mbin using octect-string-to-binary-string-primitive (OS2BSP).
In NTRUEncrypt, the message is actually a ternary polynomial, so for every 3 bits in Mbin, use a binary to ternary mapping as follows to convert it into a ternary string Mtrin.

{0, 0, 0} -> {0, 0}
{0, 0, 1} -> {0, 1}
{0, 1, 0} -> {0, -1}
{0, 1, 1} -> {1, 0}
{1, 0, 0} -> {1, 1}
{1, 0, 1} -> {1, -1}
{1, 1, 0} -> {-1, 0}
{1, 1, 1} -> {-1, 1}

Finally the message polynomial m(x) is to take each element in Mtrin as the corresponding coefficient.

See section 8 for more details of conversion, and section 10.2.2 for encryption procedure.
https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/doc/EESS1-v3.1.pdf


Hamiltonian Path Zero Knowledge Proof using Commitments to a Series of Edges

This does seem to be zero knowledge; as you say, you don't actually commit to the adjacency list. Rather, you commit to a series of edges, in random order.

Regarding the question: First, your assumption is that $n^2$ commitments, each to a single bit, is more expensive than $|E|$ commitments, each to $2\log n$ bits (to encode two numbers for the edge). This is a reasonable assumption for many commitment schemes but not necessarily for all. (Of course, it is very reasonable for sparse graphs.)

However, the main thing here is that the proof of Hamiltonicity is a theoretical proof of feasibility. Improving the concrete cost in this way is not of great interest. In any case, the protocol is unlikely to be used (applying a Karp reduction and then using Hamiltonicity will kill you in almost all cases).


Encrypt with one cipher and decrypt with a different cipher?

I've checked out the source code (well, more or less, it's not that well designed, the main crypto class is 1600 lines) and as Richie guessed, the algorithm is stored together with the ciphertext.

Pretty gruesome stuff, but it does do EAX mode for text strings to my surprise. It probably only uses it for text strings originating from the password vault code though.

File encryption is performed in CBC mode. It does (ZIP) compress and stream files using CBC mode. It uses a static IV but this is offset by a random header that is included into the encryption.

This is a homegrown project with little documentation or comments in the code and a  slightly erratic class design.

Thanks go out to Tron to supply us the link to the format defition on the Paranoiaworks website.


Does the GCM authentication tag need to be protected?

The GCM authentication tag doesn't need to be encrypted. Just attach it to the ciphertext in the clear.

A very quick intuitive justification:

It's an authentication tag derived from the ciphertext, it doesn't contain any sensitive information itself.
The security of the GCM model assumes the tag is left in the open. (The GCM spec, SP 800-38D, shows the auth tag output in the clear, see section 7.1.)


Many cryptographic algorithms are expressed as iterative algorithms. E.g., when encrypting a message with a block cipher in CBC mode, each message "block" is first XORed with the previous encrypted block, and the result of the XOR is then encrypted. The first block has no "previous block" hence we must supply a conventional alternate "zero-th block" which we call "initialization vector". Generally speaking, an IV is whatever piece of data is needed to begin running an algorithm, and is not secret (if it was secret, we would call it a "key", not an IV).

If you take a look at MD5, you see that it is an iterative algorithm which has a "running state" (four 32-bit words) and processes message data by 64-byte chunks, each yielding the next running state; the final state is the hash output. This has to begin with a conventional initial state, which is described in section 3.3 of the RFC.

Since an IV has some cost (e.g. it must be transmitted along a message), it is not there just for aesthetic reasons: algorithms which use an IV need it to fulfil some sort of security property, and this may imply some constraints on what value an IV may have. This really depends on the algorithm. For instance, with MD5, the IV is fixed and this is not an issue. For the case of CBC, see this answer to a previous question. Since uniform randomness is a difficult requirement (alea is a scarce resource, especially in embedded systems), it is considered a good thing if an encryption algorithm requires only a non-repeating IV (e.g. a simple counter); this is all that newer encryption modes such as EAX need.

An IV can be made public but nothing forces you to. It still tends to have a lifecycle distinct from that of a key, in that (for symmetric encryption) you need a new IV per message but not necessarily a new key. For instance, with TLS 1.2, a session key is created during the tunnel setup (the "handshake"), then data is encrypted as so many "records" (up to 16 kB of data per record) and each record has its own IV.


How is text converted to a number for RSA?

You never use RSA to encrypt large binary objects, since it's to expensive to do many calculations.

Instead, RSA is used in a key exchange or key transport protocol to send a key for a symmetric-key algorithm, such as AES (with a cipher chaining mode, such as CBC), which is then used to encrypt huge messages.

Also note that textbook RSA isn't secure. Some differences between textbook RSA and deployed RSA are mentioned there: https://crypto.stackexchange.com/a/1449/4874


Generating 1024 bits of entropy from a seed

You should use a well-vetted implementation of a well-researched key derivation function that can output at least 1024 bits.

HKDF-SHA-256 is the standard and secure  choice these days, although constructions based on SHA-3 and Blake2 are also in use.

If the characters you’re hashing are created by a human, use a specialized and intentionally slow password-based key derivation function like scrypt or Argon2 instead.


Question about Damgård–Jurik crypto system

The simple answer is that the element $(n+1)$ is of order $n^s$, i.e. $(n+1)^{n^s} \equiv 1 \bmod n^{s+1}$. Thus the first part can be written as $(1+n)^{jmd \bmod n^s}$.

For the other part it is $(x^mr^{n^s})^d$, it is written in that way so that it is easier to see the setting that $d \equiv 0 \bmod \lambda$ ensures this part $(x^mr^{n^s})^d \equiv 1 \bmod n^{s+1}$. To see why, note that $x^\lambda \equiv 1 \bmod n^{s+1}$ and also $(r^{n^s})^\lambda \equiv 1 \bmod n^{s+1}$. The explaination is as the following:

We know that $x\in H$ where $H=\{g^{n^s} \bmod n^{s+1}|g\in Z_{n^{s+1}}^*\}$ is a subgroup of $Z_{n^{s+1}}^*$, we know $r \in Z_{n}^*$ and $Z_{n}^*$ is a subgroup of $Z_{n^{s+1}}^*$ (thus $r$ is also in $Z_{n^{s+1}}^*$).
We know the exponent (the least common multiple of the orders of all elements of the group) of $Z_{n^{s+1}}^*$ is $n^s\lambda$ (see here, $\lambda$ in the paper is a shorthand for $\lambda(n)$). In other words, $a^{n^s\lambda}\equiv 1 \bmod n^{s+1}$ holds for any element $a$ in $Z_{n^{s+1}}^*$
Therefore, $x^\lambda=g^{n^s\lambda}\equiv 1 \bmod n^{s+1}$, and $r^{n^s\lambda}\equiv 1 \bmod n^{s+1}$

It thus follows that if $d\equiv 0 \bmod \lambda$ (i.e. $d = k\lambda $ for some k), then $(x^mr^{n^s})^d \equiv 1 \bmod n^{s+1}$.


Is this algorithm demonstrating "proof of work"

In anticipation of this question being migrated.....

there is no need for the client-side to hammer /urandom. The odds of any subsequent random byte stream hashing to the same prefix are the same (actually worse) as the odds of any simple incrementing value.... i.e. you may as well change the urandom reference to just something++
A sophisticated client-side 'attacker' who knows the number of significant digit matches would be easily able to compute a rainbow-table of tokens that match the incoming digits. This ranbow-table will not take much longer to generate than the actual proof-of-work you require, and would be almost instantaneous to query.

All this process does is make legitimate access harder, and nefarious access fast.... ;-)


Gaussian distribution over ideal lattices

The space $H$ is defined such that it is isomorphic to $\mathbb{R}^n$ for some $n$. Therefore, we can choose a basis $\{h_1,\ldots,h_n\}$ such that for every $h\in H$ there exist $x_1,\ldots,x_n\in\mathbb{R}$ such that $$h=x_1h_1+\cdots+x_nh_n.$$
So we think of elements of $H$ as linear combinations of a basis with coefficients in $\mathbb{R}$.

On the other hand, we defined a number field $K=\mathbb{Q}(\zeta)$. As a vector space, this is isomorphic to $\mathbb{Q}^n$ (this $n$ is the same $n$ from above, we simply construct $H$ that way). Choosing a basis $\{k_1,\ldots,k_n\}$, for every $k\in K$ we can find $y_1,\ldots,y_n\in\mathbb{Q}$ such that
$$k=y_1k_1+\cdots+y_nk_n.$$
So we think of elements of $K$ as linear combinations of a basis with coefficients in $\mathbb{Q}$.

The distribution $D_r$ is defined on the space $H$, which has coefficients in $\mathbb{R}$. We could try and apply this to $K$, but the coefficients of $K$ are only in $\mathbb{Q}$. The statement you cite says that we apply $D_r$ to the space which has the same basis as $K$, but with coefficients in $\mathbb{R}$. This space is denoted $K\otimes_\mathbb{Q}\mathbb{R}$.


Get RSA PlainText without Knowing Private Key

A message is encrypted with RSA as follows:

$c_1 = m_1^e \bmod{n}$

If I throw this message at your function RSA-Crack(), there is a $0.01$ probability that the function will return the plaintext $m_1$.

To increase this probability, we can use the malleability of textbook RSA (this is also known as the homomorphic property of textbook RSA). Given $c_1$, compute $c_2 = c_1\cdot 2^e\bmod{n} = (m_1\cdot 2)^e \bmod{n}$. There is again a $0.01$ probability that $c_2$ can be broken by your function. Since a break there would give you $m_1$ (just divide the answer by $2$ if it is successful), the probability that you have recovered $m_1$ is now $0.02$.

Repeat this process replacing $2$ with $3,4,5,\cdots,100$ and you have a guaranteed break of the plaintext. I.e, compute $c_i = m_1\cdot i^e\bmod{n} = (m_1\cdot i)^e\bmod{n}$ and run $c_i$ through your RSA-Crack() function. If it is successful, divide the answer by $i$ to get $m_1$.


Applicability of birthday attack to AES brute force

The citation as now expanded is clearly in the context of key search for a cipher, and grossly wrong, including time estimate to find a DES key with odds 50% with 1 million keys tested per second (that is over 11 centuries where 7.9 minutes is stated). In other contexts, the explanation could be right except for a moderate factor erring straight on the unsafe side, or vaguely related to a relevant phenomenon. In all cases, that's wrong; as well as the estimate of key test rate: one million DES keys per second on a consumer desktop CPU was already feasible circa 1997.

As pointed in comment by the question's author, in the context of key search we need to search half of the key space to find a particular key with odds 50% (baring equivalent keys, and shortcuts to search). The birthday bound is irrelevant. After we searched the number of keys indicated in the citation ($1.774\sqrt n$ where $n$ is the size of the keyspace), our odds of having found the right key (assumed randomly chosen and initially unknown) is the ratio of the number of (distinct) keys tested, to the size of the keyspace; and that's in the order of $1.774/\sqrt n$, which is negligibly small, rather than 50% as stated.

The multiplicative constant for the birthday bound should be $\sqrt{\log4}\approx1.1774$ where the citation gives $1.774$, and uses it, making even the leftmost digit of both birthday bounds stated wrong, and erring on the unsafe side; see final note. Except for that, the explanation would have been right if the issue had been to guard against finding collisions for a one-way function such as $H:\{0,1\}^{128}\to\{0,1\}^{128};\; H(K)=\operatorname{AES-128}_K(0)$.

If we consider the security of a block cipher such as DES or AES in CBC mode, it is correct to invoke the birthday bound for collisions over the block size space; and for AES-128 this is the same as the key space, which makes the order of magnitude of the numbers in the second half of the citation relevant; however in that context the explanation does not justify "why larger key sizes are necessary"; only why larger block sizes are necessary.

As a practical illustration of the relevance of the birthday bound for CBC mode, consider a 40 GiB file, that is suspected to be the result of enciphering with 3DES in CBC mode a movie file directly extracted from a Blu-ray disk (perhaps with a little random added at the end of the file to hide the exact length of the original). The encrypted file is large enough that with odds better than 50%, two enciphered 64-bit blocks are identical. This implies that the eXclusive-OR of the two corresponding blocks in the original is equal to the eXclusive-OR of the preceding blocks in the encrypted file. That observation makes it feasible to demonstrate beyond reasonable doubt the nature of the encrypted file if the original is available, even if we have to decide among thousands of potential originals.

Note: The actual birthday bound for 56-bit (resp. 64-bit and 128-bit) values is 316,058,597 (resp. 5,056,937,541 and 21,719,381,355,163,562,492). That's applying David Brink: A (Probably) Exact Solution to the Birthday Problem (in The Ramanujan Journal, June 2012, Volume 28, Issue 2, pp 223-238), conjecturing that the number of uniformly chosen values among $n\ge1$ at which odds of collision reaches 50% is
$$\left\lceil\sqrt{n\log4}+{3-\log4\over6}+{9-\log^2 4\over72\sqrt{n\log4}}-{\log^2 4\over270n}\right\rceil$$
which in cryptography we tend to approximate with $1.1774\sqrt n$ or just $\sqrt n$, with both erring somewhat on the safe side from the legitimate user's perspective.


The full AES key schedule used by each call to the AES block cipher. The use of the key schedule does not stretch across different calls for different block encryptions.

Internally, the 14 rounds (for 256 bit keys) of the AES round function use each of the 14 round keys. Those 14 round keys are what comprise the key schedule.

The linear property you observed is indeed correct when AES is used this way. Each block is encrypted without context, and always encrypts to the same ciphertext. This method is called ECB mode. In the real world, that property is a weakness and a different mode like CBC would be used to destroy that property (although the key schedule is not used to do so).