Voting scheme where the votes become public when a threshold is reached Does there exist a voting scheme where voters cast private encrypted votes that automatically become public only after the threshold number of votes is cast?

It needs to be done without a central authority that is trusted to hold keys. I don't need it to be receipt-free, I just want it to be authority free and automatic.

The reason why I need this is, that seeing other people's votes before the threshold is reached could bias the final outcome.

I am making the following assumptions regarding your requirements:

The number of participants is low enough, for it to be feasible for each participant to open a reliable, authenticated and confidential communication channel to each other participant.
The vote of each individual participant is only meant to be kept secret until the threshold of votes has been reached, at which point it becomes public how each participant voted.
System parameters $p, q, g$ are selected in advance, such that the discrete logarithm problem in a sub group of prime order $q$ of might be assumed to be hard.
The participants should not be allowed to change their votes once their votes have been cast, and collusion between participants must be prevented.
The risk of individual participants invalidating the election by opting out, is relatively low, and when it happens, it can be dealt with by starting over.

Given the above requirements, a simple approach would be to combine a binding and computationally hiding discrete logarithm based scheme with Shamir Secret Sharing.

Steps:

Each participant $P_i$ selects a value $x_i$ uniformly at random from $\mathbb Z_q$, calculates $h_i = g^{x_i} \bmod p$, and broadcasts $h_i$ to all other participants.
Each participant computes $h = (\Sigma_1^nh_i)^{(p-1)/q} \bmod p$. If $h$ equals zero, step 1 is repeated. (Extension: Each participants broadcasts $h$ and some protocol is in place to disqualify users who broadcast a value the majority of the other users find to be incorrect. For simplicity, this has been left out at this stage and the rest of the stages of the protocol.)
Each participant $P_i$ selects a degree $t$ polynomial $p_i(x)$ with coefficients $a_{i,1},..,a_{i,t}$ selected uniformly at random from $\mathbb Z_q$ and $a_{i,0}$ representing the vote of the participant.
In order to vote, each participant $P_i$ selects $n$ values $r_{i,j}$ uniformly at random from $\mathbb Z_q$, keeps them secret, broadcasts a commitment sequence $C_{i,j} = g^{p_i(j)}h^{r_{i,j}}$, sends $p_i(j)$ with confidentiality and authenticity to each participant $P_j$ who has already voted and gets $p_j(i)$ back from $P_j$.
Once at least $t+2$ votes have been cast, each participant broadcasts its $r_{i,j}$ values and all of the $p_j(i)$ values it has received from other participants.
Each participant verifies that each value $C_{j,k}$ it received when user $P_j$ voted, meets $C_{j,k} = g^{p_j(k)}h^{r_{j,k}} \bmod p$. (If not, some protocol has to be in place to disqualify users.)
Each participant solves the shared secret of each other participant and broadcasts the result.
Some protocol is in place to confirm that a majority of the participants have broadcasted the same result.

Q: Does this protocol really prevent collusion?

A: Strictly speaking, no. Nothing prevents the participants from conducting informal out-of-band exit polls during the voting in step 4. No protocol has any influence over what the participants do out-of-band, so this is something that has to be dealt with out-of-band as well.

Q: Is the Shamir Secret Sharing component really necessary? Since all participants who vote have to be online during the entire protocol, wouldn't a commitment scheme and a counter be sufficient?

A: If the possible votes are "Yea" (1) or "Nay" (0), using Shamir Secret Sharing allows a minor modification to the protocol, by which the total number of votes are counted before each individual vote is revealed. Each participant $P_j$ reveals the sum of the $p_i(j)$ values. Together with the corresponding sum of $r_{i,j}$ values, this sum can be verified using the commitments. Reconstructing a polynomial from those summed up shares, will equal the number of "Yea" votes.

Now, if some participant (e.g. the last one to reveal its sum) chooses to opt out, this user might be disqualified and the rest of the participants might wait for the next vote to be cast. No individual vote will have been revealed (through the protocol), but it is possible that the disqualified participant already knows the result (and is the only one who knows it).

Q: Isn't constructing the $h$ generator as a sum, rather than a product, susceptible to doctoring by the last participant to submit its $h_i$ value?

A: Not if we assume that $q^3 \lt p$ and every participant verifies that each $h_i$ belongs to the $q$ order subgroup. Also, constructing it as a sum allows for each participant to open their $x_i$ value, to prove that they know the discrete logarithm of $h_i$, without making it possible to calculate $log_g(h)$


How exactly is TFHE secure? TFHE (Fully Homomorphic Encryption over Torus) seems to be a state-of-the-art form of homomorphic encryption.

But, I got a bit confused.

I have recently read the paper Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP from CRYPTO 2012.

The author states in section 1.1 that

  For technical reasons, we don't implement the scheme over fractions,
  but rather mimic the invariant perspective over $\mathbb{Z}_q$ (see
  Section 1.2 for more details).

However, TFHE seems to be defined over fractions.
Does this imply that TFHE overcomes such a technical difficulty?
If so, doesn't any security side-effect come?

You have to distinguish "implement" from "define".

Brakerski defines his scheme over fractions, but implements it using integers just because it is easier to implement, more efficient and less error prone. If you represent the fractions with floating values, then you have precision issues. And if you represent them with two integers (denominator and numerator), then you probably use more space than what is needed.

That is why he says in the end of section 1.2:

  Finally, working with fractional ciphertexts brings about issues of precision in representation and other problems. We thus implement our scheme over $\mathbb{Z}$ with appropriate scaling.

Thus, this implementation choice has nothing to do with the security aspects of the scheme.

That said, TFHE does something similar: it is defined over $[0, 1[~\subset \mathbb{R}$, but if you check the code, you will see that integers are also used there.

For example, see the following lines on the file torus.h:

// Idea:
// we may want to represent an element x of the real torus by
// the integer rint(2^32.x) modulo 2^32
//  -- addition, subtraction and integer combinations are native operation
//  -- modulo 1 is mapped to mod 2^32, which is also native!
// This looks much better than using float/doubles, where modulo 1 is not
// natural at all.
typedef int32_t Torus32;
typedef int64_t Torus64;


Zero-Knowledge proof for data being decryptable to a given hash preimage Alice has $m$ which is the hash preimage of $h_m$, namely $\operatorname{SHA256}(m) = h_m$.

Consider the following protocol.  Alice does the following:
\begin{align*}
  r &:= \operatorname{Gen} \\
  h_r &:= \operatorname{SHA256}(r) \\
  \hat m &:= \operatorname{Enc}(m, r),
\end{align*}
where $\operatorname{Gen}$ is some secure random key generator and $\operatorname{Enc}$ is some symmetric encryption algorithm (say AES).

At this point, provided that Alice would give Bob $h_m$, $h_r$ and $\hat m$, can she prove to Bob using ZKP (e.g. zk-SNARKS) the following statement?

  There exists $r$ such that $h_r = \operatorname{SHA256}(r)$ and $\operatorname{SHA256}(\operatorname{Dec}(\hat m, r)) = h_m$?

I know the first part is possible ("there exists $r$ such that $h_r = \operatorname{SHA256}(r)$") but I'm not sure about the second part, specifically the composition of $\operatorname{SHA256}$ and $\operatorname{Dec}$.

My intuition is that it is possible, since we can have a witness for that question which can be verified at polynomial time, and thus it's an NP language, but I'm not sure.

There has been some recent progress [1] on efficient zero-knowledge for such statements. Essentially they present a $\Sigma$-protocol to prove statements over general circuits. To prove the AND relation you state, you could essentially just build one large circuit which takes (the bits of) $r$ as input and outputs $h_r$ and $h_m$ so that $h_r = \operatorname{SHA256}(r)$ and $h_m = \operatorname{SHA256}(\operatorname{Dec}(\hat m, r))$, where $\hat m$ is hardcoded in the circuit.

The proofs above are of linear size in the number of AND gates in the circuit. If you want something more compact you might want to have a look at SNARKs.

References

[1] https://eprint.iacr.org/2016/163.pdf


How to generate a nonce for ChaCha20 Poly1305? I am using a self implementation of ChaCha20 with Poly1305. Since the nonce is only 96 bits it cannot be chosen at random. Can anyone suggest an efficient method to generate nonce from the key ?

The RFC 7539 describe your needs.
The uniqueness:

The most important security consideration in implementing this document is the uniqueness of the nonce used in ChaCha20.  Counters and LFSRs are both acceptable ways of generating unique nonces, as is encrypting a counter using a 64-bit cipher such as DES.  Note that it is not acceptable to use a truncation of a counter encrypted with a 128-bit or 256-bit cipher, because such a truncation may repeat after a short time. (The bolds are mine)

LFSR's and counters are very efficient. Use a 96-bit binary counter or 96-bit length LFSR with a primitive polynomial. One must be careful during system reboots and especially system and power failures since you have to store the nonce somewhere to recover correctly. You need to make sure that when a failure occurs either do a long-jump on the counter/LFSR or generate a fresh new key.
Randomly generating:
You can also generate it randomly while considering the birthday bound $\mathcal{O}(\sqrt n)$. You should stop way before generating $2^{48}$ nonces under the same key to hit a collision. You can adjust the advantage of the adversary with the birthday calculations.
Combining Both
One can also combine counters/LFSR with random generation. For example, use a 48-bit binary counter and 48-bit random. For each nonce generation increment the counter/LFSR and generate a new 48-bit random.
This is more reliable than single counter/LFSR or random based one. During a failure, if the system did not correctly write the last step/stage of the counter/LFSR, then the random part would be helpful to mitigate the repeat of a previous nonce.
Consequences of repeating a nonce:

If a nonce is repeated, then both the one-time Poly1305 key and the keystream are identical between the messages. This reveals the XOR of the plaintexts, because the XOR of the plaintexts is equal to the XOR of the ciphertexts.


How is a "SHA256 reduced by X of Y rounds" built? Wikipedia reports:

  A 2011 attack breaks preimage resistance for [...] 52 out of 64 rounds for SHA-256. Pseudo-collision attack against up to 46 rounds of SHA-256.

I am having trouble determining/understanding whether the "Message Expansion" of SHA-256 is the one reduced (splitting the 512-bit message block into 16 words, and expanding them into 64 expanded message words), or the "State Update Transformation" is the one reduced (starting from the previous 256-bit chaining value, which is updated by applying the step functions 64 times).

I have the feeling that both are reduced, but I am not sure...

Taken from the OpenBSD implementation of the SHA-2 family at their CVS, where the function SHA256Transform() is used to apply a number of rounds to each block of input. It splits this into the first 16 rounds, and then the remaining ones. A reduced-round implementation of SHA-256 would simply have fewer rounds. This makes the hash significantly weaker.

The transform function:

void
SHA256Transform(u_int32_t *state, const u_int8_t *data)
{
    u_int32_t   a, b, c, d, e, f, g, h, s0, s1;
    u_int32_t   T1, W256[16];
    int     j;

    /* Initialize registers with the prev. intermediate value */
    a = state[0];
    b = state[1];
    c = state[2];
    d = state[3];
    e = state[4];
    f = state[5];
    g = state[6];
    h = state[7];

    j = 0;
    do {
        /* Rounds 0 to 15 (unrolled): */
        ROUND256_0_TO_15(a,b,c,d,e,f,g,h);
        ROUND256_0_TO_15(h,a,b,c,d,e,f,g);
        ROUND256_0_TO_15(g,h,a,b,c,d,e,f);
        ROUND256_0_TO_15(f,g,h,a,b,c,d,e);
        ROUND256_0_TO_15(e,f,g,h,a,b,c,d);
        ROUND256_0_TO_15(d,e,f,g,h,a,b,c);
        ROUND256_0_TO_15(c,d,e,f,g,h,a,b);
        ROUND256_0_TO_15(b,c,d,e,f,g,h,a);
    } while (j < 16);

    /* Now for the remaining rounds to 64: */
    do {
        ROUND256(a,b,c,d,e,f,g,h);
        ROUND256(h,a,b,c,d,e,f,g);
        ROUND256(g,h,a,b,c,d,e,f);
        ROUND256(f,g,h,a,b,c,d,e);
        ROUND256(e,f,g,h,a,b,c,d);
        ROUND256(d,e,f,g,h,a,b,c);
        ROUND256(c,d,e,f,g,h,a,b);
        ROUND256(b,c,d,e,f,g,h,a);
    } while (j < 64);

    /* Compute the current intermediate hash value */
    state[0] += a;
    state[1] += b;
    state[2] += c;
    state[3] += d;
    state[4] += e;
    state[5] += f;
    state[6] += g;
    state[7] += h;

    /* Clean up */
    a = b = c = d = e = f = g = h = T1 = 0;
}

The round macros are declared as follows:

/* Unrolled SHA-256 round macros: */

#define ROUND256_0_TO_15(a,b,c,d,e,f,g,h) do {                  \
    W256[j] = (u_int32_t)data[3] | ((u_int32_t)data[2] << 8) |      \
        ((u_int32_t)data[1] << 16) | ((u_int32_t)data[0] << 24);        \
    data += 4;                              \
    T1 = (h) + Sigma1_256((e)) + Ch((e), (f), (g)) + K256[j] + W256[j]; \
    (d) += T1;                              \
    (h) = T1 + Sigma0_256((a)) + Maj((a), (b), (c));            \
    j++;                                    \
} while(0)

#define ROUND256(a,b,c,d,e,f,g,h) do {                      \
    s0 = W256[(j+1)&0x0f];                          \
    s0 = sigma0_256(s0);                            \
    s1 = W256[(j+14)&0x0f];                         \
    s1 = sigma1_256(s1);                            \
    T1 = (h) + Sigma1_256((e)) + Ch((e), (f), (g)) + K256[j] +      \
         (W256[j&0x0f] += s1 + W256[(j+9)&0x0f] + s0);          \
    (d) += T1;                              \
    (h) = T1 + Sigma0_256((a)) + Maj((a), (b), (c));            \
    j++;                                    \
} while(0)


which en/decrypt algorithm should use for small byte array that result have same length I wanted to use Rijndael for encrypting big array of bytes, as you know this algorithm will add up to 15 byte to result (if you use block with length equal to 16). It is acceptable in most cases but in this case I can not afford such a thing (result length should be same as given length). So I think about using this algorithm for encryption but for a few remaining bytes use another algorithm. Which algorithm is proper for this conditions:

data can be small byte array with length less than 16.
result have same length as input array
be reserve able (decryption)(it is not password)
be safe enough (not out of date)

It also will be great if this algorithm work with small key (I prefer do not use all password/iv for this part).

(I use C#)

result have same length as input array

If you insist on this, then you must lose some security.

At the very least, there's no room for a given value to be encrypted in two different ways. This means that an attacker can at least tell whether two encrypted values are the same, because the encrypted values will be the same if the ciphertexts are the same.
You think that's not really a problem? But consider that in many scenarios, it means that an attacker can make guesses. They guess that the value is AB, arrange for you to encrypt AB and compare the ciphertexts. Repeat for AC, AD, etc. It isn't too bad if the attackers cannot submit plaintext, but that's rare. Most databases containing encrypted data contain some user-supplied input (e.g. names).
It's worse than that: usually, if two values start with the same prefix then their ciphertext will also start with the same prefix (except for the last few characters of the common prefix, depending on the mode). This is because most encryption modes proceed in a single pass, so they encrypt the first few bytes, then the next block and so on. If the first block of plaintext is identical and the ciphertext is the same size as the plaintext then the ciphertext for the first block will be equal if the plaintexts are equal.
Additionally, if the ciphertext is the same size as the plaintext then you may ensure some confidentiality of the data, but you won't be able to guarantee its integrity. There's no way to detect that the data has been modified without adding some redundancy information, and that redundancy information has to go somewhere.

Encryption modes solve this problem by including a unique value at the beginning of each ciphertext, called an IV¹. That's the reason why any sensible encryption mode results in ciphertext that's a little larger.

A second reason why the ciphertext is larger is padding, for modes that work on whole blocks at a time. This an be avoided by using a mode that doesn't have padding. Your library should offer CTR mode, which is fine if used correctly.

For CTR mode, like any other mode, you need a unique IV for each value that's encrypted. For CTR mode, you actually need a bit more than that: the counter value must be unique for each block. The counter value doesn't have to be random, although that's a popular choice, so it's ok to construct the counter value from the array index. If each value is at most $16 \times 2^n$ bytes long then you can use $2^n \times k$ as the IV for block $k$. (Note that the IV is a 16-byte string; be careful not to use a smaller type like 32-bit integers where you risk wraparound in arithmetic operations.)

Do note that this is only safe if the attacker sees a single version of the database. If the attacker sees multiple versions then they will see changed contents in some blocks that are encrypted with the same IV. This gives the attacker some information about the content of the block, possibly revealing both the old value and the new value depending on what partial information the attacker has on the values (data format, content of some guessable fields, …).

The simple option is to accept that storage is cheaper than security breaches, and use a high-level crypto API that doesn't require you to understand all the details.

A few more remarks…

  Rijndael

The modern name is AES. It's perfectly fine: it's the standard symmetric algorithm these days. “AES” only tells part of the story: it only says how to transform a 16-byte block of plaintext into a 16-byte block of ciphertext. To specify the algorithm, you also need to specify the mode which explains how to assemble the blocks together. Two popular modes for encryption only are CTR and CBC. (Some libraries provide a mode called ECB; never use it: this isn't a proper encryption mode, it's a building block for when you want to use a mode that isn't provided by the library.)

  this algorithm will add up to 15 byte to result (if you use block with length equal to 16)

No, actually the algorithm will add 16 bytes at the beginning for the IV. It may additionally pad the last block (CBC does, CTR doesn't).

  I can not afford such a thing (result length should be same as given length)

Scenarios where a few bytes are not possible are extremely rare. Think again.

If you really really really can't do the simple thing and use a proper mode with a proper IV, then I urge you to have someone competent review the code. I'm sorry to say, but if you needed to ask this question then the chances that you'll get it right are small, even after reading a few Stack Overflow and Stack Exchange posts.

¹  “IV” isn't the technically correct term for some modes, but it'll do.


Which is the most overall 'compatible' encryption type? What is the "MP3" of encryption formats today, which hopefully will make it easy and compatible to send to other recipients (not via e-mail), without them having to download and learn a software suite just to unlock what I sent them?

I work commercially and a part of it means sending people the end result files (usually multimedia files on the larger side). I do not work for a steady number of clients, so I need to deliver to all kinds of people where neither side knows in advance about how we prefer things done.
Most people I encounter in work aren't tech savvy when it comes to secure file transfers, and many express loud irritation from having to 'unlock' transferred files through some process they've never even encountered before. Their emotions about this tends to associate with me, as a content-delivery service, which might hurt business in the long run. But customers absolutely do want the files delivered 'securely'. That irritation, and wish for safety, are contradiction of course, but you wouldn't want to be the one to tell them that.

Some have also found their holy graal, in using AES256 or PGP or some other fairly known method, and here I come with something that doesn't correspond to that. Or, in some cases we both may be accustomed to 3DES encryption but we use different software to encrypt/decrypt, meaning my 3DES encryption won't unlock through the other guys' software even though it is the same basic encryption formula. Or the software needed to decrypt isn't available on the other person's platform.
People might also be in contact with other people who delivers files to them, meaning in the end they need to have multiple software suites installed and learned just to deal with all types of different encryptions and solutions. Sometimes topped off with a short temper.

Therefore I'm looking for advice/opinions about the probably most 'overall compatible' way of locking medium to large size files for sending over the internet, which might reduce the need for someone to adapt to me, or me to him/her. MP3 files can be used by virtually everybody. What is the MP3 of encryption, today?

Thank you for any thoughts and/or tips

A lot of (non-US federal) clients I work with request a shared Dropbox or Box for file transfer. If they want to feel "extra secure", non-tech-savvy clients in the past have enjoyed getting hardware-encrypted flash drives the most because they like how "simple and easy" it is to handle them. I don't necessarily endorse these approaches; as mentioned in the comments, marketing influences what your clients want, regardless of their requirements, but I have rarely been in a position to change their minds.

More grizzled war stories follow.

Sadly, the situation is more like "Client #1 wants MP3s, Client #2 needs WAVs, Client #3 will only talk to me if we go listen to concert music together", etc. I don't think you will find any particular format will scale to an arbitrary number of clients, who all have (or believe they have) specific needs.

Here is a sample of the scenarios I have encountered in the past decade or so:

Scientific data (C code, Fortran-77 code, text, Excel spreadsheets) sent to my lab:
password-protected DVD, client would send password in e-mail
Financial data from an insurance company: set up secure FTP server with developers on their side
Transmitting data within a company itself: Data is put into a MySQL database and I was asked to "please delete the data in a few days"
Financial data from a bank: Sent us an email that opened a web application that required a password so that we could download some data
Getting data from a university partner: Mailed us a USB-C drive with a keypad to enter a password, which...was written on a sticky-note

I'm not sure what kinds of clients you have, but I guarantee you that you will have one that will surprise you with what they want soon, if you haven't already had this happen to you!


Cycling hashing in PBKDF's and their limitations in strength? I hope this question isn't too similar to one that's already been asked. I also want to point out I know part the answer already, AFAIK: I just want some expert input on this.

Let's model a hash that more strictly is a possibly weak PBKDF. It would exist – if it worked – to slow down the cracking of passphrases (relatively short inputs), using well established secure hashes (i.e. SHA-2).

Looped hash on message (UserInput)

I'm well aware that modern ASIC/GPU technology would make cycling-hashing very brute-forceable on weak enough passwords and by cycling hashing I mean

PassHash := Hash(UserInput)
Do Loop 1024 times{
    PassHash := Hash(PassHash)
}
Output := PassHash

In this routine, "Hash" may be SHA-256 (NOT HMAC, but a regular Hash). This pseudo-routine would be just as vulnerable to rainbow tables as SHA-256, AFAIK.

So, let's purpose a small alteration, instead we use this (also bad) "KDF":

Looped hash on salted message (UserInput | Salt)

PassHash := Hash(UserInput | Salt)
Do Loop 1024 times{
    PassHash := Hash(PassHash | Salt)
}
Output := E(Hash(UserInput),Salt) | PassHash

E is performed with any good cipher that will take a 256bit key.

Above "Hash", would still be something like SHA-256. For example: Salt would be a randomly picked ~80 bits. The UserInput variable, (The Password/Passphrase) could be any length but ideally wants to be at least 112 bits.

PBKDF/2

In PBKDF/2, as I understand, we wouldn't use a HASH, but a HMAC (one reason being a lot of hash-functions are vulnerable to length-extension attacks).

Question

As I stated, I recon this code could be much worse than PBKDF2 and bCrypt and I can think of some reasons why. What I'ld like to know is: what are the biggest flaws in this routine, if any and why? And… maybe someone could demonstrate how we’ld go about attacking the design laid out above to show any major weaknesses?

Encrypting the salt is actually equivalent to just using the cipher as an initial step. That is, you could redefine the scheme as follows:

tmp := D(hash(password), salt)
password_hash = F(password, tmp)
output := salt, password_hash

Where D is the decryption function and F is the actual iterated password hash you defined.

The addition of the cipher is not significant from the point of view of slowing down dictionary attacks if it's a typical fast cipher like AES. It can only make a difference if the underlying hash function (which you call Hash) is completely broken to a degree e.g. MD5 is nowhere near being.

Note that the intermediate value, which I called tmp above and you called salt must be kept secret. Knowing it an attacker would be able to avoid the whole looping part and just test the encryption/decryption output. For that reason calling it a salt is a bit misleading.

The actual iteration function is very close to PBKDF1, as Richie Frame observed in the comments. It adds the salt at each iteration, but I do not see why that should be significantly stronger. It does not seem to offer any advantage over PBKDF2, but like PBKDF1 it is likely not significantly weaker either – with an iteration count that gives equal running time. (Any advantages PBKDF2 has are likely theoretical, but using HMAC may be a slightly better security margin. Or at least a security blanket...)

Compared to bcrypt it shares most of the advantages and disadvantages of PBKDF2. See e.g. Thomas Pornin's post on Security.SE for a treatment. The main difference being, of course, that yours is non-standard and could have undiscovered weaknesses. TL;DR is that bcrypt is superior due to having some GPU resistance, but does have some limitations like on password and output lengths.


Is there a formal definition of what a distinguisher is? I've often been reading about (polynomially bounded) distinguishers in books or papers. Although by name and intuition it is somewhat clear what a distinguisher is and does, but i am asking myself whether there is a concrete formal definition. Despite the concept being used frequently, i wasn't able to find one.

A distinguisher is an arbitrary algorithm. In fact, we do NOT want to formalize anything about the distinguisher (except that its output is a single bit, although we don't even really need to do this). In definitions, we require that no distinguisher should succeed with non-negligible probability. So, this should hold for any algorithm.

Of course, we do specify the complexity class of the distinguisher (either probabilistic polynomial-time or non-uniform polynomial-time).


How does fully homomorphic encryption compare to partially homomorphic encryption in terms of security? I found some questions and answers about the performance of Fully and Partially homomorphic encryption. I am interested in a comparison in terms of security guarantees (of any kind, formal or informal). I understand that there are various schemes for both and so a comparison between specific schemes is equally useful to me.

Is, for instance, Paillier/Elgamal more/less secure than FHE (both allow additions and multiplications)?

Is DET/OPE/ORE more/less(probably) secure than FHE (both allow equality and order comparisons)?

In short: They can not be compared, because those cryptosystems are vastly different constructions for different goals.

Taking a step back, usually the security of a cryptosystem is defined with a security parameter $\lambda$, and the security then is described as "... is less than a negligible function $f(\lambda)$ ...", so we can say that e.g. ElGamal with $\lambda = 10$ is less secure than ElGamal with $\lambda = 12$.

But as soon as looking at different constructions, this gets tricky, because they don't compare to the same negligible function any more. Also, they are just upper bounds and there is no statement possible like "it has exactly security $23$".

If you want to combine security with other aspects like runtime, then you run into other issues. Some cryptosystems have fast key generation, others have fast encryption or decryption, etc. There's just one rule of thumb: Quite surely any FHE construction is much, much slower than traditional PKE systems when aiming at similar levels of security. Also, if you consider runtime of a system and include this in your comparison, then you have to keep in mind you are comparing implementations and not the scheme itself.


Are quantum preimage attacks on hash-based random oracles serious for lattice signatures? For most of the lattice-based signature schemes in the hash-based random oracle model (like BLISS), quantum preimage attacks (e.g., Grover's alg) against the random oracle component of the signature are not considered in security estimates and this seems to be reasonable, because a preimage attack does not necessarily violate the unforgeability of the signature. But recently, some papers like Tesla, Tesla# and this,  take this kind of attack into consideration.

My question: is this attack really serious and should we look attentively at them in security estimates?

Yes, it is important.  In a lattice-based Fiat-Shamir signature scheme, the signature is (z,c) where z is a low-norm vector and c is a low-norm challenge.

The verification equation then satisfies c=H(Az-tc,m) where A and t are the public key (A is a matrix and t is a vector) and m is the message.  If the Adversary is able to find an m' such that c=H(Az-tc,m'), then (z,c) is also a signature for m'.  Thus having 128-bit classical pre-image resistance is not enough.


Challenge - Response protocol - how to incorporate client randomness I am designing a challenge-response protocol to enable a client to authenticate to a server.  The client has a private key, and a certificate (issued by a trusted CA).  At this point in the protocol, the server knows who the client claims to be, but wants to prove it.  My first attempt was:

$C ← S : r_S$

$C → S : S_C (r_S)$

where:

$r_S$ is a random challenge generated by $S$ (the server).
$S_C(r_S)$ is a signature of the challenge, signed with $C$'s (the Client's) private key.

The problem with that, is that the private-key + certificate may be used for other purposes than identifying the client to the server.  (For example, authorizing invoice payments.)  A compromised server could send the client the hash of an invoice payment authorization, and get back the necessary signature to authorize it.

Next attempt:

$C ← S : r_S$

$C → S : r_C, S_C (H(r_S | r_C))$

where:

$r_C$ is a random nonce generated by $C$.
H is a suitable cryptographic hash function
other terms are as above

Is this secure?  Specifically, can a compromised server use such a scheme to calculate $S_C(V)$ for some predetermined value $V$?

In particular,

would it be safer to put $r_C$ first in the concatenation?
and is simple concatenation good enough, or do I need to do something like calculate $\text{HMAC}_K(r_S|r_C)$ using a hardcoded key $K$ or even $\text{HMAC}_{r_C}(r_S)$ (using $r_C$ as the key to the HMAC)?

Using the same certificate/private key for different purposes should not be allowed whenever possible.
The answer to your question firstly relies on the security of the signature scheme you use. If the signature scheme is unforgeable, then you should be largely fine. Unforgeability means the malicious server who can chosen any messages and get the corresponding signatures but still cannot forge a signature of a message which it has not queried. The server gets only signatures of $H(r_s||r_c)$, but cannot generate other signatures. Then the question is how likely $H(r_s||r_c) =m$ where $m$ is something meaningful and the server wants the signature of it. In this case, unforgeability is not enough because the server simply can reuse the signature without needing to forge one. If $H$ you use is collision resistance and $r_c$ is long enough, then $H(r_s||r_c)$ should be a uniformly random value. It is unlikely $H(r_s||r_c)$ is meaningful and the probability of this case is negligible.
The order does not matter and MAC is not needed. Note here the message gets signed is $H(r_s||r_c)$ (this hash value will be hashed by the hash function used by the signature scheme), not $r_s||r_c$.


Secure Computation: Reactive Functionalities in the Hybrid Model for Standalone Security A common approach to make (secure computation) protocol descriptions and proofs simpler is to describe them in a hybrid model, where the protocol in the real world has access to some auxiliary ideal functionality F (e.g. an ideal OT functionality). Lets say I only care about standalone security (vs. UC). Assuming all calls to F are sequential (i.e. not interleaved or in parallel) and the parties do not communicate with each other in between starting a call and finishing it, then (as far as I understand) I can use regular sequential composition of standalone secure protocols to instantiate the hybrids with standalone secure protocols to obtain an overall standalone secure protocol.

My problem is with reactive functionalities, i.e. functionalities that keep a state and, for the sake of concreteness, with commitments.
Say, for example, I want to prove Blum's coin tossing protocol secure in a commitment hybrid model (see here for the protocol and a proof, which is not in the hybrid model).

Protocol recap: Alice and Bob want to toss a fair coin:

Alice commits to a random bit $r_a$.
Bob publishes a random bit $r_b$.
Alice opens commitment and the output of the protocol is defined as $r_a \oplus r_b$

It seems I run into a problem, because I cannot instantiate my hybrid with a standalone secure commitment scheme, because in between Alice doing the commitment and Alice opening it, the parties communicate.

What is the most common way of circumventing the issue?
The only thing I could find right now was in Complexity of Multi-Party Computation Functionalities, where the authors state (in Footnote 8 on page 6):

  A reactive functionality can be reduced to a non-reactive
  functionality by secret-sharing the internal state of the functionality among all n parties

I don't understand what this means. What does it mean (concretely for the example of coin tossing) and is this the most common approach of handling my described issue in the coin tossing example?

First, your question about that footnote. I guess I can expand on it since I'm probably the one who wrote the footnote.

You can model a reactive functionality as follows:

Fix an initial value for the (private, internal) state $s$
Repeat forever:

Receive input $x$ from Alice and $y$ from Bob
Compute $(s', a, b) \gets f(s, x,y)$
Give output $a$ to Alice and $b$ to Bob, and set $s := s'$

Here $f$ is a deterministic function that characterizes this functionality. The initial value of $s$ is public information. What is being proposed in that footnote is the following protocol for the reactive functionality:

Alice & Bob fix secret shares $s_A, s_B$ for the initial value of $s$
Repeat forever:

Perform a secure computation of the non-reactive functionality:

  $g\Big( (s_A, x), (s_B,y) \Big) = \Big( (a,s'_A), (b, s'_B) \Big)$, where $(s',a,b) \gets f\big(\textsf{Reconstruct}(s_A,s_B), x,y\big)$ and $(s'_A, s'_B) \gets \textsf{Share}(s')$

in other words, Alice gives input $(s_A,x)$ and Bob gives input $(s_B,y)$ to this computation. Alice receives output $(a, s'_A)$ and Bob receives $(b,s'_B)$.
Alice updates her share $s_A := s'_A$ and Bob does too: $s_B := s'_B$

This protocol's invariant is that at every step the parties hold secret shares of the reactive functionality's internal state. At each step they perform a non-reactive computation that reconstructs the internal state and performs one step of the reactive functionality.

For semi-honest security any standard secret-sharing scheme is fine to use here. For malicious security, you need to be able to detect tampering of shares (since nothing prevents Alice from receiving $s'_A$ as output in one round and giving something other than $s'_A$ as input to the next round).

Now for your specific concern about commitment. You are right that there is communication between the parties during the lifetime of the commitment functionality. And if you think of the entire lifetime of the commitment functionality as one unit, this is problematic for rewinding/simulation in the standalone setting.

But the commitment functionality has two phases: commit phase & reveal phase. The way around the issue is to require simulators that are local to each of these phases. That is, when you are simulating the reveal phase, you can't rewind to before the reveal phase (although you may have done some rewinding in the commit phase, you are now stuck with that history after you declare the commit phase to be done).

If you look at the typical security definitions for commitment, that is exactly what they say.

In a simulation-based definition for commitment, we define binding by means of an extraction game. A corrupt committer can't distinguish between committing to an honest receiver vs committing to a rewinding simulator which extracts the committed value. This is really just a statement about the commit phase only (well, mostly).
We define hiding by means of an equivocation game. A corrupt receiver can't distinguish between talking to an honest committer vs talking to a locally-rewinding simulator which doesn't get the value until the reveal phase starts. Again, this simulator is allowed to rewind in the commit phase, and in the reveal phase, but it is not allowed to rewind the reveal phase all the way back in time to the commit phase.

If you are wondering whether this means that we're already requiring stronger UC security rather than standalone, it's helpful to think of a commitment protocol that has a 10-round commit phase and 10-round reveal phase. If this protocol was UC-secure, you could use it in a larger protocol, and ask the parties to send additional messages in round 7 of the commit phase. But it's no good for the standalone definition I gave, since there may be rewinding taking us back and forth across round 7 many times. So this standalone definition says: each individual phase of the reactive functionality should be "atomic". That is indeed what happens in the description of your coin-tossing protocol: do the commit phase, wait for it to be done, only then send your random bit. So that is why your coin-tossing protocol is standalone-secure when instantiated with standalone-secure commitment.

In summary, communication between parties is kosher during the lifetime of the reactive functionality, but only as long as it is in between the distinct "phases" of the reactive functionality.


External data loading in DES Trying to write a C program that implements the DES standard (FIPS 46-3). I am unsure about how the standard should be interpreted when computing the various permutations specified in the document, with regard to the external data that is loaded in the algorithm.

For example, the IP (Initial Permutation) takes the 64 bits of input and arranges them so that the result has bit 58 of the input as its first bit, bit 50 as its second bit, and so on.

Assuming (is this correct?) that "first bit" of output means MSB, the problem still remains with what is meant by "bit 58" of input. Where do we start counting?

For example, if the input is read from a file in a buffer (C array) of 8 bytes, where is the 58th bit to be found: in buffer[0] or in buffer[7]? Both seem plausible: in buffer[0] (because logically is the last in the row, assuming it was read first) and in buffer[7] (assuming we believe we are reading an integer starting with its MSB).

What is the community consensus about this issue?

Thank you.

All standard literature on DES, including FIPS 46-3, number data bits starting from 1 for the most significant bit of the first word in reading order, incrementing by 1 as we go to lower-order bit, and moving to the next word after each multiple of the word size in bit. Here word can be 8-bit (for data and key), 32-bit (state formed by L/R), 28-bit (internal key formed by C/D).

For an implementer manipulating an array of 8 bytes at indexes 0 to 7 as input of IP, bit $i$ is for byte at index $\left\lfloor(i-1)/8\right\rfloor$ and has weight $2^{(-i)\bmod 8}$. In C, it might be testable as

Buffer[(i-1)>>3] & (128>>((i-1)&7))

Bit 58 belongs to the last of 8 bytes, Buffer[7], with weight 64 ( 0x40 ).


Security of OFB mode if PRP is used instead of PRF In the cryptography lecture at my university, we had the theorem that (randomized) OFB mode is IND-CPA secure if the used pseudorandom function (PRF) is IND-PRF secure.

Afterwards, we investigated the security of rOFB if a pseudorandom permutation (PRP) is used instead of an PRF. As we can only distinguish a PRP from a PRF if the PRF produces a collision, we can use them interchangeably as long as the block length is large enough. This is the case as for large block lengths the probability of a collision is negligible.

From this result we deduced that we can also use PRPs in rOFB mode which results in a IND-CPA secure encryption scheme.

I totally understand that we can distinguish a PRP from a random function oracle (RFO) if the RFO produces a collision. Therefore, the PRP 'does not look random' if we can query many outputs. However, the security of rOFB mode requires that we do not have a collision in the ciphertexts. Therefore, I do not understand why the security of rOFB mode is lower when we use a PRP instead of a PRF (negligibly lower, but lower) as a PRP does rule out exactly this attack on OFB.

It is clear for me that the PRP-OFB mode does not look like an OTP for many queries, but I cannot imagine why the attack surface should be negligibly higher if there is NO collision possible.

I think the final negligible term depends on the way you prove the rOFB security. If you construct OTP in the ideal word based on random functions, then use PRF; if based on random permutations, then use PRP. Note that in the latter case, replacing block ciphers with random permutations cannot guarantee that no collisions happen among the block cipher outputs. In other words, such collisions are not the same as those considered in PRF/PRP.

The attack surface for PRP is not negligibly higher. It seems higher just because you first prove the security with PRF and wants an easy reduction based on the advantage difference between PRP and PRF. Btw, any negligible difference should not matter in the security proofs.


ElGamal message signatures retrieving the secret value x If the GCD(r, p-1) is small and the value k is used to sign a message using ElGamal is also small.  Then the secret value of x can be determined.

Why is this true?  How would one retrieve x?

$\newcommand\gcd{\operatorname{gcd}}$Let's have a look at the signature equation:

$$ s = (H(m) - x·r)·k^{-1} \mod (p-1), $$
$$ s·k = H(m) - x·r  \mod (p-1), $$
and thus
$$ H(m) - s·k = x · r \mod (p-1).$$

$d = \gcd(r, p-1)$ means we find (efficiently, given $r$ and $p-1$, using the extended euclidean algorithm) a $z$ such that $z·r = d \mod (p-1)$ ... this can be regarded as an "almost-inverse" for $r$ if $d$ is small.

If we multiply the equation above by $z$, we get
$$ z·(H(m) - s·k) = x·d \mod (p-1)$$

$s$ and $r$ are the signature, $m$ and $y = g^x$ are also known to the attacker, $d$ is a known small divisor of the modulus, and $k$ is also "small", which means that we can brute-force over all possible values of $k$ and for each one see if there is a solution for $x$.

The moral of the story: Use a random $k$, which will most likely not be small.


My implementation of Serpent is bit-sliced, so there is no initial permutation involved in generation of my round subkeys. It is also NESSIE byte ordered, which means that vectors will not match the AES submission package. I assume that IP will reorder the bits appropriately if you are using a non bit-sliced version. I just rewrote most of my implementation this weekend, so I am quite familiar with it. It has been confirmed to match NESSIE monte carlo test vectors.

You are also missing several very important sections of the key schedule algo. It actually works like this:
The key is copied into the first words 0-7 without modification.
The next word after the key gets a value of 1 (128 or 192-bit keys only).
Words 8-15 are filled the following algorithm:
$w_i=(w_{i-8}\oplus w_{i-5}\oplus w_{i-3}\oplus w_{i-1}\oplus\phi\oplus (i-8))\lll 11$

Words 8-15 are then copied back to 0-7.
Words 8-131 are filled the following algorithm:
$w_i=(w_{i-8}\oplus w_{i-5}\oplus w_{i-3}\oplus w_{i-1}\oplus\phi\oplus i)\lll 11$

The words are then run through the s-boxes sequentially in reverse starting at S3 to generate the subkeys; in the bit-sliced implementation they are run in groups of 4.

Also, the key in your post is only 224 bits, I assume it is missing a group of 0s and used that missing group below.
Here is what I get for round subkeys when taking your input key as a stream of bytes.
The endianness of these values may not match your print format, the bits were literally just copied directly to a byte array for printing. Display of the 32-bit values as per most methods will result in each octet being on the opposite side of the word.

All 32-bit values displayed in Big-Endian notation (bitstream)

Using 256-bit key (bitstream)
15fc0d48d7f8199cbe3991834d96f32710000000000000000000000000000000

Working register values w()
00 = 8e0f9f48 558a778c 8e84528e f8bb274b
01 = cb02403a 15bb83d7 773c9827 6d601cee
02 = 20fdb580 79cc8369 03e251cf ebf50867
03 = 270a1401 3a28bd26 8c44a3ca a69bab6d
04 = 94f117e6 d07657a0 d125f73a 7b47e4e0
05 = 913dccde d515c235 0fe9ca28 fb399a68
06 = 2c061be7 7b11eeee bb3809b3 10084a5f
07 = ce24252b a646b113 a7287b46 4779a4d3
08 = 3327429a 3ecc1d2a 39fe97b5 463d019c
09 = 8566ab56 a7af05c4 523d7fa8 36b82985
10 = caaea3c3 4a9c05ea 048c6348 0c41da4a
11 = 6b07d353 11b49c0f c8946c59 ce3af016
12 = 7180c410 7283b04f 0414c147 d4dec121
13 = ab75cc28 731f6211 c2957c45 156db9b5
14 = 5f10aa4a b42756e8 abacc2d9 4f037314
15 = fb072e3a 30c1ef9e cc754c08 017e5076
16 = 42c1ae8e 55ce696f 01a6211d 8cd0413b
17 = 33f4f608 dde45d09 58beb177 50ac5c0f
18 = 6e9105c9 380265e3 333baa94 7bdceb45
19 = f8a9fe9f a962f4dc 9f2cdae3 cf935f2b
20 = 2bd72c96 bae44cd1 6321b8d2 e433fa93
21 = 4123a404 1760729e 09cd114f 63512829
22 = 65d162dd cdbe1365 f6ccb936 48e5d43c
23 = 531782e2 489899e0 431bb9c3 041d43ef
24 = 82c345de 223844d0 b81b4280 fa59ffea
25 = 4a959268 412267dd d22d0891 45d03f66
26 = 8e688da8 fb208f24 0da48415 c6ca0b4e
27 = d03fb7f6 47304675 87f873ec ba4f5646
28 = 5de2230d 6acde1fb 1a8a7a13 10611eb1
29 = 21eb2e4d c06d5736 77900762 21c73996
30 = 136c8322 437b1fe5 41de13e1 75bcd7f1
31 = 8f9a9744 7bc9e639 88ee3ff7 d50aa5a8
32 = e18e5703 5eeec4bf 8d52541c 3e5cbde7

Subkeys k() after application of s-boxes (bit-sliced)
00 = afb59841 dd00fa8e a8bacf8d 23348a0b
01 = 4ce7073c d19dc3e3 86e147c4 525aa4f1
02 = 853bc859 5f198377 4ee8a43e 6c376530
03 = d822f75b f2fd42d8 98b30a6f 11f7a181
04 = efadfb05 ba6117b8 7e86447c 85e2b39e
05 = da3e695c b43a7faa be163115 bad05261
06 = 17de1812 50c1e509 bcee50b9 2bd843fc
07 = 7f8c346a a83511a9 ce60ef3e 2f2a7a6f
08 = 712b4b90 3cf45cb4 4aecd5b9 4116ca07
09 = c30e78e9 60e5fd3a 26cc8297 a9872e41
10 = 73419a9c 779cc5bc f72242d5 b9ae8317
11 = 93d62ca9 944cb0e3 96aa2c4c 361f0301
12 = 8f7d7fb9 d2c9f06e 834bb439 57973518
13 = 3378d836 4f10698b e5021786 07f2f3e5
14 = f0746a92 5b43f420 0bdb585b b46790d8
15 = 33726221 324d7e5a 07474c2c 06b48192
16 = 9a19a7c5 178fe6fc 8bf7878b dab98ed8
17 = c5420071 bea61b70 e610ee09 0951a980
18 = d2f63410 d188fea6 a71ade0c ceb051d9
19 = 67e1a0f4 167c85a8 dedb5160 c9f5d180
20 = 5629b32e 36012ad2 b4324a95 d300d005
21 = c2212005 a053bc2e b4307ab3 7cdc6bfd
22 = c19dd3ed 29777279 1e6498b2 ad38a341
23 = b07c1fd1 5409d92e 501da3c2 189138e3
24 = e0fbb92e 98a14284 e299fce4 58a2fab4
25 = 94da502a d92ae595 0f47e746 2765259f
26 = 055f707f 78f9f62c 459172a0 ce7dff99
27 = 57774833 28f02da9 3d4723c7 3ab7c26f
28 = bd94be54 3acce643 252584f5 2dc7b8e4
29 = 29efbe14 69c187af c869c0e4 96536f86
30 = db9ab3eb da15bccd c8d434cb 8ae22408
31 = 065824b1 8bd2a331 dcbe2f2a a17fcd93
32 = ad627b44 1232d6b8 0c4c3e5f c1b02e40


Security of Paillier against chosen ciphertext attack Is there a proof by now that Paillier is secure against chosen-ciphertext attack? The original Paillier paper mentions that it is not.

Is it yet proofed that Paillier is secure against chosen-ciphertext attack. The original Paillier paper mentions that it is not.

It is indeed not - CCA security is incompatible with the property of partially homomorphic encryption.
If we have a ciphertext $C$ and an Oracle that will decrypt any ciphertext (other than $C$), what an attacker can do to decrypt $C$ is generate the encryption of $0$ (which is presumably not the ciphertext value $1$), and homomorphically add that to $C$, generating the ciphertext $C'$, and hand $C'$ to the decryption oracle.  As long as the encryption of $0$ is not $1$, then $C \ne C'$, and so the decryption oracle will have us the plaintext corresponding to $C'$, which will be exactly the same value as the plaintext of $C$ - the attacker wins.


Post-Quantum Blind Signatures? Are there any post-quantum blind signature algorithms?  Since hash-based blind signature schemes have proven to by impossible (based on a response to this question) is this an active area of research or is it only feasible by using extraordinarily large pre-quantum algorithm keys?

This is adressed for example in Lattice-based Blind Signatures by Markus Rückert, 2008. I only had a quick glance, and it seems there is a construction for building blind signatures based on lattice problems.

But this isn't surprising, because lattice problems can be used for:

building post-quantum encryption schemes, key exchange, signatures, etc.
building fully-homomorphic encryption schemes. Such a system preserves a lot of algebraic structure (in contrast to OWFs), and it should be quite easy to use this to create blind signatures (which are often based on some semi-homomorphic property)


LSB extraction in MPC: Doubts about correctness I have doubts about whether the protocol below for LSB extraction (denoted Mod2) from the paper Improved Primitives for Secure Multiparty Integer Computation is correct. Clarifications will be appreciated.

The protocol above calls PRandM(k, 1) in line 1 to generate random shared values $r''$ and $r'_0$ (it ignores $r'$) and then uses them in line 2 to blind $a$ and then reveals it to extract the LSB of the blinded value after which it computes the random secretly shared value $a_0$.
The protocol $looks$ correct because the LSB of $c$ is essentially $r_0\oplus a_0$ and then in line 3 we XOR it again with $r'_0$.
That is... in case $2^{k-1}+[a]+2\cdot [r'']+[r'_0]$ doesn't overflow the prime field $p$.
When it overflows the prime field, then the LSB flips and then the math is no longer true.
We also don't know whether $c$ overflows or not, because $[a]$ can be $p-1$ and in that case $c$ will be bigger than $2^{k-1}$ .
Any idea what I am missing here?

The protocol is only designed to work when $a$ is in the range $\{-2^{k-1},\dots,2^{k-1}-1\}$. This ensures that $c$ doesn't overflow mod $p$, as long as $p$ is sufficiently large.
In the paper they ensure this by choosing $p > 2^{k+\kappa+\log n}$, where $\kappa$ is a statistical security parameter and $n$ is the number of parties. See the discussions on p3-5.


Effect of CFB IV reuse If an Initialization Vector (IV) is reused (under the same encryption key) in Cipher Feedback Mode (CFB), what is the effect upon security?

I know there is some negative effect upon security, but I can't figure out if it leaks information about just the blocks with the same IV, or if it destroys security for all the data encrypted under that key.

It just leaks information about the blocks with the same IV.

Specifically, if the two messages encrypted with the same IV started with blocks $M_0$ and $M'_0$, then the attacker learns the value $M_0 \oplus M'_0$ (and if those where the same, then the attacker also learns the corresponding xor with the second block, etc)

However, the attacker learns nothing about the key, or about any message that wasn't encrypted with a shared IV.


Help deciphering caesar cipher I have to to find the shift value and the message for the following caesar cipher.
OC_VAWDGPM_VHWTVX_VXJOCVZ_GDX_MWO_VWIZVYGWIZ_NODI_

I have already tried it and with the shift value of 21 i get the following.
TH_AFBILUR_AMBYAC_ACOTHAE_LIC_RBT_ABNEADLBNE_STIN_

Does this look like the correct decrypted message to anyone?
How am i supposed to determine the correct answer?
I think I'm doing something wrong

Here are all the possible decryptions:

NB_UZVCFOL_UGVSUW_UWINBUY_FCW_LVN_UVHYUXFVHY_MNCH_
MA_TYUBENK_TFURTV_TVHMATX_EBV_KUM_TUGXTWEUGX_LMBG_
LZ_SXTADMJ_SETQSU_SUGLZSW_DAU_JTL_STFWSVDTFW_KLAF_
KY_RWSZCLI_RDSPRT_RTFKYRV_CZT_ISK_RSEVRUCSEV_JKZE_
JX_QVRYBKH_QCROQS_QSEJXQU_BYS_HRJ_QRDUQTBRDU_IJYD_
IW_PUQXAJG_PBQNPR_PRDIWPT_AXR_GQI_PQCTPSAQCT_HIXC_
HV_OTPWZIF_OAPMOQ_OQCHVOS_ZWQ_FPH_OPBSORZPBS_GHWB_
GU_NSOVYHE_NZOLNP_NPBGUNR_YVP_EOG_NOARNQYOAR_FGVA_
FT_MRNUXGD_MYNKMO_MOAFTMQ_XUO_DNF_MNZQMPXNZQ_EFUZ_
ES_LQMTWFC_LXMJLN_LNZESLP_WTN_CME_LMYPLOWMYP_DETY_
DR_KPLSVEB_KWLIKM_KMYDRKO_VSM_BLD_KLXOKNVLXO_CDSX_
CQ_JOKRUDA_JVKHJL_JLXCQJN_URL_AKC_JKWNJMUKWN_BCRW_
BP_INJQTCZ_IUJGIK_IKWBPIM_TQK_ZJB_IJVMILTJVM_ABQV_
AO_HMIPSBY_HTIFHJ_HJVAOHL_SPJ_YIA_HIULHKSIUL_ZAPU_
ZN_GLHORAX_GSHEGI_GIUZNGK_ROI_XHZ_GHTKGJRHTK_YZOT_
YM_FKGNQZW_FRGDFH_FHTYMFJ_QNH_WGY_FGSJFIQGSJ_XYNS_
XL_EJFMPYV_EQFCEG_EGSXLEI_PMG_VFX_EFRIEHPFRI_WXMR_
WK_DIELOXU_DPEBDF_DFRWKDH_OLF_UEW_DEQHDGOEQH_VWLQ_
VJ_CHDKNWT_CODACE_CEQVJCG_NKE_TDV_CDPGCFNDPG_UVKP_
UI_BGCJMVS_BNCZBD_BDPUIBF_MJD_SCU_BCOFBEMCOF_TUJO_
TH_AFBILUR_AMBYAC_ACOTHAE_LIC_RBT_ABNEADLBNE_STIN_
SG_ZEAHKTQ_ZLAXZB_ZBNSGZD_KHB_QAS_ZAMDZCKAMD_RSHM_
RF_YDZGJSP_YKZWYA_YAMRFYC_JGA_PZR_YZLCYBJZLC_QRGL_
QE_XCYFIRO_XJYVXZ_XZLQEXB_IFZ_OYQ_XYKBXAIYKB_PQFK_
PD_WBXEHQN_WIXUWY_WYKPDWA_HEY_NXP_WXJAWZHXJA_OPEJ_
OC_VAWDGPM_VHWTVX_VXJOCVZ_GDX_MWO_VWIZVYGWIZ_NODI_

You are actually doing the right thing, however you do not include the "_" as part of the characterset. Assuming the alphabet consists of 27 letters (A-Z and "_"), and using the appended JavaScript script (you can simply paste it into the console), returns one sentence which actually does make sense:

THE_FAILURE_MAY_BE_BOTH_DELIBERATE_AND_CLANDESTINE

var ciphertext = "OC_VAWDGPM_VHWTVX_VXJOCVZ_GDX_MWO_VWIZVYGWIZ_NODI_";

var alphabet = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","_"];

var rotation = 1;

var cleartext = "";

while (rotation < 27) {
for (var i=0,l=ciphertext.length;i<l;i++) {

  var character = ciphertext[i];

  var index = 0;

  // get the number in the alphabet
  for (var j=0;j<27;j++) {
    if (alphabet[j] === character) {
      index = j;
      break;
    }
  }

  // rotate

  cleartext += alphabet[(index + rotation) % 27];
}

console.log(cleartext);
rotation++;
cleartext = "";
}

EDIT: There is one thing I wanted to add regarding the script above. We are doing $index + rotation \bmod 27$ here because we are trying every possibility. In a strict sense this is another encryption of the ciphertext, only that one rotation must of course result in the cleartext. If $rotation$ is already known and you want to decrypt the cipher using this exact value, you would of course have to calculate $(index - rotation + 27) \bmod 27 $.


How to go about decrypting a cipher with known input and output? I have a known input and a known output but how would I go about working out what the cipher was used. Below are a few examples of input and output.
On the last one I noticed a repeating pattern. Would that point me in a particular direction?

Block size 8 symbols because repetitions. it is not caesar or vigenere because next symbol (B instead of A) in input doesnt mean next symbol in output(j instead of i). It is primitive cipher because 1 letter input makes 1 letter output. Closest thing is likely enigma, the world war 2 cipher machine. To decode think about it as 8 substitute ciphers. Symbol in positions 1+8n, where n=0,1,2,3,4... uses first substitution cipher. symbol in position 2+8n, where n=0,1,2,3,4... uses second substitution cipher.
How to test if im right: enter BA in input. Output will be Di.
How to recreate it: write down substitution alphabet for symbol 1 by entering in input A, then B, then C... and writing down the output. You will get a table that says 'if A then X'. Repeat for the second position, it will give you second substitution alphabet. In total you will get 8 substitution alphabets. Then you can turn letters into numbers. Im almost certain that author was lazy enough to code this substitution with math, and not actual alphabets. Seeing letters in substitution alphabets in a form of numbers you can make equations. A=1, B=2, C=3, ... X=26, A multiply 5+21=X, 1 multiply 5+21=26. Once you figured out the math for each symbol position, you can figure out math for going from symbol 1 to symbol 2, likely the same operation as converting a symbol from input to output. At this point you will have a compact representation of author's algorithm.


What functions allow for practical indistinguishability obfuscation? Recently, there has been a major theoretical breakthrough in program obfuscation, in the area of indistinguishability obfuscation.

Background: Indistinguishability obfuscation is a form of program obfuscation, with the following security property: if $C_1,C_2$ are two different circuits that both compute the same function, then $\text{Obf}(C_1)$ should be indistinguishable from $\text{Obf}(C_2)$, where $\text{Obf}(C)$ is the obfuscation of the circuit $C$.  In other words, if there are multiple ways to implement a particular functionality, the obfuscation of an implementation doesn't reveal anything about the implementation choices you made, though it might reveal the input-output function completely.

The recent breakthrough shows how to achieve indistinguishability obfuscation of any circuit in NC1.  This is a huge step forward in the theory and foundations of obfuscation.  Unfortunately, the construction is highly inefficient -- the obfuscated circuit is hugely slower than the original -- so the scheme described in this breakthrough paper is totally impractical.  However, often in cryptography if we focus in on special classes of functions, we can come up with specialized schemes that perform a lot better.

My question: What functions do we know how to obfuscate (in the sense of indistinguishability obfuscation) efficiently?  Are there classes of functions for which we can provide indistinguishability obfuscation, where the obfuscated circuit/program is efficient, and if so, what are they?  I'm fine even if the scheme relies on non-standard hardness assumptions, or even a construction where we have no proof of security but where it seems plausible that it might be secure.

Canetti ("Towards realizing random oracles," Crypto 1997) gave a reasonably efficient (very efficient, by the standards of most obfuscation work) "virtual black-box" obfuscator for "point functions," i.e., functions of the form $I_x(y) = 1$ if $x=y$, $0$ otherwise.  Such functions can be used, e.g., for password checking.

Virtual black-box obfuscation implies indistinguishability obfuscation, and is impossible for general circuits, but seemingly possible for specialized functions (like point functions).

In Canetti's construction, evaluating an obfuscated point function requires only one call to a collision-resistant hash function, and one exponentiation.  Its security relies on some strong, nonstandard, DDH-like assumption.

There are follow-up works by Wee and Canetti-Dakdouk, among others, on obfuscating point functions, hyperplanes, large-output functions, etc. etc. with VBB security.

Also, Lynn-Prabhakaran-Sahai ("Positive Results and Techniques for Obfuscation," Eurocrypt 2004) gave VBB obfuscators for certain classes of access-control functions, which I believe are not exceedingly inefficient.  They work in the random oracle model, however.

These are just a few representative works from prior to the iO revolution, when people were mainly working on VBB obfuscation for specific classes of functions.


Attacks on the RawCBC-MAC if the final step of encrypting with a second key isn't done This is from Boneh's lecture ECBC-MAC

Here is also a link to the lecture itself - https://www.coursera.org/learn/crypto/lecture/QYT6i/cbc-mac-and-nmac
CBC-MAC with $(K_1, K_2)$ on a message $M$ applies RawCBCMAC with $K_1$ to message $M$ & takes the output tag & runs the PRF on the tag using a second key $K_2$
Boneh explains a chosen message attack on RawCBCMAC

Ask the oracle for the tag on a 1 block message $m$. Let's say the tag is $t$.
Now the same tag $t$ will also be the tag for a 2nd message $ (m || t \oplus m)$

Yes, this will indeed work.
I can think of another attack on the RawCBCMAC

Ask the oracle for the tag on a message $m$ (can be any number of blocks). Let's say the tag is $t$.

Ask the oracle for the tag on a single block message ($w \oplus t$). Let's say the tag is $t'$

Now the tag for the message $(m || w)$ is same as $t'$

Is this also a valid attack on RawCBC or am I missing something?

Is this also a valid attack on RawCBC [...]?

Yes. Writing down the expressions, we get $t=F(k,m)$ and $t'=F(k,w\oplus t)$ - while abusing notation and meaning RawCBCMAC for multi-block invocations of $F$. Now the actual tag for $(m\|w)$ would be $t''=F(k,F(k,m)\oplus w)=F(k,t\oplus w)$ which is equal to $t'$.


MAC security and adversaries with memory The usual definition of MAC security is (roughly) that there is no "efficient" adversary that has non-negligible advantage in the "MAC game" where the MAC game is as follows: the challenger chooses a random key, the adversary sends some messages to the challenger, the challenger sends the MACs of those messages with the chosen key back to adversary. For the adversary to win, the adversary now has to come up with a forged message-MAC pair. The adversary's advantage is the probability that the adversary can win the game.

Every time the adversary plays, a new key is chosen by the challenger. Does it make a difference if we allow the adversary to have a "memory" of previous plays?

For example, in round 1 of the game the challenger generates a random key $k_1$ and the adversary sends $s$ messages getting back $s$ tags, but has no idea of how to forge a MAC, losing round 1.

In round 2, the challenger generates a new random key $k_2$, the adversary sends the same $s$ messages and, because of some weakness in the MAC algorithm and the fact that keys $k_1$ are $k_2$ are different, in round 2 the adversary can now come up with a forgery. Of course, for this to make sense, the adversary must be allowed to "remember" the results from round 1.

Maybe there are MAC algorithms that are secure against adversaries that do not remember results from round-to-round but insecure against adversaries that are allowed to have some memory.

Adversaries with this sort of memory are at least as strong as adversaries without memory. Are they strictly stronger?

Memory of the first round can't help the attacker win the second round.

If it could: the attacker could simulate the first round on his own (picking his own key, pretending to play the game against himself), and then play the second round against the challenger.

So, adversaries like this are not stronger -- not even if they have memory.


Why work in a subgroup QR(n) of an RSA group $Z^*_n$? I sometimes read in papers that a (sub-)group generator $g$ is taken from $\mathrm{QR}(n)$ instead of $\mathbb{Z}^*_n$, where $n = p \cdot q$ and $p$ and $q$ are prime. Is there a reason for this? What properties does $\mathrm{QR}(n)$ have? Is it an especially big subgroup?

Well, the reason that a specific cryptographical object needs to work in a specific subgroup probably has to do with the details of that object, and the cryptographical properties it needs from the subgroup.

One obvious possibility is that they need to avoid leaking information via the Jacobi symbol; that is an easily computed function that maps values in $Z^*_n$ into the values in the set $\{1, 0, -1\}$; it is interesting because the RSA operation preserves it; $Jacobi(x) = Jacobi(RSA(x))$ (where $RSA$ is either the public or the private operation, and $Jacobi$ implicitly relies on $n$).

Depending on what you're doing, this property may allow people to track which inputs refer to which outputs (for example, if you're shuffling values by encrypting them, and then randomly permuting them).  One way of making sure this sort of thing doesn't lead to a problem is to specify that all input values are in $QR(n)$; all these values have Jacobi symbol 1, and so there's no leakage.

It's also easy to create random values in $QR(n)$; pick a random number $r$ relatively prime to n, and compute $r^2 \bmod n$; that's a random value in $QR(n)$

As for the size of $QR(n)$, well, that'd be $(p-1)(q-1)/4 \approx N/4$; obviously, that's a fairly sizable group.


What is the difference between Poly-LWE and Ring-LWE? I am often confused by Poly-LWE and Ring-LWE, always thinking that they are different names for the same thing. In some literature, Poly-LWE is a simplified version of Ring-LWE? What is the difference?

One main difference is that in Ring-LWE, the ring $R$ is the full ring of integers $\mathcal{O}_K$ of a number field $K$, whereas in Poly-LWE it is of the form $R=\mathbb{Z}[x]/f(x)$ for some irreducible $f(x)$; this ring is (isomorphic to) an order of the number field $K=\mathbb{Q}(x)/f(x)$, but may not be the full ring of integers.
Another important difference is that in Ring-LWE, the (non-noisy) products $a_i \cdot s \in R^\vee_q$ belong to the dual (fractional) ideal $R^\vee$ of the ring (modulo $q$), whereas in Poly-LWE, all of $a_i, s, a_i \cdot s$ belong to $R_q$. While the latter is technically simpler, there are several advantages that come with using the dual form.
A third important difference is that in Ring-LWE we usually consider error distributions which are essentially spherical in the canonical embedding, whereas in Poly-LWE we usually consider error polynomials whose coefficients are independent small values (e.g., Gaussians)—such error polynomials may be quite “skewed” in the canonical embedding. Again, the latter choice looks technically simpler at first, but in crypto applications there are advantages to the former (especially in conjunction with the “dual” form of Ring-LWE), relating to more tightly controlling the errors as they accumulate.
The two problems can be formally related, up to some blowup and distortion in the error distribution. See https://eprint.iacr.org/2019/878 for the latest information.


How do I unpack the x and y values from the BITSTRING in a DER ECDSA public key? In ASN.1, the X and Y values for a 256-bit elliptic curve key are stored as a single 66-byte ASN.1 BITSTRING. Are the values just the first and second half of this bitstring?

The private key is an OCTET STRING at the beginning of the DER private key and I know what to do with it; the public key is a BITSTRING for some reason.

The first octet in a DER encoded BITSTRING is the number of unused bits (0 in this case). The remaining 65 octets are the elliptic curve point encoded as described in SEC 1 (http://www.secg.org/collateral/sec1_final.pdf) section 2.3.4. The first octet distinguishes the identity point and whether point compression is being used. Since you have 65=1+32+32 octets, this is an uncompressed point and the first octet should be 04, follows by the X and Y values encoded as described in section 2.3.6 (basically fixed length big endian).


Using encryption for authenticating messages (instead of signing) I want to be able to verify the authenticity of a QR code text without internet connection.

Let's say I have a peanut butter store, and I have an online store too. After purchasing at my online store the customer will be given a QR code. They print that QR code and bring it to my actual store, which doesn't have internet connection, and by scanning the QR code with my mobile app I will give them the amount they have purchased.

The QR code plain text will be something like : "John, Doe, 3 jars". Upon scanning this I will give John Doe 3 jars of peanut butter.

Now as far as I know the conventional method for this is to sign the message. But that adds a lot of overhead because I will have to generate the QR code for plaintext+signature. QR codes size is very limited and my messages are very short. So any performance consideration about hashing the message and encrypting that hash are of no importance. While ciphertext size is very important.

So I was thinking, is there any security flaw if I just encrypt the message instead of signing it? If I can decrypt the message in my offline store it means it has really come from my online store and that it has not been tampered with. This way I will avoid the size overhead of signatures, since my messages are not much longer than an SHA-256 hash themselves.

Here's the steps that will be performed:

In online store's web application:

create a text message that says a certain customer has purchased a certain amount of peanut butter
encrypt the message with my private/public key
convert to base64 and generate QR code

In actual store:

scan QR code and base64 decode
decrypt the message with my public/private key
if I'm able to decrypt the message it means the message is authentic and I will give the customer the amount of peanut butter specified in the QR code

Currently I've been able to successfully perform these steps with ECIES encryption in Java. I was just wondering if this is secure. I chose ECIES because after some research I figured it produces small sized cipher text. And I'm using "secp192r1" keys as a compromise between ciphertext size and key security.

Also I want the encryption to be asymmetric, because for security reasons I don't want to hard code my symmetric key into the mobile app.

This is not an actual work project, but it's something that's always been on my mind and I want to be able to do this in a real project if need arises.

Since everyone's answers were in the comments and I want to mark this as answered I'm answering my own question based on what I learnt from your comments and further research:

The answer is you simply can not encrypt with a private key. Encrypting with private keys is only possible in theoretical scenarios and only with RSA keys.

And if you try to encrypt with the public key, then you will have to share your private key. And no, they are not interchangeable, most importantly if someone has the private key they can derive both keys from it.

So the only possible way is to sign the message.

This answer could be useful for people like me who have read simplistic online articles about how cryptography works and were led to believe that public and private keys are interchangeable.


Which algorithms are used to factorize large integers? Even if RSA decided to cancel the Factoring Challenge, it seems that some teams keep working on it. According to Wikipedia, RSA-768 has been factored in late 2009.

What are the current large integer factorization algorithms and what the mathematical principles behind them? What are the ways for improvement (faster algorithms, better implementations...)?

The three main general-purpose algorithms for factorization are the quadratic sieve (QS), the elliptic curve method (ECM) and the number field sieve (NFS).

On Complexity

The running time of these algorithms is expressed with the L-notation: $L_n[a,c]$ means that the asymptotic complexity of factoring a number $n$ is $O(e^{(c+o(1))(\log n)^a(\log \log n)})^{1-a}$. We recognize "$\log n$" as "the size of the number $n$" so the main parameter to look at is the "$a$", but, for a given "$a$", "$c$" must not be neglected. Also, this is an asymptotic complexity, valid when $n$ is "big enough" and there is no telling whether the everyday "$n$" values (e.g. RSA keys) are "big enough" for the expression to be a precise estimate of the actual factorization effort. Last but not least, running time is only about CPU consumption, it does not cover memory usage, and memory is the bottleneck for 1024-bit integers.

Quadratic Sieve

A description of QS can be found in chapter 3 of the Handbook of Applied Cryptography. It is more thoroughly detailed in "A Course in Number Theory and Cryptography", a highly recommendable book for whoever is interested in such subjects (contrary to the Handbook, this one is not free, but it is well worth its price).

The main idea of QS is to try to find two integers which are square roots of the same value modulo $n$. If we consider $n = pq$ (with $p$ and $q$ big primes), then most integers which have a square root modulo $n$ actually have four square roots; this can be seen with the Chinese Remainder Theorem (CRT), which roughly states that when you compute modulo $n$, you are actually computing modulo $p$ and modulo $q$ at the same time. If $z$ is a quadratic residue modulo $n$ (it is the square of some integer modulo $n$), then $z$ is also a quadratic residue modulo $p$ and modulo $q$. Modulo $p$, $z$ has two square roots (if $u$ is a square root of $z$, then so is $-u$), and $z$ also has two square roots modulo $q$, yielding four possible combinations through the CRT. The four square roots of $z$ are $u$, $-u$, $v$ and $-v$ for two values $u$ and $v$.

So if we find $x$ and $y$ such that $x^2 = y^2 \mod n$, then $x$ and $y$ are two square roots of the same value modulo $n$. The bad case is then $x = ±y \mod n$, because this yields no information: this is when $x$ and $y$ are $u$ and $-u$, or $v$ and $-v$. However, there is a 1/2 probability that $x$ and $y$ are $±u$ and $±v$, respectively. At that point, a simple GCD between $n$ and $x+y$ will yield $p$ or $q$.

In QS, we set two bounds $A$ and $B$, and we look for $B$-numbers in a set $S$ of integers. A $B$-number is a number which is $B$-smooth, i.e. such that all its prime divisors are smaller than $B$. The set $S$ consists in the integers $t^2-n$, for values of $t$ which are between $\sqrt{n}$ and $\sqrt{n}+A$. So the values in $S$ are "small" integers which are each equal to the square modulo $n$ of a "bigger" integer.

Suppose that we found two $B$-smooth integers $s_1$ and $s_2$, such that $s_1 = gh^5$ for some small primes $g$ and $h$ (smaller than $B$), and $s_2 = g^3h^3$. Neither is an "obvious square" (i.e. a square in the plain integers, not computing modulo $n$); but $s_1s_2 = g^4h^8$, which is the square of $g^2h^4$ (square in the plain integers, but this then also holds true modulo $n$). However, $s_1$ and $s_2$ are also squares modulo $n$ of some $t_1$ and $t_2$, respectively, so $s_1s_2$ is a square of $t_1t_2$ modulo $n$. This yields two values $x = t_1t_2$ and $y = g^2h^4$ such that $x^2 = y^2 \mod n$, exactly what we were looking for.

The gist of QS is the generalization of this process. We accumulate many $B$-smooth values from $S$, in the hope that we will find a product of such $B$-smooth values where each prime divisor will have an even exponent, because this then yields an "obvious square" which we can equate to a "non-obvious square" obtained from the way the set $S$ was defined.

Finding $B$-smooth integers in the set $S$ involves "sieving", which in this case can be thought of as an offspring of Eratosthenes' Sieve. We "lay out" a sequence of values from $S$, then we "mark" all multiples of $r$ for every prime $r$ smaller than $B$; if one of the values has accumulated enough marks, then it is a product of "many" small primes, and thus a good candidate for being $B$-smooth.

The two parts of the algorithm are thus sieving, which can be distributed over many machines, each looking for $B$-smooth integers in a relatively small range (for big integers, we are still talking about using a few gigabytes of RAM in each machine). Then, all $B$-smooth integers are accumulated in a big matrix: one row per $B$-smooth value $s$, one column per prime $r$ smaller than $B$. The slot at row $s$ and column $r$ is a 1 if the factorization of $s$ includes $r$ with an odd exponent; otherwise, this is a 0. The matrix reduction step tries to find sums of rows (in $\mathbb{Z}_2$) which yield an all-zero row (summing two rows is equivalent to multiplying the corresponding $s$ values, and an all-zero row means that the product will have even exponents for all small primes, hence an obvious square).

The sieving will work in a reasonable time if $B$ is sufficiently big (it is easier to find $B$-numbers if you allow bigger "small primes"). On the other hand, the matrix reduction step will have good probability of finding full relations (products of $s$ values which are obvious squares) only if we have found more than $B$ such $B$-numbers; and the final matrix will have size $B^2$, which can become unbearably huge. So there is a trade-off. It has been proven (given some "reasonable" assumptions) that the optimal choice leads to a running complexity of $L_n[1/2,1]$.

A variant is known as the Multiple Polynomial Quadratic Sieve, in which $S$ may accept other kinds of integer, beyond the "$t^2-n$" format. See the main paper from Silverman.

Factoring with Elliptic Curves

The ECM factorization algorithm relies on the following idea: we compute points on an elliptic curve, using values modulo $n$ as if $n$ was prime (which it is not), fervently hoping that things will go sour at some point: we want to hit a value which is not invertible modulo $n$, because then a simple GCD will yield a non-trivial factor of $n$.

An Elliptic Curve is the set of points $(X,Y)$, where $X$ and $Y$ are from a field, such that a given cubic equation holds, usually $Y^2 = X^3 + aX + b$ for some constants $a$ and $b$. On such a set of points, we can define a group law; this requires a "neutral point", an extra conventional point called "point at infinity" which does not have $X$ and $Y$ coordinates in the field. The EC group law is easily computable, with formulas which imply a division (pay attention, this is the interesting point for ECM): to add point $(X_1,Y_1)$ to point $(X_2,Y_2)$, we must divide some value with $X_2 - X_1$. When we add two points with the same $X$ coordinate but not the same $Y$, we get the point at infinity (which somehow explains its name: we are "dividing by zero").

Since we can add points together, we can define the multiplication of a point by an integer: to multiply $P$ by $f$, we repeatedly add $P$ to itself ($f-1$ times). This can be done efficiently with a double-and-add algorithm. If we work with a finite field, then the curve is a finite group, and this implies that when adding $P$ to itself we necessarily end up with the point at infinity. Actually, any point $P$ has an order, which is an integer $d$ such that $fP$ is the point at infinity whenever $f$ is a multiple of $d$.

Integers modulo $n$ are not a field. However, if $n = pq$, then, when we compute with curve points with coordinates modulo $n$, we are actually computing points over two curves simultaneously: the curve in the field of integers modulo $p$, and the curve in the field of integers modulo $q$. This is what the Chinese Remainder Theorem is all about. So the ECM works like this:

We choose random constants $a$ and $b$ modulo $n$, and a random point on the curve.
We repeatedly multiply that point with integers $r^x$ for small primes $r$, and exponents $x$, such that $r^x$ is no bigger than a given bound $B$.
We hope that at some point we will try to do a division modulo $n$ by a value $X_2-X_1$ which will turn out not to be invertible, at which point we will have won (a GCD of $n$ and that value will yield a non-trivial factor of $n$).

The ECM relies on the hope that the point on the curve modulo $p$ (but not modulo $q$) will have a $B$-smooth order; thus, multiplying by all the $r^x$ will reach modulo $p$ (but not modulo $q$) the point at infinity, i.e. a "division by zero". Since we work modulo $n$, we will notice that division by zero as a case of "inversion modulo $n$ does not work".

The boundary $B$ is configured so that we do not spend too much time on a given curve. If we exhaust all small primes lower than $B$, then we try again with another curve (other random $a$ and $b$ constants).

There are variants which can give a boost to the performance of ECM; see this report for details.

The running complexity on a "balanced" integer (a RSA modulus $n = pq$ where $p$ and $q$ have the same size) is similar to that of the quadratic sieve. However, the complexity of ECM primarily depends on the size of the smallest factor of $n$, not the size of $n$, so this is the algorithm of choice for attacking big "unbalanced" integers (e.g. integers which have not been specially generated as RSA modulus).

Number Field Sieve

The Number Field Sieve is a very complex algorithm which I will not attempt to detail here, if only because I am quite sure that I would not get it right. As an extreme over-simplification, NFS is like QS with polynomials instead of integers everywhere. It relies on quite of lot of number theory. However, it still has the two basic steps:

a sieving step, which can be easily distributed over many machines (each having a hefty but not implausible amount of RAM);
a matrix reduction step, which can not be easily distributed over many machines, and which involves applying a theoretically simple operation (Gauss-Jordan reduction) to a matrix of humongous size.

An extra initialization step is needed to choose the parameters; it is often known as "polynomial selection" and requires quite a lot of thinking and non-negligible CPU work.

The running time of NFS on random integers (known as the General Number Field Sieve) is $L_n[1/3,c]$ for a constant $c = (64/9)^{1/3}$. It is faster than QS and ECM for integers larger than about 350 bits; all factorization records beginning with RSA-130 (430 bits) up to and including the current RSA-768 (768 bits) used GNFS. There is a variant called SNFS (Special Number Field Sieve) which is applicable only to integers which have a special format (and thus not applicable to RSA key cracking), but which has a better complexity ($L_n[1/3,c]$ with $c = (32/9)^{1/3}$, which means that SNFS can potentially factor integers twice bigger than GNFS). SNFS was used to factor a 1024-bit integer which was a divisor of $2^{1039}-1$.

For big integers, the bottleneck in factorization is the matrix reduction step, which requires terabytes of very fast RAM and cannot be easily distributed. Rumor has it that the polynomial selection for a 1024-bit "general" integer factorization has begun, but if the sieving step appears doable (though it will take several years), nobody knows yet how the matrix reduction step will be performed (even accounting for what five or ten years of technological advances will bring us).

Quantum Computers

Shor's algorithm easily factorizes very big integers. Its only drawback is that it works only on a quantum computer, which does not exist (yet).

On Scientific Progress

We may note that QS, ECM and NFS are all algorithms from the 1980s. No new, efficient algorithm has been discovered in the last 20 years. However, many optimizations have been discovered in the meantime, leading to algorithm variants (e.g. MPQS, ECM with "stage 2"...) which are widely faster than their original description, so there has been substantial progress -- but description of this progress requires going into the technical details of each algorithm.


Does the backdoor in Dual_EC_DRBG work like that? From what I read, the backdoor in Dual_EC_DRBG operates by using related $P$ and $Q$ points.

Did I understand the idea correctly?

Dual_EC_DRBG works by multiplying the $P$ point with the seed initially, and then using the $x$-coordinate of the previous resulting point (let's call that $S$) instead of the seed (that value is named $s$).

The $x$-coordinate of the current point is then multiplied by the $Q$ point, to act as an one-way function and prevent the ability to produce more bits knowing one output value.

Let's call the resulting point $R$.
Its $x$-coordinate (called $r$) is then truncated and output.

Does the backdoor work the following way?

Assuming
$Q = P \cdot x$ and $R = Q  \cdot s = (P \cdot x) \cdot s$

(and that x is known to the adversary)

it should be possible to calculate
$S = P \cdot s$, which would allow to continue generating bits since the output:

$$S = R \cdot x^{-1} \pmod n)$$

Is that true?

Not quite, but you're close.  I will write $[n]A$ for scalar multiplication of the point $A$ on the curve in question by the scalar $n$, as is more typical notation, and I will write $x(A)$ for the least nonnegative integer representative of the $x$ coordinate of $A$.

Let $E/k$ be an elliptic curve over the field $k$, and $P$ and $Q$ be two $k$-rational points of large prime order.

The initial state is a bit string interpreted as an integer $s_0$.  The $i^\mathit{th}$ state $s_i$ and output $r_i$ are given by
\begin{align*}
  s_i &= x([s_{i - 1}]P), \\
  r_i &= x([s_i]Q).
\end{align*}
If $P = [d]Q$ for some integer $d$, then $$s_{i + 1} = x([s_i]P) = x([s_i][d]Q) = x([d][s_i]Q) = x([d] x^{-1}(r_i)),$$ where $x^{-1}(r_i)$ is one of the two possible points with $x$ coordinate $r_i$.

Finding $d$ given $P$ and $Q$ is intractable in a curve for which the ECDLP is hard, but the nation-state adversary influencing cryptography standards could have picked $P$ and $d$ and then computed $Q$ from them.

You, too, can create your own Dual_EC_DRBG back door in the privacy of your own living room!  However, you probably can't get FIPS certification if you do that—and if anyone catches you at it outside your living room, you may fall afoul of US Patent 8,396,213 on how to design a key escrow euphemism for a back door.  And by design they can't distinguish whether you generated your own $P$ and $Q$ at random or picked $Q$ and $d$ first and then computed $P$ from them for a key escrow system, saving $d$ somewhere secure like a sticky note on your monitor.

So merely using base points other than the standard ones may be a violation of US patent law.  (Caveat: I may be a vulture, like many attorneys, but I have not passed the bar, and I am certainly not your patent vulture.)


Shamir Secret Sharing: Why cannot we recover polynomial's root if we have $t-1$ shares? Imagine we have $t-1$ shares in $(t,n)$ shamir secret sharing. So at least $t$ shares are needed.

Question: Why cannot we use $t-1$ shares to find a root of the polynomial and then recover the secret?

Shamir Secret Sharing (SSS) is based on constructing a polynomial of degree $t-1$, whose independent term is the secret $S$. Each share is actually a point of the polynomial.

The security of SSS is based on the fact that, when one wants to interpolate a polynomial of degree $t-1$, one needs at least $t$ points of the polynomial. It can be seen graphically that trying to interpolate with less points (e.g., with $t-1$ points) is impossible since infinite polynomials can be drawn through those points. The Wikipedia article for SSS illustrates this very well.

In cryptographic applications you will not have "infinite" polynomials, but all the possible polynomials of degree $t$ for the given field. That means that knowing $t-1$ points is useless as all possible polynomials are equally plausible. This is called "perfect secrecy".


What is the meaning of "probabilistic encryption algorithm"? I am learning cryptography by myself, and I am not able to understand the meaning of "probabilistic encryption algorithm".

How is it different from "deterministic encryption algorithm"? How can the output of a probabilistic algorithm be different for the same pair of plain text and key when used two different times? Doesn't the cipher text depend only on key and plain text?

Informally, in probabilistic encryption random values are used to encrypt a message. Thus, each time we encrypt a message we pick a fresh random value; as a result if we encrypt the same message twice we would get different encrypted value (or ciphertext).This means that the ciphertext does not depend only on key and plaintext.


How efficient are the generic attacks regarding near-collision-resistance? In a recent answer I gave a definition of near-collision-attacks. Now beyond the definition and what to do with this type of attack my knowledge is fairly limited. So here's the question:

Let $H:\{0,1\}^*\rightarrow\{0,1\}^n$ be a cryptographically secure hash function. Let $k\in\mathbb N$ be $0<k<n$. Without further details, how much effort is needed to find two strings $x_1,x_2$ such that $$\Delta(H(x_1),H(x_2))\leq k$$

holds?

As in the other answer $\Delta(x,y)$ shall denote the Hamming distance between $x$ and $y$.

The hamming distance is going to have a binomial distribution. Given two $n$-bit hashes, the probability that the hamming distance is exactly $k$ is:

$Pr(n,k) = {{n}\choose{k}}\frac{1}{2}^{k}\frac{1}{2}^{n-k} = {{n}\choose{k}}\frac{1}{2}^{n}$

So if you want to know the probability of the hamming distance being $\le k$ you need to sum:

$p = Pr(n,0) + Pr(n,1) + Pr(n,2) + ... + Pr(n,k)$

For example, if $n=128$ and $k=32$ then the probability is approximately 0.000000006421. So you'll need to try 155,738,981 times on average.

If you want to apply the birthday attack thinking to this, where the probability of success increases with the number of hashes you collect, you'll need approximately $\sqrt{\frac{1}{p}}$ messages for a 50% probability. This is a rough approximation based on the idea that the number of message pairs grows quadratically.

So in the above example, you'll need to collect 12480 hashes.


how much is secure to encrypt a password using itself (as encryption key) for storing it on an insecure media? I want to store a password securely on a storage (suppose in a usual unencrypted file).

I use this password as AES key to encrypt itself (using AES-ECB) & then store it on the media (the password length is at most 16 bytes).

When user wants to confirm it's identity, I decrypt this saved encrypted content with user input & compare it with the same input, if they were equal it means that user has authenticated successfully.

Know I've two important questions:

Is it a CORRECT solution? If not, why not?
Is it the BEST solution? If not, why not? (and please give me the better suggestion)

I think what you are looking for is a Password-Based Key Derivation Function (PBKDF).

You can take a moderately strong password, like 12-14 random letters and numbers (no dictionary words though!), and throw it into the PBKDF function together with some other parameters, e.g. salt, number of iterations and the desired key length.

After that you have a reasonably strong - say 128 bit key - for the real AES encryption/decryption.

For more info, see http://en.wikipedia.org/wiki/PBKDF2

One more thing. To prevent brute forcing of your key you should experiment with the number of iterations for the key derivation. As a good rule of thumb, choose a number that makes the algorithm run for approximately 1 second on the target machine.


Can zero knowledge proof and zero knowledge proof of knowledge transfer to each other? Recently I'm studying learning with errors crypto systems and I'm running into a problem. I try to prove that the plaintext is in some specific range(for example 0~10) using zero knowledge proof.

However, almost all the papers I find in Google are talking about constructing "zero knowledge proof of knowledge" schemes, but what I want is zero knowledge proof, can these two primitives transfer to each other?

A zero-knowledge proof $\rho$ demonstrates that an instance $\phi$ is in a relation $R$, i.e. there exists $w$ such that $(\phi, w) \in R$.

A zero-knowledge proof of knowledge $\pi$ for an instance $\phi$ demonstrates that the random tape of the PPT algorithm that calculated $\pi$ can be used as the input to a PPT extractor to output $w$ such that $(\phi,w) \in R$.

If $w$ does not exist, then there can be no such extractor.  Thus any zero-knowledge proof of knowledge is also a zero-knowledge proof.  However, not every zero-knowledge proof is a zero-knowledge proof of knowledge.  In particular, Groth-Sahai proofs do not have knowledge extraction.


How to reverse engineer a cryptography algorithm if some input-output pair is known. I am trying to reverse engineer an unknown encryption algorithm. By this, I mean I dont know what kind of algorithm is used to encrypt the words.

But I know some input-output pairs. From this point what can I deduce/reverse engineer?
Thanks

It is not possible to reverse-engineer a good encryption algorithm from plaintext/ciphertext pairs alone; it might not even be possible to test the validity of a guess unless a matching key is known (but it is often possible to rule out a guess; e.g. if individual cryptograms are 64 bytes, that's not RSA with a decent key size).

Among techniques to reverse-engineer a good encryption algorithm:

Using social engineering/bribery/spying to obtain info; experience proves that even partial info helps a lot.
Obtaining and analyzing a hardware implementation (e.g. using electronic or atomic-force microscopy).
Obtaining and de-compiling the object-code of a software implementation.
Getting extra information from a working implementation using some side channel (e.g. JTAG debug port; micro probing the bus, or for self-contained ICs perhaps with the help of ion-beam implantation technology; power analysis; timing); ideally, the attacker wants to see the data the algorithm is manipulating along its execution; but even lesser information is useful (e.g. if encryption timing varies as a deterministic function of the plaintext value for constant plaintext size, the algorithm is not a plain implementation of Salsa).
Using fault injection to cause nasty things to happen (like, glitching the power supply or lighting the IC with a laser pulse at reset, in hope of entering a debug mode that allows the attacker to reach one of the previous goals); also, careful examination of erroneous data output caused by fault injection might allow confirming an hypothesis on the algorithm, and finding the key.

Reverse engineering a bad encryption algorithm depends very much on the algorithm; sometime it is possible, there are even generic techniques for entire classes of algorithms, see this for anything affine, including linear.


Isn't the structure of a potential plaintext of a ciphertext generated by a one-time pad dispositive, cryptanalysis-wise? That is, if I generate every possible result, and analyze the structure against, for example, a dictionary, won't that identify which of the solutions in the domain is most likely the correct one?

I realize the numbers involved, but this does ultimately reduce the problem to a hardware one. If this is not true, then I'm not understanding something correctly about one-time pads.

TIA.

No that is not correct, here is the thing, given a ciphertext say ezcle, there exists a key such that this would decrypt to hello, another key such that this decrypts to harry, another key which will decrypt to frank, another key which will result in world. And every other 5 letter word in the dictionary, and every other 5 letter combination of letters (I'm restricting to letters to make things simple).

Sure there are a lot of outputs that are garbage, but there are a lot of outputs that are not garbage, but every 5 letter word in the dictionary will also appear. Thus, before doing this cryptanalysis, you had a pretty good idea that the ciphertext encrypted a 5 letter english word say. After your cryptanalysis, you have not eliminated a single 5 letter word from the possible plaintexts. Thus you have gained no extra information by doing the cryptanalysis.