Yes, only if $H(-)$ is either a $\texttt{HMAC}(-, k)$ function or an hash algorithm resistant to Length-Extension attacks1, for example, the Blake2 hash algorithm2. I'm assuming too the collision/preimage resistance, so it would be unlikely to 2 different pairs $r \ne r'$ and $i \ne i'$ collide on $H(r || i)$ = $H(r' || i')$. In this case, the $i$ index would be the key $k$ for either $\texttt{HMAC}$ or keyed-mode of the length-extension resistant hash. In fact, it is mostly how the Bitcoin HD wallets3 work to generate one-time addresses.

Due the deterministic nature of hashes, you must never reuse the same $(r, i)$ pair to generate pseudo-random values. But due this deterministic nature too, this kind of PRF is used to generate entropy where public randomness is needed, e.g, on Blockchains. On the literature, they are called Provably Fair Algorithms4,5. In such contexts, the verifiable/reproducible nature is really important to protect against cheating, the $r$ entropy would be sealed under a commitment to be revealed later for verification.


how does one prevent a LFSR from getting to an all zero state?

One method is to not initialize the LFSR to the all-zero state, and use a feedback polynomial with a constant term (the $1$ in the polynomial).
 [image credit]
Proof that it works for a LFSR in Fibonnaci form, as illustrated with polynomial $x^{16}+x^5+x^3+x^2+1$ in the above picture, by induction: if the current state of an $n$-bit LFSR is non-zero, and there is a constant term (the $1$ in the polynomial, equivalently a XOR tap on the rightmost bit), then the next state is non zero, by considering the two cases:

If any of the $n-1$ left bits is non-zero, then this bit is carried to the next state, which thus is non-zero.
Otherwise, the $n-1$ left bits are zero and the rightmost bit is one. This bit enters the XOR, and all other bits entering the XOR are zero, hence the next left bit is a one, hence the next state is non-zero.

For LFSRs in Galois form, we can invoke the equivalence with the Fibonnaci form, or make a direct proof, as follows. If the LFSR's feedback polynomial is $P(x)$ and it's state $S(x)$, the next state is defined to be $\big(x\cdot S(x)\big)\bmod P(x)$. Since the degree of $S(x)$ is at most one less than the degree of $P$, the next state can be all-zero only if one of the following holds

$x\cdot S(x)=0$, implying that $S(x)=0$
$x\cdot S(x)=P(x)$, which can't be if $P(x)$ has a constant term.

Note: The condition "feedback polynomial has a constant term" is so common in practice that it is sometime part of the definition of LFSRs. When it holds, it can be shown that Fibonnaci and Galois forms of LFSRs with the same polynomial (perhaps within reflection, depending on convention for Fibonnaci) are equivalent, in the sense that the sequence produced by one for a given initial state is the same as the sequence produced by the other for a (different) initial state. There is no other common form or kind of binary LFSRs.

Some hardware constructions want to recover from a fault (invalid setting, "upset" such as a power glitch or a cosmic ray) and have special circuitry to leave the all-zero state if it gets entered. That can be a NAND gate on all the state bits forcing a one to enter the LFSR. Or a counter clocked with the LFSR, reset when the LFSR output is a one, with the counter's high-order bit forcing a one to enter the LFSR.


How do quantum key distribution systems tolerate noise?

That question is essentially A.1 of this lengthy post, with some elements of answer in B.1

For your convenience, here’s quoting those specific sections of his linked answer:

  A. Issues prevent direct use of sifted bits

  …

  Errors creep in the sifted bits

  The many imperfections of the model (heavily simplified compared to the actual hardware and the known laws of quantum physics, even at the time the [article][2] was written) are such that, without Eve messing, sizably many sifted bits differ at Alice's and Bob's end. Sifted bits are thus unusable as key to a [cipher][3], for decryption would likely fail.

  …

  B. Classical cryptography rooted in information theory fixes them all

  Secret-Key Reconciliation protocol remove errors, and more

  Coding theory and error detection and correction are used to build a secure Secret-Key Reconciliation protocol additional to sifting, also running over the classical channels. Its objectives are to

  remove or fix errors in the sifted bits, with bounded low odds of the contrary;
  obtain an upper bound on the actual error rate, which is attributed to Eve spying the quantum channel;
  obtain and minimize an upper bound on the information leaked by running the protocol over the classical channels, that Eve is assumed to scrutinize;
  deduce a lower bound of what entropy (if any) remains in the rest; if there is less than some headroom, QKD failed.

  Such reconciliation protocol can loose little-enough entropy as to be usable in practice, and be information-theoretically provable; but no simple such one is known. A most scrutinized milestone is the cascade protocol in: Gilles Brassard and Louis Salvail's Secret-Key Reconciliation by Public Discussion, in proceedings of Eurocrypt 1993.

  …


Is it possible to see whether different EC encrypted messages are (likely to be) encrypted on the same public key?

I suppose that you mean "encrypted with the Elliptic Curve ElGamal scheme"; an elliptic curve is a particular type of group, you do not "encrypt a message with elliptic curves", but with an encryption scheme that works over an elliptic curve.

That being said, the ElGamal encryption scheme is randomized, so the fact that $M_1$ and $M_2$ are not equal does not matter at all: encryptions of $M_1$ and $M_2$ will look random to anyone that does not hold the secret key anyway, even if they are the same.

Finally, to answer your question, no, one cannot tell whether the same public key was used to encrypt both message, as each encryption is provably indistinguishable from a pair of uniformly random group elements, whatever the public key (unless, obviously, the attacker knows one of the corresponding secret keys).

EDIT: let's extend a bit on that, as your comment seems to ask for more details. Let $g$ be a generator of some group $\mathbb{G}$. Let $h_1,h_2$ be two public keys ($h_i = g^{s_i}$ for secret keys $s_i$, $i \in \{1,2\}$). Let $(M_1,M_2)$ be any two messages (id est arbitrary group elements, possibly identical). We consider two random encryptions of $M_1$ and $M_2$, with keys $h_1$ and $h_2$:

$E_1 = (g^{r_1}, h_1^{r_1}M_1)$ with a random exponent $r_1$
$E_2 = (g^{r_2}, h_2^{r_2}M_2)$ with a random exponent $r_2$

Consider an attacker that attempts to check whether the same public key was used for both encryptions. As it can only help him, let us assume that this attacker knows $M_1$ and $M_2$. Therefore, the adversary gets $(g^{r_1}, h_1^{r_1})$ and $(g^{r_2}, h_2^{r_2})$ for uniformly random exponents $r_1,r_2$, and tries to check whether $h_1 = h_2$. Suppose that he can do that with some non-negligible probability. Then I can use this adversary to break the decisional Diffie-Hellman assumption. Indeed, suppose I receive a tuple $(u, v, u', v') \in \mathbb{G}^4$, and I have to tell wether this is a random tuple, or a Diffie-Hellman tuple (id est a tuple of the form $(u,v,u^r,v^r)$ for some $r$).

I can simply proceed as follows: I send the pair $(u,v)$ to the adversary, as well as the pair $(u',v')$, and ask him whether "the same public key is used in both pair". Indeed, observe that $u = g^x$ for some $x$, and $v = h_1^x$ for some $h_1$, so $(u,v)$ can be seen as a pair $(g^x, h_1^x)$ for some random coin $x$ and public key $h_1$. Similarly, $(u',v') = (g^{x'}, h_2^{x'})$ for some exponent $x'$, and some public-key $h_2$. Now, if $(u,v,u',v')$ is a Diffie-Hellman tuple (hence $(u',v') = (u^r, v^r)$ for some $r$), then we necessarily have $h_1 = h_2$ above (and $x' = rx$), while if it is a random pair, then we have $h_1 \neq h_2$ with overwhelming probability.

So, if the adversary tells me that the same public key was used in both pair, it means $(u,v,u',v')$ is a DH tuple, and if not, it means it's a random tuple, so I can break the DDH assumption with the same probability that the adversary finds out whether the same key was used in both pairs.

Put otherwise, this means that assuming the DDH assumption (which is equivalent to the IND-CPA security of ElGamal), it is infeasible to tell whether the same public key was used for two encryptions.


Use the PHP libsodium extension or the PHP encryption library.  Both are high-quality libraries that provide well-documented functions that allow you to do what you need.  They also includes automatic integrity check (this is crucial!), and their operations are protected against timing attacks.

AES256-CTR provides only unauthenticated encryption, which is almost never what you want.  You need authenticated encryption.

The libsodium extension has the advantage of being faster in most cases, but it depends on an extension module written in C, so it might not be available everywhere.  php-encryption is slower, but it only uses PHP’s built-in OpenSSL binding, so it runs everywhere.

Note that nonces must never be loaded from disk and then used for encryption.  It’s way too easy to have a collision that way.  Instead, you should generate a fresh encryption key from a master key each time your program starts (using a KDF and some secure random bytes.)


128 bit 3DES Key and AES Key: what's the difference?

Both an AES-128 key (as defined by FIPS 197), and a TDES Keying Option 2 key (as defined by FIPS SP-800-67) are 128-bit bitstrings. Similarly, both an AES-192 key and a TDES Keying Option 1 key are 192-bit bitstrings. The differences are:

In AES, all bits of a key matter to the result; in TDES, 1 bit out of 8 (the lower-order bit of each byte in the usual representation) either

is ignored, and can have any value;
is checked, and must be the complement of the exclusive-OR of the 7 others; that is, each byte is adjusted to odd parity; see this answer for details on the oddity (pun intended) of DES key bytes.

TDES has a complementation property, which  removes an extra bit of security for a given key size in many situations (including CPA attack); that further reduces a 128-bit TDES Keying Option 2 key to 111-bit strength, and a 192-bit TDES Keying Option 1 key to 167-bit strength.
The block size is 128-bit for AES, 64-bit for TDES; this means that AES and TDES are not interchangeable, even though they use the same key (analogy: truck and car are not interchangeable, even though both might run on gasoil). As rightly pointed in that other answer, that block size difference also makes a security difference in some applications.
AES is unbroken for any practical purpose, but there are attacks on TDES (at least, with Keying Option 2) using conceivable amounts of computing power and not-far-from-conceivable amounts of memory.
I'm leaving alone the non-issue of DES weak and semi-weak keys, which is immaterial in practice, and much more for TDES.

If one generates a TDES key with knowledge that 1 above will apply when it will be used, one can generate the key at random just as for an AES key (there might be different regulatory requirements). If one generates a TDES key with knowledge that 2 above will apply (or does not have such knowledge but want to err on the compatible side), one must adjust the low-order bit of each byte according to the 7 other bits.

One can use a TDES key for AES (AES-128 or AES-192 depending on TDES keying option); however, if the key was generated with low-order bit adjustment, that weakens AES-128 by $2^{16}$ w.r.t. brute force key search, which is (somewhat) undesirable and (very) unusual (AES-192 would be weakened by $2^{24}$, which likely is still strong enough except perhaps from a certification standpoint).

One can use an AES key for TDES (assuming matching key option) if

the TDES implementation does not check parity (case 1 above);
or the AES key is parity-adjusted to transform it into a TDES key.

In any case, it would be a bad idea to use the same key for both AES and TDES, for a successful key recovery attack on either cipher (e.g. by DPA) would then translate into an attack breaking the other.


How does Microsoft's BitLocker Recovery Code work?

In my own knowledge, encrypted data can't be decrypted without knowing the key, but BitLocker breaks it.

That description indicates you might have misunderstood something there. Bitlocker does not break anything* as Microsoft BitLocker uses recovery keys (read again: “keys”), not code! The related code for recovery is pretty similar to the usual decryption code which Bitlocker also uses when you’re using your personal key. No magic or backdoors there. For details, you might want to check “What is a BitLocker recovery key?” and “BitLocker recovery keys: FAQs” as well as the linked pages of the Bitlocker documentation.
The three sub-questions are partly too broad, and partly unanswerable completely for reasons I’ll gladly describe while trying to provide you with some helpful hints nevertheless…

How does the recovery code work?

You’ve already said it yourself when you wrote I don't trust Microsoft BitLocker because it is closed source, which makes it so people can't audit it. The words “Closed source” are important to remember when asking things like that. Long story short: I won’t break any intellectual rights for you and I’m pretty sure Microsoft will not be very willing to provide anyone with any legal right to do so unless it makes sense to them.
Yet, you could very well decompile the binaries on your own computer to check on its inner workings for yourself. Doing so enables you to engage in some personal auditing efforts too. Yet, your success in doing so will definitely depend on your decompiling abilities as well as your ability to read and understand the minimal ASM source that decompilers tend to spit out.

How can I implement a recovery code function on any encryption algorithm in a mathematical way?

This question is based on your misunderstanding that Microsoft Bitlocker “breaks” things with a recovery code. As noted above: that’s not how it works.
Microsoft BitLocker uses a recovery key – which is a special key that you can create when you turn on Bitlocker Drive Encryption for the first time on each drive that you encrypt. That recovery key is what enables Bitlocker to recover things for you when you – for example – forgot your usual (non-recovery) key… without a key, you won’t get anywhere – which is why Microsoft puts an emphasis on the fact that you should store the recovery key by printing it, saving it on removable media, or saving it as a file in a secure place.
Personally I would advise against storing secrets like keys on the same computer which you use to host/store your encrypted data. Yet, your security expectations may be different than mine. (More on the related, potential security impacts later when I answer your 3rd sub-question.)
The “code” that Bitlocker uses to recover data for you using that recovery key is pretty much the same as the code it uses when you decrypt things using your usual (non-recovery) key. The differences merely reside in detection of the key-type (regular or recovery) and handling/decrypting things accordingly. There is no magic or hidden unicorns in there… and Bitlocker is definitely not breaking any encryption when you recover an encrypted drive with your recovery key. Think of it as Bitlocker using regular decryption code as usual, merely the key-type is a different one… but a “recovery key” is nothing else than a regular key. It’s a secret to unlock your data in a worst-case-scenario; eg: you tried to memorize your key, but when waking up the next morning you realize you forgot it. That’s where you would need a recovery key, which you hopefully stored in a secure place at the time you created it – which was when you first encrypted the related disk/data.
So, could you implement such a recovery functionality no matter the encryption algorithm? Generally, yes. Just note that that would be more a “software feature” than an algorithm thing. Therefore, asking about a mathematical way to do so doesn’t really make sense as it’s too broad and practically impossible to cover all individual algorithms out there. And describing how to write secure wrappers around a crypt algo core can not really be described mathematically, as it’s more a programmatically thing and not “one mathematically describable formula to rule them all”. If an algorithm can encrypt and decrypt data based on a secret/key, nothing is stopping a programmer from wrapping a functionality around the crypto algo core to offer users an option to use recovery keys to decrypt things. (In case of doubt: I’m assuming such a programmer to have access to the crypto algo sourcode, or at least the API/SDK to be able do so… while ignoring some rare, rather borderlining situations where this might not be the case, yet possible to implement nevertheless.)
Surely, making two different keys decrypt the same data can be explained and described from a cryptographical point of view as there are several options/schemes available to do so. I won’t even start listing them here because Crypto.SE already has several Q&As handling that. The search-box at the top-right of every Crypto.SE page is the perfect tool to help you find them.

Will it be a possible backdoor/vulnerability to hacker?

A recovery key and related recovery functionality that expects you to enter such a secret before it is able to decrypt the related drive can hardly provide an attack vector unless you really messed up things badly from a security point of view. That’s one of the reasons Microsoft provided ample security advice made available to you as a user.
When thinking beyond that, I’ll have to say that anything is “possible“ if the circumstances allow it. So thinking beyond the obvious renders your question a bit too broad as you can’t possibly expect anyone to handle all the potential scenarios, situations, and potential security glitches you might or might not be thinking about.
To avoid such broadness, I’ll limit my answer to this sub-question by saying that when we assuming the decryption code doesn’t include a backdoor and/or vulnerability, the recovery procedure using recovery key(s) will hardly pose any risk as it mainly uses the same parts of the code Bitlocker also uses for the usual decryption functionality when using your usual (non-recovery) keys.
Whether a “hacker” can gain access to your encrypted drives as well as to the related keys and/or recovery keys ends up being something up for you to evaluate. As long as you keep your keys secure and use Bitlocker correcly (both thing are described in the related manual/documentation which Microsoft provided for a good reason), you should be fine.
Note that the Bitlocker documentation clearly states and advises not to store keys on the same machine hosting encrypted drives/data. If you decide to store keys and (encrypted) data in the same place anyway, you logically have to assume all related risks. Meaning: If an attacker can get access to your key storage (whichever key storage option you may have chosen), you’ll surely be inviting that attacker to walk all over all the encrypted data… if (and only if) that hacker is also able to gain access to the encrypted drives those keys belong to.
Assuming an average, non-state adversary and assuming you’ve followed the ample advice provided within the Bitlocker manual, that’s rather unlikely to happen.
For such an attack to work, an adversary would have to circumvent things like the Microsoft Firewall et al – which a security-aware person like you surely will have updated, correctly configured, and activated for your system protection. Attackers can’t read a single bit of any of any your drives (encrypted or not) unless they either circumventing those barriers (firewall et al) or when they have physical access to your drives.
Additionally, the attacker would also have to get access or knowledge of your keys. Repeating it again: if you follow the Bitlocker docs and contained recommendations, those keys won’t be stored on the same computer system and can therefore not be found on the same computer system that holds your encrypted drives. That makes things hard for an attacker as the attacker would also either need to circumvent other barriers (eg: firewall et al of other system), or be able to gain physical access to the keys.
Surely, things will turn against you if there are incidents like (eg) a burglar stumbling upon your encrypted drives as well as your keys which you’ve printed out but then put neatly into your desktop drawer next to your computer for everyone to find, or (eg) you store keys on another system within the same network but an attacker can access to both encrypted drives as well as the key storage after a successful full-network breach. If you think about it, a bit of human logic can prevent most of such risks… while the rest can be learned by reading the Microsoft Bitlocker manual and following the contained recommendations.
I think it is needless to say that, if you leave your system and/or network wide open (read: in an insecure state) and if you additionally ignore the manual/documentation by leaving at least one of your keys flying around within the reach of a potential attacker, your data could be decrypted without big efforts by near to anyone who is able to gain access to both the encrypted drives as well as related keys.
Wrapping it up:

Bitlocker doesn’t decrypted without knowing the key, so assuming BitLocker breaks anything by using some magic recovery code is wrong. Bitlocker uses recovery keys via related recovery functionalities. Every software out there that offers alike functionalities based on recovery keys works in a somewhat similar way – wrapping that additional functionality around a cryptographic algorithm core. Bitlocker doesn’t contain some magic sauce voiding your key by breaking its own crypto… it’s simply a recovery functionality based on recovery/backup keys. Without a key, Bitlocker won’t be willing nor able decrypt anything. How exactly this was implemented by Microsoft can only be answered in detail when having access to and studying the sourcecode. Even if this would be available, describing the details would break the limits of sanity as it would probably take a small book instead of an answer to talk about every detail of every related function and variable.

As with every encryption: if you store the encrypted data and the key on the same system – your data safety can be considered near to void. Anyone having access (or being able to gain access) to both encrypted data as well as related key(s) can access and decrypt your data. That’s one of the reasons why cryptographers, information security people, and the Bitlocker documentation itself advise to never store encrypted data and its related secret(s)/key(s) in the same location. As long as you keep keys out of reach of potential attackers by storing them in a separate, secure place (at least not on the same machine), the success rate of a potential “hack” and the ability of an attacker to read your decrypted data will be near to or equal to the success rate of a brute-force attack on your encrypted drives.
Actually, you could boil this whole thing down to a simple: “Securing your key(s) is your key to security.” – or, how others might know it: “Always keep your secrets secret.”

To learn about the Microsoft Bitlocker security recommendations related to key storage et al, and to clearly understand how Microsoft Bitlocker (including the recovery of encrypted drives) actually works, you might want to start reading the manual. The two links I provided at the beginning of this answer serve as a pretty good entry point to do so.
For your convenience, I’ll simple mention those links again: “What is a BitLocker recovery key?” and “BitLocker recovery keys: FAQs”. You’ll discover a complete manual when following those links, which will definitely be able to explain all this in more detail.

EDIT
Since the comments area showed there’s some confusion about the keys and which key en/decrypts what…
Each of those keys (both “regular” keys and “recovery” keys) can be used by Bitlocker. Practically it goes like this: You provide a key which will be used to construct the key-protector key (using a key derivation function – KDF). The output of the KDF is used to decrypt the Volume Master Key (VMK). The VMK is then used to decrypt the “Full Volume Encryption Key” (FVEK), which is the key that actually actually en/decrypt the individual disk/volume.
So, staying in line with the notation used in the comments:
$$\text{pin/recovery key} \rightarrow KDF \rightarrow VMK \rightarrow FVEK \rightarrow \text{volume en/decryption}$$


2PC Private Set Intersection Optimized for asymmetrically sized sets

It is easy to observe that any secure protocol must touch every bit of both parties' inputs -- otherwise it's not secure.

However recent work has shown that you can amortize the protocol complexity over several runs, with state stored between the runs, so that not every execution will touch every bit.   See here for the paper.  It doesn't address set intersection directly, but since it covers a generic function it applies to your case.


computing INV in boolean circuit for MPC

Boolean circuits are Turing complete and so the answer is yes for any computation. Specifically, for this case, the circuit will assume that the loop never exits early (and if it finishes early, then the circuit will not change the result). In general, if you need to compute a branch in a circuit, then the circuit will always have both branches.

If your question is about efficiency, then there may be more efficient ways to compute this than in a circuit. For example, use MPC to compute $r\cdot a$ where $r$ is an unknown random value. Then, the parties compute $b=(r\cdot a)^{-1} \bmod q$, and then securely compute $r \cdot b$. This result is $a^{-1} \bmod q$. There are many ways to do this, using homomorphic encryption (e.g., Paillier), OT and so on. However, the main challenge is to prevent cheating, if you want malicious security. It also depends if you are looking at the honest majority or dishonest majority setting. For an honest majority, one just uses standard techniques to generate a secret sharing of $r$. The parties then run secure multiplication on shared values to get $r\cdot a$ and open it, and then each local invert the result. Finally, each uses local scalar multiplication of their share of $r$ with  $b$ to get shares of $a^{-1} \bmod q$.


Security implications of repeated hashing

In terms of a hash scheme, the security of your construction can be proven secure in the same way that the Merkel-Damgard construction is. One subtlety is that you need to add a final invocation to "hash()" to make sure you don't suffer from a length extension attack as @codeinchaos mentioned.

With regard to the technique to store password, it is not recommended to have a constant IV but rather choose some random IV for every entry in your password table. This is for the reason that whenever someone breaks into your system then she could see immediately the entries that store the same password. This technique is called "salting".


Are stream ciphers no longer considered by NIST?

I don't know, but block-cipher based modes of operation have seen a lot more scrutiny.  AES in CTR mode has been vetted much more thoroughly than any of those stream ciphers you mention.  Moreover, those stream ciphers do not offer compelling benefits over AES-CTR mode.  Therefore, it seems to me it would be entirely reasonable to focus on block-cipher based modes of operation.


What is the "single-letter characterization of the secrecy capacity"?

Secrecy capacity is defined as the maximum bit rate that can be sent securely through a channel. Single-letter means that the corresponding capacity expression does not depend on the block length $n$.

For example in a degraded wiretap channel, we have the following single-letter characterization of the capacity $C$:

$$C = I(X;Y) - I(X;Z)$$

But in more complex models like the compound wiretap channel, it's hard to find an expression that doesn't depends on $n$:

$$C = \lim_{n\to\infty} \frac{1}{n} \max_{U} ( \min_{s\in S}I(U,Y_s^n) - \max_{s\in S}I(U,Z_s^n))$$

Single-letter characterization is a desirable property, since it is simpler to express and compute.

Adapted from a mail explanation from R. F. Schaefer


It means any instances of double letters in encryption are split up by injecting a letter x (as well as the usual I = J).
In other words read the instructions as

I=J
X added into two same letters
Key KEEP DISTANCE


Any NP statement can be proven in zero knowledge (not necessarily practically efficiently, but yes in polynomial time). So, if you can define what you want as an NP relation then it can be done. However, in order to do that, you must define what you mean by "dependent" and so on.

Such statements can also be highly efficient. For example, it is possible to efficiently prove that a tuple of elements if of the "Diffie Hellman type". Informally, one can prove that for some $(g,h,u,v)$ there exists a value $r$ such that $u=g^r$ and $v=h^r$ (where $g$ is the group generator and all operations are in the group). Observe that this is exactly a proof that $u$ and $v$ are ''dependent'' variables.


In symmetric cryptography, for fully known ciphertext, one is expected to need slightly more known plaintext bits than usefull key bits in order to reliably recover the key by pure brute force. That rule also works if we reverse plaintext and ciphertext, and that's what we want here.

The key is 56 bits. Each pair (M, C) with distinct M chosen at random gives 24 bits of ciphertext. Two pairs give 2⋅24 = 48 bits, 56-48 = 8 bits are missing, and about 28 = 256 keys would match. Three pairs give 3⋅24 = 72 bits and that is enough for brute force key search to pinpoint a single key with excellent probability (in the order of 256-72 < 1/50000 ). Most likely the first key found (after an expected 255 keys have been tested, and marginally more trial encryptions) will "behave like K" for any other (M, C) pair, because it is the actual K used to build the pairs (M, C).

It is feasible to intentionally exhibit three pairs (M, C) (perhaps more) with distinct M such that at least two keys are possible; but again this is unlikely to happen by chance.

It is asked the math. Let $(M_i,C_i)$ be the given plaintext/ciphertext pairs (40+24 bits each), with distinct $M_i$, corresponding to an unknown actual key $K_A$. Let $C_{(K,i)}$ be the result of expanding $M_i$, enciphering under key $K$, and truncating to 24-bit. By that definition, $C_{(K_A,i)}=C_i$.

Because the $2^{56}$ DES keys only cover a small fraction of the $2^{64}!$ permutations of the DES block, and in that application at least one bit in the input is fixed (thus making irrelevant the DES complementation property that $E(\overline K,\overline P)=\overline{E(K,P)}$ ), and we'll have few plaintexts (or/and can observe only a small fraction of the bits of an output block), we can model the $C_{(K,i)}$ for each $(K,i)$ as uniformly random and independent 24-bit bitstrings. That's true including for $K=K_A$, under the assumption that the $M_i$ have been chosen independently of $K_A$.

Under that model, a key $K\ne K_A$ is such that $C_{(K,i)}=C_i$ for $n$ plaintext/ciphertext pairs with probability $2^{-24n}$ (that probability is halved for each ciphertext bit). It follows that with $n$ pairs, each $K$ can be eliminated with probability $1-2^{-24n}$. After testing all $2^{56}$ keys, $K_A$ remains the only possible key with probability $p_n=(1-2^{-24n})^{(2^{56}-1)}$ and there remains more than one possible key with probability $\overline{p_n}=1-(1-2^{-24n})^{(2^{56}-1)}$.

For $n\ge3$, we use that $1<c\ll1/|\epsilon|\implies1-(1-\epsilon)^c\approx\epsilon\cdot c$ to get $\overline{p_n}\approx2^{56-24\cdot n}$. Thus $\overline{p_3}\approx2^{-16}$, which is very small (meaning 3 pairs will do with excellent odds).

For $n\le2$, we use that $\log p_n=(2^{56}-1)\log(1-2^{-24n})$, and $|\epsilon|\ll1\implies\log(1+\epsilon)\approx\epsilon$ to get that $p_n\approx e^{(-2^{56-24n})}=2^{-(56-24n)/\log2}$. Thus $p_2<2^{-369}$ which is ludicrously small (meaning 2 pairs won't do). The most probable is that many keys will remain possible (in the order of $2^{56-24n}$).


What if an AES GCM nonce overflows and collides with the GHASH nonce (0^128)?

This is not allowed.  An AES-GCM implementation that accepts messages longer than $2^{39} - 256$ bits, i.e. $2^{32} - 2$ blocks, is broken.  A protocol that is defined in terms of AES-GCM on messages longer than $2^{39} - 256$ bits is nonsensical.

Protocols shouldn't be defined in terms of messages that long anyway because an adversary can waste the receiver's resources by sending an obscenely long message.  If you allow terabyte-long messages, an adversary can waste a terabyte of memory before you realize it's a forgery and drop it on the floor.

Instead, you should break messages up into units no longer than you want to have to buffer in memory before you can decide to drop forgeries on the floor, like 1500 bytes for an IP packet, or 64 KB for a TCP segment, or maybe a megabyte if appropriate for your application.

But let's suppose you did have a broken protocol that violated the rules of AES-GCM and a broken implementation that let it happen.  What happens if you do this—encrypt a message of ${>}2^{32} - 2$ blocks, with the counter truncated at 32 bits and wrapping around?  Then:

An adversary who knows the first block of plaintext can solve for the GHASH authentication key and forge arbitrarily many additional messages.
An adversary who knows the third block of plaintext can decrypt block number $2^{32}$ of the plaintext.

If the counter carries into the nonce, rather than being truncated at 32 bits, then it is a slightly different known-plaintext attack—e.g., enabling decryption of the first block of the next message, assuming sequential message numbers for the nonce, rather than block $2^{32}$ of the same message.

In brief, don't do it!


Why is NON DISCRETE logarithm problem not hard as the DISCRETE logarithm problem (so computationally hard)?

The main point is that the entire apparatus of calculus applies to exponentiation over the real numbers. For instance, if $a$ and $b$ are close, then $g^a$ and $g^b$ are close as well. The exponential function and its inverse are nice, so you can use infinite series for your computation, and some partial sum will be close enough to the correct answer. Or since exponentiation is monotonic, you can use binary search.

The groups we use for cryptography are usually discrete, and the apparatus of calculus no longer applies. For example, there is no sensible distance measure that relates the distance between $a$ and $b$ and the distance between $g^a$ and $g^b$. And this means things end up being more difficult.


Can someone explain the definition of four square roots as it pertains to groups in Z*p?

"$x$ has four square roots" means there are four distinct elements $r$ in the group such that $r^2 = x$.

For example, in $\mathbf{Z}_{15}^\times$ the element $1$ has four square roots, which are $1$, $4$, $11$, and $14$ (note that $11 \equiv -4$ and $14 \equiv -1  \pmod{15}$).


Generating multiple keys based on same password

Neither approach is particularly good because it depends too much on the PBKDF2 function. The PBKDF2 function should always be performed in such a way that the number of iterations (the work factor) is high.

Besides that, PBKDF2 should not be asked for more output than the internal hash function (usually SHA-1, so 160 bits / 20 bytes). Otherwise you give back a part of your advantage back to the attacker (this is an unwanted property of PBKDF2 itself).

You can perform the following on the client:

master = pbkdf2(uip, email, 2000, 256);
hash = hkdf(master, 'hash')
kenc = hkdf(master, 'kenc')
ciphertext = gcm-aes(kenc, message)

then send hash and ciphertext over a TLS encrypted channel to the server (obviously you do not want to leak the hash value to an attacker).

The server should contain a hash over the previously calculated hash value, storedHash = H(hashOrg). It can then do a (secure) compare with the calculated hash value calculatedHash = H(hashGiven) to perform authentication.

Because hash cannot be reversed to the master value (which is pseudo-random, with the strength of the password and the work factor combined), it can also not calculate kenc.

The additional hash on the server just puts a bit of distance between the hash send over the secure channel and the stored value. Otherwise retrieving the database is enough for an attacker to obtain hash and simply send that value to log in.

Note that PBKDF2 is computationally intensive. You can bring that down by choosing really strong passwords. You could also use an asymmetric key pair, pasting in the public or private key value when required.

The biggest issue is that you'd still need to trust the service, especially if you would use encryption in the browser. That is not something that is easily avoided. You can avoid some of this by having your server audited or by creating an open source client application and only put the code into a repository after a thorough review. But at some point the client will still have to trust you, the service provider. There is no known good way around that.

Your client application may implement a great encryption / authentication scheme and send the password together with the authentication code and authenticated ciphertext. Simple as that.

If your users wants encryption that cannot be decrypted by the service, he/she is better off encrypting with their own PGP public key, and pasting the result ASCII armored into some input form.


How is it possible for someone to "Protect against Future Unknown Attacks"

How we can thwart against attack which we dont know, or which is yet to be discovered or established?

I'll just answer in the generic sense: by adding complexity. The complexity / irregular structure of the function(s) may not be directly needed for the (incomplete) security proof of the overall cipher but it may still need to be overcome by attacks on it.

For instance, a function could be used to hide a regular algorithmic structure, so that the cipher cannot easily be written down as a set of mathematical equations. New advances may make it easier to solve the equations for a (partially) unknown key. So those kind of attacks may be avoided by adding complexity.

Of course, with the attacks being unknown, it's impossible to be sure such attacks would be thwarted. So it's a goal which is only reached if one or more attacks are nulled or at least made computationally hard.


How is the DUHK attack specific to the ANSI X9.31 RNG?

As far as I understand it, the very same problems would arise, if a hardcoded key would be used with any of the other keyed PRNG standards (like HMAC_DRBG or CTR_DRBG). What am I missing?

The issue is that, for X9.31, the key really is a long term key; it is never updated as a part of the RNG process.

That is, the state of X9.31 consists of a 'current state' (64 or 128 bits), and a 'key'; when you generate the next batch of outputs, you update the 'current state', but not the 'key'.  Hence, if you start with a fixed key, you'll end up using that for the life of the PRNG.

So, if we assume that the X9.31 has been used for a while (and so the attacker doesn't know the exact state; one of its input is the 'current time', that does act as a weak entropy source).  However, if X9.31 starts with a fixed key, that key is still in effect; if the attacker sees one output and has a guess of the current time, he can then predict future outputs (and previous as well, the state update function is invertible if you know the key).

In contrast, for the HMAC_DRBG or the CTR_DRBG generates, when they generate a batch of output, they update the 'current state', but they also update the 'current key'.  So, if the PRNG is used for a while (and so the attacker doesn't know the state of the PRNG), the attacker won't know anything about the HMAC_DRBG or CTR_DRBG key, hence the attacker has no advantage in predicting future (or previous) outputs.

Of course, if the PRNG starts off with no entropy (fixed key and state), and doesn't get enough entropy before the attacker observes the output, the attacker can easily recover the state (and predict outputs); this is true for any PRNG.  What is special about X9.31 with a fixed key is that this also holds even if the state has been given enough entropy.


Are the signcryption and the authenticated encryption same?

Your finding is correct. From your links;

In cryptography, signcryption is a public-key primitive that simultaneously performs the functions of both digital signature and encryption.
Authenticated encryption (AE) and authenticated encryption with associated data (AEAD) are forms of encryption which simultaneously assure the confidentiality and authenticity of data.

The signing in signcryption is performed with the private key operation. This can provide non-repudation since only the owner of the private key can sign.
The authentication in AE is performed with a shared key between parties. This cannot provide non-repudation since both parties have the key. We can say that the authenticity is mutual.


Can I use the ChaCha core as a 256-bit to 256-bit one-way function?

ChaCha builds on a 512 bit permutation and then applies a feed-forward by xoring the input into the output. Without truncation, that feed forward is essential for one-way-ness.

We're going to build a one-way function that maps a 32 byte value x to another 32 byte value y.

Using truncated ChaCha including the feed-forward

Put the x into the 32 key part of the input, put the normal constant into the 16 constant part and put something public (e.g. a constant or perhaps some kind of tweak) into the 16 byte nonce/offset part. Compute ChaCha including the feed-forward. Take whichever 32 bytes of output you like as y.

Computing x given y implies being able to recover the ChaCha key from the key-stream.  So this is a secure one way function if ChaCha is a secure stream cipher.

Using truncated ChaCha without the feed-forward

Since you truncate the output to half the permutation size the feed-forward isn't strictly necessary for one-way-ness.

In practice it doesn't matter which 32 bytes of output you choose, but if you want a security reduction to ChaCha it does.

The idea behind the proof is that the attacker knows 32 bytes of the input: the nonce and the constant. So they can undo that part of the feed-forward. This means that if you choose only the part of the output that's xor-ed with the nonce/constant but not the part of the input that's xor-ed with the key, you can omit the xor while retaining a security proof that this is as strong as ChaCha itself.

This construction mirrors the construction of HSalsa, so you could call it HChaCha. One important issue here is that Salsa puts the key into different words than ChaCha, so you need to take different words from the output in HChaCha.

=> take words 0, 1, 2, 3, 12, 13, 14, 15 as output.

My recommendation is to use HChaCha instead of ChaCha. Same security, better performance.

One interesting modification is to use a different nonce for each call, functioning as a tweak. It probably doesn't gain you much, but shouldn't hurt either.


This is actually touching to the notion of "rotational cryptanalysis", except you're missing the rotation part.
We usually use (modular) "Addition" or "Add" instead of "Sum", Add-Rotate-Xor are the core functions used by the so-called "ARX"-based algorithms which nowadays constitute an important part of the "fastest" stream ciphers (See Salsa/Chacha20, or the more controversial Speck, etc.) and hash functions (Blake, etc) out there.
The main idea behind ARX ciphers is that (modular) addition is not associative with the rotate, nor the XOR operation, and thus are difficult to simplify. (Exactly what you're interested in here.)
However skipping the rotation part as you did in a ARX design is an issue because it has been shown that systems made only of additions and XOR are broken since they can be reworked from rightmost to leftmost bit. To see the gory details I'll refer you to this Paul & Prenel paper that explain why this is broken: https://eprint.iacr.org/2004/294.pdf
As you'll see in the linked paper, A(R)X construct are a pain to study because they do not have nice algebraic structure like AES, RSA or ECC, which sadly means that they are usually less anayzed. This is why some cryptographers believe it would be best to avoid ARX designs when designing new cipher and schemes, and we've seen cipher such as NORX or Gimli which are explicitly not-ARX designs.
Interestingly, using only Additions and Rotations, it is possible to emulate Xor, so the Xor can be removed in a "secure way" in ARX designs, unlike the rotation. (At the cost of a somewhat lower security bound though.)


Multiple attributes under shuffled differential privacy

The theorem in the paper you refer to only assumes that $\varepsilon<1$ because it simplifies the analysis & the proof — amplification happens regardless of the value of $\varepsilon$. If you look closer at the proof (page 10), you can find a tighter formula: the result holds for any $\varepsilon$ and $\delta$ such that $\mathbb{P}\left[\frac{N_1}{N_2}\geq e^\varepsilon\right]\le\delta$, where $N_1$ and $N_2$ are independent variables sampled from $\text{Bin}\left(n-1,\frac{\gamma}{k}\right)$.
If, instead of bounding that quantity using Chernoff bound and assumptions on $\varepsilon$, you estimate it numerically, you obtain much smaller values of $\varepsilon$ and $\delta$, which show that amplification happens regardless of the value of $\varepsilon$. In a paper I co-authored, we do exactly that; the problem is different but the math ends up being the same. This is Theorem 3, you can see the comparison between the closed-form formula and the numeric estimation on Figure 2.


If you are doing an ECDH key agreement $[a]B = [b]A = [ab]G$, you should be hashing the ECDH shared secret to derive a key $k = H([ab]G)$ anyway instead of using $[ab]G$ directly, for various reasons.  More than that, you should hash the transcript of the key agreement in too, giving $k = H([ab]G, A, B, \mathit{etc.})$.  Here $H$ might be SHA-256 or HKDF-SHA256 or BLAKE2b, with inputs encoded uniquely so that two transcripts can't collide.

The same goes for essentially any fancy mathematical magic for agreeing on an element of a fancy mathemagical structure, so it applies to SIDH too.  It doesn't really matter much whether you do $H(\mathit{ecdh}, \mathit{sidh}, \mathit{transcript})$ or $H\bigl(2, H(0, \mathit{ecdh}, \mathit{transcript}), H(1, \mathit{sidh}, \mathit{transcript})\bigr)$, where $\mathit{ecdh}$ and $\mathit{sidh}$ are the mathemagical elements you summoned from the ECDH and SIDH spells.  What matters is mainly that you encode all of the inputs to the hashes uniquely and label each hash input uniquely with its purpose in the protocol (done here using fixed-width numbers 0, 1, 2, but could be done using, say, length-delimited strings).


Common password derivation function for different encryption methods

First, consider dropping bcrypt, because of its output limitations. If you are concerned about GPUs and ASICs, there's always scrypt. If you decide to go with bcrypt, you won't have 256-bit security with AES-256 and will need to pad the key somehow or disallow that combination.

I would simply call the KDF with a constant 256-bit output, which matches the blocksize of SHA-256-HMAC if you use that as PBKDF2 PRF (so it's ~ as fast as shorter outputs).
Then you can truncate the input of AES-128 to 128 bits and 3DES to 168 bits, which is what PBKDF2 would do anyway.


Is it possible to get different plaintexts from a single ciphertext using different keys?

How can I be sure that the plaintext obtained is in fact the one previously encrypted if I can't trust the source from which I get the key and the ciphertext?

In general you cannot. The standard security notions of do not imply any binding. I.e., the definitions do not rule out that, given a key $k$ and a ciphertext $c \gets \operatorname{Enc}(k,m)$ an attacker might be able to find a key $k'$, such that $m' = \operatorname{Dec}(k',c)$ for some $m' \neq m$.
In fact, for many encryption schemes, such as block ciphers in some non-authenticated mode of operation, or a stream-cipher this is always possible, since decryption will always succeed with any key. What differs between different schemes is how much control an attacker may have over $m'$. But for many schemes some control, such as ensuring that a few bits have specific values is certainly possible.

Opening an encryption scheme to a different value than was originally encrypted is called equivocation. The one-time pad as described by AleksanderRas is an extreme of an equivocal encryption scheme, being *fully equivocal.
I.e., for any ciphertext $c$ and any plaintext $m'$ it is possible to find a key $k'$, such that $\operatorname{Dec}(k',c)=m'$. Being equivocal is in fact a useful property of an encryption scheme in applications such as secure multi-party computation. However, being fully equivocal actually implies the scheme must
necessarily have a key size which is as large as the message size. There are relaxed notions of somewhere equivocal and non-committing encryption.

That name of that last notion brings us to the fact that you do in fact want your encryption scheme to not be equivocal. The opposite of an equivocal encryption scheme would be a committing encryption scheme, where the ciphertext serves as a commitment to the plaintext.

At this point your question and in particular the "key-exchange" tag lead me to believe that you are probably not actually looking for an encryption scheme, but a commitment scheme. A commitment scheme allows one party to commit to a message $m$ in a commitment $c \gets \operatorname{Com}(m;r)$. Such a commitment can later be opened usually by revealing the randomness $r$ used in the commitment.

A commitment scheme has two important properties:

It is hiding, meaning that $c$ reveals nothing about $m$.
It is binding, meaning that it is infeasible to equivocate, i.e., to open the commitment $c$ to a message $m'\neq m$.


Is it ok to store the plaintext hash of encrypted data

This will be less secure than storing only the encrypted data or storing also the hash of the encrypted data.

In your scenario, you give more options to an attacker, because it is possible to attack both the cryptosystem and the hash. For instance, think of an attacker that found a preimage attack to the hash...

Moreover, since the hash is deterministic, it allows some kinds of inference attacks, because if two stored hashs $h_1$ and $h_2$ are equal, then, they are probably hashs of the same message. This is the reason we use probabilistic encryption schemes.


What are the constraints for an IV using AES in CBC mode?

The IV for a block cipher in CBC mode must not only be "uniquely used for each message encrypted with the same key". It is usually assumed to be indistinguishable from random by an adversary.

If the IV is predictable, some attacks apply. For example, if an attacker is able to choose plaintext messages with prior knowledge of what the IV will be for this chosen plaintext, she can determine if a plaintext block in a previous message matches a guess; that's simply by submitting a message which first plaintext block is the exclusive-OR of that guess, the IV that will be used, and the ciphertext block preceding the block guessed (or the corresponding IV if the guessed block is the first block); then checking if the first ciphertext block for the chosen plaintext matches the ciphertext block for the guessed plaintext (there is a match if and only if the guess is right).

If I understand it correctly, the scheme proposed avoids transmission of the IV, replacing that IV with a (never transmitted) value obtained by enciphering a unique but predictable value, with AES and the same key as used as in the rest of the message.

This is not quite as good as a random IV. For example, an adversary temporarily gaining the capability to encipher blocks of her choice with the key (or equivalently, temporarily gaining the capability to dynamically choose plaintext blocks as a function of the previous ciphertext block within the same enciphered message) can use that capability to compute IVs that will be used in the future, in turn making it possible to verify guesses on messages encrypted after she had been denied that arbitrary block encipher capability, if she still has the capability to encipher chosen messages (having in-advance knowledge of the IVs, she proceeds just as outlined above in the regular CBC case). By contrast, with a truly random IV, the temporary possibility to encipher arbitrary blocks does not compromise the security of later messages.

Admittedly, the threat model I have been considering is quite hairy, and does not match the one usually assumed in the standard proof that CBC is IND-CPA (where the adversary has the capability to encipher arbitrary messages, but never to encipher arbitrary blocks). I fail to tell if the proposed scheme is IND-CPA, or not (that's an interesting question; an interesting variant would use decryption, rather than encryption, to prepare the IV).

Note 1: It is easy to make an implementation goof when trying to avoid reuse of a predictable value, especially if the key survives power loss.

Note 2: The scheme as described in the question does not insure integrity. That's a major practical issue.

Note 3: I fail to understand how the proposed scheme can be considered inefficient, and how "hash" crept into that consideration.


As a first note: No one would use RSA encryption to directly encrypt some (possibly large) plaintext message and RSA must not be used without a secure padding scheme  (see below in the "practical advice"). Anyways, lets look at it:

As I interpret it from your question, you suggest that you use RSA to encrypt a message $m$ interpreted as a string of characters? Then, for instance, an encoded message $k=12$ could either be $m=ab$ or $m=\ell$? You need an unambiguous encoding.

Edit

From your comment another interpretation is that you interpret your message $M$ as a string of $n$ characters $M=M_1\|\ldots\|M_n$ and treat every character $M_i$ as a single message and produce $n$ RSA ciphertexts. Issues:

Bad performance: Modular exponentiation produces non-negligible overhead and thus encrypting the message $M$ with this approach leads to $C=(C_1,\ldots,C_n)$ and costs $n$ RSA encryption operations (in comparison to a single one when encrypting $M$ as a single message - where I assume that $M$ fits into one integer of $Z_N$). Consequently, it also costs $n$ RSA decryption operations. Why should one do that?
One can efficiently do "trial encryptions" when using textbook RSA, i.e., without a secure padding scheme, to determine the message hidden when given a ciphertext, since textbook RSA is deterministic.
Apart from that, even if you use RSA-OAEP which provides IND-CCA2 security and thus non-malleability, i.e., modification of ciphertexts can be detected, in this scenario an adversary could simply drop/replace/reorder/insert any ciphertexts from/into $C$ and thus your so obtained construction does no longer provide non-malleability as single block RSA-OAEP does. However, this is a theoretical issue, since, as @fgrieu points out in his answer, public key encryption alone does not provide authenticity.

/Edit

What is done in practice is quite similar to your idea, but one interprets the entire encoded message (which is typically the result of some padding scheme) as an element of the set $Z_N=\{0,\ldots,N-1\}$, and one
uses standardized (unambiguous) encoding functions to map strings to elements of $Z_N$ and back. These are denoted as OS2I(octet string to integer) and
its inverse is denoted I2OS (integer to octet string).

For an encoding x=OS2I(M), one treats a string $M$ of $\ell$ octets, i.e., $M=M_{\ell-1}\|\ldots\|M_0$ (which you want to encrypt) as an integer $x$ in base 256 (each octet is interpreted as a non-negative integer to the base 256, where the leftmost bit is the most significant one). More precisely, one sets $x_i = M_i$ and thus

$x=x_{\ell-1}\cdot 256^{\ell-1}+\ldots+x_1\cdot 56+x_0$.

The inverse (which you call after decryption) then takes an integer $x$ and a lenght parameter $\ell$ and outputs an octet string $M$.

Practical Advice

Note that if your string $M$ you want to encrypt does not fit into $Z_N$ you need to divide it into blocks that fit into $Z_N$. But in practice no one would do so,
since RSA is used to encrypt only a very short key, e.g., 128 bits, that fits in one block (element of $Z_N$) and uses this key with a secure symmetric encryption scheme to
encrypt the (larger) message. This is what is caled hybrid encryption.

Furthermore, textbook RSA must never been used in practice for encryption and one should use standardized and secure versions of RSA
with appropriate padding schemes such as RSA-OAEP. Look for instance here. The above mentioned encoding is then applied to the padded message.


Or am I supposed to combine $f(r)$ with $h(r) \oplus b$ somehow?

Yes, $\text{Com}(b, r)$ is a function which "combines" them.  However it only "combines" them in the sense that it outputs the pair $f(r), h(r) \oplus b$
The main confusion here stems from not realizing that a tuple can be a perfectly valid singular output. (This is compounded by Boaz Barak writing the tuple without parentheses.)
From the lecture notes:

Definition 2 (Commitment schemes). A commitment scheme $Com$ is an unkeyed function
that takes two inputs: a plaintext $x ∈ \{0,1\}^n$
` and randomness $r$ chosen in $\{0,1\}^n$. The
idea is that to commit to the winner I let $x$ be my prediction, choose
$r \leftarrow_R \{0,1\}^n$
n and publish $y = Com(x, r)$. Later to prove I predicted $x$, I will publish $x$ and $r$.

(the notation is $r \leftarrow_R \{0,1\}^n$, but I'm not really sure what this actually means and it would be super helpful if someone could clarify what the notation means here!).

On page 3 of the notes, the author uses $R$ to indicate random. $\gets$ is assignment.
$\gets_R$ is used for uniform random assignment.
For more see this answer.


It's Hendrik Lenstra [to distinguish from Arjen Lenstra, both have worked on cryptography].

And, I am afraid I don't know how much the technical details in that article can be omitted, in the sense that only notation is defined and straightforward relationships are explored.

For example, clearly, a knapsack problem is exactly equivalent to an integer linear program.

And the problem finding integral points within a set, as on page 15, if one exists, is related to problems in more recent cryptographic structures such as those used in lattice based cryptography.


Regain 3DES ECB key, assuming I have both encrypted and decrypted text

It is not practically possible. There are several attacks that are slightly faster than bruteforcing $2^{112}$ key candidates, but this is only a small factor. In some sense, they are bruteforce-like, since they require $2^{113}$ smaller steps.


The standard way to prove this problem is at least as hard as the DLP problem is to show that, with an Oracle that can solve this problem, you can solve the DLP problem.

Here's how to do that (and we'll assume that the Oracle will solve random instances with nontrivial probability):

Given the DH problem $G^x = H$, find $x$, we pick random values $s_1, s_2, s_3, s_4$, and form the problem:

$$(G^{s_1})^{r_1} \cdot (G^{s_2})^{r_2} = (G^{s_3})^d \cdot (H^{s_4})$$

This is a random instance, and so the Oracle gives us, with nontrivial probability, values $r_1, r_2, d$, and so we know that:

$$s_1r_1 + s_2r_2 \equiv s_3d + xs_4 \pmod{p-1}$$

We know everything other than $x$ in the above equation, we solve it, and our work is done


ECIES is must with Symmetric?(ECIES-AES or ECIES-TDES)

Yes, ECIES is essentially a more practical implementation of ElGamal, a hybrid cryptosystem.  It uses symmetric encryption following an ephemeral key exchange.

Refer to : https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme

Compare it with : https://en.wikipedia.org/wiki/ElGamal_encryption

The only difference is that instead of using KDF+XOR or AES+GCM as the symmetric cipher, ElGamal specifies a different symmetric step mapping the message to a point and using inverse modulo to recover.

Once of the oddities is that using a KDF and then using XOR was the most popular version of ECIES for a number of years.   If used carefully, it's OK, but without properly padding the message, things can get ugly (chosen ciphertext attacks, etc.)

Ditching XOR and using AES/GCM with the shared secret seems, to me, like the better move, shifting responsibility for the authentication onto the symmetric layer.  The use of KDF/XOR is still prevalent in modern libraries, mostly because some XOR variants were FIPS certified.


Whenever you have two functions such that, for any X and any Y,
  X == S(P(X))
and also
  Y == P(S(Y)),
then
X and Y are bijective functions.

With modern secure communication systems, exactly the same plaintext message can be encrypted to many different ciphertext messages -- in particular, they are designed such that the message "attack" is unlikely to encrypt to the same ciphertext twice -- so therefore their "encryption" and "decryption" functions are not bijective.

Nevertheless, many classic ciphers are bijective, and often several of the parts inside a modern secure communication system are also bijective.

(The complete ciphertext message for a modern secure communication system typically begins with a random initialization vector or other nonce, has a "body" generated by some bijective function applied to the plaintext -- the particular bijective function is selected by a combination of the initialization vector and the encryption key -- and ends with a message authentication code.).

reciprocal ciphers

A cipher where P() and S() are not only bijective, but are the same function -- i.e., for any X, P(X) == S(X), and X == P(P(X)) -- is common, and known as a reciprocal cipher.

Some of the more famous reciprocal ciphers are:

The Enigma machine was a reciprocal cipher machine
ROT13
Beaufort cipher
Kama-sutra ciphers
XOR-based stream ciphers
One Time Pads (both XOR and Beaufort cipher versions)

Most mechanical cipher machines use a reciprocal cipher, so it wouldn't need a separate "encode mode" and "decode mode".

non-reciprocal bijective ciphers

Many classic ciphers are bijective, but not reciprocal: S(X) != P(X).

For example, the following ciphers are bijective but (usually) not reciprocal:

monoalphabetic substitution ciphers (except for Kama-sutra ciphers), and in particular the Caesar cipher (except for ROT13).
The standard Vigenère cipher, and the "variant Beaufort" cipher.
One Time Pads (the Vigenère cipher version)
transposition cipher (except for a few "paired-up" reciprocal transpositions)
permutation cipher

Practically all modern ciphers are based on either stream ciphers (RC4, A5/2, Solitaire cipher, etc.) or single-block ciphers (AES, DES, etc.), which are bijective but (almost always) not reciprocal.

Many modern single-block ciphers are built with a Feistel network structure that, in each round, cascades a reciprocal permutation E ("swap the left and right half of the block") and a keyed reciprocal substitution cipher U, to build a non-reciprocal bijective encryption function S(x) == E(U(X)) != P(X) = U(E(X).
It is widely believed that practically any non-linear function can give adequate security if it is iterated over enough rounds.

(Is it a coincidence that you used the names S() and P() that have the first letter of two common operations in cryptography, substitution and permutation, aka confusion and diffusion ?)

security

These bijective ciphers (both reciprocal and non-reciprocal) have a wide range of security, covering both ends of the spectrum:

Monoalphabetic substitution ciphers (aka cryptograms) published in newspapers as puzzles that are daily cracked by amateurs.
One-time pads which (in both reciprocal versions, and also the non-reciprocal version) are uncrackable.


Calculation of the order of the cosets used in defining the Tate Pairing

Try doing some examples. Sage (free and open source software) is very helpful here.

I think the simplest example is $E : y^2 = x^3 + 1$ over $\mathbf{F}_5$. This curve has embedding degree $k=2$.

sage: q = 5
sage: k = 2
sage: F.<z> = GF(5^2, modulus = x^2 + 2)
sage: E0 = EllipticCurve(GF(5), [0,1])
sage: E = EllipticCurve(F, [0,1])
sage: E0
Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 5
sage: E
Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field in x of size 5^2
sage: E0.order()
6
sage: E.order()
36

Here $E_0$ denotes the curve over $\mathbf{F}_5$, and $E$ denotes the curve over $\mathbf{F}_{25}$. (Sage distinguishes between these two objects, so you need different symbols for them.) We can take $r=3$; note that $r$ divides the order of $E_0(\mathbf{F}_5)$ exactly once, so the requirements are satisfied.

Let's list the points in $E(\mathbf{F}_{25})$:

sage: E.points()
[(0 : 1 : 0), (0 : 1 : 1), (0 : 4 : 1), (1 : 2*z : 1), (1 : 3*z : 1), (2 : 2 : 1), (2 : 3 : 1), (3 : z : 1), (3 : 4*z : 1), (4 : 0 : 1), (z : 2*z + 2 : 1), (z : 3*z + 3 : 1), (z + 2 : 2*z : 1), (z + 2 : 3*z : 1), (z + 3 : 0 : 1), (2*z + 1 : z : 1), (2*z + 1 : 4*z : 1), (2*z + 2 : 2*z + 2 : 1), (2*z + 2 : 3*z + 3 : 1), (2*z + 3 : 2*z + 2 : 1), (2*z + 3 : 3*z + 3 : 1), (2*z + 4 : 2 : 1), (2*z + 4 : 3 : 1), (3*z + 1 : z : 1), (3*z + 1 : 4*z : 1), (3*z + 2 : 2*z + 3 : 1), (3*z + 2 : 3*z + 2 : 1), (3*z + 3 : 2*z + 3 : 1), (3*z + 3 : 3*z + 2 : 1), (3*z + 4 : 2 : 1), (3*z + 4 : 3 : 1), (4*z : 2*z + 3 : 1), (4*z : 3*z + 2 : 1), (4*z + 2 : 2*z : 1), (4*z + 2 : 3*z : 1), (4*z + 3 : 0 : 1)]

Let's find their orders:

sage: max([P.order() for P in E.points()])
6

This last computation indicates that the maximum order of any single point in $E(\mathbf{F}_{25})$ is 6, even though the order of $E(\mathbf{F}_{25})$ itself is 36. Hopefully you know enough group theory to understand how this is possible; if not, you should review your group theory.

Let's pick a point in $E(\mathbf{F}_{25})$ of order 6. By trial and error, I find:

sage: P = E(3,z)
sage: P
(3 : z : 1)
sage: P.order()
6

Let's multiply $P$ by $h$ and see what happens (note that I have to convert $h$ from a rational number to an integer in order to do the multiplication):

sage: r = 3
sage: h = Integer(E.order()/r^2)
sage: h
4
sage: h*P
(1 : 2*z : 1)
sage: (h*P).order()
3
sage: (h*P).order() == r
True

We see that the order of $hP$ equals $r$, as expected.

Let's compute the "coset" $rE(\mathbf{F}_{25})$. Note that we convert the list of points to a dictionary and back to a list to remove duplicates:

sage: list(dict.fromkeys([r*P for P in E.points()]))
[(4 : 0 : 1), (0 : 1 : 0), (z + 3 : 0 : 1), (4*z + 3 : 0 : 1)]

Note this coset contains the point at infinity $(0:1:0)$, as claimed. Of course, this coset has $h=4$ elements, as expected:

sage: len(list(dict.fromkeys([r*P for P in E.points()]))) == h
True

I haven't answered any of your theoretical questions in your post. This is very much intentional. If you understand enough examples, the theory is obvious. If you don't understand examples, then no amount of theory knowledge will help you. Do not focus overly on the theory. Please, work with lots and lots of examples. Understand those examples and understand them well. Then, if you still have questions, ask your questions using examples to illustrate your questions. There is no shortcut to enlightenment. You MUST work with examples.


There is no "fresh client" with HOTP. The whole counter business is based on the idea that there is a single client, who maintains his counter which is more-or-less synchronized with the server counter. The synchronization window is just a way to cope with small unsynchronization events which come from realistic situations (e.g. your 3-year-old played with your car keys and pushed the "unlock button" a few dozen times).

If you want several clients, each client has his own counter, and the server must maintain one counter per client.


Encrypt text message with Wireguard public key

Wireguard is not PGP. In particular, Wireguard doesn't do several things that PGP does, because doing those things is very difficult to do securely. One of those things is encrypting anything with a public key: Wireguard only does elliptic-curve Diffie-Hellman key agreement.

In general, you should never encrypt a message with asymmetric cryptography (public/private keys) directly. You should either use a Key Encapsulation Mode (KEM), or a Diffie-Hellman style key agreement exchange (probably elliptic-curve based). You then use the resulting shared secret key to encrypt messages using an Authenticated Encryption with Associated Data (AEAD) symmetric cipher, like AES-GCM or ChaCha20-Poly1305 (Wireguard does this).

Asymmetric cryptography is good for key exchange, either with a KEM or a DH agreement. It's also good for signing and verification of messages. It's not good for encryption.


What is difference between PRG, PRF, and PRP

A Pseudo Random Function is a function that is indistinguishable from a function selected at random from the set of all functions with the same domain and value set. A Pseudo Random Permutation is, similarly, a bijective function that is indistinguishable from a bijective function selected at random from the set of all bijective functions over the same domain. For instance, a cryptographically secure block cipher parametrized by a secret key is a PRP.

The term PRG is otoh most commonly used for stateful functions that are used for generating successive pseudo random strings, e.g. to be used as a key, iv, salt, nonce etc.


Storing AES encrypted RSA private keys on a server

Given that you used a strong password to derive the AES encryption key: Yes you could securely store your RSA private key in encrypted form on a server. BUT, since there is no technical need to have your private key on the server, why would you risk it?

Look at it that way: Suppose you have very sensible data (like private photos or so). Now you could encrypt it with a strong algorithm and password and send it to all your friends, knowing that no one would be able to to decrypt it. Anyways, I personally would still not do that. Even if I trust the encryption, I would not unnecessarily give encrypted data to someone else for no good reason.


Universal Circuits in Indistinguishability Obfuscation Candidate Construction

As @D.W. guessed, the branching program for a circuit essentially reveals the original circuit.  It's not clear what you mean by "apply the whole obfuscation process to the circuit-revealing branching program," but the prospects for that do not seem good: evaluating the branching program is highly sequential (polynomial depth), and you would need to obfuscate that procedure.  In all, you've reduced the goal of "obfuscate a log-depth circuit" to "obfuscate a poly-depth circuit" – that's negative progress!

By contrast, the universal circuit has a fixed branching program, so it obviously reveals nothing about the circuit to be obfuscated (except an upper bound on its size).  Also, the UC's input (the circuit to be obfuscated) is "concealed" by the multilinear map.


Well, I went and solved the puzzle using brute force and Maple.  I won't spoil the actual answer, but here are some tips that ought to make the process a bit more quicker.

Solving the linear system modulo 2 gives you the parity of the second and third letters of the unknown plaintext.  Note that all vowels in the English alphabet map to even numbers using the standard Hill cipher encoding!
Conversely, solving the system modulo 13 tells you the fourth letter of the unknown plaintext (up to rot13).  This, together with the mod 2 solution, should help you guess what the second and third letters could be.
Even after correctly guessing the second and third letters, and ruling out any non-invertible decoding matrices, the modulo 2 solution will still not be fully determined.  Thus, some brute force and/or guesswork will be required to decode the remaining letters.  Hopefully, however, one of the possible plaintexts will show up as obviously more plausible than the others.

Ps. One more hint: 007.


How secure is Firestore / Google Cloud server-side encryption?

Server-side encryption means that the servers, owned by Google and running in a datacenter rented or owned by them, has access to the encryption keys when you log in. Compare this with client-side encryption, where only the client has access to the key and the server reads and writes opaque ciphertext. So yes, a corrupt sysadmin or someone with sufficient access to the server your data is stored on would potentially be able to obtain the encryption key and plaintext data.


Which one is faster GCM AES-128 or Curve25519?

You are not just using Curve25519. You are using a Python wrapper to NaCl, which is a high level crypto library that uses Curve25519 for Diffie-Hellman computation to derive a secret value. This secret is then used to encrypt with a particular algorithm, defaulting to Salsa20/Poly1305. So this library performs hybrid cryptography, where the data itself is encrypted with a fast, authenticated stream cipher. Although functionally the API is high level, execution certainly isn't: it's a highly focused, minimal implementation that is focused on both speed and security.

The cryptography library on the other part uses OpenSSL to speed up AES-GCM implementations. If a high enough OpenSSL library is used then AES-NI as well as CMUL for the GMAC operations should be available on high end CPU's that support it. However, it is completely possible to use an older library or one that isn't compiled for AES-NI. OpenSSL is an old generic library that may also have some more overhead; it isn't targeted forspeed in the same way that NaCL is.

If you have larger messages then the speed difference is simply due to speed differences in implementation of Salsa20/Poly1305 and AES in GCM mode. Salsa20 is a fast stream cipher, while GCM mode can generally be accelerated by hardware.

Beware that testing for speed is particularly tricky, especially on higher level languages. Differences in startup time of the compiler parser may already influence the results. You need a loop for the startup time and a loop for the testing. Both loops should contain the algorithm.

Also note that the random number generation may be pretty different on each platform.


Is it overkill to run a key generated by OpenSSL through pbkdf2?

PBKDF2 is designed for low-entropy passwords. Assuming your key is generated by a CSPRNG, then running it through PBKDF2 is redundant.  I don't, however, believe it could be weaker than the original key.


Given the first half of a SHA-1 hash, can you predict the second half?

Not without knowing anything about the message.

Each 32-bit word of the hash is a function of the current state plus one 32-bit word of the expanded message.

If the message is longer than 448 bits (512-bit block less 64 bits for length) then you would also need to know the output of the previous block, since it gets added to the output of the current block.


You are confusing the prime $p$ over which the curve is defined (the coordinate of the points are all defined mod $p$) with the prime $q$ which is the curve cardinality and is also prime.

We have $qG = G + \ldots + G = \infty$ the neutral element (like $0$ with the addition with numbers).

Taking your example, you have: $T_1 = (p+5)G$ and $T_2 = 5G$. Of course it is not the same since $p + 5 \not\equiv 5 \bmod q$.

You will find the value $q$ somewhere in the parameters of the curve and if you replace $p$ with $q$, the equality will hold.


As @fgrieu said [here], cryptography is usually not implemented in PHP. The best you can hope for is a binding/wrapper:

Search "php crypto binding" on Google

Unfortunately because pairings are not widely used in practice it is unlikely that you find them in major bindings, and although there are many bindings/wrappers listed on PBC website I don't see any for PHP.

Again agreeing with @fgrieu, this can be the opportunity to learn C++. Libraries like PBC (but also the RELIC toolkit) provide a rather "high-level" abstraction of pairings so you can use pairings with a few simple lines of C++.

Did you follow the PBC manual? It really takes you by the hand, if you need a basic use of pairings this should really suffice.

The RELIC toolkit does not have such a "beginner-friendly" tutorial but it is maintained (unlike PBC) and I find it nicer overall. To learn how to use RELIC you will have to read the test suite:

https://github.com/relic-toolkit/relic/blob/master/test/test_pp.c

If you decide to learn the use of PBC or RELIC (or MIRACL) and have questions about their use I think (community, correct me?) you might want to post question stackoverflow instead.


Designing of Password Authenticated Key Exchange (PAKE) Schemes?

The definition of PAKE just suggests that one or more parties are exchanging keys with knowledge of a shared password that authenticates the exchanged key. There are definitely use-cases of PAKEs that extend beyond, say, a web application authentication process that requires registration. For example, there could exist two or more embedded systems with shared passwords built into the firmware during manufacturing but these systems want to exchange fresh keys for communication. There are PAKEs that do cover registration (e.g. SRP), but the "definition" of a PAKE does not really require a specification for a registration process.

Personally, I think PAKE authors should specify a password bootstrapping process, if possible! It could prevent implementors from rolling-their-own protocol extensions.


how to choose a random secret key for ECDH

What curve are you considering, in what field, using what addition formulas?

From the data you provided, I assume you are talking about the curve of the form $y^2 = x^3 +  24x + 13$, in the field $\mathbb{Z}_{29}$ of the integer modulo $29$, because then your generator $G=(1,3)$ is effectively on the curve:
$$1 + 24+ 13 \equiv 9=3^2 \pmod{29}.$$
And the public points you computed, $(19,7)$ and $(15,6)$ are effectively on the curve and correspond to the correct values.

Now, simple addition formulas for such a curve would be, given two points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$,  that we sum together into $R=(x_3,y_3)=P+Q$:
$$ x_3= \left(\frac{y_2-y_1}{x_2-x_1}\right)^2-x_1-x_2 $$
$$ y_3=-y_1+\left(\frac{y_2-y_1}{x_2-x_1}\right)(x_1-x_3) $$
But those are not always working, most notably not if $x_1=x_2$, so we need another formula for point doubling, given $P=(x_1,y_1)$ and $R=(x_2,y_2)=2P$, we have that:
$$ x_2=\left(\frac{3x_1^2+24}{2y_1}\right)^2 -2x_1  $$
$$ y_2=\left(\frac{3x_1^2+24}{2y_1}\right)(x_1-x_2)-y_1$$
and even this would only work if $y_1\neq 0$.
Remark that on that regard, Wikipedia currently forgets to precise that there are such cases where the formulas cannot be used.

Now, you have a mistake in your latest computation: you want to take $P_A=(19,7)$ and multiply by 7 using those two formulas, so:
$$\begin{align}
2P_A&=(4,17)
&\text{doubling}\\
3P_A&=2P_A+P_A=(0,19)
&\text{addition}\\
4P_A&=2(2P_A)=(1,3)
&\text{doubling}\\
7P_A&=4P_A+3P_A=(23,1)
&\text{addition}\end{align}$$

So as you can see, $7(19,7)\neq\mathcal{O}$ as you computed, but it really works and is equal to $(23,1)$.

Note that there exist complete formulas for such curves, see for example this paper, so that you can have just one formulas to do everything.


Has a SHA256 output ever been found consisting entirely of the same character?

If any filtering criterion on the output of SHA-256 (with its definition independent of SHA-256 internals) leaves $n$ possible values out of $2^{256}$, then as far as we know,

the best method to exhibit an input to SHA-256 matching that criterion involves trying distinct inputs;
the expected number of hashes (compressions) required for this is $2^{256}/n$;
the $n$ outputs are equiprobable, thus the entropy of the process generating SHA-256 hashes passing that criterion from random input is $\log_2(n)$ bit/output, or $n\log_2(n)2^{-256}$ bit/input.

An output consisting purely of one character is such a criterion, with $n=16$ if we read character as hexadecimal digit. It is expected that $2^{252}$ hashes would be necessary to achieve that. Based on blockchain statistics (currently $7\cdot10^{18}$ SHA-256d per second), I guestimate that less than $2^{95}$ SHA-256 hashes have been performed by mankind; thus, with overwhelming odds, nothing giving a hash passing said criteria was ever hashed. Our best estimate of the theoretical entropy rate of this process is $4$ bit/output, or $2^{-250}$ bit/input.

I do not see how the input values found by bitcoin mining could be of any use in the study of SHA-256.


Privacy-Preserving relational databases: checking the existence of a record (or multiple records)

The computational assumption is a 2-message scheme that is PIR with

respect to the client<-server message and can easily handle databases in

which the number of entries is small but the entries themselves are large.

I'll describe a candidate for that, followed by how it can be applied for your use-case.

Notation Alert:

"s" is not really related to "Server"; I'm just following the paper that I link to for the sort-of-PIR scheme.

The suggested sort-of-PIR scheme is the following:

User U generates an RSA key-pair with modulus N, sends the public key

to the server, and stores the key-pair, with the private-key kept private.

For a desired index i out of B possible entries each of which are less than N^s,

the user sends the server a list of B ciphertexts such that the i-th is

an encryption of 1 and the others are all encryptions of 0 (page 8).

The server computes its response as the product modulo N^(s+1) of the

[corresponding database entry]-th powers of the ciphertexts in the list.

That response will decrypt (as described in that link,

not with the usual RSA decryption) to the i-th entry of the database.

On key-pair reuse:

Whether or not key-pairs can be reused is a non-trivial issue.

Since the encryption is public-key, an adversary could generate the ciphertext tuples

on its own, so that can only be a problem insofar as a server chooses its responses

maliciously and [can learn and/or wants to manipulate] the user's outputs.

Since the encryption is additively homomorphic, the flipside of that coin is that it is additively malleable.

However, I do not see any attacks on key-pair reuse that do not follow from that malleability

and/or replaying ciphertexts. $\:$ Thus, I think this is just a question of security vs efficiency.

The simplest way to apply the sort-of-PIR scheme for your use-case:

Either a base B was hard-coded into the protocol, or the user chooses it and sends it to the server for each protocol execution. $\:$ The user does whatever may be necessary regarding (the) key-pair(s), converts the id to base B, generates a list of sort-of-PIR initial messages with desired entries equal to the corresponding base-B digits, and sends that to the server. $\:$ The server sorts the set of ids and might also want to explicitly convert them to base B. $\:$ (Those might be doable offline, and even if it doesn't do the latter, "ids starting with" still refers to their base-B representation.) $\:$ Starting with partialid equal to the empty string, the server recursively does the following: if there are no ids starting with partialid then return 0, else if some id is equal to partialid return 1, else get the B results returned by running this procedure

on the B ways to extend partialid by one base-B digit, use those as the database for the sort-of-PIR

with the User's initial message corresponding to the length of partialid, and return the response given

by the sort-of-PIR scheme. $\:$ The server then sends the result of that recursive procedure to the client.

Finally, the client gets its output by decrypting with its private key(s in order)

a number of times equal to the length of (2^256)-1 in base B.

Improving efficiency:

One can use a mixed-radix system. $\:$ One can skip [Client's initial and Server's final] one or more uses of the sort-of-PIR scheme, to trade off client<-server communication for client->server communication.

One should notice that the simple way, even with the modifications mentioned in the previous two sentences, directly supports actually retrieving records that are smaller than the (smallest) modulus,

by returning the record rather than returning 1 in the recursive procedure.

In fact, it can be used to retrieve longer records, by just using a higher length parameter.

One can trade that off for slightly improved efficiency, as follows: use the record-retrieving procedure

on slightly truncated ids, where the records are the sets of suffixes for those truncated ids.

One can do better at the cost of a small failure probability by using non-cryptographic

hashes of ids with separate chaining instead of slightly truncated ids with sets of suffixes.

In the massive-database very-small-error region, one may be able to improve on the previous sentence by using [truncations of k-wise almost-independent permutations of ids] with compressed

sparse bit arrays instead of non-cryptographic hashes of ids with separate chaining.

Queries containing a list of record ids:

One can apply Rijndael to the ids before doing anything else with them and split both the transformed list and the transformed database. $\:$ (That reduces the remaining range of ids in each part.)

For large enough lists, one might be confident-enough that the transformed ids from the list will be distributed uniformly-enough to allow one to most-of-the-time make not-much-more than that many queries to each part. $\:$ For very large lists, the effect of the reduction in the range of ids in each part might overcome however many more-than-average queries are needed to each part. $\:$ It may be worthwhile for the Users to have a small probability of unnecessarily moving queries between parts, as an attempt to hide when Rijndael happened to move too many of the actual ids they're interested in into the same part.

The thing I was wrong about in my "answer tomorrow" comment:

If you allow a(n exponentially) small probability of the user outputting failure, then the growth rates of communication complexity and client's computation with respect to the number of elements are both really hard to figure out, although I'm pretty sure they're at least logarithmic and at most polylogarithmic.

(That holds even if you require that the server be able to detect failure on its own.)


In general an application - a program that uses the token for cryptographic operations - is supposed to use CKU_USER, not CKU_SO.

The CKU_SO is supposed to be used by the security officer. Of course, the only way that the SO can generally communicate with the token is through some kind of management application - sometimes combined with an authentication device such as an external PIN pad connected to an HSM. And yes, usually it is possible to write a management application yourself; it is of course dubious at best to mix that into an application that uses the key material stored within the token (especially if you also integrate the login credentials).

And yes, the SO can generally set trust on certificates. The SO is responsible for making sure that they can be trusted after all.

There can be tokens where the trust cannot be set at all. For instance smart cards may have a specific PKCS#11 interface where no management operations are applicable whatsoever.


With HMAC, can an attacker recover the key, given many known plaintext/tag pairs?

No.  Assuming HMAC is secure against known-plaintext attacks (which is a plausible assumption), the key cannot be recovered.  This follows directly from the definition of a known-plaintext attack; if you could recover the key, you would have a successful known-plaintext attack on HMAC.


Secondary hash function utility, regarding data destruction?

Specifically, why should hash functions not be used for data clearing?

I take it you mean that we would overwrite the storage with output produced by feeding its sensitive contents to a hash function.  The problem then is that this output, being a function of the data you're overwriting, therefore provides information about that input.

In particular, it could be used to efficiently test hypotheses about the content of the overwritten data.  This is the same principle as password cracking; just like password hashes allow you to quickly test password guesses, the overwritten disk sectors' contents could perhaps be used to test whether the disk contained or not some specific data before being overwritten.

You may think that this sounds like a very unlikely attack, and you could well be right about that.  But why allow it in the first place?  Particularly when the alternative is simple enough: overwrite with random or pseudorandom data that has no correlation at all to the sensitive contents you're overwriting.


This cannot be a PRF in all cases, because in the edge case where K1 = K2, the output of F3 will be 0 for all x.


What's the truth about this "absolutely unbreakable" cipher?

I will go out on a limb here and say that it reeks of snake oil. I have seen the answer by @dirdi, but I am very skeptical. It is clear from the paper that the authors have almost no understanding of cryptography: they refer to algorithms used as DES, AES and RSA, and that quantum computers break them all.

We know that quantum computers only have quadratic speedup to break symmetric ciphers, to the best of everyone's knowledge. Also the reference to DES, AES and RSA together is very suspect. I quote: "Conventional cryptographic schemes based on DES, AES and RSA encode messages with public and private keys of short length." Huh???

There is no theoretical model for this, like one has for quantum computation (with all of the problems that exist there). Rather, it is more experimental in nature - and we know where that tends to end. Bottom line, this looks really bad and like a lot of other cases where people from other fields think that they can solve all of the world's hard cryptographic problems without knowing anything about cryptography.


Does the following equation hold in bilinear pairings?

No, not in general.
$g$ is posited to be a generator, and so (for any fixed $D$), we have $H(D) = g^b$, for some integer $b$ (which is hard to compute, but we're not going to have to compute it).
So, we have $e(H(D)g^a, g) = e(g^{a+b}, g)$.
If we move the $a$ exponent out, we then get $e(g^{1 + b/a}, g) = e( g \cdot g^{b/a}, g)^a$
Doing the same thing one the other side, we would get $e(H(D)g, g)^a = e(g \cdot g^b, g)^a$
It should be clear that these two terms are not (in general) identical.


Append data to authenticated ciphertext encrypted using a stream cipher

Well, no you can't (without rescanning the entire ciphertext), and you probably shouldn't anyways.

The xSalsa20 is the easy half - it is effectively in counter mode, and so it'd be easy to generate a few more bits out of the xSalsa20 to use to encrypt the additional data you're appending (and those additional bits wouldn't change to previous ciphertext bits).

The problem is with the Poly1305 half; it treats the ciphertext as polynomial coefficients (over $GF(2^{130}-5)$) and then evaluates that polynomial for a secret value of $x$ (and then adds a secret nonce-dependent factor) - if that's all it did, then it would be fairly easy to adjust the polynomial result to account for the additional bits (by subtracting out the secret constant term, multiplying by a power of $x$ if necessary, and then adding in the new bits and adding back the secret constant term).  However, it does one further step; it takes the output of the polynomial (which is a value between $0$ and $2^{130}-6$), and takes it mod $2^{128}$.  That means that, for (almost) any tag value, there are 4 possible values that the polynomial would evaluate to, which implies 4 possible tags that the extended polynomial would need to be (because those two higher bits modify the lower bits once we multiply it by $x$), and you have no idea which one it might be (without recomputing the polynomial from scratch.

Now, one could modify the initial Poly1305 implementation to save those two upper bits that the $\bmod 2^{128}$ operation scraps away (and leaking those would not give any advantage to an attacker); this would allow an efficient incremental update.  On the other hand, doing so might not be a great idea - if an adversary sees both ciphertexts (that is, the original and the extended version, both of which uses the same nonce), he can compute an explicit polynomial which has the secret value $x$ as a root - this allows him to recover a good guess of the value of $x$, and that would allow him to modify ciphertexts at will without being detected.

Because of this threat, I believe you really do want to change the nonce whenever you modify the ciphertext; that involves a full decryption and reencryption.


Not really worked with these kinds of schemes, but here's my viewpoint.

Write $w_i=H(ID_i)v_i$. The value $H(ID_i)$ is some fixed public value, so we can kind of forget about it. That is, if $v_i$ is uniformly random, then so is $w_i$.

Now the key is generated as $sk_i=msk+w_i\pmod{p}$. Since $w_i$ is uniformly random, this is simply a generalisation of the one-time pad. In other words, $sk_i$ reveals no information whatsoever about $msk$. Therefore however many times you repeat this, the user will still learn nothing about $msk$.