From the same paper:

Use a fixed position for the leading 1 in the secret key;
Multiply the secret key by a small power of 2 to account for cofactors in the curve group and the twist group.

The first one is to make the scalar multiplication with always the same number of iterations of the loop, for constant-time reasons. The second one makes sure that the resulting point belongs to the prime order subgroup: if someone sends a point of small order, then the result of the scalar multiplication will be automatically $0$ since the secret key is a multiple of the cofactor (see page 8 of the paper).
For the public key, it is only that any value $q$ corresponds to a valid $x$-coordinate of a point that belongs either to the curve or its quadratic twist. Of course, you can take them only in $[0,2^{255}-20]$, but the main point is that it fits in $32$ bytes, and any $32$-byte values are valid.


What are the inputs of the AES key wrap algorithm?

The DEK is indeed the "plaintext" and the KEK, derived from the user's pass phrase in your case, is the KEK.

A passphrase is not a key and should never be directly used as a key; you should use a password based key derivation function (such as PBKDF2) to derive a key from a passphrase.


Constant size commitment to a membership of a fixed size of elements

I will first restate the question as I understand it after the clarifying comment. If I'm misunderstanding something, please let me know.
Let $M$ be a set of size $n$. There are two parties $A$ and $B$.
We are looking for a protocol that does the following.
$A$ chooses a subset $N\subseteq M$ with $|N|=2n/3$ and computes some message $m$ with $|m|=\ell$, where $\ell$ is a constant, independent of $n$.
Given $m$, party $B$ is able to reconstruct and output $N$ with probability $1$.
If that is a correct description of what you're looking for, then it's sadly impossible, since it would imply infinite lossless data compression.
There are $\binom{n}{\frac{2n}{3}}$ many possible subsets, so by sending $m$ you are transferring $\log_2 \binom{n}{\frac{2n}{3}}$ bits of information.
We have
$$\log_2 \binom{n}{\frac{2n}{3}} \geq \log_2\left(\frac{n}{2n/3}\right)^{2n/3}=\log_2\left(\frac{9}{4}\right)^{n/3} > \log_2 2^{n/3} = \frac{n}{3}.$$
Since $m$ is only $\ell$ bits long, the pigeonhole principle tells us that you cannot transfer more than $\ell$ bits of information. For any $n>3\ell$¹ that's clearly being violated here.

¹This happens even earlier, I just can't be bothered to do a tight analysis here, we're using pretty loose lower bounds.


Since you have ChaCha20 as the cipher, it shouldn't occupy too much resource to add a BLAKE2 hash function next to it.
The BLAKE2 hash function comes in 2 variants: BLAKE2b, and BLAKE2s. ChaCha20 uses 32-bit words, which is more compatible with BLAKE2s. The only major difference between the hash and the cipher are the shift/rotate amounts, and the HAIFA hash compression function mode of operation.
While @SAI_Peregrinus have a good suggestion, I find it a little bit radical, so if you prefer a conservative approach, you can implement an additional BLAKE2 hash function to be used in any hash-based KDF you prefer.
As for your original ideal, I wouldn't recommend it as the authenticator is based on universal hashing in a biased modular integer arithmetic.


Will non-ECC algorithms like RSA eventually become too inefficient?

RSA will never become "impractical" until it gets broken. (in polynomial-time)

As the best current algorithm to break RSA is sub-exponential (general number field sieve / GNFS). According to Moore's law computing power grows exponentially however. So simply increasing key size will always be an option.

Beyond 256-bit security EC crypto just is significantly faster than "classic" crypto. For example, for 512bits, EC crypto is 64 times faster than classic crypto (compared to private key operations using RSA).

If you are interested in key sizes you should read this paper.


As far I understood the paper (very briefly) it looks like it's talking about the default asymmetric encryption without the CA (certificate authorities). However - it seems there's the SEM part of the system which seems to know the private keys (???) and acts as the revocation authority.

I believe you can use the default Java crypto API without needing to implement it yourself. In fact I'd discourage you to do that until you REALLY know what are you doing, how/what to properly encrypt with the public key, etc. For the start - I'd advice to learn something about the cryptography elements and implementations, what you see in the papers are mathematical models of common crypto elements.

As it goes for your questions:

  Pick a generator of g of Z∗p with order q. -> for this step I just
  followed this link as reference and calculated g as g(p−1)/2modp=1
  where g is prime number.

It means to choose you keysize (so - e.g. 2048 bit keys) and generate a private key (p, q) and public key (p*q). Using a KeyPairGenerator should be effective.

  Choose cryptographic hash in the paper they have specified that they
  had used SHA-1 to generate hash. I can generate the hash values but I
  am not able to reproduce the hash functions given in base paper, does
  (0,1)∗ is used to represent binary.

Any reasonable hash function will do - so lets assume SHA-1. All numbers are binary for the computer, its only their 'human' representation how you can display them (decimal, hex, ..)

  Hash usually generates hexadecimal values do I need to convert them
  into decimal for Raise operation i.e. power

Hash returns a bit array (byte[]), you can use the BigInteger class to raise it to certain power. Don't forget all operations are under the discrete group  (so you do ($g^a$ mod p). About the steps described in the paper - you need to 'sign' the hash. And after the decryption, the signature is compared with a newly computed signature so data integrity is ensured.

As for the topic - I'd advice to spend some time understanding the default cryptography and asymmetric encryption (for this case) and usage practices and it will be much easier for you to follow the paper. The problem with the cryptography is that something is misunderstood or neglected, it will completely break the security.

In all cases - have fun :)


Is elliptic curve point multiplication semantically secure?

If an attacker can choose the points $P_i$, than this system is not semantically secure. For example, they may choose $P_2=2P_1$, and the corresponding encryption $Q_2$ would be equal to $2Q_1$.

If the points are chosen at random, this system is semantically secure if decisional Diffie-Hellman assumption holds for the curve. This assumption is presumed to hold for elliptic curves typically used in cryptography, unless the curve is chosen to have a bilinear pairing.


How can I prove I have a certain Facebook account by signature?

You have to show that you can use the account. You cannot prove it offline, without accessing the account (or storing public information there) or else anyone else could produce the same "proof".

Normally proof of ownership of a web page is done by the other party producing some random value and you publishing that value on the page. That would work here too. Alternatively, since Facebook accounts double as email, the other party could send a random secret by email to the @facebook.com address of that account, which the supposed account owner would have to find out. (Plain email is often not really a very secure transport, though.)

If you insisted on using asymmetric cryptography, you would have to publish a public key using that account. Then you could prove ownership of the corresponding private key by producing signatures using it. This would have the advantage of only needing to publish the key using the account once.


One hexadecimal digit is equivalent to 4 bits, so 16 of them would be 16 * 4 = 64 bits.
Intuitively, since one hexadecimal digit takes up exactly half an octet, your bit strength compared to using the full octet is also halved, so 128 / 2 = 64.


PKCS#7 CMS - Message digest calculation process

Closely related: What does CMS standard mean by "initial input to the message digest"
The signature schemes envisioned by PKCS7/CMS use two stages, where the data to be signed is first hashed and that hash is used in signature generation and verification (RSA, EG, DSA, and ECDSA). For your example -- RSASSA-PKCS1-v1_5 with SHA1 -- some data is hashed with SHA1, and that hash is encoded, padded and modexp'ed, which was described in older versions of PKCS1, and PKCS7, as 'encrypting with the private key', although that description was found to be harmful and is no longer used. (See my https://security.stackexchange.com/questions/159282/#159289 for some of the Qs/As here and on security.SX on this topic, and there are more you can find by searching.)
PKCS7 originally simply applied this process to the data (what is now eContent). It and its successor CMS were enhanced to allow either that basic process or a two-stage process:

the hash of (the value of) eContent (your first red bracket) is computed, and that value is placed in the messageDigest attribute in signedAttrs. In addition eContentType is copied to the contentType attribute in signedAttrs. Other attributes may be added, and some standards that build on CMS define additional requirements on the attributes in signedAttrs.

(an encoding of) the signedAttrs structure is signed. This is almost your second red bracket, except with the tag modified as described below.

The specification for these two options is intermixed in the document. First note that the previous section (5.3) defines signedAttrs:
      signedAttrs is a collection of attributes that are signed.  The
      field is optional, but it MUST be present if the content type of
      the EncapsulatedContentInfo value being signed is not id-data.
      SignedAttributes MUST be DER encoded, even if the rest of the
      structure is BER encoded.  Useful attribute types, such as signing
      time, are defined in Section 11.  If the field is present, it MUST
      contain, at a minimum, the following two attributes:

         A content-type attribute having as its value the content type
         of the EncapsulatedContentInfo value being signed.  Section
         11.1 defines the content-type attribute.  However, the
         content-type attribute MUST NOT be used as part of a
         countersignature unsigned attribute as defined in Section 11.4.

         A message-digest attribute, having as its value the message
         digest of the content.  Section 11.2 defines the message-digest
         attribute.

The part you quote (5.4) then says, more fully:
   [With or without signedAttrs] the initial input to the message
   digest calculation process is the "value" of the encapsulated content
   being signed.  Specifically, the initial input is the
   encapContentInfo eContent OCTET STRING to which the signing process
   is applied.  Only the octets comprising the value of the eContent
   OCTET STRING are input to the message digest algorithm, not the tag
   or the length octets.

   The result of the message digest calculation process depends on
   whether the signedAttrs field is present.  When the field is absent,
   the result is just the message digest of the content as described
   above.  When the field is present, however, the result is the message
   digest of the complete DER encoding of the SignedAttrs value
   contained in the signedAttrs field.  Since the SignedAttrs value,
   when present, must contain the content-type and the message-digest
   attributes, those values are indirectly included in the result.  The
   content-type attribute MUST NOT be included in a countersignature
   unsigned attribute as defined in Section 11.4.  A separate encoding
   of the signedAttrs field is performed for message digest calculation.
   The IMPLICIT [0] tag in the signedAttrs is not used for the DER
   encoding, rather an EXPLICIT SET OF tag is used.  That is, the DER
   encoding of the EXPLICIT SET OF tag, rather than of the IMPLICIT [0]
   tag, MUST be included in the message digest calculation along with
   the length and content octets of the SignedAttributes value.

Breaking that down: without signedAttrs the hash of eContent is used for the signature in section 5.5. With signedAttrs, the hash of signedAttrs -- only signedAttrs, with the tag of the encoding modified as described -- is used for the signature in 5.5. But since the content of signedAttrs includes the hash of eContent, and the value of eContentType, the signature effectively protects those as well: if you change eContent without changing signedAttrs then the verifier will detect that hash(eContent) doesn't match signedAttrs.messageDigest, and if you change eContent and signedAttrs.messageDigest then the verifier will detect that the signature isn't valid for the modified signedAttrs.
   When the signedAttrs field is absent, only the octets comprising the
   value of the SignedData encapContentInfo eContent OCTET STRING (e.g.,
   the contents of a file) are input to the message digest calculation.
   This has the advantage that the length of the content being signed
   need not be known in advance of the signature generation process.

   Although the encapContentInfo eContent OCTET STRING tag and length
   octets are not included in the message digest calculation, they are
   protected by other means.  The length octets are protected by the
   nature of the message digest algorithm since it is computationally
   infeasible to find any two distinct message contents of any length
   that have the same message digest.

This repeats, more verbosely, that without signedAttrs the hash of eContent is used for the signature in 5.5.
5.5 then completes the sequence:
   The input to the signature generation process includes the result of
   the message digest calculation process and the signer's private key.
   The details of the signature generation depend on the signature
   algorithm employed. [...]

"The result of the message digest calculation process" used for signature generation (and verification) -- as defined in 5.4 -- is EITHER: (without signedAttrs) the hash of the value of eContent OR: (with signedAttrs) the hash of the encoding of signedAttrs.


Relative security of this polyalphabetic cipher system?

This is in fact the original Viginère method with a one-letter key.

The system as proposed by him, use a keyword $K$ of length $n$ for the first $n$ letters of a text, and then used the plaintext (from the start onwards) as the key for the rest. (it'a a "plain-autokey" cipher). He did not repeat the keyword, which is a somewhat weaker system, which is how his cipher is often represented nowadays.

It's still statistically weak, by autocorrelation it's easy to find the length of the keyword, and then it's reading in depth, essentially. Friedman wrote about this method on it in one of his cryptanalysis books.

Your friend's system only has a 1-letter (or one-alphabet) keyword, essentially. It doesn't matter if we use some random alphabet for the first, you just try all first plain letters and decrypt from the second letter onwards. Only one will make sense, normally.
At least Viginère' system is not directly brute forcable in that way for long keywords.


Differential Privacy and appropriate noise distribution

In order to bridge the gap between two worst case scenarios to produce similar distribution of privatized answers certain noise is added. For example the salaries of a CEO (max) and a line worker or who ever gets minimum wage (min) may not be produce similar distribution without the noise.

Random values taken from Laplacian distribution with standard deviation is large enough to cover the gap.

This link has a good beginners tutorial with detailed explanation. Around 15.33 minutes in the video the speaker discusses about the issues like Global Sensitivity and Laplacian Noise.  Subsequently she discusses the proof too.


Actually, it turned out that scrypt was not as good as initially advertised under all conditions.

Scrypt was designed to support the specific case of password-based key derivation for full harddisk encryption. Basically, you type your password when the machine boots up (or awakes from hibernation). This is a context where the following apply:

The password processing time can take several seconds, since it is part of a boot-up procedure that will take a lot more time; under such conditions, user's patience is such that 5 seconds of dedicated time is not an unreasonable figure.
While the password is processed, nothing else happens on the machine, so the full CPU can be used for the task, and also the full RAM (so up to gigabytes).

In that context, scrypt totally rules. However, a busy authentication server, e.g. for an active Web server, can be a different beast. In particular, you will probably want to make the per-password CPU cost much lower, not only because there may be several users to handle simultaneously and concurrently with other tasks, but also because the more expensive password hashing is, the more vulnerable you become to basic denial-of-service attacks. For a busy server, a computing time down to 1 millisecond or so would be a more plausible value than the "5 seconds" alluded to above.

When scrypt must run fast, it cannot use as much RAM. In fact, at 1 ms CPU time, it uses so little RAM that GPU-based optimizations become to be worth the effort. In Litecoin, scrypt is used with 128 kBytes of RAM, and GPU implementations can be about 10x faster than CPU implementations (for the same hardware/operating cost), which is technically a function failure. One of the main points of a password hashing function is that attackers with GPU should not gain an advantage over defenders who use "normal" CPU. For fast password-hashing, bcrypt thus turns out to be more secure than scrypt. While scrypt is better than bcrypt when used for what it was designed for.

A further issue with scrypt is that it allows a time-memory trade-off: with more RAM, you can save on CPU, and vice-versa. This kind of flexibility gives some leverage to attackers who try to optimize their effort.

You may want to consult this presentation for some explanations and pointers to further information. The raw conclusion is that while scrypt is reasonably good for what it does, it cannot be said to be a drop-in improvement over bcrypt.

(As a side note, take care that use of a password-hashing function in cryptocurrencies is not the same context as use for protecting passwords in an authentication server. In an authentication server, there is an asymmetrical race between attacker and defender, because the defender uses generic hardware while the attacker can buy special-purpose dedicated hardware. In a cryptocurrency, miners compete against each other and they all buy the same GPU or ASIC anyway, so the 10x GPU speed-up in Litecoin is not a problem for Litecoin; it would be a problem, on the other hand, for an authentication server, where the defender must work with whatever PC he can get from his hosting provider.)

Such things prompted cryptographers to look for better password-hashing functions, and they did so with the usual arrangement: an open competition(*). This resulted in the Password Hashing Competition. The process took a few years and resulted in the choice of a "winner" called Argon2 (along with four other schemes with "special recognition").

The current situation is not ideal in that we now have the choice between:

the old bcrypt, that is reasonably good except against the very serious attackers who think big and use FPGA;
the newer scrypt, which is better than bcrypt in some contexts, but worse in others, and has some extra drawbacks;
the brand-new Argon2, who sustained some rather heavy scrutiny, but only for a limited amount of time, and thus cannot be universally recommended yet.

The bright side here is that the PHC appears to motivate extra research on Argon2, and that is good.

(*) For cryptographers, the most perfect academic process for research is the Thunderdome.


How do you create a large PRP from a small one?

The cascade construction extends a PRF (in particular, a PRP) with fixed input length to a PRF with an arbitrarily large input length.  If you want a PRP with large input length, you can use the Luby-Rackoff/Feistel transformation on the large-input PRF obtained from the cascade.

The cascade construction is analogous to the Merkle-Damgard paradigm for extending a fixed-input-length compression function to a hash function with arbitrary input length, except that cascade uses a secret-key primitive (the given PRP) in place of the compression function.  The secret keys for the small- and large-input PRFs are exactly the same size, and the number of invocations of the small-input PRF is the ratio of the input lengths (large divided by small).  Both of these efficiency measures are about the best one could hope for.

Let $F \colon \{0,1\}^k \times \{0,1\}^\ell \to \{0,1\}^k$ be the given PRF, where the first input denotes the "key," and denote $F_y(\cdot) = F(y,\cdot)$.  Note that the PRF output and key lengths must be equal.  If $F$ is a PRP, then $\ell=k$.

For a secret key $y \in \{0,1\}^k$ and an input $x = x_1 x_2 \cdots x_n$ where each $x_i$ is a block of length $k$ (the input length of the original PRF $F$), we compute the cascade iteratively as: $y_0 = y$, and $y_i = F_{y_{i-1}}(x_i)$ for $i=1,\ldots,n$; the final output is $y_n$. In words, the output on block $x_i$ becomes the key for the next invocation, on $x_{i+1}$.

Bellare, Canetti, and Krawczyk analyzed the cascade construction in
http://cseweb.ucsd.edu/~mihir/papers/cascade.html .  They proved that as long as the large inputs $x$ are encoded in a prefix-free manner (in particular, if all inputs have the same length), then the cascade construction yields a secure PRF.  Concrete bounds may be found in the paper.


How does the polynomial modulus work in the Fan-Vercauteren scheme?

You have to pay attention to the fact that two moduli are used: a polynomial modulus $x^n + 1$ and an integer modulus $t$ (in that example, $n = 16$ and $t = 24$).

In practice, it means that not only the degree is limited but also the coefficients: they always lie in $\mathbb{Z}_t$, which is traditionally represented as the set $[0, t-1] \cap \mathbb{Z}$, but in lattice-related texts, it is usually represented as $[-t/2, t/2)  \cap \mathbb{Z}$.

So, for the first point, it is easy if you think that for any polynomial $p(x)$, reducing it modulo itself results in a zero, i.e., $p(x) \equiv 0 \pmod{ p(x)}$, because the division $p(x) / p(x)$ is $1$ with remainder $0$. Hence, taking $p(x) = x^n+1$ gives us

$$x^n+1 = 0 \pmod{x^n+1} \Rightarrow x^n = -1  \pmod{x^n+1}.$$

Now, if you use the properties of modular multiplication, you will see that when you reduce a polynomial modulo $x^n +1$, you will actually replace the powers $x^n$ by $-1$, $x^{n+1}$ by $-x$, $x^{n+2}$ by $-x^2$, etc.

Thus, for instance, $2x^{14} \cdot x^4 = 2x^{18} = 2x^2 \cdot x^{16}$. But since $x^{16} = -1$ because of the modular reduction, we have

$$2x^{14} \cdot x^4 = -2x^2 \pmod{x^{16}+1}.$$

Until this point, only the polynomial reduction was done, but we also need to compute each coefficient modulo $t = 24$. Since $-2 = 22 \mod 24$ we get

$$2x^{14} \cdot x^4 = 22x^2 \pmod{x^{16}+1, t}.$$

Notice that if we use the representation of $\mathbb{Z}_t$ that includes negative numbers, then $-2$ equals itself modulo $t$ and the result is still $-2x^2$, as it is said in the last parenthesis of your question.


New quantum attack on lattices (or Shor strikes again)?

As mentioned in the comments, there is a serious flaw in the paper, and it has been withdrawn: see https://groups.google.com/forum/#!msg/cryptanalytic-algorithms/WNMuTfJuSRc/OtQMLRXgBwAJ and part (3) of http://www.scottaaronson.com/blog/?p=2996


Proxy Re-Encryption with provable re-encryption target

PRE schemes guarantee Q1, if they are even remotely worthwhile.
Alice could add a signature over her public signing key and the ciphertext to accomplish Q3.
I haven't seen any works that guarantee a re-encryption key from B to C is valid.


Are block ciphers more prone to implementation flaws?

A block cipher is a very versatile building blocks for implementing various cryptographic algorithms, such as hash functions, message authentication codes, and yes, also stream ciphers.  You almost never use a block cipher on its own, but as part of some higher level construction.  In a way, a block cipher is a bit like the engine in a car — it needs the rest of the car (or truck or boat or airplane) around it to actually do anything useful.

A stream cipher, on the other hand, does just one thing: it encrypts a stream of data.  (Some modern ones may also authenticate the data being encrypted, to protect it from tampering.)  While you can build a stream cipher by using a block cipher in an appropriate way, a purpose-built stream cipher has "no user-serviceable parts inside" — it's a bit as if a car had the engine and the frame permanently fused together, so that you couldn't separate them without tearing the whole car to pieces.

Now, the article does have a point is saying that the main source of vulnerabilities in block cipher based encryption schemes is not the block cipher itself, but the way it is used.  To stretch the car analogy even further, cars don't usually fail because the engine blows up — more likely they fail because there's something wrong with the drivetrain or the steering or the electrics or the suspension, or because the driver was distracted and ran into an obstacle.

Also, because there are so many different ways to use a block cipher for different purposes, it's arguably easy for a non-cryptographer to select the wrong way of using it.  In particular, to anyone who knows a bit of cryptography, saying that something is "encrypted using AES" is an immediate red flag, because it doesn't say anything about how AES is being used.

For all we know, you could be using AES-ECB (bad idea) or AES-CTR with a fixed nonce (really bad idea) or AES-CBC with a predictable IV (bad idea if the attacker can submit chosen plaintexts to be encrypted) or with padding oracle vulnerabilities (hard to avoid with CBC, and a bad idea unless you use a message authentication layer on top).  Or you could be using AES-SIV (an excellent choice for a maximally foolproof design) or AES-GCM (a pretty good choice for raw speed, and secure as long as your nonces are unique) or even AES-GCM-SIV (a fairly new mode that combines the speed of GCM with the foolproofness of SIV).

Besides, the fact that you're using AES really isn't that relevant for cryptographic security — block ciphers are, by design, interchangeable, and any other unbroken block cipher with comparable block and key sizes is basically a valid drop-in replacement for AES.  What really matters is whether you're using the block cipher in a manner that's appropriate for the purpose (e.g. any IND-CCA2 secure authenticated encryption mode for ordinary message encryption, an appropriate disk encryption mode for mutable random access data, etc.)

All that said, simply using a stream cipher doesn't magically make your code secure, either.  Sure, with fewer choices, there are fewer ways to make wrong choices — but "fewer" doesn't mean "none at all", and worse, one of the possible wrong choices you can make with stream ciphers is choosing the wrong stream cipher in the first place, or not realizing that you may need something more than just the stream cipher.

In particular, most traditional stream ciphers (including e.g. DJB's Salsa20 and ChaCha ciphers, if used without a MAC) are vulnerable by design to exactly the same bit-flipping and nonce reuse attacks as block ciphers in CTR or OFB mode are.  To protect against those attacks, you need an authentication layer on top of the cipher, and a secure way of generating unique nonce values.

So I would say that the conclusion ("block ciphers are now discouraged") is wrong.  Block ciphers are here to stay, and there's no way that stream ciphers could ever displace them, because there are lots of things block ciphers can be used for that stream ciphers cannot.

What is (or at least should be) discouraged, however, is handing out isolated low-level components like AES or Salsa20 to developers, and expecting them to build a secure cryptosystem on top of them.  What you should do instead, as far as possible, is use a standardized authenticated encryption scheme that already contains all the necessary components, and specifies how they should fit together, and which has been published and independently reviewed by multiple crypto experts.  Preferably you should also be using a pre-existing implementation of the complete system that has been written by a competent cryptographer and published and reviewed for possible implementation flaws and side channel leaks.

Whether the chosen system is based on just a block cipher (like AES-SIV) or on a block cipher and a separate MAC (like AES-GCM or Poly1305-AES) or on a stream cipher and a MAC (like Salsa20-Poly1305) is, at that point, of much lesser importance.  In fact, I would argue that it is completely irrelevant, except insofar as it affects the speed, resource use and external security constraints (e.g. whether the system needs a secure source of randomness, and whether it is safe to use on hardware that might be tampered with by an attacker) of the chosen system.

Ps. As for the recent popularization of stream cipher based encryption schemes, I would argue that it's as much a fashion swing as anything else.

At the moment, after a relatively long period where most crypto research focused on block ciphers, we just happen to have a bunch of novel stream cipher designs that are new and sexy (there haven't really been any prominent new block ciphers since AES established its position).  Several of these ciphers, like Salsa20 and ChaCha, have been designed and promoted by a well known and trusted crypto researcher (D.J. Bernstein) who also happens to be the author of a popular crypto library (NaCl) and notably skilled at writing fast and secure low level crypto code, which also just happens to mean that they come with standard implementations that run blazingly fast on popular CPUs (which is attractive to companies like Google that transmit a lot of encrypted data over HTTPS).

This also coincided with the discovery of generic attacks against several widely used block cipher based cipher suites in the SSL/TLS protocol, which made it important to find new alternatives for them.  As such, it's hardly a surprise that stream cipher based encryption schemes just happen to be in vogue right now.


Fully homomorphic encryption arbitrary functions formulation

Suppose we want to compare two integers X and Y binary represented as X=x_0,x_1,...,x_n and Y=y_0,y_1,...,y_n. Comparing X and  Y translates to bit comparison, from the msb to lsb; therefore a toy example is to consider two bit comparison, x and y. The binary expressions(computation is done in Z_2) corresponding to three of their possible relations are the following:

x > y <=> x*y + 1 = 1
x = y <=> x + y + 1 = 1
x <= y <=> x*y + x + 1 = 1

This means that if we have the FH encryptions of x and y, namely C_x and C_y, we can evaluate C = C_x*C_y+C_x . Upon decryption of C, one can know if x>y (i.e. Dec(C)=1) or x<=y (i.e. Dec(C)=0).

Then you simply extend the above solution for n bits, namely you express conditions like ANDs as multiplications and conditions like ORs as additions.

For two bit integers, X=x_0,x_1 and Y=y_0,y_1, for comparison X > Y to be true, we have the following possibilities:
    x_0 > y_0 or
    x_0 = y_0 and x_1 > y_1.

Using comparison functions defined above for a single bit we have ( keep in mind that we treat OR as addition and AND as multiplication):

greaterThan(x,y) = ( x_0 > y_0) OR ( (x_0 = y_0) AND (x_1 > y_1) )
             = ( x_0*y_0 + x_0) + [ (x_0*y_0 + x_0 + 1) * (x_1*y_1 + 1)]

And that's all, you have a function ( greater than) expressed as a multivariate polynomial which you can write in terms of simple operations ( additions and multiplications). Now the best part is that for these simple operations we know they are homomorphic (namely DEC( ENC(x) + ENC(y) ) = x+y and likewise for multiplication) with respect to some underlying homomorphic encryption scheme (like BGV https://eprint.iacr.org/2011/277.pdf or ATV-FHE https://eprint.iacr.org/2013/094.pdf).

*-denotes bitwise multiplication

Please improve this answer by editing the mathematical notations.


In Diffie-Hellman, are $g$ and $p$ universal constants or are they chosen by one party according to a set of rules?

$g$ and $p$ can be viewed as universal constants. These values are public values so the security isn't affected if an attacker knows $p$ and $g$. They also have to be the same values on both sides for a key-exchange to work.

As explained in Wikipedia (section Security):

  [$\ldots$] For this reason, a Sophie Germain prime $q$ is sometimes used to calculate $p = 2q + 1$, called a safe prime, since the order of $G$ is then only divisible by $2$ and $q$. $g$ is then sometimes chosen to generate the order $q$ subgroup of $G$, rather than $G$, so that the Legendre symbol of $g^a$ never reveals the low order bit of $a$. A protocol using such a choice is for example IKEv2.

So these are infact default values, for example the Java documentation (might be outdated for 2019) lists the following values for 512-bit keys:

p = fca682ce 8e12caba 26efccf7 110e526d b078b05e decbcd1e b4a208f3
    ae1617ae 01f35b91 a47e6df6 3413c5e1 2ed0899b cd132acd 50d99151
    bdc43ee7 37592e17
g = 678471b2 7a9cf44e e91a49c5 147db1a9 aaf244f0 5a434d64 86931d2d
    14271b9e 35030b71 fd73da17 9069b32e 2935630e 1c206235 4d0da20a
    6c416e50 be794ca4

Normally such default values are used, but it is also possible to choose new $p$ and $g$ values if you want to.


A security definition is stronger if we make it easier for the attacker to win. The point being that the stronger definition rules out even this easier way of winning

In the specific case noted in the question, you are indeed correct.
The scenario you describe is the following:

An attacker queries "Cat" and receives the tag "90". It then computes the tag "138" such that $\mathsf{Vrfy}_k(\text{Cat},138)=1$ and outputs the pair $(\text{Cat},138)$.

The regular $\mathsf{MAC\text{-}forge}$ experiment will reject this output. I.e., the attacker does not win, and therefore this security definition does not rule out the existence of said attacker.

The stronger $\mathsf{MAC\text{-}sforge}$ experiment will accept this output. I.e., the attacker wins, and therefore this security definition rules out the existence of said attacker.


What are the requirements from a Round function in Feistel network?

What does it take from the round F function to make a secure block cipher?

The ability of providing resistance to most common attacks like differential, linear, algebraic, slide and others mainly depend on the features of S-box (if used). * Simon does not use an S-box.
To design F-function, it depends on the structure of your Feistel
cipher Type I, II, III and others (which differ in term of number of
branches, number of F-function, internal structure of F-function).
The size of plaintext (64,128) could also influence the size of box
(4-bit or 8-bit), like piccolo vs Clefia. Therefore, the differential probability, linear probability and algebraic immunity differ, 8-bit S-box provide higher immunity features, therefore lower number of active S-boxes needed to provide minimum immunity, hence lower number of rounds.
The internal structure of F-functions such as SP vs SPS influences
diffusion (in term of number active-box). In addition, the use of
different MDS matrices in r-rounds (multiple round diffusion or
diffusion switching mechanism (DSM)) provide higher diffusion compared
to using 1 MDS matrix. CLEFIA employs DSM.
On the other hand, 8-bit s-boxes such as those in AES are expensive in term of
masking against side channel attacks. One way is to use smaller
s-boxes (easy to mask) to build larger s-boxes or using 4 bit S-box.

Does a high round count compensate for any mild weaknesses in the F function?

I don't think if you have self-similarity F-function, it will be
vulnerable to slide attack, increasing the number of rounds will not
providing compensate for weakness. To solve the self-similarity of F-rounds it is recommended to add constants. For how to chose round constants for simple key scheduling, I recommend to read

  Proving Resistance against Invariant Attacks: How to Choose the Round Constants

There are others structures of internal F-function (not only SP, SPS) such as ARX (e.g. the Simon cipher) that have been design in a triangle of security, performance and size, and resistance to both mathematical and implementation attacks (such as timing, DPA).


How to prove the pseudorandomness of CryptoPAn

Since you're still learning, I would give you an answer; however consider the encryption of the IP addresses 10.0.0.1 and 10.0.0.2; how would those two ciphertexts be related?  How could you use that as a distinguisher from a random permutation?


Can all affine cyphers be expressed with this formula

$a\cdot x +b $ means affine  not permutation. And $a\cdot x +b \bmod 26$ is modular affine transformation.
$a\cdot x +b \bmod 26$ can have at most $26\cdot 26$  affine transformations some of which have no inverse and therefore without an inverse an affine transformation is not suitable for encryption where it is already not close to the modern encryption methods.
To have an inverse one must have $\gcd(a,26)=1$. This means $a$ cannot be divisible by 2 or 13. To find the actual number we can use Euler's Totient Function that counts the positive integers up to a given integer $n$ that are relatively prime to $n$. Then $$\phi(26) = (13-1)\cdot (2-1) = 13$$ So there are actually $26\cdot 12 =312$ possible affine transformations.
In any case, we have $26! = 403291461126605635584000000$ permutations and $312$ affine transformations, therefore the affine transformation cannot cover all possible permutations. The reverse is correct; the permutations can represent the invertible affine transformations.


I am not aware of any existing scheme allowing this easily (excepted for PureEdDSA maybe, but I wouldn't classify it as an ECDSA variant).

However I do not believe this is impossible. So let's try to do this for ECDSA:

We have a message $m$ whose hashed value $H(m)$ is converted into an integer $z$ which gets signed into the signature $(r,s)$ by the signer.

Now the verifier will basically rely on
$$\begin{aligned}
C&=u_1\times G+u_2\times Q\\
&=u_1 \times G +u_2d \times G\\
&=(u_1+u_2 d)\times G \\
&=(zs^{-1}+rds^{-1})\times G \\
&=(z+rds)\color{red}{s^{-1}}\times G \\
&=(z+rd)\color{red}{(z+rd)^{-1}(k^{-1})^{-1}}\times G \\
&=k\times G
\end{aligned}$$
And will say that it verifies iff $C_x==r$
And as you can see, if you can change $r,s,z$ then you can force a coefficient in the latest line to cancel "almost out", by taking $bs,abr,abz$ instead and would end up with $$(abz+abrd)\color{red}{b^{-1}(z+rd)^{-1}(k^{-1})^{-1}}\times G \\
= ak\times G $$

Now the difficult part is to find out if it is possible to get $a,b,m'$ such that $H(m')$, once converted into $z'$ is such that $z'=abz$ and such that $(ak\times G)_x \equiv abr\mod n$...

I do not see why this couldn't be possible, being given so much slack on the variables... But since I don't have time right now to actually try it out, I'll try to do it later or another day and will edit this answer accordingly.


Socialist Millionaires variant, where only one party learns $x=y$?

A protocol consists of parties taking turns sending messages. Therefore one party will naturally learn the output before the other (only very few exceptions exist to this rule). This means that in almost every protocol you find (especially in the semi-honest setting) you will see that either (1) the last protocol message literally is nothing more than the party-who-learned-output revealing the output to its counterpart (so you can exclude this message) or (2) the protocol is already described so that only one party gets output. In things like Wikipedia articles, it is often just simpler to describe MPC protocols as "both parties get the output", but under the hood there is generally one-sided output.

(In the Wikipedia article you reference, the protocol is written in a way that obscures the interaction pattern. The last communication between parties is in step 7 "$\langle Q_a Q_b^{-1} | \alpha,\beta\rangle$". But this step is an abstraction of Diffie-Hellman which consists of a message from each party. Just have one party omit this message and he/she will be the only one capable of learning the output.)

Protocols for private set intersection (PSI -- the generalization of socialist millionaires) are no exception. In our paper:

  Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, Ni Trieu: Efficient Batched Oblivious PRF with Applications to Private Set Intersection.
  CCS 2016.

(and every other PSI paper I know of) we describe the protocol so that only one party gets output.

The building block of this protocol is something called a "private membership test" where a sender has a set $S$ of items, a receiver has an item $v$, and only the receiver learns whether $v \in S$. This sounds like exactly what you're looking for.

This private membership test building block goes back to this work (and perhaps earlier):

  Benny Pinkas, Thomas Schneider, Michael Zohner: Faster Private Set Intersection based on OT Extension. Usenix 2014.

Both of these papers are optimized to provide many instances of the private membership test building block primitive, since that is what is required for PSI. If you truly want just a single instance of private membership test, then there is probably nothing simpler than the classic Diffie-Hellman based PSI (homomorphic encryption is overkill if you just need semi-honest security). I describe it below, specialized to the case where Alice has just one item.

Alice (who has a single item $v$) picks random exponent $\alpha$ and sends $H(v)^\alpha$. Here $H$ is a random oracle.
Bob (who has a set of items $S$) picks random exponent $\beta$ and sends $(H(v)^\alpha)^\beta$ as well as $H(s)^\beta$ for every $s \in S$.
Alice can compute $(H(s)^\beta)^\alpha$ and check whether any of these values are equal to $(H(v)^\alpha)^\beta$. This will happen if and only if $v \in S$ (barring a negligibly unlikely collision in $H$).


How would the opponent defraud this secure communication?

For an attacker to be able to actually successfully break the security of the bank, we need to make a few assumptions, which I'll state here:

A stream cipher without proper authentication is used.
The attacker knows the data format the bank uses.
The attacker knows the recipient and amount of a transaction (i.e. the interesting values), which he may change.

First we need to consider how a stream cipher works. Most stream ciphers work by taking a key and an initialization vector and expanding this to a long keystream. The keystream $K$ is used to encrypt a message $M$ to the ciphertext $C$ as follows: $C=K\oplus M$ where $\oplus$ denotes bitwise XOR.

Now assume that the message being actually sent by the bank is $M$ containing a valid recipient and a valid transaction amount. Now further assume the attacker wants to replace this by $M'$ where he increases the amount and makes himself the recipient. One nice thing about bitwise XOR is that $a\oplus a = 0$ holds. Now the attacker can calculate the difference $\Delta=M\oplus M'$. He now replaces $C$ by $C'=C\oplus \Delta$. Now observe that $$C'=C\oplus\Delta=(K\oplus M)\oplus (M\oplus M')=K\oplus M'$$ which will decrypt to $M'$ by XOR'ing $K$ in again.

As requested by Maarten in the comments:

The (actual) Example

Assume that 0001001001100101100000001011010010 is the (legitimate) recipient ID.
Assume that 0000010111011100 is the legitimate transaction amount in USD.
Assume that 1001001100100100011110000010001010 is the attacker's ID.
Assume that 1100001101010000 is the attacker's preferred enrichment.
Assume that the message encoding consists of simple concatenation of the recipient ID and amount.
Assume that  01011000011010011001110010010110101100010100011100 is the keystream.
The message $M$ is then 00010010011001011000000010110100100000010111011100 and the (legitimate) ciphertext $C$ is 01001010000011000001110000100010001100000011000000.
The malicious message $M'$ would be
10010011001001000111100000100010101100001101010000 and therefore the
difference $\Delta$ would be
10000001010000011111100010010110001100011010001100
Thereby $C'$ is
11001011010011011110010010110100000000011001001100 which will be decoded to 10010011001001000111100000100010101100001101010000 which is $M'$ and thereby the attacker will receive 50k USD.


Attack vector difference when not allowing repetitions in BIP-39

There is no impact on security.

The seed combinations can have more entropy than the 128-bit key you feed into it. Assuming the function you use to convert the 128-bit key into the 12-word seed is injective, then you won't even be able to reach all possible seeds with the keyspace you have, since $2048^{12} \gg 2^{128}$.

The entropy in 12 random words picked from a set of 2048 is $\log_2(2048^{12}) = 132$ bits. If you only allow unique words, it is $\log_2(\frac{2048!}{(2048-12)!}) \approx 131.95$ bits. These are greater than 128.


PIN-based authentication with Diffie-Hellman modular arithmetic

I think somehow since $pin \in [0,9999]$ we should be able to brute force the value but I am unable to come up with the math to do so.

Unless the random number generator is broken, there is no way to recover pin; this would remain true even if we were able to compute discrete logs mod $P$ (which we can't).
The issue is that the public key is generated as:
$$server\_pub = 2^{R + N \cdot pin} \bmod P$$
(where $R$ is largerandom, and N is the publicly known intvalueof("server") value)
Even if we were able to compute the discrete log, that would give us $R + N \cdot pin \bmod (P-1)/2$ [1]; however for any potential value of $pin$, there is a value of $R$ that gives us the value consistent with the observed server_pub; because $R$ is assumed to be (almost) uniformly distributed over $[0, (P-1)/2)$ [2], that observed public value gives us no information about the value of pin.
Our inability to compute discrete logs does not change the above reasoning.

[1]: why $\bmod (P-1)/2$?  That's the size of the group that $2$ generates modulo this prime
[2]: in your code, $R$ is generated uniformly randomly in the code over $[1, P-1]$; that does mean that the possible value $R \equiv 0 \bmod (P-1)/2$ is less than any other value of $R$.  This would, at extremely rare occasions, allow us to deduce that a specific pin value is somewhat less likely to be the correct value - however, this is so rare (probability of us being able to deduce that is approximately $1000/ P \approx 3 \cdot 10^{-613}$) that we can ignore that.


Is it possible to determine the group order by knowing the "public" and "private" key exponents in an RSA group?

The relationship between recovering the decryption exponent $d$ and factoring the RSA modulus $n=pq$ is a classical question in cryptography. There are three useful answers:

The first answer deals with a slightly different question but is useful to gain some insight into the problem. Assume that we given a bit more than $e$ and $d$, more precisely that someone gives up $\phi(n)$ [This is more because $e$ and $d$ only gives us a multiple of $\phi(n)$]. Then, we can compute $s=n+1-\phi(n)=p+q$. As a consequence, we know both the sum ($s$) and the product ($n$) of $p$ and $q$. Thus, $p$ and $q$ are the roots of $X^2-sX+n$.
EDIT I forgot to mention that if you are using safe primes and small public exponent such as $65537$, then by removing small factors of $ed-1$, you obtain $p'q'$. Since $\phi(n)=4p'q'$, you can thus use this direct method.
EDIT 2 For more details about this method, see the related question: Why is it important that phi(n) is kept a secret, in RSA?
The second answer is the classical one, it shows a probabilistic algorithm that factors $n$ given an arbitrary multiple of $\phi(n)$, such as $ed-1$. See http://www.cs.purdue.edu/homes/ninghui/courses/Fall04/lectures/lect14-c.pdf for detailed examples. The basic idea is to rewrite $ed-1$ as $2^t O$, where $O$ is odd. Then take a random element $w$ modulo $n$. We know that $w^\phi{n}\equiv 1 \pmod{n}$, thus $(w^{O})^{2^t}\equiv 1 \pmod{n}$. Compute $w^O$, then (unless it is equal to $1$) square it repeateadly until you reach $1$. If the number $\ell$ that appears before $1$ is not $n-1$, you obtain a non trivial factor of $n$ as $gcd(n,\ell-1)$. If it does not work, try again with a different $w$.
EDIT 3: Additional information about this reduction. In fact, this attack is stronger than that: it still work if we are given a multiple $M$ of $lcm(p-1,q-1)$. Moreover, it even works when $M$ is a multiple of either $(p-1)$ or $(q-1)$.
The most recent answer is that the reduction can be made deterministic using Coppersmith's smooth root algorithm. This was showed by Jean-Sébastien Coron and Alexander May in http://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/paper/springer_joc.pdf (see also http://www.iacr.org/archive/crypto2004/31520213/det.pdf). This solution puts a few additional restriction on $p$, $q$, $e$ and $d$. Namely, $p$ and $q$ must have the same bitsizes and $ed$ should be smaller than $n^2$. This last condition is true when $e$ and $d$ are reduced modulo $\phi{n}$ but may become false for a variant of RSA that would use values of $e$ and/or $d$ not fully reduced.


Calculation of time to crack a SHA-256 hash

The "million usernames" is a red herring, because the user name is used as "salt": the hash value is computed over the password and the user name. When the attacker tries a potential password, he must choose which user name he puts in the hash function; and if a match is found, then this will be for the hash value for this user name only.

In other words, the attacker cannot do any better than choosing one hashed password to crack, for a specific user name, and crack that. That there are one million of hash values does not give any advantage to the attacker.

Now, consider that the attacker tries to crack one password; he has the hash value and the user name. There are $10^9$ possible passwords. If we assume that the passwords have been chosen randomly and uniformly, then the best that the attacker can do is to try them all (in any order) and hope for a match. On average, the attacker will need to try about half the key space, i.e. 500 millions, of possible passwords until a match is found. Since the attacker's hardware can compute 500 millions of hash values per second, the average time to crack one password is one second.

Similarly, if the attacker wants to crack, say, 10 passwords for 10 distinct users, then it will take him 10 seconds on average.

User names, as salt values, are suboptimal. In the context of this question, user names work well: their role is to prevent parallel attacks, and since no two users have the same name, then parallel attacks are indeed prevented. To break $n$ passwords the attacker must pay $n$ times the cost of breaking one password.

However, in practice, user names are reused, in two ways (at least):

When a user changes his passwords, his name remains the same, so the old and the new passwords will be hashed with the same "salt". Attacking both simultaneously will be possible.
User names are unique on a given system. But software is reused. To put things bluntly, all systems will have an "admin" user with that name; this opens the road to parallel attacks, e.g. precomputation: the attacker could precompute hash values for a given user name (such as "admin") and the billion of possible passwords; thus, when the attacker actually gains access to the database, breaking the "admin" password will be a matter of a single lookup, which will take a microsecond or so (assuming the table is in RAM), not one second. Attackers could even collude and exchange tables, so that one attacker computes the table and his dozens of friends benefit from that one-time effort.

Thus, random strings are considered to be better salts, because they will ensure worldwide uniqueness with high probability, much better than user names (assuming that the random salts are large enough; UUID are good practical salts).

On the concept of password hashing, see this answer for a lengthy introduction.


Mitigating timing attacks with a random sleep

Adding random sleep may make it slightly harder, but not more than that. The problem with adding random noise is that the average time will still be different between the two measurements you are trying to make. So, you will need more measurements, but eventually will get the right thing, since the averages will stand out. This is how timing attacks can be done over the Internet (see Remote Timing Attacks are Practical), even though there is timing noise in networks.


Finding the period of a function with a single output qubit - impact on RSA

My questions are, how reasonable are these claims?

Sounds fairly reasonable; they suggest an alternative factoring algorithm where they trade-off circuit depth to reduce the number of qubits required.
Would this trade-off be a good thing in practice?  We don't know.  We don't have a large scale quantum computer in front of us, and so we don't know the relative cost of different things, such as how expensive qubits are compared to a longer time to complete the computation (and if your logical qubits aren't perfect, a longer computation implies a larger probability of an intermediate error somewhere).
On the other hand:

What is the impact on post-quantum RSA security? Post-quantum RSA security is considered by some people as not that worrisome since it requires a non-negligible number of qubits to be practically broken.

Even if the number of qubits were the major cost factor in quantum algorithms, this algorithm doesn't reduce them all that much overall.  After all, I don't believe we have that good of a view about the size of a quantum computer an adversary might have when they get one; if they did have a 2k logical qubit computer (and so could use this algorithm to factor a 2048 bit number), they could plausibly have a 4k qubit (and so could use standard Shor's).  Our ignorance of the size of a quantum computer someone might have is far greater than just a factor of 2.


Where do the constants for SHA-1/2/3 come from?

Regarding the IVs and round constants of hash functions...

The question for SHA1 and SHA2 families have already been answered. Rotational constants were chosen by the designers to make the hash functions secure (or in the case of SHA1, not secure enough). Derivative hash functions such as SHA-224 and SHA-384 use different initial values which are simply the next primes on the list (9 through 16th). SHA-512/t uses different initial values based on the output of a slightly modified version of SHA-512 processing a short string.

SHA3 is a completely different construction. It has no initial values, the working state is simply all 0 bits. The round constants of SHA3 and Keccak are based on a linear feedback shift register, this takes up much less space in code vs hard coded numbers like those in SHA-2, and very cheap to implement in hardware. The rotational offsets for SHA3 and Keccak are a reordered set of triangular numbers modulo the lane size, which for SHA3 is 64-bits. This is also very cheap in both software and hardware, as it is simply a reordering of bits within the state.


Decryption possible only within a period of time

This is possible, but only if you introduce one or more parties in addition to the sender and receiver. Also, the receiver must be online when decrypting.

Typically, the security requirements would be that (a) if the recipient tries to decrypt inside the time window, he should be able to decrypt, even if the sender is not cooperating; (b) if the recipient did not decrypt the message inside the time window, he should not be able to learn anything about the contents of the ciphertext; and (c) any additional parties should not learn anything about the ciphertext.

From such requirements, it should be fairly straight-forward to come up with reasonable schemes. Some variant of threshold decryption should do the trick.


Is it feasible to build an index of prime factors?

Let's assume for an instant that you could build a large table of all primes. Then... what ? How would you use it ? What would you look up ?

If you "just" scan the table and try to divide the number to factor by each prime, then this is known as trial division; there is no need to store the primes (they can be regenerated on-the-fly; that's the division which is expensive). Yet this is an highly inefficient factorization algorithm. We know much better factorization algorithms (which nonetheless utterly fail at making the slightest scratch on the surface of a 2048-bit RSA modulus).

Of course, the list of 1024-bit primes is so large that storing it, or even simply generating each prime, is ludicrously infeasible. There are about $2^{1014}$ such primes; that's close to  $10^{308}$. Suppose you are an omnipotent but severely bored deity, and you decide to store these primes, using a storage device which uses the size of an hydrogen atom for each prime (we, as humans, can certainly not store that much information in so small a space, but hey, that's a piece of cake for an omnipotent God). The known universe has an approximate volume of $10^{79}$ m3. The volume of an hydrogen atom is close to $10^{-30}$ m3. So our eccentric divinity can pack about $10^{109}$ values in the whole Universe. He would still need $10^{199}$ complete Universes to store them all. $10^{199}$ is a mind-boggling number (if your mind is not boggled by it, then it must already be much more boggled by something else). It is ten billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions of billions. In other words, a lot. And we are still talking about complete Universes packed with atom-sized integers.


What is the difference between Argon2d and Argon2i?

As @sejpm already hinted in his comment: both scale the same when it comes to the parameters.

You might still want to read the RFC to get the complete picture, but the general differences can be quickly summarized:

Argon2i

Argon2i is invulnerable to side-channel timing attacks, but is weaker against time-memory trade-off (TMTO) attacks.

Argon2i uses data-independent memory access, which is preferred for things like password hashing and password-based key derivation.

Argon2d

Argon2d is vulnerable to side-channel timing attacks, but offers the best resistance to TMTO attacks.

Argon2d uses data-depending memory access, which makes it more suitable for things like cryptocurrencies and proof-of-work (POW) applications with no threats from side-channel timing attacks.


How to make PKCS conformation oracle for trying Bleichenbacher’s RSA attack?

I unfortunately don't have enough reputation to comment, forgive the answer that is a link to another answer. Your question is explained well in this answer:

https://crypto.stackexchange.com/a/12706/17884


ElGamal in $\mathbb Z^*_p$ with $g$ not a generator of $\mathbb Z^*_p$

Because in the exercise $g$ is is not a generator of $\mathbb Z^*_p$, the exercise would indeed be incorrect in a context explicitly giving a definition of ElGamal encryption that both

requires $g$ to be a generator of the group the message belongs to,
and chooses the message in $\mathbb Z^*_p$, here as an integer in range $[1,22]$.

Otherwise, the exercise and it's (now reformatted) correction are OK.

A common definition of ElGamal encryption (note: $h$ is used where the question uses $y$) has the message (representative) $m'$ in a finite cyclic group $G$ with generator $g$. In the question's examples, the message would be restricted to $G=\{1,2,3,4,6,8,9,12,13,16,18\}$. That makes the exercise fine.
Note: We do not need to rewrite that set as $\mathbb Z^*_{11}$, and cannot do this while keeping the same multiplication law as in $\mathbb Z^*_{23}$.

Another possible definition of ElGamal encryption makes no such restriction on $m'$, allows it to take any value in any finite commutative group (including $\mathbb Z^*_p$, possibly without restriction to prime $p$), and picks an element $g$ in that group that needs not be a generator of the full group (but needs to generate a large cyclic subgroup in which the discrete logarithm is hard, and other properties often associated). That still allows decryption of any message in the base group. In that definition, the question's message could be any integer in range $[1,22]$. That also makes the exercise consistent.

However, in that second definition, security suffers somewhat. When as in the question the base group is $\mathbb Z^*_p$ with $p$ prime, and $g$ generates a subgroup $G$ of prime order $(p-1)/2$, it is possible to test if the message $m'$ belongs to the subgroup $G$ generated by $g$. That's because ElGamal's ciphertext includes $c_2=m'\cdot g^z\bmod p$ for some integer $z$, therefore $m'$ belongs to $G$ if and only if $c_2$ does, and we can test that by checking if $c_2^{(p-1)/2}\bmod p\,=1$. That's a one-bit information leak about a message $m'$ picked randomly in $[1,22]$. Such information leak is against modern definitions of a cipher's security. We can:

Ignore that issue. That's reasonable in the example, since it has a much worse security issue: $p$ is small enough that finding the private key $x$ from public key $g^x\bmod p$ is easy, thus deciphering is easy. $p$ would need hundreds of decimal digits for true security.
Restrict to messages $m'$ that belong to $G$. When the order of $|G|$ is prime $(p-1)/2$ as in the example, that's easy. We can test if $m'$ belongs to $G$ by checking if $m'^{(p-1)/2}\bmod p\,=1$, and if it does not use $\tilde m'=p-m'$ (which does) instead of $m'$. We can get back to $m'$ after decryption (e.g. by requiring $m'<p/2$ which allows recognition of if decryption yielded $m'$ or $\tilde m'$).
Have the sender make $m'$ a random element of $\mathbb Z^*_p$, then hash it (which makes the leak immaterial) to obtain the key of a symmetric cipher used to encrypt the true message. That's hybrid encryption.
Have the sender choose a random $r\in\{1,\dots,|G|\}$, then compute $m'=g^r\bmod p$, which is a random member of subgroup $G$ (but we can not chose $m'$ directly representing a long message to send, thus typically that's still used with hybrid encryption).

It is common (and desirable for security to some degree, for at least the reason above) to use $g$ such that $G$ is a group of prime order. When using $\mathbb Z^*_p$ as the base group, it is typical to use a Schnorr group, perhaps with $p$ 2048-bit and $|G|$ 256-bit, both prime.


As you suspect, it's a concatenation symbol. Some times it's $|$ and others $||$.  Or $+$. Python and PL/SQL examples to confirm. Or a cryptographic example: bottom of page 5 of FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and
Extendable-Output Functions.

If it were bitwise OR, you'd make a real mess of the public key's use with PUBKEY | CHECKSUM | VERSION.

It can get weird though if you dig deeper as: Is there a common symbol for concatenating two (finite) sequences?


Can Poly1305 be used with block ciphers running in CTR mode?

Q2: No, Poly1305 not limited to stream ciphers.  Yes, Poly1305 can be used with block ciphers running in CTR mode, if you use it appropriately.

I don't know whether the NaCl use is secure (whether NaCl uses it appropriately); I haven't tried to analyze NaCl.  Given that NaCl was built by reputable cryptographers, I would be inclined to guess that it's probably fine.  I realize this doesn't answer your full question.

Alternatively, if you were asking because you were thinking of designing your own scheme that makes use of Poly1305, my reaction is: if you're designing it, you should just use some reputable authenticated encryption scheme.  From an engineering perspective, that's probably the best solution: it minimizes the chances you foul things up somehow.  If you try to use Poly1305 in some custom way you design, the risk of introducing security problems is higher.


Which hash function is usually used in RSA?

In general there is no default hash algorithm in the PKCS#1 standards, neither for RSA with PKCS#1 v1.5 padding or RSA with PSS. Both these schemes are defined in RFC 3447 RSA PKCS#1 v2.1. Note that PKCS#1 v2.2 adds a few SHA-2 hash functions (SHA-224 and SHA-512/224 and SHA-512/256) to the mix - neither of which makes much sense.

PSS uses a Mask Generation Function MGF1 which defaults to SHA-1:

  The default mask generation function is MGF1 with SHA-1

however, that's not the hash used to hash the message itself, it's just used to pre-process the hash before modular exponentiation. The strength of the hash used for MGF1 is not that important.

Many API's that have been around for some time rely on SHA-1 as a default. MD5 and SHA-1 have been around for a long time, and most libraries seemed to have taken the more secure SHA-1 as more future proof.
You might find very old libraries that default on MD5, but I haven't come across them yet.

The low level security of SHA-1 shows one of the reasons why defaults should not be used. Once a library sets a default, it's impossible to get rid of, even if the default algorithm - SHA-1 in this case - is found to be insecure.  Explicit parameterization is much better. It may require some initial effort when coding, but that is easily recovered during the maintenance phase of software.

Usually the specific SHA-2 algorithm needs to be configured in API's if SHA-2 is to be used. That's also because there is more than one SHA-2 algorithm: there are 2, with 6 variants in total. SHA-3 has 4 variants, so I don't expect this to change in the future. Furthermore, it has two SHAKE variants, SHAKE128 and SHAKE256 that can be used for RSA-FDH.


In the question, each function $F_s$ is transforming an $l_1$-bit bitstring into an $l_2$-bit bitstring.

I read $\mathcal{F}$ being "a family of keyed functions" as meaning that we can re-express all the $F_s$ (that is $\mathcal{F}$) as a single function $F$ with an extra (say, first) argument $K$ in $\{0,1\}^k$ designated the key, and one such key $K_s$ for each $s$ in $S$, such that $\forall x\in{\{0, 1\}^{\ell_1}}, F_s(x)=F(K_s,x)$.

Alternatively, we could have $K_s=s$, and the first argument of $F$ coming from $S$ (that would be the keyspace) rather than some $\{0,1\}^k$. The context should tell.

Addition: That use of "a family of keyed functions" is at least ambiguous and uncommon as far as I can tell. The answer is trying to make sense out of it, but is far from an endorsement.


Find Points of order 2 on elliptic curve

Let $E$ an elliptic curve defined by the equation $y^2 = f(x)$ over a prime field $\mathbf F_p$ with $p>3$, with $f$ a degree $3$ polynomial.

A point $P=(x_0,y_0)$ of order $2$ is a point that satisfies $2P = \mathcal O$ where $\mathcal O$ is the neutral element of the group law also known as the infinity point. Then we have
$$
2P = \mathcal O \quad \Longleftrightarrow \quad P + P = \mathcal O \quad \Longleftrightarrow \quad P = -P,
$$
but $-P = (x_0,-y_0)$ so it means that $y_0 = - y_0$ so $y_0 = 0$. There we have it, a point of order $2$ must have its $y$-coordinate set to 0, and plugging it into the curve equation, then $x_0$ satisfies the equation
$$
f(x_0) = 0.
$$
To find all the $2$-torsion points you must find the roots of this polynomial.

Example: the curve $y^2 = x^3 + 10x + 6$ on the field $\mathbf F_{17}$ has three points of order $2$: $(1,0)$, $(2,0)$ and $(14,0)$, since we have $x^3 + 10x + 6 = (x-1)(x-2)(x+3)$.


I found the answer:
Schnorr protocol is witness-hiding - proved in GGM model in https://www.shoup.net/papers/dlbounds1.pdf (as part of proof that Schnorr identification protocol is secure).

At the same time, it's not possible to prove it in standard model based on discrete-log problem: http://www.cs.cornell.edu/~rafael/papers/schnorr.pdf


Proving collision resistance of a hash function?

Recall that randomly chosen functions, used to model good hash functions, are collision resistant if we need on the order of $2^{n/2}$ queries in order to discover a collision with success probability a constant bounded away from zero.

Proof by contrapositive:

Assume $h$ is NOT collision resistant. Then we can find such collisions much faster than specified above, i.e., we can find $x\neq x'$ $x,x' \in \{0,1\}^{2n}$ with $h(x)=h(x')$. There are two possibilites.

In the first case $g(x)=g(x')$, in which case any function $f$ would yield a collision in $h$.

If on the other hand, $g$ is collision resistant and thus $g(x)\neq g(x')$, we must now have  $f(g(x) || g(x)) = f(g(x') || g(x'))$ which implies that $f$ is not collision resistant since it is giving a collision to distinct inputs.


Is it safe to compute HMAC(Base64(IV) || "," || Base64(CipherText)) instead of HMAC(IV || CipherText)?

I want to know if the following would also be equally secure

Yes, both schemes are equally secure. Also for what you are trying to achieve you really shouldn't puzzle things together yourself but rather use pre-made modes like AES-GCM, AES-EAX or ChaCha20-Poly1305.

In fact, we can prove the above claimed security equivalence. Because Encrypt-then-MACis easily proven secure if the MAC is a vector-PRF (or vector-MACs) (i.e. a PRF that takes a triple of IV, associated data and ciphertext instead of a string as input) we're gonna prove the equivalence of these two vector PRFs and argue why the first one is a vector PRF.

$F_K(IV,\perp,C)=\operatorname{HMAC}(K;IV\|C)$ is a vector-PRF assuming HMAC itself is a normal PRF. To see this first note that IV has fixed length in all cases and thereby the concatenation is unambiguous, that is you always know what part is the IV and which part the ciphertext. Now because of this whenever the input to $F$ is different, so is the input to HMAC and because HMAC is a PRF we get a freshly chosen random string in that case which makes the behaviour indistinguishable from a vector MAC.

Next we'll prove that if $f_1$ and $f_2$ are injective and if $f_1$ has a data-independent output length (which we assumed earlier remember!), then $G_K(IV,\perp,C)=\operatorname{HMAC}(K;f_1(IV)\|f_2(C))$ is a vector PRF as well. For your case imagine $f_1$ being the base-64 encoding of IV and $f_2$ being the base-64 encoding of the ciphertext prepended by the comma literal.
So first note that because both functions are injective there's never a case when there's two distinct inputs that map to the same output. Because of this all non-repeated inputs to the underlying vector PRF are unique and therefore we always get freshly random outputs making this on a vector PRF as well.

If you might be wondering whether it's safe to assume that HMAC is even a PRF, then note that this is the basic use-case that HMAC was designed for and the entire reason it is a secure MAC.


The old hash functions you mention (MD5, SHA-1) are based on the Merkle-Damgård construction. SHA-3 uses a sponge construction instead. There are certainly more variations possible, but these are the popular ones.

There are multiple constructions possible but for most hash functions the input is indeed split in blocks. These blocks are directly put in some kind of compression / sponge function which is used to update the state of the hash function. A hash function also has an initial state provided for when zero blocks have been processed.

Generally the last block is padded and a length of the input is included to create the final state. In the case of MD5 and SHA-1 the state is directly output as the hash value, but in more modern hash constructions there may be more processing before the final output is produced. This happens for instance for SHA-3.

A hash function is required to always produce a different output for any different input. As they may process a virtually unlimited amount of input while producing a small amount of output there must of course be many messages that produce the same output; this is called the pigeon hole principle.

It is however computationally infeasible to find those input.at least when the hash function is not broken. MD5 is such a broken hash function for which this property is clearly not true anymore.

So lets visit your questions with this knowledge:

$H(b_1 || b_2) = H(H(b_1) || H(b_2))$ - clearly different inputs
$H(b_1 || b_2) = H(b_1 || H(b_2))$ - clearly different inputs
$H(b_1 || b_2) = H(H(b_1 || H(b_2)))$ - clearly different inputs
Associativity (I assume it's not the case) - clearly different inputs
Commutativity (clearly not the case) - clearly different inputs

So, no, hash functions do not possess any of these mathematical properties, which is not surprising if you consider that it should be infeasible to reverse a hash value.

It's much more interesting to have a look at how the internal compression function or sponge function behaves.


Could one construct a cipher that is secure for friendly parties to use but insecure for hostile parties?

Mathematically, it can probably be done.  There has been research into trapdoor block ciphers.  See, e.g., A family of trapdoor ciphers by Rijmen and Preneel, and follow-up papers.

In practice, though, the problem statement is not realistic.  The assumptions are just not realistic.  Today, there's no reason why Red would be limited to using Blue's ciphers.  Instead, Red could just use any well-vetted cipher, like AES.  There's no reason why Blue should assume that Red will use Blue's ciphers; that's just not how adversaries are likely to behave given the current state of the public literature.  So while your problem statement might have been relevant and interesting to ponder 40 years ago, when there was no public literature on cryptography ... today, it is irrelevant.


The ACME protocol was designed by the Internet Security Research Group, and is used by Let's Encrypt to sign domain-validation TLS certificates. Since the transport of GRPC is HTTP/2, which uses TLS for encryption and authentication (when enabled) that should be what you want.


Shor's algorithm for elliptic curve discrete logarithm problem

Could one adapt Shor's algorithm to solve the DLP?  Yes: Shor's original paper (arXiv preprint) explains how, in §6 on p. 321.

Could one adapt Shor's algorithm to solve the ECDLP?  Yes.  Researchers at Microsoft recently published estimates for how big a quantum computer you would need to do so.  (Spoiler: Smaller than RSA at comparable classical security levels.)

Could one write down how it works in a few easy-to-understand steps?  Maybe, but that's above my pay grade at the moment if you find those two papers to obscure!  You might start with Scott Aaronson's article on Shor's algorithm, see if you can find the hidden subgroup problem hidden in the algorithm, and adapt it to the hidden subgroup problem in discrete logs.


CSPRNG that cannot be used as random extractor

There is some relationship between the two notions, but a CSPRNG is designed to be computationally secure (secure against adversaries with bounded computation time), whereas a randomness extractor is required to be information-theoretically secure (unconditionally secure against adversaries with unbounded computation time).  So, they're different primitives.

I would not expect a typical CSPRNG to be a secure randomness extractor.  Typically CSPRNGs use computationally secure primitives, like AES etc.; they don't make any attempt or claims of providing security against adversaries with unlimited computing power.

Also, CSPRNGs are often designed to address other issues as well, such as recovery from state compromise (robustness against state compromise extension attacks), efficient use of the available entropy, and ability to stretch a finite amount of entropy into an unlimited stream of pseudorandom bits (e.g., using a PRG).

CSPRNGs are practical primitives, intended for applied cryptography, and were invented by applied cryptographers.  Randomness extractors have typically been studied in the theoretical literature and are rarely (if ever) used in practice, for a variety of reasons, and were invented by theoreticians for studying fundamental theoretical questions.  These differences reflect differences in the goals and values of those two communities.

We can also compare randomness extractors to pseudorandom generators (PRGs), but again, they're very different.  PRG's are not designed to act as a randomness extractor, so there is no reason whatsoever to expect any particular PRG to do a good job at randomness extraction.  Indeed, I'd expect that many secure PRG's might be perfectly good as a PRG but no good at all as a randomness extractor.  The purpose of a randomness extractor is designed to take a non-uniformly distributed seed and turn it into a uniformly distributed output.  That's very different from the task that PRG's are designed for.  PRG's are designed to be secure if their seed is distributed uniformly at random.  There is no guarantee whatsoever that they will be secure if the seed is distributed non-uniformly, and indeed, for some secure PRGs, they might be insecure when used with a non-uniformly distributed seed.

In short, if you take a CSPRNG or a PRG, I would not expect it to necessarily act as a secure randomness extractor.  They're just different things.


If IV is sent/shared with the cipher text then where is the need to randomise the IV?

Randomizing the IV makes it so that you can send the same plaintext twice, and still get different ciphertext. If you don't do that, an adversary will be able to tell whether or not two messages are identical. This can provide a way for an adversary to infer the contents of messages without actually directly attacking the cipher.

A randomized IV prevents this, even though the IV itself is typically made public, since there's no way an attacker can use the transmitted IV to decipher the message without also knowing the key.

It's a lot like salting passwords, really.


Solving modular matrix equations via Gaussian elimination or System of linear equations (SIS assumption?)

Let $A' := [A_1 ~ | ~ \dots ~ | ~ A_k ] \in \mathbb{Z}_q^{m \times n k}$
and
$C' := [C_1 ~ | ~ \dots ~ | ~ C_k ] \in \mathbb{Z}_q^{m \times n k}$.
Then define $A \in Z_q^{m\times m}$ as the matrix whose columns are the first $m$ columns of $A'$. Likewise, define $C$ using the first $m$ columns of $C'$.
Then, $S$ satisfies $S \cdot A = C \pmod q$, thus, you can find it by computing $A^{-1}\cdot C \pmod q$.

Side note: why do you think that this problem is similar to the SIS problem? Notice that the SIS problem has a parameter $\beta$ that is an upper-bound to the norm of the accepted solutions and Gaussian elimination is likely to output solutions whose norm is above $\beta$ (thus, not valid solutions).


What you are describing is essentially the same things as a hash list. A hash list is a sequence of hashes over which another hash is calculated. Your scheme does the same thing after sorting. The sorting won't matter for the security of the scheme; it won't increase the chance of collisions.

Hash lists are also used for a well known structure called a Merkle tree, which allows for hashing data in parallel. Aggregating hashes using another hash is also performed in a meriad of protocols, including PKIX protocols (digital certificates, Cryptographic Message Syntax etc.). In those protocols the final hash is usually used within digital signature generation.


Can a message be encrypted with BOTH mono-alpha and poly-alpha ciphers?

I'm assuming that your Columnar Transposition Cipher (CTC) is as described as this site, since I found that the keyword ANNIE works.

OTP

First of all, the combined cipher (Caesar shift 7 plus CTC) can always be the OTP, as long as we don't require a truly random OTP. The simple reason; x-or the plaintext and ciphertext get the OTP keystream.

This is your OTP key;

  zpgzmdgvimgddgwmfdypurgdaagcgqhhulnohospvisfikencaiuspaplrpvdszgpjctgigfzmlrtuordrxzuzttzyllcyuvcdmzbsvnorznadqieerdcneslflvnqztpknyohgagorodtazczrdypyshyrolzigrnvtxaceufmrjusmyvtichxpdxsttpsousllyccusveqhodrnpfzrzuubmtjyvqag

And if you asked if OTP can replace the CTC, the answer yes again with the key;

  sizsfwzobfzwwzpfywrinkzwttzvzjaaneghahlioblybdxgvtbnlitiekiowlszicvmzbzysfekmnhkwkqsnsmmsreevrnovwfsuloghksgtwjbxxkwvgxleyeogjsmidgrhaztzhkhwmtsvskwrirlarkhesbzkgomqtvxnyfkcnlfrombvaqiwqlmmilhnleervvnloxjahwkgiysksnnufmcrojtz

Vigenère

In the Vigenère cipher, the password only affects $\operatorname{StrLen}(\text{password})$ characters whereas the CTC distributes the plaintexts implies they are not equal ciphers.

Note: If Vigenère is equal to CTC then the security will be the same as CTC.

Note: there may be a collision that is for some plaintexts a Vigenère Cipher will produce the same ciphertext as a CTC. This will have very low probability, and generating one is an interesting question.


Are pseudorandom permutation really permutation in mathematical sense?

Formally, a block cipher is a family of permutations, indexed by the key.  More specifically, let $P$ be the set of all permutations (shufflings of elements as you put it) on the set of $n$ bit strings, i.e. the Symmetric Group $Sym(\{0,1\}^n)$.  The $n$-bit block cipher $B$ is a subset of $P$.  The key specifies which element of the subset $B$ is to be used in the encryption/decryption process.

As CodesInChaos points out in a comment, you are confusing the idea of transposition of the $n$ individual bits of the input with a permutation over the set of $n$-bit strings.  Think of DES as being like a monoalphabetic substitution cipher, except instead of having an alphabet of 26 letters it has an alphabet of all $2^{64}$ 64-bit strings.  More precisely (following the formal definition above), DES is a family of $2^{56}$ different monoalphabetic ciphers, and the 56 bit key specifies which monoalphabetic cipher will be used for encryption/decryption.


What is the precise NP statement of Zcash?

I found your question intriguing enough to take a dive in the source code. Note that I have absolutely no experience with ZCash; I know a few ins and outs of Monero though, and I have done some tinkering with some very simple R1CS systems.

Since the ZCash "Sapling" update, it seems like the knowledge proof protocols are based on the bellman library. Their proofs are conveniently stored in the zcash-proofs directory of the ZCash Rust library. Their individual circuit "gadgets" are in the sapling-crypto/circuit directory, in which you'll find the Spend and Output circuits. These all build upon the other circuits in that directory, among which a SHA256 hash and a blake2s implementation, and ECC cryptography running in a circuit.

All the above should already give you some insight in what happens: the precise NP-statement and the complete R1CS system will be way too long to present in a simple Stack Exchange answer. I think, even presenting all the constraints on a high level would take us to far, but I think that an illustration of a few constraints may give you a lot of insight! For a high-level overview, I think the ZCash blog gives a good starting point. If you want to dive in depth, there's also the protocol specification; especially "4.15: Zk-SNARK statements" will interest you.

From the above blog, these are some high level constraints:

the input values sum to the output values for each shielded transfer.
the sender proves that they have the private spending keys of the input notes, giving them the authority to spend.
The private spending keys of the input notes are cryptographically linked to a signature over the whole transaction, in such a way that the transaction cannot be modified by a party who did not know these private keys.

Let's explore 1, for example.
Each transaction has a sequence of Spend descriptions and a sequence of Output descriptions. The latter is the simplest of both, so let's go with that.

The spec contains four constraints:

Note commitment integrity: the commitment of the note is honestly and correctly generated.
Value commitment integrity: the value commitment of a transaction is the commitment of a value.
Small order check; the point $g_d$ should not be of small order -- implementation detail in the specific curve they use.
Ephemeral public key integrity: the ephemeral public key of the transaction equals $[esk]\times g_d$.

I encourage you to look at the other statements yourself from here; especially the protocol spec is quite detailed in this.


In general you simply create a new symmetric secret key for each message. You wrap this using a trusted public key for the person holding the private key. In general you use KEM just because you don't want to encrypt/decrypt the entire message with the asymmetric key pair. Using a hybrid cryptosystem is much more efficient.

If you need to create a transport protocol you could also use KEM to establish session keys. You'd need to store those session keys for the duration of the session. Keys don't generally take a lot of resources, but you would have to keep them relatively secure, yes (at least as secure as the data you're sending during the session anyway).

In the case of a transport protocol with sessions you'd probably be better of by using an authenticated key agreement protocol though. In that case you may not need KEM.

For symmetric systems it is better to use the term "secret key" than "private key". This helps to distinguish symmetric keys from private keys that are part of an asymmetric key pair.


I'll consider that you are using a 256-bit curve per ANS X9.62:2005.

Not all 256-bit bitstrings are a formally valid private key; when using big-endian conventions, these must represent a positive integer less than $n$, the order of the largest prime order subgroup. Quoting the normative A.4.1 Preliminaries in the standard:

  An elliptic curve key pair for given elliptic curve domain parameters is a pair $(d, Q)$, where $d$ is an integer in $[1, n – 1]$, and Q is a point on the curve such that $Q = d\,G$.

For the Koblitz curve secp256k1 of SEC 2,
$n=2^{256}-\mathtt{14551231950b75fc4402da1732fc9bebf}_{16}$.
For P-256 (also known as secp256r1),
$n=2^{256}-2^{224}+2^{192}-\mathtt{4319055258e8617b0c46353d039cdaaf}_{16}$.

The all-zero bitstring, and the bitstrings representing $n$ or more in big-endian convention, have no corresponding public key per the standard. They are in a proportion about $2^{-128}$ for secp256k1, $2^{-32}$ for P-256.

Note: we could reduce modulo $n$ bitstrings representing more then $n$, but that would be non-standard, and would still leave two bitstrings (corresponding to $0$ and $n$) without a public key.

Note: This answer disregards the ASN.1 representation of a private key.


Can you use memory errors as a source of randomness for cryptography?

(..) would it be viable to allocate a very large amount of memory (perhaps in a long loop) and use the errors that eventually occur as a source of randomness?

No. Practical use of memory errors as a source of randomness would require manipulation of DRAM timing parameters, as envisioned in this answer and it's reference.
The rate of memory error in a correctly working computer at ground level is very low; anything larger than one error detected per week (as reported by machine with ECC logging) is reason for maintenance [#]. Hence the proposed method requires a terminally impractical delay to get any entropy, or an unreliable computer; and for one well built, that mostly happens at altitude (especially in the South Atlantic Anomaly). Plus, if the machine has ECC, errors are hard to detect portably (reporting of ECC errors tends to be a proprietary mess); and if it is not, and there are sizably many errors, it is to fear one will eventually prevent the program from running as intended.
More practical sources of entropy include

Audio or video input; more generally output of an ADC.
Time of events measured to high accuracy relative to CPU clock (e.g. by way of a performance counter as obtained by RDTSC instruction or API to that). Sources include:

key presses (value gives extra entropy)
mouse/pointing device movement (position gives extra entropy)
arrival of network packets
availability of data from a spinning hard disk
change of second in a real-time clock IC with independent crystal (low entropy rate, but quite reliably entropic)

Extracting the entropy is relatively easy: essentially, hash anything entropic you can get. The one extremely difficult thing is asserting a reliable lower bound of how much entropy was really gathered. Be extremely conservative, and don't assume that something that holds, will. Things change unexpectedly, especially when there's an active adversary, as we assume in crypto.

[#] Reliability studies on DRAM give widely varying estimates. However we are talking like 100 FIT par DRAM IC within a factor of 100, where Failure In Time is the expected number of failures per 109 device⋅hour. Taking the upper extreme 104 FIT, a computer with 4 DIMMs each with 18 DRAM ICs (enough for 32 GiB with ECC using DDR4 mainstream by late 2017), we get 1.2 expected failures per week.
My limited field experience with servers is that when there are ECC alarms more often than once per week, there's a cause, most often a mismatch in memory specs or settings (for new machines only) or a particular bit in one particular IC of a particular DIMM that's marginal (or worn out, for machines that have been humming quietly for some time). The error log's main virtue is to help identifying such condition, and what DIMM to replace rather than scrapping the whole lot.
There are techniques to purposely increase the rate of occurrence of DRAM errors; including lowering the refresh rate much below manufacturer specs, and/or using a RowHammer read/write pattern. However that's extremely dependent on DRAM model. Doing this reliably, portably and within an OS is very difficult; there's a reason MemTest wants to own as much of the machine as feasible.


Key Derivation Function (KDF): Can a key derived from KDF be considered as a secure key?

Yes, this is exactly what KDFs and PRFs are designed for. That is, no reasonably efficient attacker will be able to tell if you used an actual random key or something generated from the KDF/PRF. This is of course assuming that your initial seed/master secret was of sufficient entropy, and the way you derive the various values are not done in a silly way.

The practice of deriving many keys from an initial master secret using a KDF is extremely common and you will find it used in almost any standard security protocol like TLS, IPsec or SSH.

  In other words, is there any situation where we should not consider a derived key as an actual random key?

Above I only considered security from the perspective of practice, i.e., where we assume that the adversary cannot run for an arbitrarily long time. However, in a theoretical model where we allow the adversary to run arbitrarily long, there are  many examples where using anything other than a totally random string will break your security. The most common example of course being the one-time pad.


It's exactly how it sounds.  Note: 428a2f98 when interpreted as a hexadecimal fraction has the value of 4/16 + 2/(16^2) + 8/(16^3) + 10/(16^4) + ... which is approximately equal to 0.2599210496991873, so when you add back the non-fractional part you get 1.2599210496991873 which is the cube-root of the first prime number (2).

In python:

In [1]: 1+sum([int(c,16)/(16.**(i+1)) for (i,c) in enumerate('428a2f98')])
Out[1]: 1.2599210496991873

In [2]: 2**(1/3.)
Out[2]: 1.2599210498948732

To generate the constants you can the gmpy2 python library with the following code:

from gmpy2 import mpfr, floor, next_prime

def convert_primes_cube_fractional_part_to_hex_constant(prime, hex_chars=8):
    """
    Note if you want the first 8 decimal (base=10) digits of a number,
    you multiply the fractional part by 10**8 and then look at the integer part
    In this case we want first 8 hex digits, so multiply fractional part by 16**8
    and then look at integer part (and return in hexadecimal).
    """
    cube_root = mpfr(prime)**(1/mpfr(3))
    frac_part = cube_root - floor(cube_root)
    format_str = '%%0%dx' % hex_chars
    # format_str will be '%08x' if hex_chars=8 so always emits
    # 8 zero-padded hex digits
    return format_str % floor(frac_part*(16**hex_chars))

def generate_n_primes(n=64):
    p = 2
    i = 0
    while i < n:
        yield p
        p = next_prime(p)
        i += 1

After defining those functions you can run, the following to recreate the table:

>>> for i,p in enumerate(generate_n_primes(64)):
        if i % 8 == 0:
            print ""
        print convert_primes_cube_fractional_part_to_hex_constant(p, hex_chars=8),

428a2f98 71374491 b5c0fbcf e9b5dba5 3956c25b 59f111f1 923f82a4 ab1c5ed5
d807aa98 12835b01 243185be 550c7dc3 72be5d74 80deb1fe 9bdc06a7 c19bf174
e49b69c1 efbe4786 0fc19dc6 240ca1cc 2de92c6f 4a7484aa 5cb0a9dc 76f988da
983e5152 a831c66d b00327c8 bf597fc7 c6e00bf3 d5a79147 06ca6351 14292967
27b70a85 2e1b2138 4d2c6dfc 53380d13 650a7354 766a0abb 81c2c92e 92722c85
a2bfe8a1 a81a664b c24b8b70 c76c51a3 d192e819 d6990624 f40e3585 106aa070
19a4c116 1e376c08 2748774c 34b0bcb5 391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3
748f82ee 78a5636f 84c87814 8cc70208 90befffa a4506ceb bef9a3f7 c67178f2

Note this exactly matches the table in the NIST publication.

You can generate the other SHA-512 constants with the following code.  Note you first have to increase the multiple precision floating point math in gmpy2 to ~100 digits from the default 53 digits, or you'll find the last few hexdigits are always 0 due to loss of precision.

>>> gmpy2.get_context().precision=100
>>> for i,p in enumerate(generate_n_primes(80)):
        if i % 4 == 0:
            print ""
        print convert_primes_cube_fractional_part_to_hex_constant(p, hex_chars=16),


Group membership with unique anonymous claims

A paper was published in 2015 describing a scheme called Anonize to do just that.

It appears to be constructed around a specially designed Non-Interactive Zero-Knowledge Proof of Knowledge (NIZKPoK) protocol used by clients.

First, a registration is made, whereby a client sends a commitment to a seed of a pseudo-random function. Sent back to it by the Server is the Server's signature on that commitment and the client's id, which becomes that client's master token. Then the client uses the seed to generate a single-use token. Finally, to submit a response the client has to prove by NIZK that it knows some master token, a survey conductor's signature authorizing some client to go through the survey, and that it indeed computed the single-use token by the seed it knows.

It's notable that the scheme actually makes it possible to conduct multiple ad-hoc surveys on a single server, without giving the server's operator an opportunity to track clients across multiple surveys. That is achieved by using a survey id, which is different for every survey, to generate single use tokens. A client can, on the other hand, only generate one single-use token for each survey id, which means it will only be able to submit one answer.

A usable online implementation can be found here and the development reference implementation is hosted over here.


SSL certificate / SSL configuration - FIPS-197 compliance

FIPS 197 is the AES specification. An implementation complies with it if, and only if, it correctly implements the AES algorithm. The standard applies only to implementations of AES; it doesn't apply to certificates, or TLS server configurations, or computer systems in general. In particular, since it only applies to implementations of AES, it doesn't actually require that you use AES at any point in your system. Other FIPS apply to broader things (e.g. FIPS 140-2 applies to cryptographic modules) and do specify acceptable algorithms to use, but the algorithm specification itself just tells you how the algorithm works.

Unlike FIPS 140-2, FIPS 197 compliance isn't a big deal. It just means whoever coded the AES implementation did it correctly; it doesn't even mean they did so securely.


Yes, you got it right. You XOR'ed the correct bits, copied the IV and then shortened the message. Nothing wrong with that approach.
The only thing that I'm a bit critical about is the one based indexing instead of the zero based indexing. Most mathematicians use zero based indexing (because it is compatible with modular calculations, for instance) and similarly do most developers and therefore cryptographers...


Is it secure to use TOTP with same key and different time-counters?

Yes, that's fine where TOTPs are generated in accordance with RFC 6238; this is because the time is combined with the secret before generating the HMAC. This means that it isn't practically possible to derive the time (or information about it, such as the time difference) based on the key alone because of the Avalanche effect in the hashing algorithm that is used.


Can a low density subset sum problem be intractable?

Yes.    By reduction from 1-in-3-SAT, subset sum remains

NP-hard when the subset's size is part of the input, so we can

[add an arbitrarily large number to each element

and  (that_number)*(subset_size)  to the target]

to get that for all positive integers c, [subset sum with density less than 1/(1+(n^c))] is NP-hard.

Here's a much better question:  "Is it possible for a subset sum problem to be"

strongly hard-on-average "even if it's density is less than 0.9408?"

(I do not know the answer to the better question.)