Use ElGamal to solve Diffie-Hellman problem

Since you're learning, I won't go ahead and give you the answer; I will try to point you in the right direction.

Consider what Elgamal decryption is: if the private key is $a$ (and hence the public key is $g^a$), and you're given a ciphertext $(b, c)$, the ElGamal decryption is $b^{-a} \cdot c$

Now, assume that we have an Oracle that, given an arbitrary public key $g^x$, and a ciphertext $(g^y, z)$, would return the ElGamal decryption.  Can you see how you could use that by passing it a public key and ciphertext of your choosing (hint: write out what the decryption would look like in that case)?

(Further hint: given $g^x$, it is easy to compute $g^{-x}$, as that's just the multiplicative inverse)


Concrete Example of AND Gate Using Garbled Circuit

The main conceptual idea behind garbling is to "label" Boolean values on wires in the circuit with keys of a (symmetric key) encryption scheme.
Computations are then done in terms of these labels, instead of the underlying Boolean values. Throughout the rest of this, I will use $\mathsf{in}_0, \mathsf{in}_1, \mathsf{out}$ to denote the two input wires of the AND gate, and the (single) output wire.
If we view these as directly taking Boolean values, these satisfy the equation:

$$\mathsf{in}_0\land \mathsf{in}_1 = \mathsf{out}$$
In particular, given $\mathsf{in}_0, \mathsf{in}_1$, we can compute $\mathsf{out}$ using this formula.

One way to make this computation "private" would be if instead of directly having $\mathsf{in}_i$ and $\mathsf{out}$ take Boolean values, we "obfuscate" things somewhat.
Generate the keys $k_{\mathsf{in}_0, 0}, k_{\mathsf{in}_0, 1}, k_{\mathsf{in}_1, 0}, k_{\mathsf{in}_1, 1}, k_{\mathsf{out}, 0}, k_{\mathsf{out}, 1}$.
Note that there are precisely 6 keys --- for each of the (three) wires in the circuit, we generate a key for each of the possible values the wire can take.

Now if someone gives me two keys $k_{\mathsf{in}_0, i}, k_{\mathsf{in}_1, j}$, I don't know what the "values" underlying the keys $i$ and $j$ are.
But I also don't know how to compute the AND of the keys, meaning I can't yet compute $k_{\mathsf{out}, i\land j}$.
If I could somehow (without learning the values $i$ and $j$ directly) we'd be done.

Garbling allows us to do this by computing the four ciphertexts $C_{i, j} = \mathsf{Enc}_{k_{\mathsf{in}_0, i}}(\mathsf{Enc}_{k_{\mathsf{in}_1, j}}(k_{\mathsf{out}, i\land j}))$.
If we know both keys $k_{\mathsf{in}_0, i}$ and $k_{\mathsf{in}_1, j}$, we can decrypt the ciphertext $C_{i, j}$ to learn $k_{\mathsf{out}, i\land j}$.
But if I don't know those keys, by the security of the underling encryption scheme I cannot decrypt $C_{i, j}$, keeping "the rest" of the possible computations "private".

So Alice's job (in the garbling step) is to generate all of the above information:

Two keys for each wire in the circuit.
$2k$ ciphertexts for each $k$-arity gate in the circuit.

This process is called "garbling" the circuit.


Is it OK to just hash a symmetric key to derive an authentication key?

Yes this is "OK".

  Please correct me if I'm wrong there.

You are correct.

It's effectively ratcheting the original key.

However there may be a more elegant solution such as using static keys for auth and ephemeral keys for key agreement (i.e. use Ephemeral-Ephemeral Diffie-Hellman for each new message).


Increased CRC collision probability when adding bits to input message

First of all, if your goal is to keep the garbled messages to "once every hundred years", well, you already don't meet that goal, even before the change.  With an 8 bit CRC, a random change has a probability 1/256 of being accepted; hence if your wireless network has a transmission error at least once every three months (which, to me, sounds like an unrealistically reliable transmission mechanism), you get an undetected garbling more often than "once every hundred years".

Now, what you're doing is effectively assigning two different CRC (or hash) values for each message; when you receive a message and its CRC (hash), you'll accept the message if either of those two hash values appear in the received CRC field, and reject the message if it's any of the other 254 values.  Hence, you're reducing the probability of undetected error from 1 in 256 to 1 in 128.  The actual values of the bits don't really change this, as long as we model the garbling process as 'random'.

Now, the CRC algorithm has the nice property that if the error is limited to an n-bit burst (that is, all bits outside of that n-bit region are received correctly, with n=8 in your case), then it'll always detect the error.  This is a nice property if the garbling process will tend to affect only limited portions of the entire message.  However, I don't see how you can maintain that property (even with n=7), while maintaining backwards compatibility (which I suspect is important).

So, the bottom line is that your idea will make undetected errors more likely; however you're already not meeting your stated goal.  You may need to rethink this protocol more drastically if your reliability requirements are a hard requirement.


What is the shortest type of text encryption?

You don't say what mode of operation you are using with AES. The mode of operation can have a big impact on the ciphertext expansion. There are streaming modes, such as CTR, for which the ciphertext will be the same size as the plaintext. For these modes (an pretty much any mode you would want to use in practice) you will also have to transmit a nonce or IV in addition to the ciphertext.

One thing you should be aware of is that modes like CTR are malleable, which is a huge security issues. So, I highly recommend you use authenticated encryption so that you don't have these security issues. This could be done by computing an HMAC over the ciphertext or using an authenticated mode.


How to contruct a pseudorandom with a specific property

Depending on what you consider an acceptable approach, you could get there by having a random-looking function from your PRF domain to a prime-order cyclic group, and then use the permutation $x \mapsto x^k$ on the group.

Under reasonable assumptions and choice of group, this is a PRF. And since the key-dependent part is a permutation, two keys will never map the same $i$ to the same function value.

So this construction satisfies your requirements, but it is not a tribe ensemble.


Use of Lamport's Signature as a primitive

I don't know of a use of Lamport's scheme precisely as Lamport originally published it; however if we include generalizations of the idea (such as Winternitz signatures), then it has been used as the basis of Hash Based Signatures, such as this proposal


Why is 0x10001 used as an RSA exponent so often?

Here is the beginning of that answer from info security stackexchange for the reader’s convenience:

  There is no known weakness for any short or long public exponent for RSA, as long as the public exponent is "correct" (i.e. relatively prime to p-1 for all primes p which divide the modulus).

  If you use a small exponent and you do not use any padding for encryption and you encrypt the exact same message with several distinct public keys, then your message is at risk: if $e = 3,$ and you encrypt message $m$ with public keys $n_1,n_2,n_3$ then you have $c_i= m^3 \pmod{n_i}$ and use the chinese remainder theorem to recover the message by a
  non modular cube root extraction.

  The weakness, here, is not the small exponent; rather, it is the use of an improper padding (namely, no padding at all) for encryption.


Secure method of encrypting data within a database

Using the same key and IV for different, independently encrypted cells is a bad idea, regardless of which encryption algorithm you use. It would allow attackers to find either XORs of cells (with CTR) or at least equality of prefixes (with CBC).

If you are going to use authenticated encryption, you need to choose whether the MAC applies to each cell independently (which adds data anyway) or the row as a whole.

If you choose the row as a whole, you might want to encrypt the whole row as one, too, since you'll need to read all of it anyway. But if the MAC verification is much faster than decryption, you might still want per-cell encryption with a row-wide MAC.
If you choose per-cell MACs, you are already adding significant data, so you might be able to get away with a per-cell IV too. Or you might be even more determined to avoid adding any extra data, depends on your requirements.

If you end up wanting to do per-cell encryption, but can't have per-cell IVs, CTR is probably your best bet. With CTR the IVs don't need to be random, just unique, so you can calculate the per-cell IV as an offset from the row IV/nonce. Just make sure your offset algorithm will always result in a unique input to each CTR block. E.g. if cells can be at most 256 blocks long, you could use the rightmost byte within the cell, the next one for a cell index and the rest for the row nonce.

CBC is also an option, if you can derive a per-cell IV from the row IV in an unpredictable way. E.g. using $HMAC(k, r || i)$, where $r$ is the row IV and $i$ the row index. That's slower, though. (You could also use the block cipher to derive it.)

Regardless, you should also make sure that the key and IV will differ when a cell is overwritten. With a per-row IV that means the whole row needs to be rewritten with a new IV.

All in all, it's probably simpler to either just have the whole row encrypted and authenticated as a whole or have each cell with their own IV and MAC. Those options allow you to just use an authenticated encryption mode, too.


Oblivious Encryption: Oblivious Transfer Based Encryption

If your goal is to let Alice to securely send a message to Bob (in the presence of a passive eavesdropper), then it achieves this goal. It is not secure if the adversary is active.

Potentially you can use OT extension (if random oracle model is acceptable) instead of OT to improve efficiency, if Alice and Bob needs to communicate multiple times. Basically OT extension uses a small number of base OT invocations (involving public key operations) to bootstrap, then you can invoke symmetric key based OT functionality many times. Some References:

Yuval Ishai, Joe Kilian, Kobbi Nissim, Erez Petrank:
Extending Oblivious Transfers Efficiently. CRYPTO 2003
Gilad Asharov and Yehuda Lindell and Thomas Schneider and Michael Zohner, More Efficient Oblivious Transfer and Extensions for Faster Secure Computation, CCS13
Vladimir Kolesnikov, Ranjit Kumaresan:
Improved OT Extension for Transferring Short Secrets. CRYPTO 2013
Marcel Keller, Emmanuela Orsini, Peter Scholl:
Actively Secure OT Extension with Optimal Overhead. CRYPTO 2015
Arpita Patra, Pratik Sarkar, Ajith Suresh:
Fast Actively Secure OT Extension for Short Secrets. NDSS 2017

That's said, your protocol is not quite efficient (for achieving the goal) and there are easier and better ways of doing that (e.g. just do a key exchange and encrypt the message with the session key).


GnuPG follows the OpenPGP format, which is a protocol in its own right -- it uses AES (among other algorithms) but is more complex than "just AES with the right parameters".

There is at least one OpenPGP implementation in Javascript (I have not tried it, though).


Is there a way to compare the 923 bit pairing based key with RSA or AES, etc

There is nothing really new about this research. It is just a fast implementation of a construction known since 1994.

Source:

http://superconductor.voltage.com/2012/06/understanding-the-recent-fujitsu-discrete-log-calculation.html


Key management in Java + Remembering passwords

There is no way you can make this secure without using some kind of DRM or additional devices. If an attacker has access to the running program then the attacker is able to retrieve the password. You can of course try to hide and / or scramble the password in memory, but that's about anything you can do. It then comes down to obfuscation.

Sometimes the operating system has access to additional resources to secure passwords. You need to provide your password to the operating system almost by default. So for instance Windows has a Credential Manager that you can access from your applications. I looked around and I found some way to make use of it here (warning: I've never used or viewed this solution). Obviously such code won't be portable across operating systems.

In the end, you're probably better off trying to protect your application itself. Make sure your input is sanitized and that the debug port isn't left wide open. Make sure you limit access to the application. Once an attacker has full access to a user account - or worse, a system account - then your application security is probably the least of the user's worries.


CBC variant: why encrypt the nonce with a different key?

I believe that it has to do with the model of nonce selection, in particular, that the attacker is allowed to choose the nonce (as long as it is unique).

If we assume that such an attacker is plausible, then if the nonce is encrypted with the same key as everythine else, then attacker can perform a chosen nonce/plaintext attack which serves as a distinguisher, as well as allows an attacker to decrypt low-entropy plaintext.

Here's how it works: suppose the attacker has a ciphertext where he has a guess $t$ to the value $m[i]$, and (of course, the ciphertext values $c[i-1]$ and $c[i]$).  Then, the attacker constructs a message with the first block being $c[i] \oplus t \oplus c[i-1]$, and asks it to be encrypted with the nonce value $t \oplus c[i-1]$.  He then examines the first block of the resulting ciphertext; if it happens to be the value $c[i]$, then (with high probability) his guess is correct.

If his guess of $t$ was correct, that is if $t = m[i]$, then we have
$c[i] = E_k( t \oplus c[i-1])$ (as that's the formula the encryptor used to create $c[i]$)

So, here is what the encryption process would do: the mode would first encrypt the nonce; the nonce is $t \oplus c[i-1]$, and so the result of the encryption would be $c[i]$.  That is then exclusive or'ed with the first block of the plaintext message, which is $c[i] \oplus t \oplus c[i-1]$; the result of that xor is $t \oplus c[i-1]$.  That is then encrypted; again, the result of that encryption is $c[i]$; and that is the first block of the encryption.

If $t \ne m[i]$, it is quite unlikely that the result of the two encryptions will happen to be the value $c[i]$.

Having the process that initially encrypts the nonce use a distinct key foils this attack.

Now, if we assume that the attacker cannot arbitrarily choose the nonce (e.g. the nonces are sequential), then this attack does not apply; reusing the same key is safe.


Is there any cryptosystem that works on floating point real number?

One of the big problems in using floating-point as part of an encryption algorithm is round-off error.  For more details, look at What Every Computer Scientist Should Know About Floating-Point Arithmetic and Round-off error (Wikipedia).

The basic problem is that in floating-point math, not only does round-off error occur, but you can't depend on different computers doing it consistently.  Here is an example where the same source program gives different results (on the same system) depending on whether x87-based floating point (which stores numbers in a 80-bit format) was used rather than the SSE instructions (which use a more traditional 64-bit double precision float).

So to make a floating-point algorithm work, you would have to find a way of avoiding round-off error, while integers and bitstrings avoid that problem entirely.


I'd go with hash(ProverPublicKey || RandomChallenge || Data) over your idea of hash(RandomChallenge || Data). Your scheme has the problem that the prover might challenge another party to prove that they have the data and forward that prove to the original challenger.

Related keywords are proof-of-retrievability, proof-of-ownership or proof-of-data-possession.


Is there any knapsack-based cryptosystem that has not yet been broken?

It seems that the Okamoto-Tanaka-Uchiyama and the Murakami-Nasako knapsack cryptosystem have not been broken, but I'm not an expert in this field and cannot tell whether it received enough attention from experts to be deemed secure. The OTU cryptosystem was analyzed in this paper, and the authors state that they "actually
believe that this system may be secure with an appropriate choice of the
parameters".

In any case, the link you gave seem strange. Why not trying to publish your cryptosystem in a peer-reviewed conference, or recruiting an expert to study its security, rather than offering a "crowdfunded money prize" to anyone that breaks it? It does not look like a good way to make people confident regarding the security of your proposal.


What gives SHA-256 its preimage resistance?

You appear to be thinking "the output of the round function appears to be a simple function of the previous round, and a word from the message; why can't we select message words to steer the output to whatever we wanted".

Well, there's something missing in the simple description you gave; message expansion.  The W inputs are not just directly taken from the input message; the first 16 are, but the other 48 are linear functions of the input message.  If you modify one input word, you necessarily modify a number of the W inputs; this effectively stops this simple steering strategy, as tweaking one W input (to get a desired state) will necessarily modify others (which will modify the state you're trying to set up).

This doesn't prove the SHA-256 is secure (SHA-1 does the same sort of message expansion, and we know that's weak); however it does show that this approach doesn't appear to be fruitful.


Which is the best algorithm for large scale file encryption other than AES?

You shouldn't encrypt large files as if they were just one message; you should split them up into small chunks and encrypt each chunk separately with an AEAD, using some construction that:

Protects against modification, reordering, insertion and deletion of chunks;
Protects against truncation of the file;
Rotates keys once too much data has been processed by a single key.

One reason is that cryptographic libraries typically are implemented so that you need an entire message in memory to encrypt it. Another reason is that users of tools often expect that the output will be produced incrementally (so they can pipe it to other tools), but typical AEAD ciphers demand that you never output the decryptions of forged ciphertexts, so encrypting the whole file as just one message requires you to authenticate the whole thing before you produce any output. (Not that outputting authentic prefixes of a forgery is always safe.)

See:

https://www.imperialviolet.org/2014/06/27/streamingencryption.html
https://github.com/miscreant/meta/wiki/STREAM
https://libsodium.gitbook.io/doc/secret-key_cryptography/secretstream

Once you have adopted this paradigm, the message length and ciphertext size limits in ciphers that you're concerned about don't matter anymore, because each you only ever encrypt short messages and you can build in key rotation if you go past the ciphertext limit for a single key. For example the Libsodium secretstream API I link to above offers this feature:

  Ratcheting: at any point in the stream, it is possible to "forget" the key used to encrypt the previous messages, and switch to a new key.

So if you just keep a count of how much data you've processed and instruct the library to rekey when it approaches a limit, you have, as the documentation puts it, "no practical limits to the total length of the stream."


The security effect caused by an MDS matrix in word-oriented designs

The current research aims to lighter MDS for implementation in constrained resource environment. The lighter MDS require less number of xors in the binary form (AES MDS). In term of security effect, this paper took the advantage of zero XOR-sum of more than two coefficients of each row of the MixColumns matrix to mound an  (theoritical) attack on AES up to 4.5-5 rounds.

to conclude this ,  zero XOR-sum of more than two coefficients of each row of the MDS matrix could be degradation to the security of the cipher , it is good to find MDS with no zero XOR-sum but this could a tradeoff for finding lighter MDS.


Low entropy - how does it compromise the crypto

If the adversary can guess the key, then they can do all the things that a legitimate user can do: decrypt secret messages, sign statements transferring money to their accounts, etc.  The min-entropy of the process used to generate keys must be high enough that the adversary has no hope of guessing the generated keys by chance.


This illustrates the importance of getting the key order right with 3DES two-key keying option. With the correct order of $k_1$, $k_2$, $k_1$ you get something that should be impossible to attack with current resources, while with the incorrect order in the question it is feasible to attack.

The outer two encryption layers can be joined into a single cipher, which we may call DES2. That is a 64-bit block cipher with a 56-bit key, just like DES. It is approximately twice as expensive to compute.

The question then becomes the simple case of applying the meet-in-the-middle attack to double encryption. The inner cipher is DES, the outer DES2. The fastest option is to build the table for the inner encryption encryption in $2^{56}$ DES calls, since you then only need to compute the outer cipher $2^{55}$ times on average (i.e. $2^{56}$ DES calls).

You need memory for a $2^{56}$ item table, unless you apply a time-memory tradeoff. It would be expensive but on the verge of doable even with this brute force approach. You may also be able to get away with a factor of 2 or so fewer calls by making use of related keys. Other improvements are likely possible.


Leaking information when a value is blinded

To make sure the values of a uniformly chosen random polynomial in $F_p[x]$ are uniformly distributed, you need to impose a maximum degree for the polynomial, since there is no uniform distribution on a countably infinite space.

Having done this and ensuring the uniformity of the polynomial values, your questions boil down to questioning the uniformity of and independence of quantities like $$a+Z$$ and pairs $$(aZ+W,aZ'+W')$$ where $Z,W,Z',W'$ are uniform and pairwise independent. And they are, since linear polynomials over $F_p$ are permutation polynomials.

To clarify, for both questions, the adversary cannot learn anything about the quantity of concern, since it is an independent random variable from the quantities they have access to. For example, $p(\cdot)$ being uniformly chosen means $p(x_1)$ is uniformly distributed and when $r_1$ which is also uniform is added to it $b_1 p(x_1)+r_1$ is distributed like $aZ+W$, which is itself uniform.


Why does plain RSA not work with big messages ($m>n$)?

The issue is that we use modular arithmetic. In modular arithmetic, you may view $m \bmod n$ as the remainder of $m$ when divided by $n$. So, for example, $7 \bmod 2 = 1$, also written as $7 \equiv 1 \pmod 2$, because $2(3) + 1 = 7$.

Now consider what you're guaranteed by $m \equiv c^d \pmod n$, the decryption formula for plain RSA. You're guaranteed that $c^d$ is equivalent to the message modulo $n$. You're not guaranteed that it is precisely equal. Now, if the message is smaller than the modulus — if $m < n$ — then by the way we program modular reduction, where we usually give the smallest positive integer modulo $n$ , you're going to get $m$ exactly when you compute $c^d \bmod n$. But if $m>n$, if the message is bigger, you're going to get a smaller integer that is equivalent modulo $n$.

And indeed this is the case with your example. Note that your example message $m = 33555553$ is larger than your example $n = 4075961$. So when you compute $c^d$, you're going to find an equivalent integer modulo $n$, but not exactly the one you wanted.

In this case, you got back $c^d \bmod n = 947865$. But note what happens if you reduce your original message modulo $n$: you get that your original message is equivalent to $c^d \bmod n$.

In summary: if your message is larger than your modulus, you won't get the exact message back when you decrypt. You'll get an equivalent message instead. To avoid this, you can instead encrypt a key used in a symmetric cryptosystem (or any cryptosystem that can handle messages of the length you're wanting). As Ricky Demer linked in his comment, this is sometimes called a hybrid cryptosystem. Once you've done this, you just use the other cryptosystem's key to do all of your encryption for you.


Security analysis of a matrix multiplication protocol

Why over a secure channel? Wouldn't this work pretty well if you take A and B not invertible also in the presence of an eavesdropper? Then Bob could use a similar trick to get AB by sending BS to Alice (where S is invertible) and then recover AB from ABS that Alice sends back. This seems extremely inefficient though.

In any case, Bob knows quite a lot about A. Row-reducing RA should give the same reduced row-echelon form as A has. The rank of RA is the same as the rank of A and so on.


SHA-3 block sizes / bitrate calculation?

First of all, in the case of SHA-3 we don't call it block size but bitrate.

SHA-3 has been formally defined in FIPS 202 and in its reference manual.

  We define the sponge function denoted by $\operatorname{KECCAK}[r,c]$ by applying the sponge construction as specified in Algorithm 1 with $\operatorname{KECCAK-}\!f[r+c]$, multi-rate padding and the bitrate $r$.
  $$\operatorname{KECCAK}[r,c] = \operatorname{SPONGE}[\operatorname{KECCAK-}\!f[r + c], \mathrm{pad10^∗1}, r]$$

$c$ is the capacity, it defines the security level of the sponge.

The value $b = r + c$ is called the width of the state. It is either $25$, $50$, $100$, $200$, $400$, $800$ or $1600$.

  In the scope of the SHA-3 contest, we proposed the largest permutation, namely $\operatorname{KECCAK-}\!f[1600]$.

So in our cases $b = 1600$.

The notation $\operatorname{SHA3-}\!x(M)$ produces a digest $x$ bits long and has a security claim $d = x$. Without going into details, $d$ can be seen as $c/2$ (see here and here, Chapter 7, page 71).

Therefore in:

$\operatorname{SHA3-224}(M)$, $c = 2\times224 = 448$ and $r = 1600 - c = 1152$
$\operatorname{SHA3-256}(M)$, $c = 2\times256 = 512$ and $r = 1600 - c = 1088$
$\operatorname{SHA3-384}(M)$, $c = 2\times384 = 768$ and $r = 1600 - c = 832$
$\operatorname{SHA3-512}(M)$, $c = 2\times512 = 1024$ and $r = 1600 - c = 576$

Hence:

$\operatorname{SHA3-224}(M) = \operatorname{KECCAK}[1152,448]$ with $\mathit{bitrate} = 1152$
$\operatorname{SHA3-256}(M) = \operatorname{KECCAK}[1088,512]$ with $\mathit{bitrate} = 1088$
$\operatorname{SHA3-384}(M) = \operatorname{KECCAK}[832,768]$ with $\mathit{bitrate} = 832$
$\operatorname{SHA3-512}(M) = \operatorname{KECCAK}[576,1024]$ with $\mathit{bitrate} = 576$

As the speed of the algorithm is directly related to $r$ (bit rate absorption), the higher the security, the slower the function will be.


Security-wise having statistical security is always better than computational security if the security parameter is equal. This is because statistical security ($\forall A: Pr[A(f(x)) = x] \le negl(n)$) implies computational security ($\forall B: Pr[B(f(x)) = x] \le negl(n)$) with B all algorithms in P-SPACE and A being all algorithms (which includes all algorithms in B).

However, there is a catch. In practice the security parameters differ by a large amount. While one can argue by just using the same security parameters for statiscial security and computational security, it's still a problem. This is because statistically secure functions usually use smaller security parameters compared to computationally secure functions in practice to reduce computation time and space since they aim different targets; and most statistically secure protocols are usually not designed to be used as functions with computational security (but it's not impossible doing so either; the Fiat-Shamir transformation is one example since it can transform interactive zero-knowledge proofs with statistical security into non-interactive proofs with computationally security secure in the Random Oracle Model).

Typically you want to archive different targets with statistical security and computationally security:

Statistical secure functions are usually used in interactive settings which are repeated fixed times. For example, think about lotteries. If one could repeat a lottery unlimited times for free at any time, everyone would be winning. But in reality you can participate in a lottery only once per week and you need to pay per participation.
Computational security functions usually deals with algorithms which try to extract a secret x out of the information y (and have some additional power I skip here). The adversary is allowed to use any stragegy he wants, but is limited to the time and space. Because the problem is that 'hard' (being in NP) the adversary still is unlikely to be successfull, unless he is very lucky.

In the protocols which implement secure functionality computational security and statistical security are differentiated if both are needed since the security parameters do differ in practice.


Advice for a high schooler intending to read about post-quantum crptography

Up to and excluding the point "test it against a quantum computer stimulator (sic)", the question is about a feasible endeavor, though first implementing a more classical algorithm could be a useful warmup.

But I see a giant gap at said point: a quantum computer simulator attempts to simulate a quantum computer running a quantum algorithm, which (in the context) would be one attacking a cryptographic algorithm of the NIST PQC Round 2 (intended to run on classical computer). And by standard definition of security in PQC, there should be no known (sub-exponential or otherwise practical) algorithm that can attack a PQC algorithm. Therefore, finding an algorithm that is interesting to simulate would be extremely difficult. It's also very unlikely that the simulator would be powerful enough.

Among the NIST PQC Round 2 encryption algorithms, my feeling is that Classic McEliece is not the harder to grasp; but I've not studied them all, and on PQC I'd rather follow poncho's feelings than mine. As he pointed in comment, signature algorithms are also worth consideration.

If you do not have a clear understanding of the difference between encryption and signature, well I suggest to deffer working on PQC until you know more about asymmetric cryptography as currently practiced. That's hard enough.


Simulator in Private Outsourced Computation over Outsourced Datasets

The objective of the simulator is to make the simulated world (often called the ideal world) indistinguishable from the real world (running the actual protocol). See my write-up on the UC framework here for more detail.

In the proof setup, the entity attempting to distinguish between the two worlds is often assumed to provide the inputs to the parties. That keeps things as generic as possible.

So, what should be done is have $\mathcal{Z}$ pick the inputs for the parties.


Salsa20 alone does not protect integrity.

Poly1305 protects integrity, as it is a Message Authentication Code (MAC). A MAC takes a secret key and a message, and outputs an authentication tag. Any change to the message will cause the resulting tag to not match. Only someone with the key can generate the tag, which means that an attacker shouldn't be able to flip bits undetected.

At a very high level, Poly1305 takes a message and a two-part key and turns it into a very big polynomial (modulo a large prime).

$MAC=(m_{1}r^{n}+m_{2}r^{n-1}\ldots+m_{n}r^{1}+k)\mod p$, where $m_1$, $m_2$, etc, are blocks of the message and r & k are the key.

In the case of Poly1305 the prime p is $2^{130}-5$.

To encode a message $M$ into blocks you take 16 bytes from the message, append a 1 byte to the end, then treat the 17 bytes as a little-endian number (this process ensures that trailing zeroes are detected).

There are also some restrictions on how $r$ is chosen.

The end result is very difficult to compute by an attacker not knowing r and k, even if they know the plaintext of the message.

Loup Valliant has a good explanation with a bit more detail on how Poly1305 actually works.1 And of course DJB's paper provides even more detail, though it's harder to understand.2


Alas, there is no simple satisfactory answer to this question.  What I can offer is a very strong property that $m \mapsto H\bigl(k \mathbin\| H(k \mathbin\| m)\bigr)$ fails to achieve; a more pedestrian property which even HMAC may or may not achieve but is typically asked to achieve; a reason not to worry about it for any new systems; and some historical background that went into making this mess.

Random oracle indifferentiability.  The construction fails to achieve a very strong property, which is convenient for reasoning, but is perhaps stronger than needed for most protocols.  Let $H$ be a uniform random function.  For any $k$, define $F_k(m) := H(k \mathbin\| m)$; obviously $F_k$ too is a uniform random function for any $k$.  There are protocols that are secure when instantiated using $F_k$, but are trivially insecure when instantiated using ${F_k}^2$, where ${F_k}^2(m) := F_k(F_k(m))$.  (Of course, you could fix it by using $H(k \mathbin\| 1 \mathbin\| H(k \mathbin\| 0 \mathbin\| m))$—a single bit distinction between the inner and outer hashes.)

This doesn't mean that the protocols are useful in the real world, although they can be contrived[1]—it just means there are counterexamples to the proposition one might hope for that any protocol which is secure when instantiated with $F_k$ is also secure when instantiated with ${F_k}^2$.

Note that the protocols may also fail to be secure with $F_k$ when $H = \operatorname{SHA-256}$, because of the usual length extension attacks on SHA-256. The counterexamples shown in [1] demonstrate that even if $F_k$ had no other attacks like length extension attacks, the mere substitution of ${F_k}^2$ for $F_k$ could cause a secure protocol to become insecure.  In contrast, as long as the key is two bits shorter than a block, the HMAC construction is shown indifferentiable in [1].  Of course, so is the much simpler $H(k \mathbin\| 1 \mathbin\| H(k \mathbin\| 0 \mathbin\| m))$.

Pseudorandomness.  We considered any fixed key $k$ above, known to an attacker.  But the usual security conjecture for HMAC is merely pseudorandomness, where $k$ is secret—this is enough to make HMAC a secure MAC that resists forgery (up to a modest number of messages authenticated[2]), and enough to securely derive secret subkeys from a secret master key using HMAC as in HKDF.  Specifically, we conjecture that if $k$ is a uniform random key, then it is hard to tell $\operatorname{HMAC-\!}H_k$ apart from a uniform random function.

As it turns out, the security story traced over the decades in the literature for the pseudorandomness of HMAC for a Merkle–Damgård iterated hash function like MD5 is extremely complicated!  In 1996, Bellare, Canetti, and Krawczyk first tried to address it[3] (actually, just the weaker MAC security, not the stronger PRF security) for a double-key variant called NMAC, under the assumption that the underlying compression function is a PRF and is collision-resistant; they then conjectured that deriving two keys from one by ipad and opad oughta be good enough.

For MD5 and SHA-1, the assumption of collision resistance turned out to be unrealistic.  In 2006, Bellare revisited the question without assuming collision resistance[4], but with a very complex proof and non-tight bounds that make it unclear concretely how many messages are safe to authenticate with HMAC.  They also addressed the security of HMAC's key derivation, but only by assuming that the compression function resists a certain class of related-key attacks—which essentially boils down to assuming the compression function is designed to make HMAC's key derivation secure.

The question was revisited again in 2013 by Koblitz and Menezes[5], and in 2014 by Gaẑi, Pietrzak, and Rybár[6], which incited an academic spat[7][8][9] over the definitions and assumptions that are reasonable for the underlying compression function to give a reasonable security bound for reasonable confidence in the security of HMAC.

The conclusion is that so far, after a quarter century of analysis, nobody has found evidence that HMAC should fail to achieve reasonable PRF security for all reasonable hash functions you might instantiate it with—but the ‘provable security’ framework provides meager confidence with very loose bounds about the PRF-security of HMAC in terms of the PRF-security of the underlying compression function.  What does this say about $H(k \mathbin\| H(k \mathbin\| m))$ instead, or $H(k \mathbin\| 0^b \mathbin\| H(k \mathbin\| 1^b \mathbin\| m))$?  Who knows!

The bright side.
Today, ‘hash functions’ like BLAKE2 and SHA-3 are designed so that the prefix construction $H(k \mathbin\| m)$ makes a secure PRF, and come with built-in PRF modes, keyed BLAKE2 or KMAC, with a theorem relating the security of the PRF to the primitive.  So there is essentially no reason to worry about HMAC for any new designs like BLAKE2 or SHA-3.

Historical background.

Kaliski and Robshaw first proposed $H(k \mathbin\| H(k \mathbin\| m))$ in 1995 for IPsec[10], along with $H(k_1 \mathbin\| H(k_2 \mathbin\| m))$ and $H(k \mathbin\| m \mathbin\| k)$, the last of which is sometimes known as ‘envelope MAC’.  They picked MD5 because it was new and exciting at the time, and chose these structures to thwart length extension attacks on MD5, and included heuristic security conjectures for the compositions.  These heuristics led them to consider deriving $k_i = H(k \mathbin\| i)$ for the two-key case, but they didn't propose it.

Curiously, they were unconcerned with collision attacks on MD5, whose first hints of practicality came the very next year[11], but they were concerned with preimage attacks that might reveal $k$ given $H(k \mathbin\| H(m))$—which is still infeasible today, which should indicate the level of rigor that went into these proposals.
Shortly afterward in 1995, Preneel and van Oorschot described specific attacks on $H(k \mathbin\| H(k \mathbin\| m))$ and other constructions[12], where $H$ is an iterated Merkle–Damgård construction.  The attacks don't mean the construction is completely insecure, per se—it just indicated that the cost is less than an ideal MAC.

The crux of what they observed is that if a MAC is constructed by $g(f(\cdots f(f(iv, m_1), m_2)\cdots, m_n))$ for random functions $f$ and $g$, it's collisions in $f$ that spell trouble because they can be extended into collisions of longer messages.*  The worst cases are when $g$ is a permutation, which means collisions in $H$ are guaranteed to imply collisions in $f$ which you can turn into many other collisions.

The paper is written in an older style that is a little unfamiliar to the modern norms of cryptography literature.  It is phrased as a collection of examples of attacks on the MAC, with cost analyses, rather than as bounds on success probabilities of all possible cost-limited attacks.  It concludes with a somewhat baroque construction MDx-MAC that heuristically seems to avoid the attacks.

I won't go into details, but MDx-MAC involves deriving multiple subkeys with ‘envelope MAC’, swapping out the underlying hash function's initialization vectors, changing the constants inside the compression function, etc.—not a very satisfying way to compose a MAC out of a primitive like MD5.
Later in 1996, Bellare, Canetti, and Krawczyk proposed HMAC[13] as we know it today in, e.g., RFC 2104, and offered a preliminary analysis[14] by way of an intermediate two-key construction $\operatorname{NMAC-}\!H_{k_1,k_2}(m) := H_{k_1}(H_{k_2}(m))$.  They showed, loosely, that if $H_{k_1}$ is a secure MAC of short messages, and $H_{k_2}$ is collision-resistant (under the somewhat obscure term ‘weakly collision-resistant’; the corresponding ‘strongly collision-resistant’ means ‘second-preimage-resistant’), then $\operatorname{NMAC-}\!H$ is a secure MAC of long messages, by setting a bound on the forgery probability of $\operatorname{NMAC-}\!H$ in terms of the forgery probability of $H_{k_2}$ and the collision probability of $H_{k_2}$.

Note that the double-length key does not imply double-security of NMAC; it just means NMAC needs twice the key material to attain the security attained by an ideal MAC with a single-length key.  One could imagine instantiating NMAC by taking MD5, and using $k_1$ and $k_2$ instead of the standard initialization vector.  But Bellare et al. figured that people wouldn't want to modify the existing MD5 code they had, so they suggested another approach: use $H((k_1 \oplus \mathrm{opad}) \mathbin\| H((k_2 \oplus \mathrm{ipad}) \mathbin\| m))$.  However, they only heuristically conjectured the security of HMAC in relation to NMAC.

* This idea can be taken on its face to suggest a construction for MACs: pick a universal hash family $f_{k_1}$ which merely has low collision probabilities (but from which two outputs, if revealed directly, might trivially determine $k_1$ and enable finding collisions, like Poly1305); pick a short-input, short-output pseudorandom function family $g_{k_2}$ to conceal the output; and use $g_{k_2}(f_{k_1}(m))$.  Universal hash families have the advantage that can be extremely cheap to evaluate, e.g. by dot products or Horner's rule in a finite field.  (It might even be safe to use $k_1 = k_2$, but I don't know!)  Though Preneel and van Oorschot's ideas might have suggested this structure, it attained no practical significance to my knowledge until the development of AES-GCM-SIV decades later[15], by Shay Gueron and our own Yehuda Lindell.


Where can I find official test vectors for NIST SP 800-56C r1 Single Step KDF


Length extension attack SHA-1 message division with padding problem?

OK, lets go through this step by step:

the message size of http://example.com/downloadfile=report.pdf is 10 bytes, as only the filename (report.pdf) is hashed according to the article;
the key size is usually known and was explicitly set in the article to 11 bytes, not 15 (11 bytes is a bit short for a key size, by the way);
so the length of the message is 10 + 11 = 21 bytes, or 168 bits and A8 is indeed 168;
to the padding + length encoding needs to be 64 - 21 = 43 bytes, lets check that:
%80%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%A8
yep, that seems to be correct.

Note that 64 bytes is 512 bits for the block size and that e.g. %80 is the encoding of a single byte with value 80h, so you need to count the characters and then divide by 3.

So I'm not sure how you got your input values for the message size and key size, but they are way off. So you would not end up with the right values, regardless of the correctness of your formulas.


A function $H(x)$ is given. If there is an algorithm $B(H(x))$ that get part of $x$, is $H(x)$ a one-way function?

If there is an algorithm $B(H(x))$ that get part of $x$, is $H(x)$ a one-way function?

That remains possible.
Simplifying the definition of a One-Way Function in Katz and Lindel's Introduction to Modern Cryptography, it's an efficiently computable function $f$ such that no algorithm $\mathcal A$ exists that, given as input $y=f(x)$ for a random $x$, outputs $x'$ with $f(x')=y$ with non-vanishing probability.
That definition is compatible with existence of an algorithm $\mathcal B$ that, given as input $y=f(x)$ for a random $x$, always outputs some segment of $x$ (e.g. it's first bit).
Illustration: assume a function $h$ that's indistinguishable from a random oracle (SHA-3 aspires to that). It's demonstrably a OWF. Construct a function $f$ with $f(x)$ the first bit of $x$ followed by $h(x)$. An algorithm $\mathcal B$ always producing the first bit of $x$ from $f(x)$ is trivial, yet an algorithm $\mathcal A$ breaking the one-wayness of $f$ can be turned into an algorithm  $\mathcal A'$ breaking the one-wayness of $h$, with at least half the success probability of $\mathcal A$.

The question's quote is in this online document. I'm ready to follow the OP that the proof made is locally wrong, but I do not exclude this can be repaired by some simple argument, on the tune of: if we can find a component $x_1$, by symmetry, we can find any $x_i$. Lattice based crypto is just too far from my comfort zone, and the time I spent on the paper too low, that I can have a useful opinion.
Note: the question mentions "14.1 (2015): 2-8", but that's incompatible with this and this stating "Volume: 14, Issue: 1, Jan.-Feb. 1 2017". Said online document is dated May 20, 2015, as well as another online version bearing "Content may change prior to final publication", thus I can't exclude the document was later revised.


As Shan Chen said, the reduction is easy. Note if the DDH adversary gets $g^a,g^b,g^{ab}$ then it gets $g(a,b)$, and if it gets $g^a,g^b,g^{c}$, then he gets a uniformly random string.

Now for the second question. First for a prime number $p$, the order of $\mathbb{Z}^*_p$ is $p-1$. If $G$ is a (integer) cyclic group of prime order $q$, then you are not using $\mathbb{Z}^*_p$, but the order-$q$ subgroup of it ($q$ needs to be large which I assume here).

Why DDH is not hard in $\mathbb{Z}^*_p$? By Euler's criterion, in $\mathbb{Z}^*_p$ there are $\frac{(p - 1)}{2}$ quadratic residues and $\frac{(p − 1)}{2}$ non-residues. So in for a random $x \in \mathbb{Z}^*_p$, the probability of $x$ being a residue (non-residue) is exactly $\frac{1}{2}$. Legendre symbol for an element $x \in \mathbb{Z}^*_p$ can be calculated as:

$$
\Big(\frac{x}{p}\Big)= x^{\frac{p-1}{2}} \bmod p
$$

and the symbol tells whether $a$ is a residue or non-residue:
\begin{equation*}
\Big(\frac{x}{p}\Big) = \begin{cases}
1 &\text{if $x$ is a residue}\\
-1 &\text{if $x$ is a non-residue}
\end{cases}
\end{equation*}

Now given the DDH tuple $(g^a,g^b,g^c) \in (\mathbb{Z}_p^*)^3$, we can calculate the Legendre symbols of $g^a,g^b,g^{c}$. If either $\Big(\frac{g^a}{p}\Big)$ or $\Big(\frac{g^b}{p}\Big)$ is 1, then $Pr[\Big(\frac{g^{ab}}{p}\Big)=1] =1$.

The reason is that a residue $x$ is congruent to a perfect square. So that if $g^a$ is a residue, then it can be expressed as $g^a=h^2$. For $g^{ab}$, it can be rewritten as $(h^b)^2$, which is also a residue.

But for a random $c$ that $c\ne ab$, the probability of it being a residue is only $\frac{1}{2}$, which means we can distinguish $g^{ab}$ and $g^c$ easily.

If the DDH tuple $(g^a,g^b,g^c) \in G^3$, since $q$ divide $p-1$ and $p-1$ is even, $\frac{p-1}{2} = kq$ for some $k$, then $\Big(\frac{g^a}{p}\Big), \Big(\frac{g^b}{p}\Big),\Big(\frac{g^{ab}}{p}\Big), \Big(\frac{g^c}{p}\Big)$ are all 1 (because all elements in $G$ are of order $q$, thus the $q$-th power of all elements in $G$ congruent to 1).


Choose Argon2i or Argon2id for secure password hashing on a website?

It depends. If you use weak parameters, then no matter what algorithm you choose the brute-forcing can be done relatively easy.
Think against what risks do you want to protect passwords. Argon2d gives some possibility of side-channel attacks. This is relatively complex and expensive approach. I'd suggest you to estimate the risk that somebody will pay a lot of money to implement side-channel attack. If you are implementing an application where passwords protect banking transactions of millions of USD, then the risk may be higher. If you are implementing an application focused on cooking receipts or traveling recommendations, then may be nobody will be willing to pay a lot of money for a side-channel attack. Then Argon2d may be a perfect choice for you.
I would suggest following (it is a matter of taste): Take Argon2id, it combines advantages and disadvantages of both Argon2d and Argon2i. It combines advantages of both. Pay better more attention to the proper selection of tuning parameters.


Is it safe to use fast/small hash for key identity?

In general, you never want to use CRC/weak checksum for any computations on secret material (like keys). CRC is a linear function and by showing CRC of a key, you reveal a lot of equations that hold among the key bits. This is equivalent to showing the same number of bits of the key as the length of the checksum.

The proper way of doing it has been suggested by @puzzlepalace: Take a cryptographic hash function (like SHA-2), compute the hash of the key and take only 32-bits of the digest.

Key fingerprint of 32-bits may be too small: if you have ~2^16 keys, you will get different keys that give the same fingerprint. You need to take this into account when designing your system.


A similar construct to a time-lock puzzle is a verifiable delay function. They have a similar notion of "inherent sequentially". They have an unrelated "public verifiability" property which you do not care about.

Boneh et al. build verifiable delay function from a construct called ``Incrementally Verifiable Computation'', which they can instantiate from certain SNARKs/SNARGs. There exist lattice based SNARGS, which I imagine are post-quantum.

I have not checked if all of these notions line up to directly give someone post-quantum VDFs (and therefore post-quantum Time-Lock Puzzles), but this seems like an excellent candidate for what you're looking for.


How reasonable is deriving the key a corpus of RSA-PSS signed messages?

We don't know any forgery algorithm which can do a better job if there are more signed messages available, or smaller signed messages available.

The best way we know to forge messages is to factor $n$.  The best algorithm we know to factor $n = pq$ when $2^{1023} < p < q < 2^{1024}$ are (near) uniform random primes, the general number field sieve, costs more than $e^{(\log n)^{1/3} (\log \log n)^{2/3}}$, and uses only the modulus $n$, without reference to any signed messages.

The standard PSS security theorem is that if you had an algorithm to forge signatures, then someone could use your signature forger as a subroutine in a program to invert $x \mapsto x^e \bmod n$ with essentially the same probability of success as the forger, and as many additional modular exponentiations as the forger makes hash or signing queries.  Consequently, PSS forgery can't be much cheaper than computing $e^{\mathit{th}}$ roots, but we don't know any way to actually do it besides factoring $n$ in order to compute $e^{\mathit{th}}$ roots in the first place.


Zero knowledge proof of possession of key

Alice can prove that the decryption of $C$ is $M$. This can be done using zero knowledge proofs.

Simple example: Suppose $C = (x,w)$ is an ElGamal encryption of $M$ under public key $y$, that is $(x,w) = (g^r, y^r M)$ for some $r$. Suppose that the decryption key is $a$, that is, $y=g^a$. Then we know that $M = wx^{-a}$, or $x^a = w/M$. That is, the logarithm of $w/M$ to the base $x$ is the same as the logarithm of $y$ to the base $g$.  Conversely, if the logarithms are equal, the decryption of $C$ is $M$.

Now Alice can prove that the decryption of $C$ is $M$ by proving the equality of the two discrete logarithms. There are standard zero knowledge proofs for this.


Are there any known collisions for the SHA (1 & 2) family of hash functions?

This answer is now out of date as on Feb 23 2017, a collision for SHA-1 was found. See What is the new attack on SHA-1 “SHAttered” and how does it work?

In short, no.

So, what is the current state of cryptanalysis with SHA-1 (for reference only as this question relates to SHA-2) and SHA-2? Bruce Schneier has declared SHA-1 broken. That is because researchers found a way to break full SHA-1 in $2^{69}$ operations. Much less than the $2^{80}$ operations it should take to find a collision due to the birthday paradox.

As far as we know, the best available collision attacks on full round SHA-2 hash functions is still brute force $2^{n/2}$ (where $n$ is the bit length of the output).


In the reduction proof below, where OWF exists only if is a PRG. I am not able to understand the highlighted part

This is an example of proof by contradiction. If you have ever seen a proof that the square root of 2 is irrational, that probably used a similar logical argument. Our goal is to prove that $\mathcal A$ does not exist, but we do that by assuming it does exist and then deducing that something goes wrong. The place to pay attention is bullet 4 where we assume $\mathcal A$ exists; mathematicians and computer scientists could make life easier at this point by adding "SPOILER ALERT: It doesn't!". The next three bullets proceed from this assumption and at the end of bullet 7 the wheels fall off because, as you realised, we have constructed a case where the distinguisher wins and because we know that $G$ is a PRG this cannot happen. We go back to bullet 4 and realise that we must have gone wrong by assuming the existence of $\mathcal A$. We conclude that no such $\mathcal A$ can exist.
The variable $z$ is meant to represent a response to a challenge from the adversary. After that the proof shows how you can distinguish the response if you can lay your hands on $\mathcal A$ (SPOILER ALERT: You can't).


Is a continuous stream of encrypted data embedded in garbage more or less secure than only encrypting the data?

It depends on what your requirements are. In general, it is accepted that an observer knows when meaningful data is exchanged - even if he can't read it - because, well, we simply don't care. But in some cases this may be unacceptable, such as in p2p protocols where anonymity is very desirable and a fuzzy network can add a decent amount of secrecy.

On the other hand, continuously streaming is quite heavyweight, as it is in general not possible to keep streaming indefinitely (and intercepting all the garbage data and interpreting it as meaningless probably isn't free either, although that depends on your transmission protocol).

  or sending encrypted pseudo-random data

Huh? Why would you encrypt pseudorandom data? This is actually a bad idea - by doing that and encrypting your pseudorandom stream with the same key, you will have tainted all the garbage data with your key material - the same key used to encrypt your precious ciphertext - thereby giving the attacker orders of magnitude more stuff to work with. If the underlying pseudorandom data that you originally encrypted is broken, boom, you just gave your opponent lots of plaintext/ciphertext pairs, and your key (and therefore, your ciphertext) is now potentially compromised.

No, just send pseudorandom data that's independent of all other information you might rely on, so just grab a few hundred bits of entropy and run some cipher in CTR mode or something to produce a nice pseudorandom bitstream - this way, even if this part of your scheme is broken, your ciphertext remains safe (even if the attacker now knows its size and roughly when it was sent).

  but otherwise adds the risk of a Known-plaintext attack should the
  garbage-generator (or the way separating actual message) be predicted.

How so? If your cryptography is sound, and the garbage data does not leak any information about the plaintext or any key material (which it shouldn't, since it's just random bits), the two methods should provide equally optimal privacy. Even if an attacker somehow managed to distinguish the relevant ciphertext, he still wouldn't be able to decrypt it.

  Does the answer also depend on whether the messages shall be secure
  "forever" or if it is sufficient to maintain secrecy for a limited
  amount of time?

Again, it depends on your requirements. There is no "one size fits all" cryptography, and every application needs its own version of it, that's why there are so many different protocols and schemes around. You need to figure out yours and implement it.

So basically, define your use of the word "secure" in your first sentence. Secure against what, and how secure should it be (should it provide only privacy? privacy and anonymity? perhaps integrity too, what about authenticity? etc...)


Working Precision and Time-constant Arithmetic with ECC?

You can have additions and multiplications take constant time on a hardware level; however, the multiply units generally take 4 cycles due to the array multiplier design for a 32-bit width, at 64-bit on Intel, it's 6 cycles.  The division will always be iterative, which is the problem.

Here's an example of a routine that I have for adding two 256 numbers in constant time on my i7 (note, these times will be different for different cores):

add256:
        xorl      %r9d, %r9d         # 1 cycle
        movq      (%rsi), %rax       # 1 cycle
        addq      %rax, (%rdi)       # 1 cycle
        movq      8(%rsi), %rdx      # 1 cycle
        adcq      %rdx, 8(%rdi)      # 1 cycle
        movq      16(%rsi), %rcx     # 1 cycle
        adcq      %rcx, 16(%rdi)     # 1 cycle
        movq      24(%rsi), %r8      # 1 cycle
        adcq      %r8, 24(%rdi)      # 1 cycle
        setb      %r9b               # 1 cycle
        ret                          # 1 cycle

You are not going to get true constant time unless you are in assembly.  I believe that the best way to get constant time would be to just figure out the maximum it time it takes to do a calculation, and then pad intermediate cycles with junk because the ADD and MUL will take different times.

The thing that will hurt you the most is the division that is iterative, as that takes an arbitrary amount of cycles.


Shamir's Secret Sharing Scheme - prime security?

The prime can be just any prime, so it doesn't have to be chosen randomly (but of course it can). And the prime is made public, so it is not part of the shares. Public values are known by definition by everyone, therefore are not part of the shares.

But you're right, the quote is wrong about the size of the share, because it neglects $x$. However, it's really close, because $y$ is usually the same length as $p$ (uniform distributed), but $x$ can be chosen to be small.


Comparing stronger vs. weaker assumptions

Yes you are right. Essentially when we say $A$ is a stronger assumption than $B$, what we mean is that assumption $A$ implies assumption $B$. $A$ implies $B$ tells us that:

if $A$ is true, then $B$ must be true.

$A$ implies $B$ is also equivalent to $\neg B$ implies $\neg A$, thus

if $B$ is false, then $A$ must be false.

In cryptography, assumptions often are related to the hardness of some problems. In this context, stronger assumptions are "easier" problems that can be reduced to  weaker assumptions that are "harder"problems (solving the harder problems means the easier ones are also solvable). For example, say we have the following two assumptions:

$A$: factoring an integer $n$ is difficult;
$B$: factoring an integer $n$ with only large prime factors is difficult.

Clearly, if $A$ is true, then $B$ is true; if $B$ is false, $A$ is false. If we can solve $B$ then we can use the algorithm that solves $B$ to solve $A$.


Are there two known strings which have the same MD5 hash value?


Is there any more asymetric-time permutation than x^3 (mod p)?

One approach is suggested by the ideas introduced by this paper.  I'll spell them out for you:

The verifier selects two large safe primes $p, q$ (that is, primes where $(p-1)/2$ and $(q-1)/2$ are also prime), the value $n = p \times q$, an integer $z$, and a quadratic residue ($\bmod n$) $a$.
The challenge (the "hard direction") is, given the values $n, z$ and $a$, compute $a^{2^{z}} \bmod n$
The verification (the "easy direction") is, given $a^{2^z} \bmod n$, recover $a$ (which is moderately easy to do, effectively an RSA operation, if you know the factorization of $n$).

This is a trapdoor function, but one which the verifier knows the trap door (and doesn't need to rely on anyone else).  This works fine if we have a unique verifier (as in a challenge-response system); it's less useful if the verification logic needs to be public.

And, the function is a permutation, if we restrict ourselves to the quadratic residues modulo $n$.

The point of this construction is that the asymmetry ratio can be as large as desired; it's effectively $O(z / \log n)$, as $z$ is an arbitrary integer, we can set this to whatever we feel like.


Does GCM (or GHASH) only provide 64-bit security against forgeries?

According to the references, AES-GCM offers roughly 64-bit authenticity security (i.e., against forgery attacks) for 128-bit block size and long-enough (>=64-bit) tag size. When the number of queries appears in a security bound, "online" security should always be the case (for the bound items involving the number of queries). The word "query" corresponds to an oracle, which cannot be attacked offline.


Why doesn't GMAC/GCM encrypt its authentication tag?

Latency, probably.

$\mathrm{GHASH}_K(m) \oplus \mathrm{AES}_K(n)$ lets you compute both in parallel, whereas encrypting the $\mathrm{GHASH}$ output would add significant latency for short messages. The authors go to great detail about this in Section 3 of the original GCM document.

A similar competing mode at the time, CWC, did indeed encrypt the MAC output but was not as efficient.


Rabin, like RSA, requires $p\ne q$. Basically, this is because the rings $\mathbf{Z}_{pq}$ (for $p\ne q$) and $\mathbf{Z}_{p^2}$ have fundamental differences. Crucially, $\mathbf{Z}_{pq}$ is isomorphic to $\mathbf{Z}_p \times \mathbf{Z}_q$, and your decryption algorithm depends on that property. On the other hand, $\mathbf{Z}_{p^2}$ is not isomorphic to $\mathbf{Z}_p^2 = \mathbf{Z}_p \times \mathbf{Z}_p$, so your decryption algorithm doesn't work.


How can I determine if a hash function is secure?

The best way to approach problems like this is to start by assuming that a simple solution exists.  That assumption might be wrong, of course, but:

since this is a textbook problem, it probably does have a relatively simple solution that you should be able to figure out based on what you've learned, and
even if that wasn't the case, you should still at least try to look for simple solutions before spending time on anything more complicated.

Thus, you should assume that, on one hand, if your hash function doesn't satisfy one of the three security properties the question asks about, then there should be a fairly simple example where that property is violated.  On the other hand, if it does satisfy them, then there should be some fairly straightforward way to prove that conclusively, or at least to reduce it to some widely held assumption (e.g. "if someone can break this hash, then they can also break SHA-256").

With that in mind, let's take a closer look at your hash function.  It's specified as taking a sequence of $n$ input blocks, which are combined according to a particular expression involving addition (modulo $2^{512}$) and bitwise XOR:

$$H(B_1, \dots, B_n) = ((((B_1 + B_2) \oplus B_3) + B_4) \oplus B_5) + \dots$$

How do we simplify that?  Well, the fewer blocks there are, the simpler the expression gets.  So let's start by considering the simplest possible case, i.e. $n=1$.  With just a single block of input, your hash function looks like this:

$$H(B_1) = B_1$$

Now, consider the three security properties you've been asked about, and see if you can come up with single-block counterexamples:

preimage resistance: if given a value $X$, can you find a single-block message $M = B_1$ such that $H(M) = X$?
second preimage resistance: if given a single-block message $M = B_1$, can you find another single-block message $M' = B_1' \ne B_1$ such that $H(M) = H(M')$?
collision resistance: can you find any two single-block messages $M = B_1$ and $M' = B_1' \ne B_1$ such that $H(M) = H(M')$?

Hopefully, you should be able to answer "yes" to at least one of the three questions above.  (I won't spoil which one.)  In fact, with a little bit more thought, you should be able to figure out that, for single-block messages, the answer to the other two questions is definitely "no".

However, we're not done yet.  What if we consider messages consisting of two blocks?  Then the hash function will look like this:

$$H(B_1, B_2) = B_1 + B_2$$

where $+$, of course, denotes addition modulo $2^{512}$.  With that in mind, let's consider the three questions again.  (Of course, you don't need to reconsider the one for which you already found a single-block counterexample above.)

preimage resistance: if given a 512-bit value $X$, can you find a two-block message $M = (B_1, B_2)$ such that $H(M) = X$?
second preimage resistance: if given a two-block message $M = (B_1, B_2)$, can you find another two-block message $M' = (B_1', B_2') \ne M$ such that $H(M) = H(M')$?
collision resistance: can you find any pair of two-block messages $M = (B_1, B_2)$ and $M' = (B_1', B_2') \ne M$ such that $H(M) = H(M')$?

If, after considering the two-block case, your answer to some of those three questions was still "no", then it might be time to start considering whether the way you arrived at the "no" answer for the one- and two-block cases could be generalized to any number of blocks.  Or you could decide to spend some time considering the three block case, if you think that the answer might be "yes" in that case.

But in fact, in this case, that should not be necessary; just considering the one- and two-block cases should be enough to give a definitive answer to all three questions for this hash.

Ps. As for the extra question about the number of collisions at the end, first note that the question (or your transcription of it) clearly has some typos: four 512-bit blocks work out to 2048 bits or 2 kilobits, not 2 megabits!

In any case, we of course don't know exactly how many collisions SHA-256 has on that set of inputs, since the input space is too large to count them by brute force, and any method of determining the exact number significantly faster than by brute force would require breaking SHA-256, or at least come worryingly close to it.

However, you should be able to come up with a lower bound on the number of collisions SHA-256 or any other hash with a 256-bit output size can have for that input space, just using simple arithmetic.  (The generalized pigeonhole principle may be useful here.)  And your hash function $H$ is simple enough that you can count the exact number of collisions it will have on the input space $D$, and compare that with the lower bound.

In fact, just for a yes/no answer, you don't really even need to calculate the actual number of collisions.  All you really need to do is consider how close to the theoretical lower bound for a 512-bit hash your function $H$ gets, and then consider how making the hash output longer / shorter affects the lower bound.

(Also, yes, the result you'll get may seem counterintuitive.  What it really demonstrated is simply that the total number of collisions doesn't necessarily correlate with the difficulty of actually finding one.)


Can One-time-password be used as nonce in HMAC to prevent replay?

(Note: I think, In general OTP is usually understood as One-Time Pad. Here it means One-Time Password.)

Using an OTP as a nonce does not seem possible in general. An OTP doesn't necessarily always have to be distinct. Since there is some kind of synchronization between the communicating parties the OTP might repeat.

Specifically, say your OTP consists of randomish 64 bits. Then whenever you need a password it is fine if both parties derive 64 random bits independently of previous values.

If you need a nonce, however this gives you a decent collision probability after about a billion repetitions. (Due to the birthday bound.)

However, practically, most hash functions have good PRF properties and can be used to generate nonces.


$s_1, ..., s_N \stackrel{\$}{\leftarrow} S$

means coordinate-wise sampling:

$s_1 \stackrel{\$}{\leftarrow} S$

$s_2 \stackrel{\$}{\leftarrow} S$

...

$s_N \stackrel{\$}{\leftarrow} S$


AES-XTS vs AES-CTR for Write Once Storage

Analyzing the risks and correctly setting the threat model is important when choosing the encryption schemes.

If the attacker is a passive attacker, that he can only read the hard disk while transmitted, as it pointed out in the comparison of the XTS vs CTR question, there is no benefit against for passive attacker.

When the attacker, however, is an active attacker you will need authentication. CTR and XTS modes are not authenticated encryption modes. In CTR mode, when the attacker modified a bit the ciphertext will turn into a valid plaintext. It is also possible in  XTS mode, a little harder to achieve. To mitigate, you can hash the whole disk and then apply a digital signature on it. The signature can be transmitted over another channel.

You can see a discussion here Why not authenticate full-disk encryption? about integrating the authentication into a filesystem.


Is it safe to reuse ECDH asymmetric keys for authentication?

Such keys are called static keys. Keys that are newly generated each time are called ephemeral keys. Note that you need to trust the public keys of the static key pairs to use them for authentication. This trust can be established by embedding the DH public keys in leaf certificates within an PKI.
Please note that there is an issue when static keys are used on both sides during common Diffie-Hellman key agreement: the generated secret will be static as well, as the whole scheme has now become deterministic. The solution for this is to send a nonce as well as a public key by one of the parties; this nonce can then be used during key establishment to create a unique secret key.
More information in chapter 6 of NIST SP 800-56A, specifically 6.3
Scheme Using No Ephemeral Key Pairs, C(0, 2) scheme.


Small subgroup attack on Diffie-Hellman key exchange

Does it mean that i have to try all 5 values from S or the key can be
  indeed determined uniquely without performing exhaustive search on S?

In the general case, you cannot determine the key without performing exhaustive search on $S$.

Small subgroup attacks aim to make the key belong to a small subgroup to make the exhaustive search feasible in practice. So by definition, usual small subgroup attacks require exhaustive search.

I posted something about Small subgroup confinement attack on Diffie-Hellman to fully understand the functioning of the attack, maybe it can help you.


Is the RC4 KSA the same as an extractor?

It would not work as a randomness extractor as there is a detectable correlation between the key, the internal state, and the output.

http://saluc.engr.uconn.edu/refs/stream_cipher/fluhrer01weaknessRC4.pdf
https://eprint.iacr.org/2011/448.pdf

It does expand the key by concatenating it until it fills a 256-byte array and it is used to mix the internal state. So it acts like it, but it is not one, and should not be used as one.


Is there such a thing as perfect CPA security?

The CPA indistinguishability experiment definition that you give is taken from Katz & Lindell's textbook.  In my copy (2nd Ed.), it's on page 74.

  It would seem like this definition cannot be met since the adversary can use the oracle access to compute $\text{Enc}_k(m_i)$ for $i=1,2$ as many times as necessary until one of them coincides with $c\leftarrow \text{Enc}_k(m_b)$, at which point $\mathcal A$ knows what $b$ is. Is my thinking correct?

One thing you're missing is that earlier the chapter stipulates that only probabilistic polynomial time (PPT) adversaries will be considered.  Earlier in the chapter (pp. 49-50):

  However, when it comes to the computational power of the adversary, we will from now on model the adversary as efficient and thus only consider adversarial strategies that can be implemented in probabilistic polynomial time.

So the first problem with your adversary is that you've not demonstrated that it is a PPT algorithm.  Significantly, if the number of calls to the encryption oracle is an exponential function of one of the security parameters (as brute force guessing algorithms tend to be), then it's disqualified.

The second problem is that the encryption algorithm is also PPT (see Definition 3.7, p. 52), which means it's probabilistic—it's allowed to make random choices.  This means that you can't assume it's the oracle is mathematical function—calling $\text{Enc}_k(m)$ multiple times with the same $m$ can (and should!) produce different results.


Specification of the scream stream cipher is unclear

I've just dived into that paper for you, with the following results:

You've got that one correct.
The eight-byte input is multiplied with matrix M. There is no mention or indication of the polynomial you mention. Simply follow the paper.

The matrices are fixed [[1,2],[2,1]] and [[1,3],[1,3]]. So, 2 and 3 are NOT replaced by x. The multiplication is on GF(256) with the polynomial specified at page 4. Thus, you have to do something like this: GF256_Multiply(2, S1[x], 0x1C3) where 2 = M1(0,1) = M1(1,0) for example. That's why they call T0 and T1 "lookup tables". These are fixed tables which imply M1 and M2 are fixed too.

(Notice: This was corrected thanks to OP's own research and the corrections OP mentioned in the comments to this answer.)
I think you got a bit confused there. MSB (= Most Significant Bit) and LSB (= Least Significant Bit) define "bits", while the paper explicitly talks about "bytes" in section 3. Therefore, they did not need to define any MSB or LSB. The paper simply defines $byte_0$ (which is, reading from left to right, the leftmost byte), and $byte_3$ (which is the rightmost byte). So you practically extract the 4 bytes into $byte_0$ up to $byte_3$ from left to right (aka "first in, first out").

Hope that helps.


If we don't trust current PQ algorithms enough to use them on their own why should we trust them for a hybrid?

Trusting the algorithms is not a black and white issue. Given that we cannot unequivocally prove the hardness of the problems underlying basic cryptographic primitives, we have no choice but to assume that they are hard. A vast amount of effort in cryptographic research is spent on minimising these assumptions and analysing their hardness. We already have a long track record with lattice-based cryptography and hard problems in lattices. However, we have a far longer track record with problems like RSA and discrete log/Diffie-Hellman assumptions. As such, we have more "trust" in them. Furthermore, key lengths is tricky, and although certain problems may indeed be very hard, understanding how hard they are is crucial for setting key lengths. (This is why Elliptic curve keys can be 256 bits vs RSA key that have be 2048 bits at the very minimum.) With lattice and other assumptions used for PQC, we have less experience with this.

So, we have no reason whatsoever to believe that lattice-based or other PQ proposals will not be good enough in the long term if quantum computers at scale are ever built. However, we also have less history with these assumptions, and the prudent and conservative approach is to take both (with hybrid encryption). As time goes on, we will learn more and more about the lattice and other assumptions, and will feel more comfortable about using them by themselves.


Actually, that was proposed here back in 1998 (sorry, an electronic version of the paper does not appear to be on the web) -- the author claimed a modest speedup in the private operations.  However, that speed up would appear to be about the same if you just did "multiprime RSA", that is, selected an RSA modulus of the form $pqr$ for three distinct primes $p$, $q$ and $r$.

As for the security, well, reducing the size of the primes does make factoring methods such as ECM easier.  However, with the current state of the art, it would appear that ECM against a product of three 682-bit primes (whether two of the primes were duplicated or not) would be harder than doing NFS (which doesn't care how big the primes were); however it's still enough to make people uneasy.

If you are really interested in performance, you probably should look at Elliptic Curve systems anyways...


Does XOR'ing a random number with its inverse reduce its security if the result is a palindrome?

The xor of two random strings is a random string, so you're basically generating a 128-bit random string from a 256-bit random string.

Yes, it reduces security compared to a pure 256-bit random string.
Yes. As you pointed out, there are only $2^{128}$ possible strings.
Yes. The attacker can generate all $2^{128}$ strings and trivially concatenate them with their reflection in each step.
No, both have 128-bit security against brute force attacks.
No, as mentioned there is no security gain in using palindromes, which implies that there is no advantage at all in use palindromes. For example, a 256-bit palindrome can be stored "compressed" in 128 bits, but it still provides only 128 bits of security. You could simply use a normal 128-bit key instead, which fits in the same size, has the same security, and is a lot simpler.


How can one prove correctness of shared secrets in secret sharing schemes?

Here is one possible approach:

The dealer generates a group suitable for a Pedersen commitment scheme (namely, an Elliptic Curve with prime order $p$, and two elements $G, H$ where no one knows the discrete log of $H$ with respect to $G$) - we can do this in a multiplicative group; I just find the additive notation a bit easier in this case, as the notation for the math on the commitments matches that of the uncommitted values.
The dealer selects a Shamir Secret Sharing polynomial (the constant term the shared secret, the rest of the coefficients random) over $GF(p)$; he also creates a Pedersen commitment for each coefficient $c_i$ (using a random value $r_i$), and publishes it (and so he publishes the values $c_iG + r_iH$), along with a series of NIZKPs that he knows the values $c_i$ that he committed to
The dealer generates shares for each one; with user $x$, he generates the share $z = c_nx^n + c_{n-1}x^{n-1} + … + c_0x^0$ and also generates a NIZPF that $x^n(c_nG + r_nH) + x^{n-1}(c_{n-1}G + r_{n-1}H) + … + x^0(c_0G + r_0H)$ is a commitment to $z$; he sends $z$ and the NIZKP to the user.

Each user can verify (based on the public NIZKPs) that the dealer has committed to a single group-wide polynomial.  In addition, based on the NIZKP that the dealer gives to each user, they can verify that their share is consistent with that group-wide polynomial.


Why is RSA decryption the inverse of encryption?

RSA is based on the Carmichael function $\lambda$ (or if you prefer Euler's totient function $\varphi$):

$$x^{\lambda(n)} \equiv 1 \pmod n$$

for every integer x that is coprime to n.

From this you trivially get:

$$x^{k\lambda(n)} \equiv (x^{\lambda(n)})^k \equiv 1^k \equiv 1 \pmod n$$

and multiplying both sides with x:

$$x^{k\lambda(n)+1} \equiv x \pmod n$$

the last equation holds for all integers even if they're not co-prime to n.

We chose $e$ and $d$ such that their product is 1 modulo $\lambda(n)$ or equivalently $e \cdot d = k\lambda(n)+1$ for some $k$.

Thus $(x^e)^d \equiv x^{ed} \equiv x \mod n$ which means that encryption followed by decryption returns an integer equivalent to the plaintext. By limiting $x$ to $0 \leq x < n$ you will get the original integer.

The wikipedia page for RSA lists proofs for the correctness of RSA as well.


Can length extension attacks be avoided by a single bit flip?

The mistake I made is that flipping a bit (or all bits) of the output will still leak the full state of the hash function, after which it is possible to perform a length extension attack by updating more data from the given intermediate state. The bit flip is of course easily reversed by an adversary. Thanks go to fgrieu and yyyyyyy for pointing this out.

Performing a final calculation may still work, but it should of course not allow an attacker to retrieve the state after the last block was compressed. That means that the final operation needs to be one-way as well. This disallows simple instructions such as XOR (with known data) that can be reversed.


Cryptosystems used to generate public key certificate

The ciphersuites only define the properties of the SSL channel that is to be created. The certificate - including the private key usage indicated in the certificate - should be consistent with the ciphersuite.

For instance if you have a ciphersuite starting with TLS_RSA then the certificate should allow encryption, and the public/private key should be RSA of course. If you have a TLS_DHE or TLS_ECDHE ciphersuite then the certificate should allow authentication with any supported authentication algorithm. Authentication is generally supported by the certificate of course, as that is the main use case for TLS certificates in the first place.

How the certificate was generated is outside the realm of TLS. Basically it doesn't care, as long as you can create a trust chain to a trusted certificate in the certificate store. For this it does need to be able to verify signatures though, so the algorithms used to sign certificates need to be supported.


Why does Neumann think cryptography isn't the solution?

That New York Times article actually continues after that quote:

Dr. Neumann explained that there are always ways to get around cryptography barriers and that these methods have nothing to do with breaking codes.
"It's like the voting machines," he said. "You'd like to have some integrity in the electoral process and now folks are coming out of the woodwork saying, `We have this perfect algorithm for privacy and security.' "

So it's very clear that this is the difference between secure systems and just the cryptographic algorithms.
That said, if things are managed right then cryptography certainly has its benefits.

As another example, nobody will argue that TLS doesn't have its advantages. But even there, the huge number of Certificate Authorities and the enormous amount of trust put on them and the browser manufacturers threatens the system, even though the TLS protocol is relatively secure when implemented correctly.


Schnorr signature is a pair challenge-response $(e, s)$ with challenge computed as a hash of message $m$ and initial commitment $r$; signature is verified by re-creating that commitment with challenge and response only.

For blind Schnorr signature, one keeps verification equation while randomizing both challenge and response with $\beta, \alpha$ respectively, see page 368. Hash is calculated by receiver of the signature; signer computes his response having blinded challenge $e = H(m, r') + \beta$ only, without $\beta$ and $r'$ to enforce blindness property. That is, having an $(e, r)$ pair verified, signer can not recognize it as any of his signatures sent to receivers.

In case receiver would send $e = H(m, r)$ unblinded to signer, or let signer calculate the hash himself, signer would recognize the receiver later.

The only missing part is how to calculate $r'$ such that verification equation would hold for $(e, r)$ after blinding. Best be done yourself as a homework.

Blind signatures are here to avoid recognition. That is, to have no algorithm that, having a signature and a database (records of signatures issued), would output who this signature was produced for. To achieve this, two challenge-response pairs were introduced, and the user is actually generating $e = H(m, r)$ himself. Connection between that pairs is user secret. Having it open, blindness property would be lost.


Why FHE only needs support for addition and multiplication

Yes, it is related and they don't need only addition and multiplication. If you know from the electronics the Functional completeness;

  In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression

What operation is suitable for functional completeness is fine. However, addition and multiplication are common since many mathematical structures have it. Besides, there are others,for example; there is a partial FHE that only supports x-or.

It is a similar idea in FHE and you can build almost any circuits. The basic problem is the semantic security which prevents the direct comparison of ciphertexts. You compare in a different way.

Also, if you look at TFHE: Fast Fully Homomorphic Encryption over the Torus yo can see the supported boolean operations;

  The library supports the homomorphic evaluation of the 10 binary gates (And, Or, Xor, Nand, Nor, etc…), as well as the negation and the Mux gate. Each binary gate takes about 13 milliseconds single-core time to evaluate, which improves [DM15] by a factor 53, and the mux gate takes about 26 CPU-ms.

To calculate $E(m_1^{m_2})$? is really depend on the scheme. But basically you cannot use $E(m_1^{m_2}) = E(m_1) E(m_1) \dots E(m_1)$ since it will reveal your $m_2$. You need at least the repatings squaring method to hide the actual value.

With square-and-multiply you can at least hide the actual value of the power, not the size. let convert the below code into bit based FHE;

Let b be the “base” of the power, let p be the exponent.
Let r = the multiplicative identity (e.g.: 1).
Let s = b.
While p > 0 do:
    if p is odd
        let r = r * s.  // The "multiply"
    Let s = s * s       // The "square"
    Let p = p / 2 //(throw out the remainder).
The result is r

FHE version ( I keep $b=m_1$ and $p=m_2$);

While C(p,0) do:
    r =(r*s∗ S)+(r∗S′)
    Let s = s * s
    Let p = p >> 1
The result is r

in this code C(p,0) is the comparator as in Representing a function as FHE circuit. The multiply is performed by the if condition 'S' keep the value of p is odd. Since it is semantically secure we apply multiplication by the bit for if and it's inverse for the else case.

As you can see from this circuit this will only release the number of bits in $m_2$

In Short: We can build almost any circuit, however, some circuits may reveal some information that either sensitive or not depending on the problem


Efficient attack on RSA with known padding scheme and public key

As the padding is deterministic and the amount of input values is minimal, you can just try and encrypt each possible value with the public key. If the result - the ciphertext - is identical to the one you have then you've found the input value and therefore the PIN. You are guaranteed success in $2^{16}$ tries after all, that's 65536 tries in total.


Difference between Symmetric and Asymmetric. Is this answer correct, based on a written test?

I don't believe he is answering the right question.  You essentially asked "why are public keys so much larger than symmetric keys", and after his first sentence (which started to address the question, but was a bit vague), he tried to answer the distinct question "why are public key operations so much slower" (not that he got the details of that correct; his last sentence appeared to imply that public key operations take an exponential amount of time).


Can "collisions" occur with encryption algorithms?

For a given Key K and two messages $m_1$, $m_2$ is it possible for an encryption algorithm (say AES256) to produce this: $AES(K, m_1) = AES(K, m_2)$.

Not if $m_1$ is different than $m_2$. Assuming you are talking about AES as a block cipher, and $m_1$ and $m_2$ as input blocks, this is not possible. Every different input block will have a unique output block. Take this cropped image as an example of a 4-bit block cipher with a fixed key, with 16 plaintexts and 16 ciphertexts:

As you can see, 11 encrypts into 12, and thus 12 decrypts to 11. If, as per your example, 13 also encrypted to 12, how would you correctly decrypt 12? Also, how would you decrypt 9?

Well, you couldn't, because a block cipher is a bijection, that is the amount of plaintexts and ciphertexts are composed of sets of equal size, and there is a one-to-one mapping between them, with all of them being paired.

The following behaviors of a block cipher are possible:

$AES(K_1, m_1) = AES(K_2, m_1)$
$AES(K_1, m_1) = AES(K_2, m_2)$
$AES(K_1, m_1) = m_1$

As fgrieu pointed out, a mode of operation with a third input (such as an IV or a prior block) may cause this to happen within a group of blocks, but since the decryption process depends on that third input as well, it will decrypt properly.


Why in BCNS protocol both parties don't follow the exact same key extraction approach

Answer of your question is in page $7$.

Lemma2:

For odd $q$, let $v=w+e\in Z_q$ for $w,e\in Z_q$ such that $2e\pm 1\in E \pmod q$. Let $\bar v=dbl(v)$ then $rec(2w,\langle \bar v\rangle _{2q,2})=\lfloor \bar v \rceil _{2q,2}$.


Is "6 bit packed ASCII" an effective encoding to obscure text data?

No. I actually new how to do such coding on my MSX machine in the mid-eighties (when I was 12). I'm pretty sure I could have decoded it back then. Note that binary code was much more used at that time; you had to code in assembler to get any kind of performance. It was also pretty common to compress things in such a way because you did not have much memory either.

What you're describing is an encoding scheme. Encoding is something different from encryption. Obviously it can obfuscate text, but that obfuscation is just skin deep. This is especially the case if somebody starts to look for strings.

You could however encode to base64 with a different alphabet. That kind of obfuscate things enough that you have to revert the encoding to read it. You could also XOR your scheme with a (multi-)byte pattern to make things less readable for humans.


Is this a good Pseudo-Random Number Generator?

What could possibly be an advantage of your method from directly sampling the bytes from the prime number distribution?
Like:
Start at some integer $k$ and sample the 8 bits as: $k*30+\lbrace -13,-11,-7,-1,1,7,11,13\rbrace$, each time when it is a prime number, you set the bit at that position to 1, otherwise to 0. If your sampled Byte is $<= 64$ use k-= Byte, otherwise use k+= Byte for the next sample.
Isn't this much simpler than your method, or am I missing something of importance?


Why does the PKCS1 RSA private key structure contain more than just exponent and modulus?

It has to do with optimizing RSA.

It turns out that using the Chinese Remainder Theorem with $p$, $q$, $d\pmod{p-1}$, and $d\pmod{q-1}$ (i.e., prime1, prime2, exponent1, exponent2 from the data structure in the question) to run the decryption operation faster than if you only had $d,n$.

For more information on how it is done, I found this reference http://www.di-mgt.com.au/crt_rsa.html


Initialization vector in symmetric-key encryption

If you really can't use an IV (why?), then just about the best thing you can do is use something like SIV mode (RFC 5297).  SIV is a "maximally misuse-resistant" authenticated encryption mode which provides the following characteristics:

If every message is tagged with a unique nonce, SIV provides full IND-CCA2 security (up to the usual limits; i.e. it still leaks the length of the message).
Without a nonce, SIV remains IND-CCA2 secure as long as the same message is never encrypted twice (with the same associated data, if any).
If a message is encrypted twice without a nonce (or with an accidentally reused nonce), the only thing an attacker can learn is that those two messages are the same.

The down side of SIV mode is that it's a two-pass encryption mode: the encryption code must process the message twice.  Thus, it is best suited for fairly short messages that can be held entirely in memory.  Basically, on the first pass, SIV computes a secure message authentication code of the plaintext and any associated data (including the nonce, if provided); on the second pass, the message is encrypted using conventional CTR mode encryption, with the MAC from the first pass used as a "synthetic IV" (whence the name of the mode).

Also, to allow the message to be decrypted (and its authenticity verified), the 128-bit MAC/IV must be transmitted along with the message.  Thus, SIV adds an unavoidable 16-byte overhead to each message, and is therefore not suited for format-preserving encryption.  Of course, the same is true of every authenticated encryption mode, and indeed of every mode capable of providing semantic security, whether authenticated or not.


The usual curves we use in ECC are often not suitable for pairing-based cryptography (e.g. you may not find an efficient bilinear mapping), while pairing-friendly curves may not be suitable for normal ECC (e.g. in gap Diffie–Hellman groups, DDH is not hard).

There is an IETF draft on Pairing-Friendly Curves, summarizing the popular curves used in pairing-based cryptography


Is it secure to repeatedly rehash a digest to extend the digest length?

Section 2.6 of their submission talks about this.
There they state that for most cases they simply use SHA-256, -384 or -512.
In the (uncommon?) case that a hash function with a larger output is needed, they use the OFB-like1 construction.
The rationale being that a collision on the OFB construction would immediately imply a collision on the underlying hash function - as the direct output is part of the expanded output.
This also explains why they don't want to involve another (more efficient) function: To reduce security guarantees and prefer simplicity over optimization for rarely needed scenarios.

1: OFB-Mode is a way to construct a PRG and an CPA-secure encryption scheme out of a fixed-length PRF. It works essentially as $K_i=F_k(K_{i-1})$ outputting $K_1\|K_2\|\ldots\|K_\ell$ for a PRF $F$ and a secret random key $k$.


Note: For $y^2 \equiv x^3 + ax + b$, you want $$m\equiv(3x^2+a)*(2y)^{-1}$$ which is a shortcut that only makes sense once you understand how elliptic curves work.

"Why does it say y=1 and 4 for x=1?"

Like you said, plug in & solve: $$y^2 \equiv 1^3 + 2(1) + 3 \equiv 6 \equiv 1\space(mod\space5)$$
Ask yourself "Is there a square such that it is $\equiv 1 \space(mod\space 5)$?"
$$1^2\equiv1 \space \space and\space\space 4^2\equiv16\equiv1\space (mod \space5).$$
This means (1,1) and (1,4) are points on the discrete version (mod 5) of the curve.
If we weren't working (mod 5), plugging in 1 would give us (1,2) and (1,-2), which are points on the continuous version of the elliptic curve.
Below on the left is the continuous version of an arbitrary elliptic curve; on the right is what happens when you start working mod a number.

Example: Find 2P on the curve $E: y^2 \equiv x^3 + 2x + 3 \space(mod\space5)$ where P = (1,3)

2P = (1,3) + (1,3).  When adding two points on an elliptic curve, there are two cases:
Case 1: The points are not the same: Find the line that includes both of the points on the curve.  This line will have a third point on the curve.  Find that point and reflect about the x-axis to have the final point.
Case 2: The points are the same: Find the line tangent to our point on the curve.  This line will intersect the curve at one more point.  Find that point and reflect about the x-axis to have the final point.
Now what is the line tangent to (1,3) on E?
Use implicit differentiation (simple calculus):
$$dy/dx = (3x^2 + 2)/(2y)$$.
Now at our point (1,3): $$dy/dx = 5/6 = 5*6^{-1} (mod \space5)$$
It is easy to see (and find) that $6^{-1} \equiv 1 \space(mod\space 5)$
So m = 5 is the slope for our line tangent to (1,3): $$L: y-3 = 5(x - 1)$$
So $$y = 5x - 2.$$
Now where else do E and L intersect?
We have

$E: y^2 \equiv x^3 + 2x + 3 \space(mod\space5)$

$L: y = 5x - 2$

Plug L into E: $$(5x-2)^2 \equiv x^3 + 2x + 3$$
Expand: $$25x^2 - 20x + 4 \equiv x^3 + 2x + 3$$
There is a useful algebraic property for cubic polynomials that is fun and not hard to prove:  The summation of the polynomial's roots equal the negative of the $x^2$ term's coefficient.  That is,
$$\sum roots = -(coeff.\space of\space x^2\space term)$$
So in rearranging the polynomial further, we care only about the $x^2$ terms:
$$0 \equiv x^3 - 25x^2 ...$$
We already added (1,3) to itself, so it must be that 1 is a root of multiplicity 2.
$$1 + 1 + r_3 = -(-25) = 25$$ implies the last root is 23.  Recall we are working (mod 5) though, so our last root is 23 $\equiv 3$
Now plug $r_3$ into our linear equation: $$y = 5(3) - 2 = 13 \equiv 3\space(mod\space5)$$
Reflect
Lastly, reflect our point (3,3) about the x-axis to get (3,-3).  Recall again we're working (mod 5), so add the modulus to -3 until is it in the range $[0,4]$.
$\therefore$ 2P = (3,2)


Relaxing Semi-Honest Security in Multiparty Computation

I'm not sure that the issue here is uniform versus non-uniform, but I'll address this first. It is possible to provide a uniform definition. In order to see what it would look like, I recommend reading Oded Goldreich's uniform treatment of zero knowledge http://www.wisdom.weizmann.ac.il/~oded/PS/uniform.ps.

In any case, your question is more about quantifying over all possible inputs, versus over a specific distribution. (Note that in Oded's uniform treatment, the quantification is over all poly-time samplable distributions. Here, you wish to guarantee security for a specific distribution only.) It is possible to define such a notion and it does make sense. The only question is if it buys you something. I have used such a notion once, in order to construct a secure password authentication protocol; see the definition in http://u.cs.biu.ac.il/~lindell/PAPERS/session-key.ps (Section 2.3.2). In this definition, the password is chosen randomly from a dictionary as part of the ideal and real models. You could do the same thing and choose a random key.


The BIT STRING value starts with a single byte that indicates the number of bits that are not used. Bit strings may be of any size and they may therefore not be a multiple of 8. So they start with the number of bits that should be skipped at the end. In your case, it tells the user that all bits of the last byte 58 (01011000 in bits) are part of the value.

Most of the time the BIT STRING encodes a byte array anyway, so it will generally be set to 00 instead of one of the other 7 possibilities.

The first bit is the leftmost bit, and the final bit is the rightmost bit. But that's only of importance if the order of bits is of consequence. In this case the BIT STRING contains the uncompressed EC point $W$ so it is not important.

You can find this, and more in the Layman's guide to ASN.1 by  Burton S. Kaliski Jr. section 5.4 "BIT STRING", and of course the standard documents ITU-T X.680 and X.690 (both payware, so I won't link).