Prove that decryption in LWE based PK cryptosystem works correctly except with negligible probability

Denote the public key as $({\bf a}_i, a'_i)_{i=1}^m,$ with each "sample" in $\mathbb{F}_q^n \times \mathbb{F}_q,$ where $a'_i = \langle {\bf a}_i, {\bf s}\rangle + e_i$ with each $e_i \leftarrow D_e$ i.i.d. (guaranteed that $\sum_{i=1}^m e_i < q/4$ with overwhelming probability).

Consider an encryption of 0 given by $\mathsf{ct} = ({\bf u}, v)$ over the private random coins $(b_i)_{i=1}^m,$ where ${\bf u} = \sum_{i=1}^m b_i{\bf a}_i \in \mathbb{F}_q^n$ and $v = \sum_{i=1}^m b_ia'_i \in \mathbb{F}_q$

(You can consider the case of an encryption of 1, by just adding $\lceil q/2\rceil$ to $v,$ of course.)

The decryption algorithm applied to $\mathsf{ct} = ({\bf u}, v)$ will output 0, correctly, so long as $v - \langle {\bf u}, {\bf s}\rangle$ is closer to 0 than $q/2$; that is, if $|v - \langle {\bf u}, {\bf s}\rangle| < q/4.$

And $$v - \langle {\bf u}, {\bf s}\rangle = \sum_{i=1}^m b_ia'_i - \langle\sum_{i=1}^m b_i{\bf a}_i, {\bf s}\rangle$$
and since $a'_i = \langle {\bf a}_i, {\bf s}\rangle + e_i,$ we get that the above is then
$$... = \sum_{i=1}^m b_i\left(\langle {\bf a}_i, {\bf s}\rangle + e_i\right) - \langle\sum_{i=1}^m b_i{\bf a}_i, {\bf s}\rangle$$
$$= \sum_{i=1}^m b_i\langle {\bf a}_i, {\bf s}\rangle + \sum_{i=1}^m b_ie_i - \langle\sum_{i=1}^m b_i{\bf a}_i, {\bf s}\rangle$$
$$= \sum_{i=1}^m b_ie_i.$$

Since we are guaranteed (except with $\mathsf{negl}(n)$ probability..) that $\sum_{i=1}^m e_i < q/4,$ we conclude that $|v - \langle {\bf u}, {\bf s}\rangle| < q/4$ implying correctness of decrypting 0-bits. The proof for 1-bits is the same -- but you'd end up with $\sum_{i=1}^m b_ie_i + \lceil q/2\rceil$ at the end, so the result would be closer to $q/2$ than 0, again by the upper bound w.h.p. on sums of $m$ small errors that you started with.


Is it safe to use GZIP to avoid padding related attacks

You are basically using gzip to convey the length of the given message. As long as your implementation of AES-CBC is secure (e.g. by using a random IV) then the given scheme should be secure against padding oracle attacks. This is easy to prove as there is nothing that removes the padding from the plaintext.

CBC padding in general does not add any security to the block cipher mode. You could just pad with zero bytes if you already know the size of the plaintext. In that sense the scheme is safe as long as no information is leaked to an attacker after decryption. Note that using gzip may influence the size of the plaintext so you need to make sure an attacker cannot learn too much from the size of the ciphertext.

Your scheme is therefore safe if the attacker only has access to the ciphertext. In that case it does provide confidentiality.

So now for the bad news...

This does not mean that the data within the ciphertext container cannot be altered. As there is no cryptographically secure authentication tag present, an attacker could very well be able to change the ciphertext in a way that cannot be detected. So the application code that processes the decrypted data could still be fooled to leak information about the plain text.

In other words, although you have now successfully protected against padding oracle attacks, you haven't protected yourself against similar, active attacks on the ciphertext. Please add some kind of secure authentication tag. It is by far the best way to protect yourself against these kinds of active attacks.


How can the Stern's algorithm be used to attack McEliece?

Forgive me if I missed something.
Is $K$ a generator matrix? I believe yes, which means the original code is linear.
The translate of the original code by subtracting $y$ is a coset, sometimes called affine subspace. It has almost all the nice properties of a subspace.
In particular sums of elements of the translated code are codewords in the original code (characteristic two means sum is the same as difference).


What is the history of recommended RSA key sizes?

512 bits (rounded down from the 664 bits or 200 digits in the patent) was recommended from its conception in 1974 and throughout the 1980s. Indeed, 463 bits was considered sufficient in the mid-1990s for the RSA-140 challenge. Whether key strengths as low as 100 digits (330 bits) were ever used in the early 1980s embedded systems is unclear; but probable given the RSA-100 challenge of 1991.
RSA's recommended key size increased to 768 (user) or 1024 (enterprise) at some point in the late 1990s1 due to academic successes in breaking bit strengths leading up to 512 bits.
Current recommendations (SP 800-572) are now 2048 or 3072 bits, depending on interoperability requirements.
In practice, these key strengths do not smoothly match Moore's Law as each new key size requires overhauling embedded systems and resolving interoperability requirements. So the trend has been to pick a key size much larger than necessary until the risk of breaching occurs, then pick another key size much larger than necessary.
A coarse stepwise increase governed by infrastructure costs and collective public perception of key strength.
 1. Inferred from this RSA article and this (irritatingly uncited) Wikipedia section.
 2. A sister document of the PDF cited in the question.


Do perfect squares count as valid moduli for an RSA semi-prime?

There is a simple way to detect if a number is square because there is an efficient way to compute square roots.
This should not be a realistic threat as the chance of picking two $b$-bit primes uniformly at random and getting a match will be about $b(\log 2)/2^b$. Given that a broken random number generator that always returns the same value would cause this to happen, it should not be discounted as a threat. However many standards specify a minimum difference between $p$ and $q$ to block Fermat's difference of squares attack (e.g. ANSI X9.31) which should stop such moduli being generated. Moreover, if such moduli were generated, they would not function properly as RSA moduli as the decryption process would not work.


In RSA, exponents are small, so the encryption/decryption can be done quickly. Here, exponent is of the form $2^t$, where $t$ is very large. For example, consider RSA 2048 - exponents have at most 2048 bits. If you set $2^t=2048=2^{11}$, then to solve this puzzle one will need to do only 2048 squarings, roughly the same as you need to do a decryption in RSA. But if you set $t=2^{128}$, then one will need to do $2^{128}$ squarings, which is far outside from current computational powers.

But if you can factorize the number, then you know the order of the group and can reduce exponent modulo this order: $a^{2^t} = a^{2^t mod \phi(n)}$.

Similarity with RSA is that both problems are based on exponentiation in so-called "RSA" group (multiplication mod $pq$) and both used the fact that for an attacker the group order is unknown.

For choice of primes numbers I recommend to read the wiki article. In brief, the primes should have the same size in bits and each of the primes should be of the form $p=2q+1$, where $q$ is some another prime, to defend from Pollard's p-1 method. Also $p+1$ must also have large prime factors, to defend from Pollard's p+1 method. If you choose primes randomly of the form $p=2q+1$ then everything will be fine. Actually if you simply choose random primes of specified size (as done in the article) then chances that it is breakable are very negligible.


The answer is in what Apple means by "ephemeral session key". See the BlackHat session starting around 12:00 in.

The raw file encryption keys are wrapped with a ephemeral key when outside the SEP (Secure Enclave Processor), the actual key is never exposed to the normal application processor. The ephemeral keys are bound to the boot session of the phone.


Is there a problem with this non-ECDSA message signing?

The problem with this method is that it is insecure.  Anyone with Alice's public key can sign any message they want, by computing:

$e = hash(message)$

$J = eA$

This $J_x$ will verify correctly according to your verification procedure.


Lightweight cipher using only 8-bit operations

I second Richie Frame's observation that AES is an excellent choice. I'd use AES-128 in CTR mode, which has the advantage that decryption is the same as encryption (thus is as fast, contrary to some other modes).

Update: SPECK, considered in this other answer, is good if compactness or speed per encryption for narrow block size are the choice criteria. SPECK-32 can be competitive with AES from the standpoint of cycles/byte on a Z80 (as asked in the question) because the state fits in registers. But I doubt SPECK-128 can be competitive with AES from the standpoint of cycles/byte on a Z80, because the  multi-bit rotation and large number of rounds are going to be show stoppers; and the state has to be in memory.

AES is good on 8-bit CPU (especially if a wide block is desired) because

It has a natural implementation with as the only data transformations: XOR between octets, and lookup of two 256-octet tables. Contrary to many modern ciphers, no word rotation is needed, which is extremely desirable in the context, in which that would be slow even when using assembly.
With an implementation (still natural) separating derivation of round subkeys from encryption itself, speed for large data will be hard to beat, thanks to the carefully crafted structure of AES.
Typical C compilers can generate fair code, and optimization is relatively easy.
With the precaution of locating the two 256-octet tables on page boundaries, a natural implementation on a CPU without data cache (such as the Z80) will typically exhibits no data timing dependency (but I have seen small caches, e.g. 16-octet, in the read path of Flash memory).

As illustration, here is reference code:

// ezAES: Public domain AES-128 encryption.
// C99-conformant. Well suited to 8-bit CPUs.
// CAUTION: vulnerable to fault attacks and side-channels, including
// Differential Power Analysis, and possibly data cache timing attack.

// Data types
typedef unsigned char octet_t;      // 8-bit octet
typedef octet_t ezAESblk_t[16];     // AES data block
typedef octet_t ezAESkey_t[16];     // key for AES-128
typedef octet_t ezAESsks_t[11*16];  // subkeys for AES-128

// Sbox for encryption, FIPS-197 figure 7
static const octet_t ezAESs[256] = {
    0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0,
    0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,
    0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,
    0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,
    0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73,0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,
    0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,
    0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,
    0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16
    };

// Tabulation of (x<<1)^((x>>7)*0x1B)
static const octet_t ezAESt[256] = {
    0x00,0x02,0x04,0x06,0x08,0x0a,0x0c,0x0e,0x10,0x12,0x14,0x16,0x18,0x1a,0x1c,0x1e,0x20,0x22,0x24,0x26,0x28,0x2a,0x2c,0x2e,0x30,0x32,0x34,0x36,0x38,0x3a,0x3c,0x3e,
    0x40,0x42,0x44,0x46,0x48,0x4a,0x4c,0x4e,0x50,0x52,0x54,0x56,0x58,0x5a,0x5c,0x5e,0x60,0x62,0x64,0x66,0x68,0x6a,0x6c,0x6e,0x70,0x72,0x74,0x76,0x78,0x7a,0x7c,0x7e,
    0x80,0x82,0x84,0x86,0x88,0x8a,0x8c,0x8e,0x90,0x92,0x94,0x96,0x98,0x9a,0x9c,0x9e,0xa0,0xa2,0xa4,0xa6,0xa8,0xaa,0xac,0xae,0xb0,0xb2,0xb4,0xb6,0xb8,0xba,0xbc,0xbe,
    0xc0,0xc2,0xc4,0xc6,0xc8,0xca,0xcc,0xce,0xd0,0xd2,0xd4,0xd6,0xd8,0xda,0xdc,0xde,0xe0,0xe2,0xe4,0xe6,0xe8,0xea,0xec,0xee,0xf0,0xf2,0xf4,0xf6,0xf8,0xfa,0xfc,0xfe,
    0x1b,0x19,0x1f,0x1d,0x13,0x11,0x17,0x15,0x0b,0x09,0x0f,0x0d,0x03,0x01,0x07,0x05,0x3b,0x39,0x3f,0x3d,0x33,0x31,0x37,0x35,0x2b,0x29,0x2f,0x2d,0x23,0x21,0x27,0x25,
    0x5b,0x59,0x5f,0x5d,0x53,0x51,0x57,0x55,0x4b,0x49,0x4f,0x4d,0x43,0x41,0x47,0x45,0x7b,0x79,0x7f,0x7d,0x73,0x71,0x77,0x75,0x6b,0x69,0x6f,0x6d,0x63,0x61,0x67,0x65,
    0x9b,0x99,0x9f,0x9d,0x93,0x91,0x97,0x95,0x8b,0x89,0x8f,0x8d,0x83,0x81,0x87,0x85,0xbb,0xb9,0xbf,0xbd,0xb3,0xb1,0xb7,0xb5,0xab,0xa9,0xaf,0xad,0xa3,0xa1,0xa7,0xa5,
    0xdb,0xd9,0xdf,0xdd,0xd3,0xd1,0xd7,0xd5,0xcb,0xc9,0xcf,0xcd,0xc3,0xc1,0xc7,0xc5,0xfb,0xf9,0xff,0xfd,0xf3,0xf1,0xf7,0xf5,0xeb,0xe9,0xef,0xed,0xe3,0xe1,0xe7,0xe5
    };

// Round constants
static const octet_t ezAESr[10] = {
    0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x1b,0x36
    };

// encrypt one block
void ezAESenc
    (
          ezAESblk_t    oC, // ciphertext output
    const ezAESblk_t    iP, // plaintext input
    const ezAESsks_t    iS  // round subkeys
    ) {
    ezAESblk_t vB;          // current state of the block
    ezAESblk_t vT;          // temporary
    octet_t vn;

    // first AddRoundKey
    vn = 16;
    do {
        --vn;
        vB[vn] = iP[vn] ^ iS[vn];
    } while( vn!=0 );

    // round loop, started 10 times; exits with break in the middle of the last round
    for( ; ; ) {

        // ShiftRows and SubBytes, performed 10 times
        vT[ 0] = ezAESs[vB[ 0]]; vT[ 1] = ezAESs[vB[ 5]]; vT[ 2] = ezAESs[vB[10]]; vT[ 3] = ezAESs[vB[15]];
        vT[ 4] = ezAESs[vB[ 4]]; vT[ 5] = ezAESs[vB[ 9]]; vT[ 6] = ezAESs[vB[14]]; vT[ 7] = ezAESs[vB[ 3]];
        vT[ 8] = ezAESs[vB[ 8]]; vT[ 9] = ezAESs[vB[13]]; vT[10] = ezAESs[vB[ 2]]; vT[11] = ezAESs[vB[ 7]];
        vT[12] = ezAESs[vB[12]]; vT[13] = ezAESs[vB[ 1]]; vT[14] = ezAESs[vB[ 6]]; vT[15] = ezAESs[vB[11]];

        if ( (vn += 16)==10*16 )
            break;

        // MixColumns and AddRoundKey, performed 9 times
#define EZAESMA(x) \
    vB[x+2] = vT[x+0]^vT[x+1];                  /* 1 1 0 0 */               \
    vB[x+3] = vT[x+2]^vT[x+3];                  /* 0 0 1 1 */               \
    vB[x+0] = ezAESt[vB[x+2]]^vT[x+1]^vB[x+3]   /* 2 3 1 1 */ ^iS[x+0+vn];  \
    vB[x+2] ^= ezAESt[vB[x+3]]^vT[x+3]          /* 1 1 2 3 */ ^iS[x+2+vn];  \
    vB[x+3] = vT[x+1]^vT[x+2];                  /* 0 1 1 0 */               \
    vT[x+3] ^= vT[x+0];                         /* 1 0 0 1 */               \
    vB[x+1] = ezAESt[vB[x+3]]^vT[x+2]^vT[x+3]   /* 1 2 3 1 */ ^iS[x+1+vn];  \
    vB[x+3] ^= ezAESt[vT[x+3]]^vT[x+0]          /* 3 1 1 2 */ ^iS[x+3+vn];
        EZAESMA( 0)
        EZAESMA( 4)
        EZAESMA( 8)
        EZAESMA(12)
#undef EZAESMA
        // here the content of vT is immaterial
        }

    // last AddRoundKey
    vn = 16;
    do  {
        --vn;
        oC[vn] = vT[vn] ^ iS[10*16+vn];
    } while( vn!=0 );
}

// prepare round subkeys
void ezAESkey (
          ezAESsks_t    oS, // round subkeys output
    const ezAESkey_t    iK  // key input
    ) {
    octet_t vj, vk;

    // first subkey is the key
    vj = 16;
    do {
        --vj;
        oS[vj] = iK[vj];
    }
    while ( vj!=0 );

     // for each 4-octet word of each 10 other subkeys
    vk = 0;
    do  {
        if( (vj&15)==0 ) {
            oS[16+vj] = ezAESs[oS[13+vj]]^oS[  vj]^ezAESr[vk++];
            oS[17+vj] = ezAESs[oS[14+vj]]^oS[1+vj];
            oS[18+vj] = ezAESs[oS[15+vj]]^oS[2+vj];
            oS[19+vj] = ezAESs[oS[12+vj]]^oS[3+vj];
            }
        else {
            oS[16+vj] = oS[12+vj]^oS[  vj];
            oS[17+vj] = oS[13+vj]^oS[1+vj];
            oS[18+vj] = oS[14+vj]^oS[2+vj];
            oS[19+vj] = oS[15+vj]^oS[3+vj];
            }
    } while( ( vj += 4)!=10*16 );
}

// Minimal test and demo. Returns 0 for OK, 1 for error.
int ezAESchk(void) {
    // test values from FIPS-197 appendix C.1
    const ezAESkey_t key = {
        0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f
    };
    const ezAESblk_t plaintext = {
        0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff
    };
    const ezAESblk_t ciphertext = {
        0x69,0xc4,0xe0,0xd8,0x6a,0x7b,0x04,0x30,0xd8,0xcd,0xb7,0x80,0x70,0xb4,0xc5,0x5a
    };
    ezAESsks_t subkeys;
    ezAESblk_t result;
    octet_t j, r;

    // derive the round subkeys
    ezAESkey( subkeys, key );

    // encrypt
    ezAESenc( result, plaintext, subkeys );

    // compare result and known-good ciphertext
    for( j = r = 0; j<16; ++j)
        r |= result[j] ^ ciphertext[j];

    return r!=0;    // 0 for OK, 1 for error
};


Physical entropy source: How many bits entropy per byte is sufficent?

First, take note of my answer to the question Estimating bits of entropy. A key phrase therein:

  You'll never be able to look at a bitstream without knowing the distribution and say "there are X bits of entropy here."

The ent program doesn't know the distribution of the data it's looking at; instead it performs some statistical tests that any sufficiently-long random bitstream will pass with overwhelming probability. Here, I mean "pass" in the sense of having an "estimated entropy" near 8 bits per byte, which is exactly what truly random data has.

So,
$$\text{bitstream is random} \implies \text{bitstream passes ent}$$
is about all we can say. Thus the (hidden) premise of your post - namely that because ent claims your soundcard's data looks random, it actually is random - is faulty. ent cannot be used to determine whether data is actually random. As an example, if a program has a fixed output, that output's entropy is 0 bits; but ent will declare otherwise since it does not have this external knowledge.

This is probably unnecessarily pedantic, but cryptography is a subtle science, and I think we need to acknowledge the particulars.

With all of that out of the way, can you feed your soundcard data into the kernel's random pool? So long as you trust that the soundcard hasn't been tampered with and actually is reporting random data, sure! For multiple reasons:

The soundcard isn't the only source of random data, so even if it is somewhat predictable, oh well - as long as it's not a malicious privileged device
If you feed random data into the Linux kernel as non-root, it doesn't use that source to increase the "entropy counter" at all: so it may be that your soundcard will act as a random source anyways, but not necessarily be counted as "random" by the kernel (n.b.: the entropy counter is of dubious value, but I am mentioning this for completeness)
The Linux kernel mixes and stirs "random" sources before presentation; it already doesn't much trust the sources to be uniformly random, etc

So with these reasons in mind, throwing any data you'd like into the kernel's random pool should be safe, even if the data isn't great. The exception is data that is carefully crafted with potential knowledge of the other random sources, as explained in the above link, but such a malicious source is a non-issue for most folks.


Some general categories that come to mind:

Same functionalities from less extreme assumptions; in particular, from falsifiable ones. For example, the FE for Turing machines in GKPVZ requires SNARKs and extractable witness encryption, both of require less plausible "knowledge-type assumptions." See Gentry/Wichs
Or taking the above further: Succinct-ciphertext functional encryption without obfuscation. Obfuscation is likely to be slow in practice for a long time. Wouldn't it be nice if we could have, say, a practical, compact-ciphertext functional encryption scheme for P/poly from (say) the NTRU problem alone?
Stronger notions of security, directly. Currently, iO-based functional encryption schemes are proven selectively secure, boosted to full security by complexity leveraging, and then boosted to SIM security by De Caro et al's compiler. Being able to prove the strongest possible notions of FE security from 'first principles' would be nice.
Anath, et al defines a notion of delegatable functional encryption. It could be interesting to explore how far this can be taken in general.
Boneh, et al gives one example of a definition of function privacy for functional encryption. "Full" function privacy for all P/poly is impossible, since VBB cannot exist for all P/poly in the real world, but restricted notions may be possible for all functions (or 'full privacy' for restricted classes of functions)
(Disclaimer: my work) You could also consider functional encryption in a setting where the function is represented by, say, Java code: AFKLSZ


Computing power function with BGW scheme

The exact solution will depend on the specific setting you have in mind, but yes, it should be basically feasible. Suppose for example that Alice has a private input $a$, and Bob has a private $t$-bit input $b = b_0b_1\cdots b_{t-1}$ (the length $t$ is public; we always have to assume some public bound on the values of the parties anyway, whatever the protocol we plan to run).

A simple solution would be the following: Alice computes $a_i \gets a^{2^i}$ for $i=0$ to $t-1$. Then, both parties run any MPC protocol to securely compute $$\prod_{i=0}^{t-1} \left((a_i-1)\cdot b_i + 1\right) = \prod_{i=0}^{t-1} a_i^{b_i} = a^{\sum_i 2^i b_i} = a^b.$$

This requires $t$ secure multiplications and $t$ secure additions.

In this simple, setting where both parties hold one of the inputs (instead of, say, shares of the inputs),  you can also use the following natural ElGamal-based solution:

Alice encrypts her input with an ElGamal encryption scheme over a group of prime order $p$, and sends the ciphertext to Bob;
Bob can homomorphically compute an encryption of $a^b \bmod p$ from this ciphertext and sends it back to Alice;
Alice decrypts the result and get $a^b \bmod p$.

The protocol can be repeated multiple time with different primes $p_i$ until $\prod_i p_i > a^b$, and $a^b$ can then be reconstructed over the integers via CRT. There are a few details to take care of in this solution (e.g. if Alice's input is $0$, she would have to encrypt some arbitrary non-zero value instead, set her output to $0$, and ignore the content of the ciphertexts sent by Bob), but that should work.

There are alternative, more complex solutions that would be more suited in other scenarios (e.g. if $b$ is very large, and if the inputs are not known to each party but secretly shared between them, etc), see for example my paper on encryption switching, or this paper.


Reversing a hash of known hashing algorithm

The i'th byte of the digest is a function of this byte of the message, and the previous byte.

So, to recover the original message from the digest, we just work our ways across the message, recovering each byte in succession.

First, we need to recover the first byte of the message.  Because there is no previous byte of the message, the formula for the digest simplifies to:

digest[0] = ( (129 * message[0] ) % 256.

Question: since we know the value digest[0], how can we recover message[0],

Next, assume we know the first i bytes of the message, and now we're attempting to recover message[i].  We know the formula:

digest[i] = ( (129 * message[i]) XOR message[i-1]) % 256

And we know the values digest[i] and message[i-1]; how can we use this to recover message[i]?

One hint that may simplify things: if we have $A = 129 * B % 256$, then we also have $B = 129 * A % 256$; that's because $129 * 129 = 1 \pmod{256}$


This is a monoalphabetic substitution cipher - the same letter in the plaintext will always be represented as a identical letter in the ciphertext (for example the plaintext-letter "E" is always a "V" in the ciphertext).

Frequency analysis works better the longer the text is. For very short texts (as yours) it can be very difficult to have an exact representation of the frequency analysis. If the most occuring letter is not "E", then you can move on to the second-most common letter (which would be the letter "T")
Other / similar techniques:

Double-letter-words: Another technique you could try is to find all the words that have repeating letters, for your example that would be the last word "cheers". I think that in the English language the most common double-letter-words have 2 "L" in them, like "kill". But again this would fail, since here the double-letter-word is "cheers".

Word-frequency-analysis: You can also do a frequency analysis for whole words instead of single letters. Again, for the English language, this would be the word "the". For a long text you would expect that the word "the" would show up most often.

As you can see most of these common techniques would fail for your cipher-text. So the best technique you can use is brute-force.


Is Porticor's "homomorphic" key encryption something that can really be done or is it just marketing hype?

The details are very sparse as to what they are actually doing. So, I'll speculate. Below are some claims and what I think they are doing.

  The master key (in its plain unencrypted form) will be literally nowhere in the cloud, yet completely usable for split-key encryption.

Typically this is done using some sort of secret sharing, which doesn't necessarily mean homomorphic encryption (HE). That said, there are some advantages with using HE. Under typical secret sharing, the secret must be reconstructed at some point. With HE, that is no longer the case. Encryption and Decryption can be done homomorphically (see this and this). Timing results of both are promising and could be considered practical, especially for the first link.

  we only have an encrypted form of the master keys. In more technical words, the Porticor product will perform split-key encryption with a partially homomorphically encrypted master key.

This leads me to believe they are doing something similar to the two links above. They store an encrypted version of the master key and their management key (similar to the safe deposit box they describe), and use those to encrypt/decrypt data. Most likely they are doing something similar to the first link as the result of that encryption/decryption is plaintext where the result of the 2nd link is not plaintext but the plaintext encrypted with the homomorphic key.

Assuming I am correct (who knows though as they don't publish the details yet), I would say it is practical. Look at the timing results in that paper. At the same time, it is somewhat marketing hype. Sure "The master key (in its plain unencrypted form) will be literally nowhere in the cloud, yet completely usable for split-key encryption" but the data must be decrypted at some point and can be stolen at that point in time. Also, I'm not sure I'd trust my data being protected by such new techniques yet. The field of homomorphic encryption is such an unstable field right now.


Does hashing an encrypted message suffer from any drawbacks?

Your scheme is of course insecure against any active attacks. B or another man-in-the-middle can just change the data and then calculate a new hash. This is why you need a MAC instead of a hash. And it depends on the method of encryption / hash if hash-then-encrypt is safe.

If anybody proposes such schemes you should try and use an authenticated cipher such as GCM. That will however still leave you vulnerable to protocol errors, so while you're at it: use TLS.


Changing the IV of the AES key wrap algorithm

No, not really.

If you change the IV to a secret value, you prevent the attacker from checking that the key is correct by comparing to the IV, but they can still check by actually using the key. And if you make it a secret value, you need to pass it to the decryptor somehow, so it can be checked by the legitimate user.

If you choose another constant, Kerckhoffs' principle would suggest assuming the attacker knows it. E.g. if you used it in some server software and the attacker got access to your server they would see it.

There is no convincing security advantage to changing it at all. Its precise value does not affect the security of the key-wrap algorithm. The only reasons you would change it are those mentioned by NIST (pdf, 2.2.3.2), like to accommodate key-lengths that are not multiples of 64 bits (e.g. unpadded 3DES keys).


Can data stay encrypted unless I'm eliminated?

If your friends and the reporters can decrypt the data without any action from you, then even if you're alive they should be able decrypt. You could trust a certain threshold of them to not collude with each other unless they're certain you're dead, in which case secret sharing the key might work.

If you trust your parties to publish the secret material as soon as they can get it (and not destroy it), something like this might also work: suppose you hide the key in a certain location, encrypt the location such that breaking (brute-forcing) the encryption will take at least $t$ time given a large amount of computational power, and send the encrypted location to all the parties. Before $t$ time is up, you move the key to a new location, and again encrypt the location to all the parties. This way, even if you don't trust the parties to not collude, they will not be able to access it as long as you keep moving the key in time.


The order of the base point of Curve25519 is the a 253-bit integer $2^{252}+ 27742317777372353535851937790883648493$. Choosing as private key a random positive integer less than said order is a common choice in cryptosystems based on the difficulty of the Discrete Logarithm in some group. That might be why private keys are said to be 253-bit.

However, per comment: the set of Curve25519 secret keys is defined as those 32-byte bytestrings which, when converted to integer (per little-endian convention on top of the byte level), form a 255-bit integer $n\in2^{254}+8\{0,1,2,3,\dots,2^{251}-1\}$. That bytestring is 256 bits, among which 251 are variable, and 5 are set to predefined values (the 3 low-order bits and 2 high-order bits: these are zero, except the second-highest order bit). Nothing reasonably adds up to 253.

Note: that's not to be confused with the security level, believed to be comparable to 128-bit symmetric cryptography (best attack cost $2^{140}$ bit operations).

References:

Daniel J. Bernstein, Curve25519: new Diffie-Hellman speed record, in proceedings of PKC 2006
Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang: High-speed high-security signatures, in proceedings of CHES 2011 and JoCE 2012.


The Diffie-Hellman key exchange is performed in the device pairing phase with P-256 elliptic curve to generate a shared secret DHKey. The function $\texttt{f}_5$ is then used to derive the long-term keys LTK and MacKey from DHKey according to this equation:

MacKey || LTK = $\texttt{f}_5$ (DHKey, N_master, N_slave, BD_ADDR_master, BD_ADDR_slave)

where N_master is the random number sent by the master to the slave, N_slave is the random number sent by the slave to the master, BD_ADDR_master is the device address of the master and BD_ADDR_slave is the device address of the slave.

This is very similar to TLS, where a master secret is generated using Diffie-Hellman key exchange and then the individual encryption keys are derived from the master secret using symmetric primitives.


I understand that if a block cipher has $k$-bit keys and $n$-bit input/output blocks, then if $k>n$, we can expect one message-ciphertext pair to narrow us down (I think?) to $2^{k−n}$ possible keys, right?

That is approximately correct (if the block cipher with the wrong key acts like a random permutation; this is generally a safe assumption); if block "one message-ciphertext pair", you mean "a single $n$-bit plaintext/ciphertext block.

However, that's not necessarily what we mean by a "message-ciphertext pair".  We often want to encrypt messages that are larger than $n$ bits; to do this, we use a mode of operation (which uses the block cipher to encrypt larger messages); if we have a larger message (and we know the plaintext and the ciphertext of this larger message), then we usually (depending on the exact mode used) have a number of $n$-bit plaintext/ciphertext blocks.

The upshot of this is that if we have a $k$-bit message (and corresponding ciphertext), this is usually sufficient to allow us to recognize the key (with a possible 1 or 2 false hits; those can be eliminated if we take a message slightly larger than $k$ bits); if $k>n$, then we would get several plaintext/ciphertext pairs against the underlying block cipher


How is public key cryptography used for digital signature?

Aleksander's answer is very close, but there is one key difference between encrypting and signing a message.  When you create a digital signature, you are not encrypting the whole message.  The intent is only to validate that the message was indeed sent from you, not to prevent others from reading the message.

To sign a message, first a cryptographic hash is created.  This is a calculated string that provides a unique "fingerprint" for your message, that anyone can reproduce on the other end to validate that the message received is the same as the message sent.  This hash, rather than the message itself is what is first encrypted by the recipient's public key, then your private key, then it's appended along with the message as the signature and sent to the recipient.

The recipient must then use the sender's public key first, then their private key to decrypt the hash.  Once they have the received hash, the last step is to create their own hash of the message, and compare the two.  If the hashes match, the signature is valid, and everybody is happy!

Here's a great explanation: http://www.cs.utsa.edu/~bylander/cs1023/signature-encryption-example.html


Start with “Shamir's Secret Sharing” concepts…

  Abstract. In this paper we show how to divide data D into n pieces in such a way that D is easily reconstructable from any k pieces, but even complete knowledge of k - 1 pieces reveals absolutely no information about D. This technique enables the construction of robust key management schemes for cryptographic systems that can function securely and reliably even when misfortunes destroy half the pieces and security breaches expose all but one of the remaining pieces.

source: http://dl.acm.org

In a nutshell:

I have a secret $S$. Let's say $S=10$ (or a password turned into the value $10$), and I want to share it between $N=2$ people. I create a polynomial of degree $d=N-1$ (because I care to have a secret for two people):
$$f(x) = ax + b$$

We set $b = S$, and let $a$ be a random value larger than $S$ and $N$. For example, let's say $a=13$.

Therefore:

$$    f(1) = 13*1+10 = 23
\\    f(2) = 13*2+10 = 36
$$
Now, send $f(1)$ to person $1$, and $f(2)$ to person $2$. In order to obtain the secret $S$ and to unlock the door, both person $1$'s value and person $2$'s value are needed.

Using polynomial approximation, we can get the resulting $f(x)$ from the people values:
$$ f(x) = \sum_{i=1}^N f(i) \cdot
             \prod_{j\neq i} \frac{x-x_j}{x_i-x_j}
 = \sum_{i=1}^N f(i) \cdot
             \prod_{j\neq i} \frac{x-j}{i-j}
$$


Non interactive Zero Knowledge Proof for Satisfiability of Pairing Product Equations

I have read some part of above paper, definitely you can find implementations of such prover and verifier algorithms, even more complicated ones. For example, you can find implementations of prover and verifier in several zero-knowledge proofs in Libsnrak library.

By the way, you can also find implementation of Groth-Maller simulation-extractable zk-SNARK from Crypto 2017 in Libsnark that considers quite similar concept to the paper that you have mentioned.

I would also recommend to look at implementation of Pinocchio, a practical verifiable computation system, that has implementation of a prover and a verifier in a zero-knowledge SNARK that are particular type of none-interactive zero-knowledge proofs.


Avoiding replay attack on certified announcements

[let] the last 8 bytes be the HMAC(key, msg)

64 bits is a pretty small tag size, and not considered "cryptographically strong".  I would suggest using the full HMAC output if possible, or see here for some discussion of reduced tag length.

  should this scheme avoid replay attack?

Assuming that the HMAC cannot be broken (which would imply that the key is kept secure and a sufficient tag size is used), this scheme looks fine against replay attacks.

(I suggest opening a new question with regard to your key derivation scheme)


Do I need an IV to use AES-CTR as a CSPRNG?

When using counter mode you can start at any value, it doesn't matter.  The only important thing is that you never use the same counter value twice for the lifetime of the key.  So, as long as your key is actually random and, as you say, you don't use it for more than 1 MB of data, then your generator should be fine.


While you do operate block-by-block when generating the pseudorandom stream, the actual encryption step (i.e., the XOR) is bitwise, and therefore does not require the message to be padded.

For example, the message "Hello" will be processed as follows (pseudocode):

byte stream[16] = AES(Key, Nonce);
byte plaintext[5]  = "Hello";
byte ciphertext[5];
for i from 0 to 5:
    ciphertext[i] = plaintext[i] XOR stream[i];

The remaining bytes of the pseudorandom stream, beyond the length of the message, are simply discarded.


Hash length extension attack - SHA256 to 512 - impossible, correct?

No, there is no known way.

It would actually be rather surprising if there were even a theoretical way; the SHA-256 and the SHA-512 compression functions are rather different (for one, one works with 32 bit words and the other works with 64 bit words); one wouldn't expect them to share any sort of relation.


Set/change password functionality on password: should I apply bcrypt server- or client-side?

Normally password hashing is done server side. It doesn't need to be, but if you use client-side password stretching there are a few things to be concerned about.

Your web clients will need to have javascript enabled. People may disable it for security, privacy  or accessibility reasons. Or because noscript browsing is more convenient. Or because they want to reduce battery drain.
Resource limitations - If the client doesn't have a high end computer then advanced password hashing might take longer than expected. Maybe their CPU is much slower than a desktop, laptop, or server. Maybe they don't have much RAM available. (For memory-hard password hash algorithms, which bcrypt isn't.)
Attacker/Defender Efficiency - Given the option to do server-side hashing with a native optimized implementation of a hash function or a client-side implementation in javascript the serverside implementation will be more efficient. Consider an algorithm running both client-side and server-side with the same parameters. Both do the same amount of work, but the server will finish first. To meet user demands for responsiveness you will lower the cost parameters of client-side hashing, compared to the cost parameters for server-side. This makes an offline password cracker's job easier if your password database does get breached.
If you do client-side password hashing then the salt needs to be known to anyone attempting to log in. This would allow attackers to use a pre-computation based attack against specific targets if they could anticipate stealing password hashes from the server.

Some people also add "A password hash is password-equivalent so client side hashing adds no security at all." This is good advice for people that think password hashing is an alternative to authenticated encryption (it isn't) but often people mistakenly use it as an argument to not do client side password-stretching. It's a bad argument because client- or server-side, you're still vulnerable to eavesdropping if you don't use encryption

One major advantage to client-side hashing is that it takes the burden of password stretching away from the server. To validate passwords the server needs to stretch every password submission it gets. (Ignoring successful brute-force prevention.) This could be exploited for a denial of service attack.

For desktop applications I might recommend client side hashing. (With end-to-end encryption with pinned server keys.)

If you use client-side password stretching then you SHOULD NOT store raw password hashes in your database. This would let anyone who stole a password-hash database to log in as any user without determining what their password was. Instead store a hash of the hash. As in something like $\text{SHA-512}(\text{bccrypt}(password, salt))$.

(Bcrypt would be done client-side and SHA-2 server-side. Normally plain-old-hashing of passwords is not secure, but hashing the hash is okay because the input has already been salted and stretched. People won't bypass the bcrypt part and go directly to searching for SHA-2 preimages because finding preimages would be a waste of time compared to guessing and hashing passwords.)

You said:

  I could verify on the server that bcrypt was applied with at least X (for example, 12) iterations.

Which leads me to believe you're misunderstanding something. It sounds like you want to hash both client-side and server-side.

First, that isn't possible unless you also have the original (plaintext) password. Second, that is a waste of effort, assuming you're testing $H(p) == H(p)$ not $H(H(p)) == \text{StoredHash}$. (The latter being splitting hash-stretching work between client and server. The former being redundant because both client and server do the same work.)

To verify that enough bcrypt rounds were used you only need to password-hash (using bcrypt) each new password once. Just hash the plaintext password server-side whenever an account's password is changed with the appropriate parameters. Then save that hash to use for password verification from that point on, for the remaining lifespan of that password.

Lastly, I think I should recommend against client-side hashing. Not because it's inherently bad, but because I think server-side hashing will be safer and easier to implement.

You also should be using argon2, which is designed to be costly by requiring both CPU and RAM resources. bcrypt requires small amounts of RAM and it's cost parameter is only used to alter CPU time. argon2 was the winner of the password hashing competition.

If you're using PHP consider using the built-in password hashing API, whether you use bcrypt or argon2. It supports both algorithms, takes care of salt generation for you, and is a very simple API.


Building adversary to show a PRF is not secure

Query $0^n$ to your oracle, receive $a\Vert b$ as a response.
If $F(b,0^n) = a$ output $1$, otherwise output $0$.

In the case that the oracle is $F'$, since $F'(k,x)$ is defined as $F(F(k,0^n),x)\Vert F(k,x)$ your response will be $a\Vert b = F(F(k,0^n),0^n)\Vert F(k,0^n) = F(k',0^n)\Vert k'$, it will always be true that $F(b,0^n) = a$. I.e.
$$\Pr_k[\mathcal{A}^{F'(k,\cdot)}(1^n)=1] = 1.$$

In the case that the oracle is a truly random function $g : \{0,1\}^n \times \{0,1\}^n  \to \{0,1\}^n$, $a$ is distributed uniformly and independently of $b$. Therefore the probability of $F(b,0^n) = a$ is $2^{-n}$. Thus,
$$\Pr_g[\mathcal{A}^{g(\cdot)}(1^n)=1] = 2^{-n}.$$

And therefore

$$\left|\Pr_k[\mathcal{A}^{F'(k,\cdot)}(1^n)=1]-\Pr_g[\mathcal{A}^{g(\cdot)}(1^n)=1]\right|=1-2^{-n},$$
which is clearly non-negligible.


Provable Lower Bounds for some Algorithmic Problems?

maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it

Even that limited goal is beyond what we can prove.  People have done studies on tiny functions (functions small enough that exhaustive search is possible); the difference between evaluating the function forward and backwards was surprisingly small.  One would hope that the difference becomes wider once the size of the function increases; however we can't prove it.

Does this question make sense?

Yes, it does (although, depending on how you define things, the $c \cdot 319557$ may be the time required to evaluate in the forward direction, rather than the number of bits); we just don't know the answer.
Now, the obvious question may be, if we can prove that comparison based sorting takes $\Omega(n \log n)$ operations, why can't we do anything analogous with inverting functions?  Well, with the comparison based sorting proof, the only information we allow the sorting algorithm about the relative order of elements is to call the Oracle, which returns a single bit each time.  And, we can prove that any sorting algorithm with that restriction must call the Oracle $\Omega(n \log n)$ times (because it needs to distinguish between $n!$ different sort orders), and hence must take at least $\Omega(n \log n)$ time.  However, that proof is valid only if we restrict the program in that way; sorting algorithms that don't abide by that restriction (e.g. radix sorting or interpolation sorting) can go faster.  And (the point I'm really trying to make) when we ask for a function to be inverted by any means, we don't require the program to use any sort of Oracle to get the information we need, hence the type of proof we used for comparison based sorting doesn't work.


I am trying to create a simple image encryptor in python result isnt promising

What you've done is this:-

It's called electronic code book style encryption.  For block cipher encryption read your own pixel transformation algorithm.  And for plain text, read original pixel values. Can you see the how the pattern repeats?  That's the length of your hashed password, and what's called the block width.  You've used it over and over again encrypting a block width's amount of pixels.  Because the background is constant white, it encrypts to the same value over and over.  And as the block width straddles the bike, it kinda still shows up against the constantly repeated background.

What you need to do it this:-

It's called cipher block chaining and creates a relationship between sequential blocks.  You'll have to adjust your algorithm so that one block's data is somehow propagated to the next one.  The traditional way (as illustrated) is to simply xor it. Now every subsequent block will be affected by the previous block and you'll get a much more random pattern.

You don't need the initialisation vector thing at the moment. You can address that later when your chaining algorithm works.  It's highly recommended though to stop relay attacks and leak encrypted information when you repeatedly transmit the same information (the cipher text will be identical each time suggesting the same information was sent).

Note.  It's also traditional to use a fairly complicated set of xor and bit shift operations to encrypt your information /image.  These would be inside the block cipher encryption box.  They create an avalanche effect so very small changes create massive ones.  You use just a shift operator.  I'm not 100% confident that a simple shift will not still show the bike's outline somewhat. Anyone?


RSA & DH at risk due to math advances, will this eventually affect elliptic curves too?

A couple things:

This article is two years old, so take its predictions with a grain of salt.
In the two years that have elapsed, the predicted advances have not materialized, and there is little indication they will soon.
The core of those arguments was Joux's 2013 result on the discrete logarithm problem in finite fields of small characteristic. Those methods do not directly apply to any standard cryptographic primitive like RSA or DH, and it is not known how to translate Joux's algorithm into an attack on these primitives. The underlying math is fundamentally different.
It's important to be cautious and conservative when choosing cryptographic primitives, but people have been predicting the death of RSA and DH for many years, and they've lasted this long.

Again, it's not known how to translate Joux's methods into a general-purpose algorithm for the discrete log problem in any other group. Thus, while it's possible for his attack to work in elliptic curve groups, there simply isn't any indication that this is the case.


What is the most practical fully homomorphic cryptosystem?

Bottom line. The short answer is that none of them are practical ... yet.  But there is a lot of active research, and if we're lucky, maybe that will lead to enough improvements that it might become practical.  We'll see.

More information. You can find some useful information at the following questions:

What Partial Homomorphic Encryption implementations exist and how do I leverage them? discusses some schemes that fall short of being fully homomorphic but are more practical and are enough to be useful in some settings.
In what ways does Full or Partial Homomorphic Encryption benefit the cloud? discusses applications of fully homormophic encryption and links to some papers that discuss the state-of-the-art and how practical the best schemes are.

These resources may be of interest:

Shai Halevi's Homomorphic Encryption Tutorial, presented at CRYPTO 2011.
Helger Lipmaa's collection of research papers on fully homomorphic encryption.

See also the following research papers:

Kristin Lauter and Michael Naehrig and Vinod Vaikuntanathan.  Can Homomorphic Encryption be Practical?
Jean-Sebastien Coron and David Naccache and Mehdi Tibouchi.  Optimization of Fully Homomorphic Encryption.
Marten van Dijk and Craig Gentry and Shai Halevi and Vinod Vaikuntanathan.  Fully Homomorphic Encryption over the Integers.
Damien Stehle and Ron Steinfeld.  Faster Fully Homomorphic Encryption.

This is a rapidly-evolving space, so anything I write here may become out of date quickly.  You will need to follow the research literature to learn the latest and greatest.


Can Diffie-Hellman be scaled up or force-multiplied?

Short Answer: Yes

Long Answer:
From what I understand about quantum computing, they are only more efficient as long as the bit-depth of the problem falls within the bit-processing capabilities of the quantum processor. Example: a 64-bit quantum processor could solve 64-bit traditional encryption keys in a near-zero real time. 128-bit keys would still take a very long time, as would 256-bit. 512-bit, 1024-bit and higher bit-depth encryption schemes. Even if quantum computers get much much much more powerful, it is fairly easy to scale the key size to an arbitrarily high number of bits to defeat quantum computing methods.

Diffie-Hellman keys can be generated for very-high bit lengths, as it is not difficult to generate the numbers required for it. It IS, however, difficult so solve, and that hasn't changed, and likely won't change for a very long while.


How can I encrypt + authenticate short strings into similar short ciphertexts?

First, convert the string which is to be encrypted into a sequence of bytes. UTF-8 is easy enough; you may reduce the size a bit, depending on what you know on the input strings (e.g. if the strings are domain names, they are ASCII-compatible, so you need only 7 bits per character -- actually a bit less). For the rest of this post, we need to assume that the encoding does not yield any byte of numerical value zero (which is true of both ASCII and UTF-8, if the source string does not have any embedded zero).

Once you have $d$ bytes, append at least $m$ bytes of value 0. This is the authenticity check: an attacker will have at a probability of at most $2^{-8m}$ to produce what will look like a "valid" encrypted string. This is a trade-off: a higher $m$ makes life more difficult for the attacker, but costs you space.

Let $n = d + m$. You now have a sequence of $n$ bytes (note: you can "round up" the size by adding some extra zeros beyond the $m$ zeros). Encrypt that sequence of $n$ bytes into another sequence of $n$ bytes by applying a block cipher with blocks of $n$ bytes (see below). This must be a single application of the cipher, no chaining mode, no IV.

Finally, represent the resulting $n$ bytes as a sequence of characters in your destination alphabet. Since you want to stick to 38 characters (lowercase letters, digits, dot and dash), this means interpreting the $n$ bytes as an integer, and converting it to base 38. In Java, this would may like this:

/*
 * WARNING: this code is completely untested, I write it "on-the-go". I have not
 * tried to run or even compile it. It is also grossly inefficient (although it
 * should be fast enough for most applications).
 *
 * convertToName() converts a sequence of bytes (normally the output of the
 * encryption function) into a string suitable for being the local part of an
 * email address. convertFromName() does the opposite (or returns null on
 * invalidly encoded string).
 */

static String convertToName(byte[] enc)
{
    StringBuilder sb = new StringBuilder();
    BigInteger z = BigInteger.ONE
        .shiftLeft(enc.length * 8)
        .subtract(BigInteger.ONE);
    BigInteger x = new BigInteger(1, enc);
    BigInteger u = BigInteger.valueOf(38);
    while (z.signum() > 0) {
        BigInteger[] qr = x.divideAndRemainder(u);
        x = qr[0];
        int c = qr[1].intValue();
        if (c < 26) {
            c += 'a';
        } else if (c < 36) {
            c += '0' - 26;
        } else {
            c = (c == 36) ? '.' : '-';
        }
        sb.append((char)c);
        z = z.divide(u);
    }
    return sb.toString();
}

static byte[] convertFromName(String name)
{
    BigInteger u = BigInteger.valueOf(38);
    BigInteger x = BigInteger.ZERO;
    BigInteger z = BigInteger.ONE;
    for (int i = name.length() - 1; i >= 0; i --) {
        int c = name.charAt(i);
        if (c >= 'a' && c <= 'z') {
            c -= 'a';
        } else if (c >= '0' && c <= '9') {
            c -= '0' - 26;
        } else if (c == '.') {
            c = 36;
        } else if (c == '-') {
            c = 37;
        } else {
            return null;
        }
        x = x.multiply(u).add(BigInteger.valueOf(c));
        z = z.multiply(u);
    }
    byte[] b = x.toByteArray();
    int encLen = z.subtract(BigInteger.ONE).bitLength() / 8;
    if (encLen < b) {
        byte[] enc = new byte[encLen];
        System.arraycopy(b, b.length - encLen, enc, 0, encLen);
        return enc;
    } else if (encLen == b) {
        return b;
    } else {
        byte[] enc = new byte[encLen];
        System.arraycopy(b, 0, enc, encLen - b.length, encLen);
        return enc;
    }
}

When decrypted, you call convertFromName(), and reject if you get null; otherwise, you should have a sequence of $n$ bytes, which you then decrypt with the block cipher. You check that there are at least $m$ zeros at the end of the decrypted block (that's the authenticity check), and finally decode the string using whatever convention you used in the first place (e.g. UTF-8).

All of the above is just encoding and decoding things. Remains "only" the yummy part: the block cipher. What you need is a pseudo-random permutation of the space of $n$-byte values, selected by a key which you use to encrypt and decrypt.

For $n = 8$ you can use Triple-DES. For $n = 16$, no hesitation, use AES. For larger blocks, there is no completely established rock solid standard, but for $n = 32$ you can have a look at Rijndael: the original Rijndael is defined over blocks of 128, 192 and 256 bits, with keys of 128, 192 or 256 bits (AES is Rijndael with 128-bit blocks, but the versions with larger blocks, while not being "the AES" per se, are considered reasonably robust nonetheless). For larger blocks, see Threefish, which is very new (this is not a good thing for a cryptographic algorithm) and received only limited attention as a block cipher, but goes up to 1024-bit blocks (that's for $n = 128$).

The idea would be the following: in the conversion above, you add enough extra zeros (beyond the $m$ zeros for the integrity check) to reach the next $n$ for which you have a suitable block cipher in the list given above.

On a general basis, you may want to implement "Format Preserving Encryption", e.g. using the Thorp shuffle as described by Morris, Rogaway and Stegers. This could allow you to have a "block cipher" for any $n$, without having to round up to the next value for which there is a suitable conventional block cipher. This is a mixed blessing, though: by keeping $n$ as is without ever adding more zeros than the initial $m$, you are effectively leaking the original length of the plaintext string. By making sure that $n$ is always one of $\{8,16,32,64,128\}$, you are masking part of that information while keeping your "local names" small when possible.

Numerical application: with $m = 3$ (the attacker has only one chance in 16777216 to create an invalid string which will be accepted by the check on $m$ zeros), input strings ("domain names") will yield output strings ("local names for email addresses") of the following length:

if $d \leq 5$, you uses 3DES and get strings of 13 characters;
if $5 \lt d \leq 13$, you use AES and get strings of 25 characters;
if $13 \lt d \leq 29$, you use a cipher with 256-bit blocks, and get strings of 49 characters;
if $29 \lt d \leq 61$, you use a cipher with 512-bit blocks, and get strings of 98 characters.

If you use UTF-8 encoding, $d = 13$ means 13 characters for input. But if you assume that input strings consist only of ASCII characters with codes from 33 to 126 inclusive (no control character, no space), you can store 15 characters in 13 bytes.


Mathematical definition of deterministic and non-deterministic random bit generators

Deterministic random bit generator is a function that takes as input a secret seed and possibly other inputs and produces (long) strings of output bits with the following property: for all adversaries with (polynomially) bounded computational power, the distribution of output bits is indistinguishable from a uniform, independent distribution of bits.

I don't think there is a strictly "mathematical" definition of true random bit source (I guess this is what you mean by 'non-deterministic') since it would need to define something that is now well captured by mathematics (external, physical source of entropy).

NIST in its standard SP800-90Ar1 defines non-deterministic random bit generator as:

  An RBG that always has access to an entropy source and (when working properly) produces output bitstrings that have full entropy. Often called a True Random Number (or Bit) Generator. (Contrast with a deterministic random bit generator).

A good reference book that covers the topic of randomness and random bit generators is "Random Number Generators - Principles and Practices".


Fiat-Shamir transform: reliance on hash input by interactive proof

I think you have the verification of Fiat Shamir wrong. The proof consists of $(h,r)$ and $y$ which is public anyway and only the relation $h = H(y,g^r y^h)$ is checked. As a result in your first case the proof is trivially valid. Your second case is interesting as it is not secure against an adaptive adversary. There is a paper by  David Bernhard, Olivier Pereira and Bogdan Warinschi on this issue which considers its applications to e-voting as well. Please take a look  at https://eprint.iacr.org/2016/771 page 6.


CKM_RSA_PKCS vs CKM_RSA_X_509 mechanisms in PKCS#11

As very clearly indicated by the specification, CKM_RSA_X_509 performs "raw" RSA. Raw RSA is simply modular exponentiation. So it performs just the RSASP1 function in the PKCS#1 standards. This means that a user should - at the minimum - also provide a secure padding mechanism. Otherwise the conditions to perform a secure RSA signing operation are not met.
CKM_RSA_PKCS on the other hand also performs the padding as defined in the PKCS#1 standards. This padding is defined within EMSA-PKCS1-v1_5, steps 3, 4 and 5. This means that this mechanism should only accept messages that are 11 bytes shorter than the size of the modulus. To create a valid RSASSA-PKCS1-v1_5 signature, you need to perform steps 1 and 2 of EMSA-PKCS1-v1_5 yourself.
Both of these mechanisms are only building blocks for creating a signing algorithm. You won't get a valid PKCS#1 signature by supplying random data to either mechanism. These methods have been defined to give more control to the user of the mechanism.
Sometimes protocols such as older SSL specifications do use their own signature schemes (concatenating an MD5 and SHA-1 hash, leaving out the hash indicator). Those protocols cannot be supported without a direct implementation or lower level primitive being available.
Another reason that CKM_RSA_PKCS exist is that it may not be very efficient to perform the full PKCS#1 v1.5 signature generation on the security token. It is very inefficient to send an entire text document to a smart card. Just sending a hash structure calculated on the host computer is much faster.

A final note: you should never let an attacker be able to use CKM_RSA_X_509 for the keys in your token, nor should you give him alter the padding you supply to that mechanism. In general it is better to use up to date mechanisms that represent complete signature schemes.
EDIT: apparently access to the private key operation in itself is not enough to break the RSA key. Of course letting an attacker have access to the private key operations is insecure in itself, but it won't allow copying / breaking the private key if the operation is well implemented. I presume it does open some attack vectors for the simple reason that an attacker has more control over the input to the modular exponentiation.


Hash functions to generate a one-time pad

First things first: a PRNG (Pseudo Random Number Generator) can not provide a one-time pad.

As a reminder: a one-time pad…

has to be truly random,
must be at least as long as the plaintext,
is never reused in whole or in part, and
is kept completely secret.

Only when all four points are met, we´re talking about OTP.

Your PRNG idea fails to meet those parameters as it is neither truly random, nor as long as the plaintext. Also, when not using a CSRNG (Cryptographically Secure Random Number Generator), you´re bound to reuse it in part due to the repeating internal state of regular PRNG algorithms.

Example: the “Mersenne Twister” PRNG you mentioned as example is not cryptographically secure. Given a small amount of output, it´s relatively easy to compute all future outputs. In other words: it´s rather predictable and nothing you want to use when it comes to cryptography. Such algorithms were not build to be cryptographically secure! They were designed for things like Monte-Carlo simulations.

Keeping it short (and actively ignoring other potential issues like missing authentication etc.): the security of your “cipher” will stand and fall with the security of your PRNG – which means that whatever you create with a regular PRNG, can not be considered to be cryptographically secure.

Honestly, when I look at the well-vetted options available (various cryptographically secure stream-ciphers, numerous secure block ciphers which can be run in CTR mode, etc.) I can only wonder why you would even think about creating your own, home-brew solution based on some PRNG. You can trust in the fact that trying to create a stream cipher based on a simple PRNG is a really bad idea.

Same goes for your related key generation ideas… there is a reason why pbkdf solutions exist!


Do Rabin Fingerprints have any advantages over CRC?

This is an expanded version of my comment above.  At the top of page 135 of the paper cited by the OP, the construction of the cryptographic CRC is defined  in the following words:

  $\ldots$ for any message $M(x)$ of binary length $m$ bits, $h_p(M)$
  is defined as (the coefficients of) $M(x)\cdot x^n \bmod p(x)$.

Thus, the definition of cryptographic CRC in the cited paper is
the same as what the OP claims the Rabin fingerprint
is. On the other hand, the cited paper says Rabin's construction
is essentially the same

  $\ldots$ except for the multiplication by $x^n$ in the modular
  process

In other words, the OP seems to have interchanged the
definitions of CRC and Rabin fingerprint in his question.

The cited paper
also seems to be implying (the phrasing is somewhat ambiguous)
that Rabin's fingerprint is weaker than the cryptographic CRC
defined above, which, by the way, is the same as the way CRC
error detection is used in communications systems, as I stated
in my comment.


Point at infinity for Jacobian coordinates

Jacobian coordinates are obtained by letting $x = X/Z^2$ and $y = Y/Z^3$.  The usual Weierstrass equation $y^2 = x^3 + a x+ b$ then, by multiplying both sides by $Z^6$, becomes
$$
Y^2 = X^3 + aXZ^4 + bZ^6
$$

An affine point $P = (x,y)$ corresponds to the Jacobian point $P = (t^2x:t^3y:t)$ for any $t \neq 0$.  Observe that letting $P = (X:Y:Z)$, one gets $X/Z^2 = (t^2x)/t^2 = x$ and $Y/Z^3 = (t^3y)/t^3=y$; that is, the affine coordinates of $P$, as expected.

The point at infinity $\mathcal{O}$ corresponds to $Z = 0$.  Plugging $Z=0$ in the above equation yields $Y^2 = X^3$.  The point at infinity has therefore for representation $(t^2:t^3:0)$ for any $t \neq 0$ ---you can check that $(t^3)^2 = (t^2)^3$.  For example, taking $t=1$ yields $\mathcal{O} = (1:1:0)$, which is the usual representation chosen to represent the point at infinity in Jacobian coordinates.  But any $t \neq 0$ is valid; $(1:-1:0)$ is also a valid representation for the point at infinity in Jacobian coordinates (this corresponds to $t=-1$).

Note. The case $t=0$ is not valid because $(0:0:0)$ is not.  This supposes that the elliptic curve is defined over a field.  Over a ring $R$, $t$ should be chosen in $R^*$.  Remark that if $R$ is a field then $R^* = R \setminus \{0\}$.


"open-key model" attacks, why would one be concerned?

It is not uncommon for a paper to state that the proposed design was not designed to protect against related key attacks. One reason for this is the over-powered nature of the attack against confidentiality: If the adversary already possesses the key, and can encrypt and decrypt at will, then one has to wonder how/why the adversary even stands to benefit from running an attack.

The open key model appears to go a step further, and assume that the adversary may have even chosen the key in question.

As far as confidentiality goes, there appears to be little point to defending against a known/chosen key attack. Doing so would likely require a more elaborate design, or at least more rounds, which will degrade performance in the "regular" use case to protect against an edge case situation that seems unlikely to occur in practice.

As to why a paper would explicitly mention such a thing: It is better to see "we made no attempt to protect against this class of attack" as opposed to not even mentioning the existence of the class of attacks. If the authors decline to mention related key attacks, it could be interpreted that they were not aware of them, as opposed to did not care to defend against them.

On the opposite side, there is one compelling reason to try and defend against known/chosen key attacks: If the cipher is to be used as a component of a hashing function, known/chosen key attacks become a relevant threat model. For example, this is mentioned briefly on page 9 of the proposal for simon/speck.


Take a point $G$ on the elliptic curve $E$. Someone calculates point $P = h*G$ where $h$ is some secret number (this can be done with point addition and duplications fast). Your task: Given public points $P$ and $G$ and curve $E$, find the secret $h$.

Solving this problem is hard. That is the problem that makes elliptic curves secure.

  Does a larger n value imply a higher security level?

Yes, the $n$ in your explanation is the order of a point on a curve, or put another way, it is the number of times you have to add the point to itself until you end up with the point at infinity $O$.

(There is also the order of the group of points on $E$ which is simply the number of points on the curve. Don't confuse these two orders, they are not the same thing).

Having a point $G$ with high point-order $n$ implies that the group has at least order $n$ as well.

So why do you want to pick a point with high order $n$?

The reason for this is, that if you pick a point with low order, there is a mathematical way that allows an attacker to solve the elliptic curves discrete logarithm problem faster. This is known as the MOV attack on elliptic curves:

http://www.cs.rit.edu/~txb7419/Crypto/MOVAttack.php

Note: If you play around with curves (something I suggest you should do), you will find that some points can have a scary low order. I did some experiments with a toy curve in the past:

$y^2 = x^3 + 1001*x + 75$, modulo prime $p$ = 7919

This curve has group order 7888.
If you examine the points on this toy curve (you can brute-force everything) you'll find most of them have point-order 7888 as well. Point <4023, 6036> is for example one of them. The point with the lowest point-order I've found on this curve is <7285, 14> with order of just 6.

Due to the MOV condition the second point would be a very bad point choice as G on this curve.


Is SHA-256 a one way permutation when restricting the domain to {0,1}^256?

There's been similar questions before but the answer is probably no with very high probability.

You can imagine a hash as being a little box with a dwarf in it. You give him a message and the first thing he does is looks for the message in his book. If he finds it, he gives you the n-bit string he wrote in his book.

If it's not in his book, he rolls some dice to create a random n-bit string. He then writes in his book both your message and the random string he just rolled. He then hands you the random n-bit string. If you pass him the same message again, he gives you back the same n-bit string.

Now we have a mental model of a hash, let's ask what happens when we start querying this construction.

Suppose we start counting from zero to $2^{256}$. We write the output of the hash of the counter in a table next to the counter that generated it. How many entries will it take before the probability is greater than 50% that an evaluation of hash(x) will hit an item already in the list?

Well each time the dwarf encounters a value not in his list, he rolls his dice. The value that comes out of those rolls might well collide with an item already in the list. The birthday paradox tells us that it will happen after approximately $\sqrt{2^{256}}$ queries.

That's about 0% of the hash space. This is why we can say with a good degree of confidence that no hash is a permutation.


Did authentication/signature primitives fall under the Wassenaar Arrangement?

I don't know about MACs (keyed Hashes e.g. HMAC might fall under the definition of symmetric but that's not clear to me) but there are restrictions on asymmetric crypto as well, RSA and Diffie-Hellman are restricted to 512 bits and ECDH is restricted to 112 bits (which effectively is a security level of 56 bits, the same as the limit on symmetric crypto):

  b. An "asymmetric algorithm" where the security of the algorithm is
  based on any of the following:

  Factorisation of integers in excess of 512 bits (e.g., RSA);
  Computation of discrete logarithms in a multiplicative group
  of a finite field of size greater than 512 bits (e.g., DiffieHellman
  over Z/pZ); or
  Discrete logarithms in a group other than mentioned in
  5.A.2.a.1.b.2. in excess of 112 bits (e.g., Diffie-Hellman over
  an elliptic curve);

Source: Wassenar Arrangement Section 5. A. 2. a. 1. b (Page 87)

Edit: As dave_thompson_085 points out, these restrictions do not apply to authentication / digital signature, and only to things like key exchange.


Cipher Block Chaining (CBC) encryption in SSL

The sequence number is used to disallow re-ordering of the messages / records themselves, not the blocks inside them. The block cipher / mode of operation is used to keep the data within the messages confidential; the chaining happens over one message, not over all messages - at least not for newer the newer TLS protocols.

Re-ordering of blocks within the messages can be performed if CBC mode is used. However, the plaintext message that is encrypted has been protected with an authentication tag using HMAC, which means that the altered plaintext message will fail verification afterwards.

ECB mode is always insecure if the blocks can have any, interdependent data. The reason for this is that identical plaintext blocks will always result in identical ciphertext blocks, which leaks information. It is similar to using the same IV for CBC mode, but for each and every block. Block ciphers in ECB mode are not CPA secure.

Note that the newer TLS 1.3 protocol disallows CBC mode altogether. There have been many issues with the authenticate-then-encrypt and CBC mode in TLS, requiring protocol specific alterations to CBC padding mode for instance. Nowadays either an authenticated stream or stream cipher mode should be preferred. Most of these modes - such as GCM - use counter (CTR) mode instead of CBC.

CBC is mainly used for legacy applications. It has wide support in crypto libraries, which makes it a logical choice for applications that do not require anything better. Most cryptographers here will however try to avoid CBC mode as it requires a random IV and padding or ciphertext stealing. It only provides real benefits over insecure modes such as ECB.

SSL is an old name. Nowadays TLS should be preferred as SSL may refer to the old protocols which are now commonly disabled in clients / servers. There was some talk about reintroducing the SSL name for TLS 1.3 but fortunately - in my strongly voiced opinion - that didn't happen.


Can a list of hashes with property $X_{n+1} = \operatorname{SHA-256}(X_n)$ loop?

Is SHA-256 designed to loop after exactly $16^{64}$ hashed hashes, or is there a chance it will do so before that point?

SHA-256 behaves more or less like a random function. You can expect it to loop after approximately $\sqrt{2^{256}} = 2^{128}$ iterations due to the birthday paradox


Is there a way to change encryption scheme from AES to FHE without data leakage?

If you are talking about FHE (as stated in the title, but not in the question body) then yes, this is possible.
Encrypt the symmetric key $k$ that was used to originally encrypt the data as well as the symmetric ciphertext $c$ under the FHE public key. Then homomorphically evaluate the decryption circuit of the symmetric encryption scheme on those ciphertexts. By the correctness of the FHE scheme the result will be a ciphertext encrypting the original data under the FHE public key.


Can we find the exact number given remainder of the numbers with mod m?

If you know $m$ and the $x_i$ but not the $t_i$ then there's no way to find $p$ in general. For example, suppose that $m$ is prime. Then, for any $p \ne 0$, there is a set of suitable $t_i$, given by $t_i = p^{-1} x_i$. The only value for $p$ that may be impossible is $0$, which is possible only if all the $x_i$ are zero.

More generally, the only information you can have about $p$ is to rule out certain factors in common with $m$. If $k$ is a factor of $m$ and the $x_i$ are not all multiples of $k$ then $p$ cannot be a multiple of $k$ either. That's all the information you have about $p$.

(Note that in this answer, I work modulo $m$, so e.g. when I write $p \ne 0$ I mean $p \ne 0 \pmod m$.)


Compared to GCM or XTS modes, how secure is H xor R1, E (R2, R1, Message) for confidentiality and integrity?

I don't see any reason to expect this to provide integrity (INT-PTXT or INT-CTXT).  In fact, if $R1,R2$ were known to the attacker, I can show that in general it does not provide integrity: there exist some encryption algorithms that are IND-CPA secure but where your scheme does not provide integrity.  (e.g., any stream cipher.)  This sounds like a certificational weakness that makes me skeptical about this construction.

I can't see any reason why you would want to invent a homebrew scheme, that comes with no proof of security, and might have some problems that are known not to occur in existing authenticated encryption schemes... rather than using a well-analyzed authenticated encryption mode.

Basically: don't use this.  Use a standard authenticated encryption mode.  There's a reason they are standard; they have been analyzed in depth.

Here is the attack on integrity, assuming $E$ is a stream cipher.  Suppose we are given an encryption of message $M$, and $R1,R2$ are known.  The attack will change the ciphertext into a valid encryption of some other message $M'$ of the attacker's choice, as follows.

Compute $\Delta = \text{hash}(R1,R2,M) \oplus \text{hash}(R1,R2,M')$.  Xor $M \oplus M'$ into the part of the ciphertext that encrypts the message $M$.  Next, xor $\Delta$ into the part of the ciphertext that encrypts $R1$.  This is now a valid encryption of $M'$ (an encryption that'll be accepted by the recipient and that decrypts to $M'$), which breaks integrity.

Why does this attack work?  If you xor $\Delta$ into the $R1$ part of the ciphertext, this will cause the recipient to think the hash is $H \oplus \Delta$ instead of $H$.  That sounds like a bad property in itself, to me.

I realize this property doesn't actually break your scheme, because in your scheme, $R1,R2$ are presumably not known to the attacker.

Nonetheless, it "smells" to me like it is going to be hard to prove the security of your scheme, because of a circular dependency here.  The integrity of the message depends upon the integrity of $H$, which in turn seems to partly rely on the integrity of $R1$, but the integrity of $R1$ depends upon the integrity of $H$.  In addition, there is no "separation of concerns".  The integrity of the message depends upon the secrecy of $R1,R2$; and the secrecy of the scheme depends upon its integrity properties.  Standard proofs typically rely upon a separation of concerns, where integrity does not rely upon confidentiality.  These kinds of circular dependencies seem like like they are going to make it challenging to prove this scheme secure (if it is even secure).

Now maybe there is a way to prove your scheme secure.  But the onus is on you to show the proof of security.  Why would we use a scheme with no proof of security, when we have one that does come with a proof of security?


May an adversary be fooled by a random-looking input that in reality is fixed?

Would an adversary realize that it is not interacting with the scheme but with a "simulation" if it finds out that k=5 in the challenge setting?

This is commonly stated as Kerckhoff's Principal, which I prefer to cite as Shannon's Maxim (they both stated it, and Shannon's Maxim sounds better). The idea is, the adversary should be assumed to know everything about a secure system, except the key, if it is to be considered secure at all. As such, the adversary must be assumed to know that you could lie to them about the value of $k$.
Also, a signature scheme could not be considered secure if it involves an oracle capable of lying about what signatures are valid or invalid. As such, if the system is to be secure at all, it must behave the same for an attacker as if they were a legitimate verifier.


Is phi-hiding assumption as hard as integer factorization?

Firstly, the phi-hiding assumption [CMS,KK] states that it is computationally-hard to distinguish the cases $(e,\phi(N))=1$ (where $(\cdot,\cdot)$ denotes the GCD) and $e|\phi(N)$ for a given RSA modulus $N$ and "small" prime $e>2$ ($e\ll N^{1/4}$, to be precise). In the former case, the exponentiation map $x\mapsto x^e\bmod{N}$ is injective (i.e., the RSA permutation), whereas in the latter case the map is lossy. Therefore, one could rephrase the assumption as assuming that the lossy and injective modes of the exponentiation map are computationally-indistinguishable [KK]. Note that this is stronger than simply assuming it to be hard to find small factors of $\phi(N)$ (the same way DDH is a stronger assumption than CDH is).$^*$
The assumption is clearly at least as strong as the factoring assumption as given an efficient algorithm that factors $N$, it is easy to compute $\varphi(N)$ and therefore decide whether a given prime $e$ divides $\varphi(N)$. Moreover, it is claimed in [KK] to be at least as strong as the RSA assumption. I couldn't find a proof of this anywhere, but the following reduction seems to work: given $(N,e)$ where either $(e,\phi(N))=1$ or $(e,\phi(N))=1$ and access to an oracle $A$ that computes $e$-th roots:

Sample $x_1,\cdots,x_n$ uniformly at random from $\mathbb{Z}_N^*$
Send $x_1^e\bmod{N},\cdots,x_n^e\bmod{N}$ to the oracle $A$ to obtain $x_1',\cdots,x_n'$
Return "$(e,\varphi(N)=1)$" if $x_i=x_i'$ for all $i\in[1,n]$

Showing the converse statement -- i.e., that the factoring assumption is at least as strong as the phi-hiding assumption -- is, as far as I know, an open problem.$^{**}$ This would require factoring $N$ (or find $e$-th root for that matter) given access to an oracle that on input $(N,e)$ decides whether $(e,\phi(N))=1$. Settling this problem would require first settling the equivalence between RSA problem and factoring (which is an easier question).
Finally, it is worth pointing out that for "large" value of $e$s ($e\geq N^{1/4}$, to be precise), the phi-hiding assumption does not hold as given such an $e|\phi(N)$ it is possible to factor $N$ using Coppersmith's attacks. You can read more about this in [CMS,KK]. Some moduli where the assumption does not hold are. discussed in [SF]
$^*$The definition in this Wikipedia article is also wrong: computing $\varphi(N)$ given $N$ is known to be equivalent to factoring $N$.
$^{**}$ Although it is believed that the equivalence holds: see discussion in [KK,§1.1].
[CMS]: Cachin, Micali and Stadler, Computationally Private Information Retrieval with Polylogarithmic Communication, Eurocrypt'99
[KK]: Kakvi and Kiltz, Optimal Security Proofs for Full Domain Hash, Revisited, JoC'18
[SF]: Schridde and Freisleben, On the Validity of the Phi-Hiding Assumption in Cryptographic Protocols, Asiacrypt'08


Actually, you are quite correct; you have not been given enough information to determine the probability.

The piece of information that you have not been given is the probability distribution that the plaintext was originally chosen from.  Perhaps all 128 possible plaintexts were chosen with equal probability (that is, with probability $1/128$).  Perhaps the plaintext 1001001 was chosen with probability 0.25, and the plaintext 0110110 was chosen with probability 0.75, and all other plaintexts had zero probability.  The point is that you do not know.

The entire point of a one time pad is that knowledge of the ciphertext gives the attacker no new information about the probability distribution of the plaintext; that is, the ciphertext does not make any specific plaintext any more or less probable.  The question asks you about the probability distribution given a specific ciphertext; we know that it is the same as it was without the ciphertext - however, we don't know what the original probability was.


Can a PRF distiguisher invoke the function's algorithm?

The adversary $\mathcal{A}$ is allowed to invoke the algorithm $\mathcal{F}$ (if it is P.P.T.) in any PRF definiton known to me.
We are generally interested in security against every possible P.P.T. algorithm $\mathcal{A}$ and require that for every such algorithm $\mathcal{A}$ it holds that $\mathcal{A}$ can only distinguish from a random function with non-negligible probability.
If $\mathcal{F}$ is a P.P.T. algorithm, there exists an adversary $\mathcal{A}$ that includes the $\mathcal{F}$ functionality. This adversary is able to invoke $\mathcal{F}$ and we require from our PRF, that it is secure against that adversary too.
The same argument holds for parts of the algorithm $\mathcal{F}$.

As far as I understood it, for your example the important question is the following:
Does the adversary $\mathcal{A}$ know $c$?
Again, we need indistinguishability against all adversaries from a PRF, which means that we need indistinguishability even against an adversary that knows this fixed $c$.


Why Boneh-Franklin BasicIdent IBE is not chosen-ciphertext secure? Why use random oracle?

First, recall that in a chosen-ciphertext attack (CCA) model, the attacker has access to a decryption oracle. A scheme is said CCA-secure if access to a decryption oracle does not give any advantage to the attacker.

Knowing this, a very simple CCA attack can be done on BasicIdent. I will use the description of the scheme from Wikipedia.

As you can see, ciphertexts in BasicIdent are tuples of the form
$$c = (u,v) = \left(rP, m \oplus H_2\left(g_{ID}^r\right)\right)$$

The important thing here is that the second term of the ciphertext is simply the message XOR'ed with a hash. So, in the IND security game, the attacker can take the challenge ciphertext $c^* = (u^*, v^*)$ and produce a new ciphertext $\hat c = (u^*, v^* \oplus \hat m)$, for some random message $\hat m$. This new ciphertext must  be accepted by the decryption oracle since $c^* \neq \hat c$. The result from the decryption oracle is $m_b \oplus \hat m$, and the attacker can trivially extract the original message $m_b$ from this since he knows $\hat m$.


Is it a vulnerability (for message authentication) to have a variable iteration-count for PBKDF2?

No, variable message iteration count (or more generally workfactor parameters) passed in the ciphertext (including in clear and unauthenticated) is not by itself a vulnerability, to either encryption or authentication, under the following reasonable assumptions:

The adversary can only get and manipulate the ciphertexts, and get plaintexts  (with the exception of those s/he is trying to decrypt); not alter the programs used, nor spy their execution.
PBKDF2 (or more generally a sound entropy-stretching function) is well-implemented, and used to convert password and salt to wide symmetric key(s) then used for symmetric encryption and message authentication. Here, "well-implemented" and "sound" includes:

The password-streching function does not exhibit much more collisions for different passwords than a random function for any iteration count (or more generally workfactor parameters) that can be parsed from the ciphertext (and leads to bearable execution time). For PBKDF2, an iteration count of 0 (or negative, if the encoding has provisions for that) should be rejected, as specified in RFC2898 / PKCS#5 v2.0 by
    c       iteration count, a positive integer .
An hypothetical implementation accepting an iteration count of 0 and in that case giving constant output (or one depending only on salt) would be vulnerable.
The code used for decryption and authentication is not sensitive to side-channel attacks made worse by some choice of the iteration count/workfactor parameters.

There is no other implementation goof (or backdoor, perhaps disguised as goof) that the introduction of the variable workfactor can trigger.
The symmetric encryption and authentication primitives are secure, assuming their wide key has enough entropy.

Argument (not a formal proof): With the password unknown, the entropy in the symmetric keys actually used by the verifier remains high (nearly that of the password or as limited by key width, whichever is lower), including under an attack where the workfactor has been altered. The best attack for the adversary remains to find the password, and the cost of that increases with the workfactor used for a ciphertext that the adversary can intercept and is encrypted or authenticated with the right password; other ciphertexts (including any that the adversary could build without knowledge of the password) do not help towards finding the password.

The main practical danger lies in the consequences of the increased complexity introduced by variable iteration count: the code is more complex, thus more likely to contain an undetected weakness.


Yes, the hash will be unique every time - if the input string is unique every time.

This follows trivially from SHA-256's collision resistance: If your input strings are different but the outputs are the same it's a collision in SHA-256 which would be a huge surprise to find for everyone and a publication-worthy result.

Now the more interesting question is whether your input string will be unique every time. If everything is fixed length - except perhaps the counter - then yes, it will be unique. If the secret key is variable length there may be "unlucky" situations where the last byte of the counter matches the first byte of the secret key and the allocations which belongs where are different (i.e. whether the byte belongs to the counter or the secret key). The "safest" choice here would be to pad everything (except one of the values) to a fixed upper bound length.


You are correct; whoever put together the above proof typo'ed that point; we have $c \times d \equiv 1 \pmod {\phi(n)}$, or more accurately, $c \times d \equiv 1 \pmod {lcm(p-1, q-1)}$.

On the other hand, the attacker isn't expected to be able to compute step 2 (he can't, he doesn't know the value of $lcm(p-1,q-1)$, and hence cannot compute $d$).  Instead, it is there to establish the relationship between $c$ and $d$ (and why they cancel out in step 3)


cipher text only attacks on deterministic homomorphic encryption schemes

This is an interesting question. If the input set does not have any identity element (for both mul and add operations) then one cannot construct a field and subsequently there cannot be homomorphic operations.  More clearly, if the input plaintext elements do not form a field (and their respective ciphertext elements do not form a field either)  then there cannot be homomorphisms of operations. This is by definition of Field.

So if the input set contains identity elements (and other properties needed to become a field) then while the given set members may not have any obvious relation. There would be some constant $c$ for which  $enc(n_1) + c * enc(n_2) = enc(0) $ subsequently finding which attacks mentioned in previous question apply !

Also  an attacker could try to find random complex relations among them. For example is $ enc(a) + enc(a) = enc(b) $ or is $ enc(a) *enc( b) = enc(c) $ etc. revealing inferences.


Why does P1363 require RW signature with $0 ≤ s < n/2$?

That practice of replacing the result of $y=x^d\bmod N$ (or $y=x^e\bmod N$) by $\hat y=\min(y,N-y)$ is also in ISO/IEC 9796-2:2010 (paywalled) and ancestors; I first met that in [INCITS/ANSI]/ISO/IEC 9796:1991, also given in the Handbook of Applied Cryptography, see in particular note 11.36. ISO/IEC 9796 was a broken and now withdrawn signature scheme with message recovery based on RSA or RW, very different from ISO/IEC 9796-2.

With $e=2$ (or more generally even), $\;y^e\bmod N\;=\;(N-y)^e\bmod N$. Thus in a RW signature application, signatures $y$ and $N-y$ are equivalent. One rationale of using $\hat y$ is to choose a canonical signature among $y$ and $N-y$. This allows the verifier to check that the signature is less than $N/2$, which prevents an adversary from turning a signature $y$ into a different but equally acceptable signature $N-y$ (some definition of signature security consider that a break).

With odd $e$ (RSA), there is no such security rationale. However we can still use $\hat y$ rather than $y$, if the low-order bit of $x$ is set to 0 by the padding scheme: if $\hat x=\hat y^e\bmod N$ turn out to be odd, the verifier uses $x=N-\hat x$ instead.

Whatever $e$, the maximum bit size of $\hat y$ is one less than the maximum bit size of $y$ (for arbitrary $x$). That size reduction, however small in proportion, allows:

Direct re-encryption of $\hat y$ under textbook RSA using a different $N'$ of the same size as $N$, including when $N'<N$, which can happen when encryption and signature keys have modulus specified only by their common bit size (and is bound to happen for one of the two parties in some protocols between peers each using a single key for both encryption and signature, as in the European Digital Tachograph).
Use of $N$ with $8k+1$ bits with convenient signatures of $k$ bytes; such $N$ have been extensively used in early public-key systems; as illustration, the example given in ISO/IEC 9791:1991, appendix B.1.1, has as 513-bit $N$.Incidentally, the leftmost 129 bits are all-zero except the leftmost one, which simplifies quotient estimation, perhaps at the price of somewhat easier factorization in particular with NFS, but that was not known at the time.


Can I prove that a message is part of a set of known messages without disclosing the message?

Yes, this can be done. For your simple example, what you want amounts to an "OR proof", a proofs that shows that one of two statements is true. Let $(c, c')$ be your ciphertext; to show that it encrypts either 1 or 2, you just have to prove that "$(g,h,c,c')$ is a DDH tuple OR $(g,hc,c'/2)$ is a DDH tuple".

Proving that a tuple $(g,h,g',h')$ is a DDH tuple is the classical "proof of same discrete logarithm in different bases" (you prove that $\log_g(g') = \log_h(h')$) (see e.g. this answer). To perform an OR proof, the idea is simply to perform two proofs for the two statements in the clause in parallel, but sending a challenge that binds only the prover to, say, the sum of the challenges. This gives him the freedom to choose one of the challenges before the execution of the protocol, and therefore to forge the corresponding proof, but not both; therefore, the prover will be able to forge at most one proof, and the verifier cannot know which one. See for example this article.

This generalizes to OR with arbitrarily many clauses, and so to "sets of messages" of arbitrary size, but the size of this proof is linear in the size of the set of messages. I know that if you use the additive ElGamal instead (a ciphertext is of the form $(g^r, h^rg^m)$), there are way more efficient methods: this article, for example, provides a zero knowledge proof of membership of an (additive) Elgamal plaintext to a known set of size $n$ in communication $O(\log n)$. The same holds for other cryptosystems with additive properties; for the standard ElGamal scheme, there might also be efficient proofs (in fact, there are necessarily such proofs, as we have ZK arguments for any statement in communication polylog, but the constants involved in these generic construction would be highly impractical here), but I do not know much about this specific case.


Should I use md5 for my new application?

When I need to show to others that they are wrong and it is their word against mine, I look to the words of industry recognized experts and then challenge them to find an industry recognized expert that supports their belief.

In this case, Bruce Schneier has written a lot on MD5 (in Bruce style, each word links to a different blog post or article of his).

Wikipedia even has a nice article on MD5 security.

That said, you specify in your question that this is potentially for a "non-security-sensitive" application. What do you mean by that? Your comment seems to suggest that you are signing hashes of files. That to me seems security sensitive.


AES does not operate on or produce characters — it has no knowledge or care of any particular character encoding. AES and other modern block ciphers accept and output arrays of bytes. The same concept applies to the key, and (in block modes that require one), the initialization vector.

How (and if) you choose to encode the output is up to you. For storing in a file or database, there is typically no need to encode the output – byte buffers work just fine. For showing the result to a user, things like hex-encoding are frequently used. For transport mediums that require only 7-bit clean ASCII, you can encode with Base64.

That said, CryptoJS appears to automatically encode outputs with Base64. I question the wisdom of this as a default (along with several others made by the CryptoJS authors), but that's the situation as it stands.


Is there an additively homomorphic encryption scheme that supports calculating a square root on the ciphertext?

I believe that such a system (with Homomorphic addition and approximate squareroots) is likely to be Fully Homomorphic, and hence it is unlikely that you could find an efficient candidate among existing systems (or, if you did, well, that's a Really Significant result).

Let us assume that:

Subtraction (as well as addition) can be done homomorphically
The approximate squareroot of 2 is 1.

Then, we can compute the "or" of two encrypted values $a$ and $b$ (which are both encrypted versions of either 0 or 1), by computing:

$$\sqrt{\sqrt{a+a+b+b}}$$

It is easy to verify that the result will be an encrypted 0 if both $a$ and $b$ are 0, and 1 if either (or both) are 1.

That, with homomorphic subtraction, is a complete set, and so we have a FHE system on our hands.


identifying presence of encryption of zero in additive homomorphic encryption

I do not think what you want is possible with any simple solution - by simple, I mean computationally less expensive than downloading and decrypting all the ciphertexts. Basically, multiplicative homomorphism allows you to check some algebraic "OR": if there is a single 0, then the product of all the plaintexts will be 0.

Additive homomorphism, on the other hand, only allow you to check some algebraic "AND", id est, to check whether all the encrypted values are 0 or not (this is done simply by computing some linear combination of all the ciphertexts with uniformly random coefficients, and decrypting the result ony; if it's zero, then with overwhelming probability, all the ciphertexts encrypt 0). What you're looking for is an algebraic "OR" on additive encryption, which typically require a linear number of ciphertexts (so basically, it will not be really better than downloading and decrypting everything).

(By the way, you mentioned that with a multiplicative scheme, "the server could multiply all the encryptions and give the result". You should note that here, you assume a multiplicative scheme which can encrypt the zero value. The only such scheme I know off (appart from fully homomorphic encryption) is the one I constructed in a recent paper)

EDIT: now, it depends on your setting. If you assume each plaintext $m$ was encrypted as $E(m), E(R\times b)$ where $R$ is a random coin, and $b$ is a bit which is 0 if $m$ is non zero, and 1 else, then you have a solution: the server simply computes and sends a random linear combination of the E(R^b), and the client decrypt the single resulting ciphertext. If it encrypts a random value, there was a zero; else, there was no zero. However, this extended encryption scheme $E(m), E(R\times b)$ is not additively homomorphic anymore.