How to backup a secret encrypted by multi parties without revealing the secret? I'm searching for a way to backup a secret that only the end user knows the information with 2 trusted hosts.

But trusted hosts shouldn't have access to secret at any time.

First basic version :
Alice encrypt secret using Server A public key
Alice encrypt encrypted secret using Server B public key.
Alice store this double encrypted secret somewhere safe

To restore :
Alice ask server B to decrypt double encrypted secret
Alice ask server A to decrypt result
Alice get secret ... but server A also !

It could work if :
to restore :
Alice ask server B to decrypt double encrypted secret
Alice encrypt result using a magical encryption mechanism (?)
Alice ask server A to decrypt this information (homomorphic ??)
Alice receive result and decrypt using a magical decryption mechanism (?)
Alice get secret ... and server A got just an encrypted information !

Is an encryption mechanism like this exists ?

Is there an alternative approach to my goal ?

Thanks

If the goal is to store the secret on two servers and Alice so that, if Alice had access to both servers, you can recover the secret, but neither server by itself could (even if you could recover Alice's stored value).

If so, this problem is essentially secret sharing.  In this case, it can be done fairly easily:

Alice generates two random strings $P, Q$ as long as the secret $S$
Alice gives the value $P$ to server 1
Alice gives the value $Q$ to server 2
Alice stores the value $P \oplus Q \oplus S$ (that is, the strings $P$, $Q$ and $S$ exclusive-or'ed together) in her storage

It should be obvious that neither server (even with Alice's stored value) can recover the secret $S$; however if Alice can recover the secret if she has access to both.

And, secret sharing can do more than that (using somewhat more sophisticated mechanisms); Alice can share her secret among 5 servers, so that if she has access to any 3 (perhaps two of them crashed), then she could still recover the secret (but all the server's without Alice's stored value could).


What's a cryptographic primitive, really? The more I encounter the term "cryptographic primitive," the less I feel confident that I truly understand what it means.  Is it just me, or is there no universal definition for the term?  Or does the term have some contextual sensitivity that I'm missing?

Some questions that illustrate my confusion:

Does the term refer to algorithms for which we only have heuristic security arguments?
Does it refer to the building blocks invoked by a mode of operation or protocol, independently of the form of their security arguments?
Does it refer to popular security goals like message authentication code, pseudorandom function, collision resistant hash function, etc., that are commonly used as building blocks in modes and protocols?
In Merkle–Damgård hash functions like SHA-2, which is the primitive:

The hash function as a whole?
The compression function?
One but not the other, varying with the context in which we're talking about SHA-2?  (E.g., analyzing the security of SHA-2 vs. analyzing the security of a protocol that uses it.)

Since there are security proofs for HMAC that appeal to properties of the compression function of a Merkle–Damgård hash, which is the "primitive" in this case, the hash function or the compression function?
In SHA-3, which of these are "primitives" or not?

SHA3-256
Keccak sponge functions
Keccak permutations

As others have pointed out in the comments, "cryptographic primitives" are generic building blocks. What exactly this means depends on your point of view and the level of abstraction.

The most basic primitives are those, where a function is considered secure, but either you can't break it down any further or there is no security argument for its individual parts. Examples:

Modular exponentiation in prime fields can't be broken down any more, and we can use this with the inherent discrete log problem to crete public key cryptography.
Symmetric encryption - we consider symmetric encryption like AES secure, with clearly defined security properties. But its individual parts, e.g. single rounds or single steps in rounds, don't have any meaningful security properties. Sure, they bring certain amounts of confusion and diffusion. However, the strength of the cipher is also a result of the entire construction - as e.g. attacks on AES with reduced rounds are known.

And then there are primitives, which are not specified any further. For example if you assume a public key encryption scheme and just need its generic algorithms (Enc, Dec), then that encryption scheme is your building block. It isn't the underlying trapdoor one-way function, because you don't care which one is actually used.

To answer your questions:

No, actually quite differently. Primitives are defined by their security properties. Some have heuristical security properties, namely withstood cryptanalysis for years (e.g. cryptographic hash functions and symmetric encryption). Others have provable security properties - with or without assumptions. Examples with assumptions are public key cryptography, an example without assumption is Shamir's secret sharing - its security is unconditional.
Well, the primitive is defined by its security property. I am not sure what you mean with "form of security arguments". But everything with a provable security argument (and some heuristic ones for only the most basic things like symmetric encryption) can be a primitive for a higher level of abstraction.
Yes, it can.
(and 5., 6.) Hash functions in general can be considered primitives. Compression functions in general are not cryptographic primitives, because they have no security property. But surely you could call it primitive - without cryptographic. This is just like hash functions: In general, a hash function is not cryptographic. If you talk about a cryptographic hash function, you should actually call it a cryptographic hash function - unless the context is absolutely clear.
But whenever you talk about a specific function and not the general one, then the term primitive is a bad choice.


How is SPHINCS Hash-based signature "stateless"? I really hope someone can help me with these questions related to SPHINCS.

I am trying to understand the concept of “stateless” vs. “stateful” signature scheme which is the basis of SPHINCS. I went to read Chapter 6.4 of Goldreich’s Foundations of Cryptography, Volume 2. In page 546, image attached with this question, he gives a small example of one parent node x authenticating two children nodes, x_0 and x_1.

Here are my questions:

Q1: node x generates (S_x, V_x) pair where S_x is the Secret Key and V_x is the Public Key. Then node x generates two additional pairs (S_x0,V_x0 )  and (S_x1,V_x1) for nodes x_0  and x_1, respectively. Is there is any relationship between S_x  and S_x0,S_x1 other than the fact that they use the same G(1^n) ?

Q2: the public key is only V_x?

Q3: signing only occurs with children nodes. Say I sign α with S_x0, thus the signature is going to be σ=f_Sx0(α),V_x0,auth_x0  where auth_x0= f_Sx(V_x0) ?

Q4: In SPHINCS, can we assume that all private keys are also generated with the same G(1^n) ? and thus we are always going to generate the same private keys given the same seed? Thus the “stateless” came from?

Thank you very much

I don't have Goldreich in front of me, however it would appear that he is discussing something rather different from a Merkle tree (at least, as it appears in a hash based signature method).

In those Merkle trees, the trees are built bottom-up, not top-down.  That is, the top nodes don't define the values that the child nodes hold; instead, the top node value is a (oneway) function of the child nodes.  In addition, the value that a node has is potentially public (that is, we don't mind if someone learns it); there is no secret component to it.  The only secrets are the private keys to the one time (or few time) signatures at the bottom of each Merkle tree.

As for the difference between stateful and stateless based based signature methods:

Stateful schemes have a Merkle tree (or tree of trees) with a number of one-time signatures at the bottom; each one-time signature can be used (you guessed it) once; hence the signer needs to keep track of which ones he has used; that is, when he uses a one-time signature to sign a message, he must update his state.
Stateless schemes (such as Sphincs) has a large tree-of-trees; but at the bottom, they have a number of few time signatures (Sphincs uses HORST); each such few time signature can sign several messages.  So, when Sphincs signs a message, the signer picks a random few-time-signature, uses that to sign the message, and then authenticates that through the Merkle trees up to the root (which is the public key).  Since we are using a few-time signature, we don't mind if we pick the same few-time signature multiple times on occasion; the few time signature scheme can handle it.  And, since we don't need to update any state when generating a signature, this is considered "stateless".


Privacy-Preserving relational databases: checking the existence of a record (or multiple records) I would like to know if there exists a protocol which performs the following operation in a privacy-preserving fashion:

User $U$ wants to know whether a record is stored in the database. The primary key of the record is an id which is known by the user.
User $U$ sends a "private" query containing the record id.
The database server receives the private query, runs it in a privacy-preserving fashion and returns the "encrypted" result to user $U$.
User $U$ "decrypts" the result and learns whether the record is stored.

PIR for relational databases may work but I don't need to actually retrieve the record. I only need to know whether the record is there or not (0 or 1).

Does there exist such a protocol?

If so, is it extensible to queries containing a list of record ids?

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

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

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

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

Notation Alert:

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

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

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

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

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

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

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

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

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

That response will decrypt (as described in that link,

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

On key-pair reuse:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Improving efficiency:

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

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

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

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

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

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

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

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

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

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

Queries containing a list of record ids:

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

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

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

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

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


How is the plaintext to ciphertext expansion ratio on AES cipher? My understanding for AES cipher is just mapping a plaintext of a some length to a ciphertext of the same length.

Is the ratio always |Ciphertext|/|Plaintext| = 1?

Please correct me if you have noticed something. I may luck some assumptions.

AES as a block cipher

AES is a block cipher. Since it is invertible, there must be a one-to-one mapping between plaintext and ciphertext blocks. So when talking about a single block, the ratio of ciphertext to plaintext is indeed $1$.

Ciphers and modes of operation

However, a block cipher is not a complete cipher. In order to encrypt quantities of information greater than the block size and/or to encrypt the same plaintext while maintaining indistinguishability, you have to use a mode of operation.

A mode of operation requires an initialization vector, which will add a constant amount of size overhead to the size of the cryptogram. Different use cases and modes of operation can support/require varying minimum IV sizes. IV sizes of 96 to 256 bits are common.

A proper mode of operation includes authentication and integrity of the ciphertext, as well as associated data. The authentication tag will also contribute to the size overhead. Tags can vary in size depending on the application. Very constrained environments may use tags for short lived data that would be unacceptably short in other environments, while less constrained environments may use tags that would be unacceptably large in other contexts. A tag size of 64 to 256 bits is a reasonable range.

Conclusion

In the worst case scenario, for AES which has a 128-bit block size, encrypting a single block with an 128-bit IV will double the size of the cryptogram compared to the size of the plaintext, giving a ratio of $2:1$ ciphertext to plaintext size.*

When you include authentication, assuming a 256-bit tag for a single block, then you have a ratio of $4 : 1$.

In the best case scenario, encrypting a very very long message with any sized initialization vector and authentication tag will cause a negligible increase in the size of the cryptogram compared to the size of the plaintext. The ratio of ciphertext to plaintext size will approach $1$ as the size of the plaintext becomes larger.

* It is arguable that encrypting a single bit is the worst case scenario, but this answer concerns itself with a minimum unit of 1 block size.


PRNG with a truly random seed? PRNG (Wikipedia):

  "The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values)."

My questions are:

Is a PRNG-generated sequence with a truly random seed considered a cryptographically secure PRNG?

If not:

How does a CSPRNG-generated sequence differ from a PRNG-generated sequence?

Is a PRNG-generated sequence with a truly random seed considered a cryptographically secure PRNG?

Not necessarily. If you have a PRNG algorithm that has not been designed with security in mind then just giving it a random seed doesn't make it a Cryptographically Secure PRNG (CSPRNG). If a PRNG has not been designed to be a CSPRNG then it is extremely unlikely to be one by chance.

  How does a CSPRNG-generated sequence differ from a PRNG-generated sequence?

This is a bit of a weird question since a CSPRNG is of course a PRNG. Let's compare the CSPRNG against a non-secure PRNG instead.

The output of a CSPRNG should not leak any information about previous or following outputs of the PRNG. It should be impossible to recreate the state of the PRNG (at any point in time) without recovering the seed information, which all the output depends on. This isn't a generic requirement for a PRNG. For instance, the  Mersenne Twister, which does otherwise pass the Diehard tests, does allow an attacker to calculate the state vector given enough output.

A CSPRNG may have additional constraints such as a very low bias on the outputs, providing a well distributed output. It is possible to argue that these would be required for any PRNG, but PRNG's could be build for speed - providing good enough output for specific applications. Cryptographic applications generally require a very high level of unbiased, well distributed output.

Note that many CSPRNG algorithms may reseed at any time, mixing in the new seed entropy into the current state. There isn't necessarily one seed. Of course there is at least one initial seed; otherwise the CSPRNG cannot generate the initial output.


Are there some well-known crypto APIs that leak information? Are there any well-known crypto APIs or libraries that leak or used to leak information (it can be the key or anything else)?

The classic one that I can think of off the top of my head, that also happened relatively recently and posed a pretty widespread threat, was the Heartbleed bug.  It was a big security vulnerability that would reveal authentication info in one of the most common ways communication gets encrypted over the internet, SSL/TLS.  Most computers were affected, if I recall correctly, except coincidentally Macs, because they happened to use a different library to handle SSL/TLS.


Pohlig-Hellman: While solving in a subgrp, why is multiplication done mod the parent group's $p$ while the exponent is expanded as per $p_i$ of subgrp In the Pohlig-Hellman algorithm, we take a Discrete Log Problem (DLP) in a group & solve it in subgroups $p_1^{n_1}$, $p_2^{n_2}$, $p_3^{n_3}$ etc & then combine it with the Chinese Remainder Theorem (CRT).
The original DLP is $\bmod p$ & the order $p -1 = n = p_1^{n_1} * p_2^{n_2} * p_3^{n_3} .... $
When we are solving for a subgroup $p_1^{n_1}$, we frame number of coefficients of $x$ based on the max value $x$ can take i.e. $p_1^{n_1} - 1$
For example, if we are solving for $3^4$, then we frame $x$ as
$x = c_0 + 3c_1 + 3^2c_2 + 3^3c_3$
$x$ has 4 coefficients here ($c_0$, $c_1$, $c_2$ & $c_3$) because the max value of x is [$p_1^{n_1} - 1$] (because it's $\bmod p_1^{n_1}$)
However, when we actually solve for finding the coeffs of $x$ for subgroup $p_1^{n_1}$, we do the calculations with $\bmod q$, instead of $\bmod p_1^{n_1}$. Why is that?
For e.g. if we take the example here: When they calculate $8006^{2025} = 1$ for subgroup $2^2$, this is actually calculated as $8006^{2025} \bmod p$ rather than $\bmod p_1^{n_1}$. It's the same in all the calculations. Why is this? Shouldn't it be done $\bmod p_1^{n_1}$
When we are finding $x = x_1 \bmod {p_i}^{n_i}$, we are doing calculations $\bmod q$ instead of doing them $\bmod {p_i}^{n_i}$.
EDIT: Or an alternate question could be this - the operations of the subgroup is always going to be $\bmod p$ rather than $\bmod {p_i}^{n_i}$.  Considering that, then why are the 3 congruence equations we get for the 3 subgroups also not $\bmod p$. Why are they $\bmod 4$, $\bmod 81$ & $\bmod 25$?
EDIT2: Based on various answers, I have boiled down my question to one line
While multiplication in the subgroup is being done modulo p, why are exponents in the subgroup expanded modulo $p_i$?
Is there any theory explaining this?

The question's example asks finding the solutions $x$ of equation $a^x\equiv b\pmod p$ given $p$, $a$, $b$, with $p=8101$, $a=6$, $b=7531$. It's stated $a$ is a generator of $\mathbb Z_{8101}$, but it's meant $\mathbb Z_{8101}^*$, which is the multiplicative group modulo $p$. The $^*$ (or $^\times$) means we use the multiplicative law of the ring of integers modulo $p$, or equivalently that we form the group by keeping the elements of the ring that are invertible, as mandated by a group axiom. In particular, that implies we exclude $0$, and any $c$ with $\gcd(c,p)\ne1$.
That Discrete Logarithm Problem is modulo prime $p$, a simplifying special case¹. The aforementioned group $\mathbb Z_p^*$ is thus² cyclic. It has order $n=p-1$, that is $n$ elements which we can designate by their integer representative in range $[1,n]$. The order of any element $c$ of that group, defined as the smallest integer $\ell>0$ with $c^\ell\equiv1\pmod p$ thus divides the order $n$ of the group. We are told that $a$ is a generator, which means the order of $a$ is $n$, and we can check this³.
We are now in the situation where we can apply the general Pohlig-Hellman algorithm as stated in Wikipedia, with their $\mathbb G$ of order $n$ our $\mathbb Z_p^*$ of order $n=p-1$, their $g$, $h$ and $e_i$ our $a$, $b$, and $n_i$ :

The first step in that algorithm is factoring $n$ into $n=\prod{p_i}^{n_i}$, that is $8100=2^2\cdot3^4\cdot5^2$. For each $i$ we'll form a subgroup of $\mathbb Z_p^*$ where we solve a sub-problem.
Each of this sub-problems is $\left(a^{n/({p_i}^{n_i})}\right)^{x_{p_i}}\equiv b^{n/({p_i}^{n_i})}\pmod p$ (per the linked example's notation, which uses $x_2$, $x_3$, $x_5$ where Wikipedia uses $x_1$, $x_2$, $x_3$). Each of this sub-problem is in the (cyclic) subgroup of $\mathbb Z_p^*$ generated by $a^{n/({p_i}^{n_i})}\bmod p$, of order ${p_i}^{n_i}$. We solve each separately using Pohlig-Hellman for group of prime-power order. Calculations involving elements of a subgroup are within the main group, thus in $\mathbb Z_p^*$, thus modulo $p$. Calculations involving exponents (in particular, the solution $x_{p_i}$ ) are modulo the subgroup order, that is ${p_i}^{n_i}$.
Then we join the solutions $x_{p_i}$ in a Chinese Remainder Theorem step, where the coprime moduli are the ${p_i}^{n_i}$, which product is our $n=p-1$.

In summary, all calculations involving a multiplication by $a$ or $b$ are modulo $p$, so as to be in the group $\mathbb Z_p^*$. Same for raising $a$ or $b$ (or a product of powers thereof) to some power. Only operations involving an exponent (that is the integer defining to which power we raise such combination of $a$ or/and $b$) is made modulo something other than $p$: the group order or a subgroup order, thus modulo $n$ where $n=p-1$, or modulo some divisor of $n$.

why are the 3 congruence equations we get for the 3 subgroups also not $\bmod p$. Why are they $\bmod 4$, $\bmod 81$ & $\bmod 25$?

Because they are congruence modulo the orders ${p_i}^{n_i}$ of the 3 subgroups of $\mathbb Z_p^*$ generated by the 3 elements $a^{n/({p_i}^{n_i})}\bmod p$. Relations (multiplicative) in these subgroups of $\mathbb Z_p^*$ would be modulo $p$.

While multiplication in the subgroup is being done modulo $p$, why are exponents in the subgroup expanded modulo $p_i$?

For any finite group $(\mathbb G,*)$ of order $r$ (that is, with $r$ elements), for any $x\in\mathbb G$, it holds⁴ $\underbrace{x*x\ldots x*x}_{r\text{ terms}}=x^r=1$, where $1$ is the neutral of the group.
Therefore, for any integers $s$ and $t$, $x^s*x^t=x^{s\cdot t\bmod r}$, where $s\cdot t\bmod r$ is computed over integers regardless of the group's nature and it's group law $*$. That's why exponents are computed modulo the group order.
When we consider a subgroup of $\mathbb Z_p^*$ (thus where computations are modulo $p$) that has order $p_i$ (as in this sub-question) or ${p_i}^{n_i}$ (as in the overall problem), that subgroup is a group of order $r=p_i$ or $r={p_i}^{n_i}$. When working in that subgroup, we can thus reduce exponents modulo $r$.
Notice that the order $r$ of a finite subgroup always divides the main group's order, here $n=p-1$.

solve it in subgroups ${p_1}^{n_1}$, ${p_2}^{n_2}$, ${p_3}^{n_3}$ etc

It's important to be precise here: we are solving an equation $a^x\equiv b\pmod p$ in a subgroup of order ${p_i}^{n_i}$ of the main group $\mathbb Z_p^*$. Therefore, equations related to exponents are stated (and solved) in the ring of integers modulo ${p_i}^{n_i}$ noted $\mathbb Z_{{p_i}^{n_i}}$ ; while equations related to exponents in the main group are in the ring of integers modulo $n=p-1$ noted $\mathbb Z_n$.

Picky note on notation:
For integer $m>0$, the notation $u\equiv v\pmod m$ is read as “$u$ (is) congruent to $v$ modulo $m$” or sometime “$u$ equal(s) $v$ ... modulo $m$”, as a shortcut for “(the representative of) $u$ equals (the representative of) $v$ in the ring of integers modulo $m$”. That notation means (equivalently):

that $m$ divides $u-v$
that $u-v$ is a multiple of $m$
that the remainder of the Euclidean division of $\left\lvert u-v\right\rvert$ by $m$ is $0$
that exists integer $w$ with $u=(w\cdot m)+v$

The notations $u=v\bmod m$ and $v\bmod m=u$, in which $\bmod$ is an operator combining two integers into an integer, are respectively read as “$u$ equal(s) ... $v$ modulo $m$” and “$v$ modulo $m$ equal(s) $u$”. Both mean (equivalently):

that $u\equiv v\pmod m$ as defined above, and $0\le u<m$
that $u$ is

the remainder in the Euclidean division of $v$ by $m$, when $v\ge0$
$m-1-((-u-1)\bmod m)$, otherwise

When hearing ”$u$ equals $v$ modulo $m$” (without a discernible pause), or seeing $u=v\mod m$ (with extra spacing on the left of $\bmod$ due to the use of \mod rather than \pmod or \bmod), there can be an ambiguity about if $0\le u<m$ is meant, and that maters in some crypto applications. When we write $c=m^e\bmod n$ in RSA, we positively assert $0\le c<n$. For consistency, we want to write $\forall k\in\mathbb N,\;2^k\equiv2^{k\bmod 42}\pmod{43}$, rather than $\forall k\in\mathbb N,\;2^k=2^{k\bmod 42}\bmod 43$, which has counterexample $k=6$.

¹ When solving for $a^x\equiv b\pmod m$ in the most general case of a composite $m$, the outer step could be to factor $m$ as $m=\prod{m_j}^{k_j}$ with $m_j$ prime; then solve each of the problems $a^{x_j}\equiv b\pmod{m_j^{k_j}}$; then join the solutions. Here there's a single $m_1$ (one special case), and $k_1=1$ (another special case).
² The converse is not true, see this.
³ The standard technique is ensuring $a^{n/p_i}\not\equiv1\pmod p$ for each prime $p_i$ dividing $n$. Here $n=p-1=8100=2^2\cdot3^4\cdot5^2$ thus $p_i\in\{2,3,5\}$, and neither of $6^{4050}\bmod8101$ , $6^{2700}\bmod8101$ , $6^{1620}\bmod8101$ is $1$, thus $a=6$ indeed is a generator.
⁴ Fermat's little theorem, in the form $a^{p-1}\equiv1\pmod p$ for prime $p$ and $a$ not divisible by $p$, is precisely a restriction of that statement with $(\mathbb G,*)$ the group $\mathbb Z_p^*$ with $p$ is prime.


In zkSNARKS, does R1CS require every step of the calculation, or just statements which confirm the calculation was performed correctly? I was attempting to figure out a way to implement the modulo operation as a set of gates in an Rank-1 Constraint System, detailed by Vitalik Buterin here

However, it occurred to me that maybe we don't actually need to break down each step of the calculation into an R1CS gate, as long we sufficiently implement gates which verify the prover performed the calculation correctly.

So instead of a complicated series of gates, the following calculations can be performed "behind the scenes" (assuming unsigned ints):

m = x % y
d = x // y

And the gates in our R1CS only need to consist of:

x = d*y + m
m < y

(I am aware that m < y is a tad complicated, but not nearly as complicated as actually performing the modulo operation itself)

Am I correct that we should only include the bare minimum constraints?  Or are there some sort of security flaws when doing this and it is better to have a more complicated system of gates to validate every step of the calculation?

This is already explained in the linked Buterin blogpost. Essentially what you are trying to achieve here, ie. implementing a MOD "gate" in a zkSNARK is simply cannot be done efficiently. This is because that MOD is not supported in finite cyclic group arithmetic. If there is an efficient MOD gate, then by applying the Chinese Remainder Theorem, one could also break the Discrete Logarithm problem over said finite group.

More precisely, given  $g^x$, if there is an efficient MOD gate, then it means that you can obtain $x \pmod{p_{0}}$ and $x \pmod{p_{1}}$ efficiently  - for two arbitrarily chosen primes $p_{0},p_{1}$ - from $g^x$. Then by applying the Chinese Remainder Theorem, it is trivial to get $x$, hence Discrete Logarithm Problem could be solved efficiently.

Note: in your second approach, namely creating MOD gate with the following constraints:
$$x = d*y + m \land
m < y$$
would also require a single MOD, since a malicious prover could make $d*y$ overflow modulo the field modulus. This needs to be checked in the circuit, otherwise a false remainder could be proven correct.


Complexity of solving the discrete logarithm problem for the group formed from product of 2 safe primes The complexity of solving the discrete logarithm problem depends on the choice of the group $G$. A popular choice is $Z_p^*$ where $p$ is a safe prime (${p=2p' +1}$ and $p'$ is also prime). In this case, $G$ is a group of prime order so every element in it is a generator. We can do then:

Pick ${g}$ as a random element from $Z_p^*$
Pick a random $x$
Evaluate ${y = g^x \: mod \: p}$

Now we can assume solving $x = {log_g(y)}$ is hard if $p$ is large enough.

However, I often see the group $G$ is chosen as $Z_N^*$ where $N=pq$ and both $p$ and $q$ are safe primes. The algorithm is as follows:

Pick $g$ as a random element from $Z_N^*$
Pick $x$ as a random element from $(0, N')$ where ${N' =  p' q'}$ where ${p=2p' + 1}$ and ${q=2q' + 1}$
Evaluate ${y = g^x \: mod \: N}$

This construction is used in various publications from MacKenzie and Fujisaki&Okamoto.

What's that group? Does $Z_N^*$ guarantee computing discrete logarithm is hard? Since ${Z_N^*}$ is not a group of a prime order, is there any guarantee $g$ is a generator?

What's that group?

Algebraically, it is isomorphic to the group $\mathbb{Z}_{p-1} \times \mathbb{Z}_{q-1} = \mathbb{Z}_{p'} \times \mathbb{Z}_{q'} \times \mathbb{Z}_2 \times \mathbb{Z}_2$.

  Does $\mathbb{Z}_N^*$ guarantee computing discrete logarithm is hard?

It can be shown that it is at least as hard as factoring $N$ (as if you can compute discrete logs, you can factor).

Hence, if factoring $N$ is infeasible, so is computing discrete logs.

  Since $\mathbb{Z}_N^*$ is not a group of a prime order, is there any guarantee $g$ is a generator.

Actually, there is a guarantee that $g$ is not a generator for the entire group; that's because $\mathbb{Z}_N^*$ is not a cyclic group, and hence does not have a generator.

In particular, the subgroup generated by a single value $g$ will never contain both elements $a$ and $b$ where:

$a \bmod p$ is a Quadratic Residue $\bmod p$, and $a \bmod q$ is a Quadratic Nonresidue $\bmod q$
$b \bmod p$ is a Quadratic Nonresidue $\bmod p$, and $b \bmod q$ is a Quadratic Residue $\bmod q$

(Such elements $a$ and $b$ will always exist in $\mathbb{Z}_N^*$)


Santa Claus' secret permutation This December, $N$ friends play secret santa: they select a random permutation $\sigma$ of $N$ (without fixed point). For Santa Claus, everyone has to bring a gift to the next person in the permutation. To preserve the magical spirit of the game, each participant should only know the strict necessary (i.e. their image by $\sigma$) until the gifts are disclosed in the end of the month.

However, they cannot meet face-to-face before sharing the gifts and would like to generate a proper $\sigma$. We assume that they can communicate together using any cryptographic primitives. Besides, they have no access to a third-party to help generating $\sigma$.

Is there a distributed protocol to generate a random permutation $\sigma$ among them? Which of the following properties can be guaranteed?

Secrecy: Each participant $i$ should only know $\sigma(i)$, and should have no other knowledge about $\sigma$ (i.e. given the messages sent and received by $i$ and $\sigma(i)$, all permutations $\mu$ with $\mu(i) = \sigma(i)$ should be equiprobable).
Secrecy++: Each subgroup of $k < N - 1$ participants should only be able to recover their respective $\sigma(i)$ if they cheat and share information together (again, all permutations that follow these constraints should be equiprobable given their common knowledge). Note that for $k = N - 1$ the permutation is obviously recovered.
Fairness: Each participant cannot cheat to force the value of its $\sigma(i)$, whatever messages they send. Similarly, they cannot force any other $\sigma(j)$, nor bias the distribution of $\sigma$ as a whole.
Fairness++: Each subgroup of $k < N$ participants cannot bias the distribution of $\sigma$.
Validity: $\sigma$ is without fixed point.

The validity property can also be replaced by other sets of permutations:

all permutations ($S_N$)
the alternating group ($A_N$)
similarly, a subgroup of $S_N$
other subsets of $S_N$.

Solution for $N = 2$ :

With validity: there is only one choice of $\sigma$: the transposition.
Without validity: each participant draws a number $x_i \in \{0, 1\}$ and sends it to the other using a commitment scheme. Once the messages are received, they open the values. Let $X = x_0 \oplus x_1$ (i.e. modulo 2). If $X = 0$, $\sigma$ is the identity, otherwise it is the transposition.

A solution is given by Peter Ryan, Crypto Santa.  In The New Codebreakers, vol. 9100 of Lecture Notes in Computer Science, pp. 543-549, Springer, 2016. http://dx.doi.org/10.1007/978-3-662-49301-4_33

An earlier version (with Sjouke Mauw and Sasa Radomirovic) can be found at http://hdl.handle.net/10993/25936 (Open access), Security protocols for Secret Santa.


Can we share an n-bit string by using shamir's secret sharing n times? For Shamir's Secret Sharing, with a secret of size $n$, instead of having a finite field of order $n$, can we just use Shamir's Secret Sharing $n$ times, once for each bit, using a field of order 2?

Is this still as strong as using Shamir's Secret Sharing once with a field of order $n$? Are there any other drawbacks to this method?

For Shamir's Secret Sharing, with a secret of size $n$, instead of having a finite field of order $n$, can we just use Shamir's Secret Sharing $n$ times, once for each bit, using a field of order $2$?

If you are asking whether Shamir Secret Sharing works over the field $GF(2)$, well, no it doesn't (unless we have exactly one share); the problem is that, for each share, we need to give it a distinct nonzero $x$ coordinate.  For $GF(2)$, there's only one available value (1), and so, unless we're happy with there being only one share that we can distribute, it doesn't work.

However, if you mean 'can we use a field with a characteristic of 2' (say, $GF(2^8)$, yes, that works just great (and, in fact, what is commonly used in practice); $GF(2^8)$ gives us 255 possible shares, and that's often enough.

In addition, it is perfectly safe to split up a secret, and share each part separately; the only issue with your proposal is the size of the field.  Of course, if you were using $GF(2^8)$, you could split up the secret into 8 bit pieces, rather than a single bit, if you so choose.


AES mix column stage In a PDF related to AES algorithm for mix column stage is written:

  The multiplication mentioned above is performed over a Galois Field.
  The mathematics behind this is beyond the scope of this paper. This
  section will instead concentrate on the implementation of the
  multiplication which can be done quite easily with the use of the
  following two tables in (HEX).

Is there a formula (suitable for programming) to do this multiplication?

What they are trying to say that an effective way to multiply $a$ and $b$ in $GF(2^8)$ is to first check if either $a$ or $b$ are zero (if either are zero, the result of the multiplication is zero), and if neither are zero, then:

$$a \otimes b = E( L(a) + L(b) \bmod 255 )$$

where $E$ and $L$ are lookups in the ETable, LTable given, and the addition is over the integers (and not addition in the $GF(2^8)$ field).

There are more mathematically elegant ways of expressing it; however this is just about the most efficient way to implement it on a standard CPU.

However, this has doesn't have that much to do with AES; yes, AES does computation within $GF(2^8)$, however it never requires us to multiply two variables.

What the MixCollumn step asks for is multiplication by the fixed values 1, 2 and 3.

Now, computing $1 \otimes x$ is easy; $1 \otimes x = x$

Computing $2 \otimes x$ is only slightly more involved; because AES uses a polynomial representation of $GF(2^8)$, this can be simplified by shifting left by one, and then xor'ing the fixed value $0x1b$ if the original msbit was one; in a C-type notation, $2 \otimes x$ would be the value:

((x<<1) & 0xff) ^ (x & 0x80 ? 0x1b : 0x00)

Once we can compute $2 \otimes x$, computing $3 \otimes x$ is easy; $3 \otimes x = (2 \otimes x) \oplus (1 \otimes x) = (2 \otimes x) \oplus x$


Can Hash Functions take fixed-size input? I‘ve argued for quite some time with a friend about wether or not this C# method can be qualified as a Hash Function.
public override int GetHashCode() {
    return X.GetHashCode() * 31 + Y.GetHashCode();
}

My argument is that this simply returns a 32-bit integer value, using a fixed input size of 2 variable 32-bit integer values (and one constant 32-bit integer value), while one of the prerequisites for a Hash Function is an arbitrary input size.
Using two 32-bit integer inputs is not arbitrary as far as i can tell.
Unless arbitrary refers to the possibility in general (meaning 2 different functions can have fixed-size input, but the specific sizes aren‘t limited and can be different for each) and not the need for each function to have the ability to accept an arbitrary input size, while returning the output with the same size, no matter the input size.
The values of X.GetHashCode() and Y.GetHashCode() are variable 32-bit integer values and are the result of a Hash Function.
Now, the way i see it, you can just simplify that code to: h(x, y)=x*31+y , where x and y are 32-bit integer values.
Which leaves you with 64-bit fixed input size, so either my simplification is faulted, or it‘s not a Hash Function, correct?
If that simplification is not correct, why not?
And what exactly dis/qualifies this as a Hash Function?
Does the input values being the results of a Hash Function affect the qualification of the code as a Hash Function in any way?
Even if it is guaranteed that the inputs will be the result of a Hash Function, that doesn‘t make this function a Hash Function, does it? (Like how 'f(log2(4), log2(3)) , where f(x, y) = x+y' would not be a logarithmic function just because of the inputs.)
Thank you for your time. Any suggestion is much appreciated.
Also, sorry if some parts are unclear or poorly formatted. I‘m not really versed in this, be it the mathemathical definitions, the language, or stackexchange in general.

The C#/.NET GetHashCode() is not a cryptographic hash function.  As a non-cryptographic hash function I think what you've written is reasonable assuming that X and Y are the only "public" properties that make up the object.
Having said that, cryptographic hash functions are very different both in implementation and purpose than C#/.NET/Java hash codes and probably other languages as well, so you might want to take this question to a more appropriate venue.


Should a tweak value be secret like a key or visible like an IV? In tweakable block ciphers the tweak acts some ways like part of the key and in other ways, acts like an initialization vector.

Should the the tweak remain secret like the key or visible like the an initialization vector. Or perhaps this may differ from one algorithm to another?

The way it is defined in the paper "Tweakable Block Ciphers" by Moses Liskov, Ronald L. Rivest and David Wagner:

  A tweakable block cipher should also be secure, meaning that even if an
  adversary has control of the tweak input, we want the tweakable block cipher
  to remain secure.

Furthermore:

  For this operator, we call the new (second) input a tweak" rather than a nonce" or initialization vector," but the intent is similar.

so it is intended to be similar to an IV or nonce, not to be similar to a secret key.

Although a higher level mode of operation could still define the tweak to be secret, it certainly isn't intended to be, and it is unclear what the advantage would be, given that the block cipher itself doesn't depend on it.

So the only reason why the tweak would need to be kept secret is that it itself contains information that needs to be kept secret for other uses.


I have this list of LibSodium primitives, which should I pick so that the implementations tend to be interoperable? When I integrate lib sodium, into a c# project, and try to consume, encryption and decryption in a particular way, it works, but the confusion is about, which method to use while encryption or decryption, as it provides various ways to encrypt/decrypt. For example :

Problem Statement 1: Currently, I have multiple applications, in various technologies like, an android App, iOS App (Swift / Objective C), Node Js App, Web API (C#), Web Site (C#), Web Service (Java), Windows Application (C#, C++), there can be more, but these are the first once to be targeted. These application interact with database and my database is encrypted currently with custom aes encryption format (and can only be accessed with C#), moving forward, I think we are finalizing on LibSodium so that same encryption decryption can be implemented in almost all languages.

While exploring Lib Sodium, its confusing to surely know which encryption or decryption, as seen in attached screenshots is the best/the most secured way to go ahead:

Use a best methodology i.e Stream Encryption, CryptoHash etc. (Any one)
Use combinations of multiple Methods, Like first use Stream Encryption and then to go for CryptoHash etc. ( this might have some performance issue).

Problem Statement 2: Another problem which I am facing is, to find similar methods in other programming languages, i.e. If I use Stream Encryption in C#, its known as xor in Node Js, and some other name in c++, then how should I find its equivalent every time in other languages ?

P.S. I did go through the documentation of lib sodium so please don't comment the link of lib sodium

For symmetric encryption (encrypt data with a key, decrypt with the same key) use crypto_secretbox functions or possibly the crypto_secretstream functions. This seems to be what you want for problem 1.

Crypto_generichash() is not an encryption function. It's a hashing function. It takes in a message and spits out a short value known as a hash. The hash is unique per message, and different messages tend to have wildly different hashes. There is no known way to find out what message created a given hash faster than just trying all messages. Likewise there's no known way to find 2 messages that result in the same hash faster than trying all messages.

Problem statement 2: The function names should be the same in the libsodium bindings for all languages. XOR is a logic operation, not a stream encryption function.

It is worth thoroughly reading the documentation, and probably some tutorials about encryption in general. Some of what you're confused about (hashes vs encryption) is very basic, a bit like someone not knowing the difference between equality comparison (==) and assignment (=) and wanting to implement binary search. It makes it a bit difficult for me to formulate a useful answer. There is NOTHING WRONG with not having learned this stuff yet, it's not obvious or generally taught in school. If you want to learn a lot of this I suggest Dan Boneh's coursera course. It's a free graduate level course.

TL;DR: You probably want crypto_secretbox_easy(), though I'm not totally sure based on your short description.


Does an information-theoretically secure hash function exist? Does an information theoretically secure hash function exist? (By exist I mean is discovered/invented and implemented, not whether it could exist.)

The Gilbert-MacWilliams-Sloane MAC referred to by @SqueamishOssifrage in the comments is information theoretically secure "for single use", at the cost of having hashes that have length $2\ell$ for fixed length messages of length $\ell.$

Poly1305 is not information theoretically secure.

It is much more flexible, can take essentially arbitrary length inputs, and has a low probability $p$ of being spoofed which depends on four factors, $\delta,C,D,L$ and which is essentially $\delta$ plus a tiny correction factor, so $$p\leq \delta+f(L,D)2^{-106}.$$ See the original paper by Bernstein (Springer LNCS vol. 3557, also available at his site https://cr.yp.to/mac/poly1305-20050329.pdf) :

One can have up to $C\leq 2^{64}$ authenticated messages
Messages are of maximum length $L.$
One can attempt up to $D$ forgeries
$\delta$ is the probability of distinguishing AES output from a random permutation

To start with, we don't know what $\delta$ is. AES could be replaced if it was found to be weak, but the big issue is that, there is no way of handling arbitrary input length messages with a probability distribution, which would enable one to define information theoretic security, which depends on entropy, a well defined functional of a probability distribution.


Mathematically / statistically "safe" way to differentiate between crypto and random blob? I assume the United Kingdom will impose (as opposed to just talk about it) restrictions on crypto software that may be used within it's borders.

Me, quite the border clown (yes, I always bring a up to nine (only because I can't fit ten times 100ml plus containers into a 1000ml bag) re-sealable, see-through containers of pure tap-H2O, all of them put into a clear see-through, re-sealable plastic bag of no larger volume then 1 liter, to the airport, just to have them all individually sent through expensive-looking devices, checked for any impurities for my own safety, and only to empty all of them right after I have gotten them back from very grumpy border agents into my large mouth) and always having been a hardcore believer in the European Union and every person's unalienateable right to speak freely, privately and without any government intrusion; I would like to bring a USB thumbdrive with a few megs of /dev/random, generated by Linux with the help of a hardware PRNG, or just some concatenated hotbits.

I assume I will be questioned about the contents of the USB thumbdrive and will, truthfully, state that the contents are just random bytes. Depending on the amount of humor (in this case, humour) of the border agent I will spend some snuggly time in a holding cell thereafter.

What means do I have to prove, mathematically and statistically, that my random bits are indeed just that – random bits? What attacks (NIST-tools, chi-squared test, …) might the border agency run against my random bytes to try to prove their non-randomness? What software might he use? What software should he use?

Disclaimer: I am in no way affiliated with any nations government except casting my vote very four or five years. I might one day have to come back to this page from my suggly holding cell. See, officer, I told you.

If anything can distinguish a blob of random data from an encryption of some (known) data (other than any intentionally added data formats, like a header or a length difference), the encryption algorithm is called broken.
(This is one of the variants of the ciphertext  indistinguishability criterion for ciphers.)

As there are several encryption algorithms which seem to fulfill this criterion, this means in reverse, no, you can't prove that some self-created blob of random data is really random.

A possible solution would be to have some third party generate the random data for you, and sign a confirmation that it is random. I'm not sure that there is such a service – while random.org offers random numbers (or bytes), I don't see something which can certify those.
(One idea would be to store a transcript of the TLS connection by which you downloaded it, but that can also be faked.)

You can download pregenerated files from random.org – assuming random.org isn't part of your conspiracy, this should be good enough to prove you don't have encrypted data there. (But it would also be utterly useless to carry them around in your USB drive, other than to annoy the border guards.)

Another thing to keep in mind: Even if you have real random data with you (which you might previously have shared with someone else), you (or your partner) can later use this to encrypt plaintext (using a one-time-pad) to be sent over the Internet. So allowing you to bring random data into the country just opens the way for you to use encryption later.


Predicting PRNG given some of its previous output I a have a question about PRNGs and this is my very first experience with them. I have the following generator that takes a 56-bit seed $p$ during initialization and then chooses both $X$ and $Y$ randomly from the interval $[0, p]$.

Every time it is called, it returns the output of the next function:

def next(self):
    self.x = (2*self.x + 5) % self.p
    self.y = (3*self.y + 7) % self.p
    return (self.x ^ self.y)

I have the first 9 outputs of the generator and I need to predict the next output.

prng_output = [210205973, 22795300, 58776750, 121262470, \
           264731963, 140842553, 242590528, 195244728, 86752752]

I have thought of the solution which turned out to be correct by very slow, so apparently there must be another way to solve it.

My solution was to constrain the range of values for $p$ according to the given output. Also, generate all values for $X$ and for every value of $X$, calculate the first 9 values according to the previous equation and XOR it with the output to get $Y$. Finally, check of the sequence of $Y$s is valid or not (also according to the previous equation).

After some reading I learned that a reduced state (reduce the number of bits) of the generator can be determined.

So my question is how to crack the given generator, what is the "reduced state" of the generator, and how can I use that "reduced state"?

I'm not familiar with the terminology "reduced state", so I can't address that half of the question.

However, this particular PRNG makes it easy to reconstruct the internal state; we note that the state function can be rewritten as:

x := 2*x + 5 - kx * p
y := 3*y + 7 - ky * p

for some small integers $k_x$, $k_x$ (in fact, $0 \le k_x \le 2$ and $0 \le k_y \le 3$.  Once we do that rewrite, we notice that the lower bits no longer depend on the higher bits.

So, what we can do is:

Iterate over the possible $k_x$, $k_y$ values used to generate the second, third and fourth outputs; a total of 1728 possibilities.
For each set, we go through the possibilities for bit 0 of p and the initial x (note: because the initial y can be immediately deduced from the x and the first output, we don't have to iterate through that)
Check to see if there's a combination that gives the bit 0's on the second, third and fourth outputs that we have; if there is, then start looking through the various possibilities for bit 1 of p and initial x.

When we manage to get through all 29 bits, and get all the bits of the output we observed, then we have the answer (and in fact, continuing the generate outputs will, in this case, continue to generate the listed outputs).

Going through the above procedure gives us the answers p = 295075153, x0 = 89059908, y0 = 164204369, next output = 231886864


Is there proof to the relation between the gap Diffie-Hellman problem and the the Cha-Cheon signature scheme? I am trying to prove that:

"If the gap Diffie-Hellman problem is easy, then the Cha-Cheon signature scheme will be broken."

Can you help me to prove it? Is there any proof to the relation between the gap Diffie-Hellman problem and the the Cha-Cheon signature scheme?

My related question: Can you help me design a simple communication protocol?

I have to make two assumptions regarding your question first.

I assume you speak of the ID-based signature scheme from "An Identity-Based Signature from Gap Diffie-Hellman Groups".
You mean "If the computational Diffie Hellman problem (CDHP) is easy..." (the scheme works in Gap Diffie Hellman (GDH) groups, but the security proof relies on the CDHP.

Ok, now we briefly recall the scheme (I use the notation of the paper): In this scheme we have a GDH group $G$ of order $\ell$ generated by $P$. Note that in a GDH group the decisional Diffie-Hellman problem is easy, but the CDHP is assumed to be hard (such groups can for instance be realized using pairing friendly elliptic curve groups).

The master public key is $P_{pub}=sP$ where $s$ is random element in $Z_\ell$ and $s$ is kept secret by the system.

A users secret is $D_{ID}=sH_2(ID)$ and $ID\in\{0,1\}^*$ the users identifier and $H_2$ maps strings to $G$. The users public key is $Q_{ID}=H_2(ID)$.

A signature is the tuple $(U,V)$ with $U=rQ_{ID}$ for random $r\in Z_\ell$ and $V=(r+h)D_{ID}$ with $h=H_1(m,U)$ where $H_1$ is a hash function maps to $Z_\ell$.

Now signature verification amounts to checking whether $(P,P_{pub},U+hQ_{ID},V)$ is a valid Diffie- Hellman tuple. Now, this means that it is of the form $(P,aP,bP,cP)$ with $c\equiv ab\pmod \ell$.

Let us rewrite $(P,P_{pub},U+hQ_{ID},V)$ to $(P,sP,rQ_{ID}+hQ_{ID},(r+h)D_{ID})$. Now, we see that the last element can be rewritten to $(r+h)D_{ID}=rsQ_{ID}+hsQ_{ID}=s(rQ_{ID}+hQ_{ID})$, which shows the correctness. This means that a honestly computed signature is a valid Diffie-Hellman tuple.

Now forging would require to break the CDHP in $G$, i.e., one can efficiently compute $abP$ given $P,aP,bP$.

Forgery:

Observe, that $U$ and $hQ_{ID}$ can be computed by anybody. Now let us view $(P,sP,U+hQ_{ID})$ as an CDHP instance. Now, assume the $CDHP$ in $G$ is easy. This means that we can compute $s(U+hQ_{ID})$ given $(P,sP,U+hQ_{ID})$.

Now lets us inspect $s(U+hQ_{ID})$. We see that

$s(U+hQ_{ID})=sU+hsQ_{ID}=srQ_{ID}+hsQ_{ID}=rD_{ID}+hD_{ID}=(h+r)D_{ID}$.

Note that this is exactly a $V$ for a valid signature.

Total break:

Note that one can also totally break the scheme if the CDHP is easy, as one can compute $D_{ID}$ from $P_{pub}$ and $Q_{ID}$. Then you can also compute any signature you want.

Consequently, if the CDHP is easy, the signature scheme does not work anymore.

Hope that helps.


Can the encryption exponent e be greater than ϕ(N)? So I was just wondering in RSA, can the encryption exponent e be greater than ϕ(N)??

For an examples sake, lets just say N = 707, so p = 101 & q = 7. So, we have ϕ(707) = 600.

Can I have e = 707? because I can calculate d = 443 by de=1 mod 600.

I have seen it almost everywhere that 1 < e < ϕ(N). But my question is WHY?

Why can't I have e = 707 & d = 443 in the setting I described above?

From Euler's Theorem, it turns out that, for $\gcd{(a, n)} = 1$, we have:

$$\large a^e \equiv a^{e ~ \mathrm{mod} ~ \varphi{(n)}} \pmod{n}$$

So, really, having $e > \varphi{(n)}$ doesn't do anything - you may as well use the reduced exponent:

$$e ~ \mathrm{mod} ~ \varphi{(n)}$$

You can absolutely use $e = n$ if you want to, it does not leak information about the private key. It's just slow. I mean use $e = n$ directly, of course - do not reduce it modulo $\varphi{(n)}$ to make it faster, since all you would get is a reduced public exponent of $p + q - 1$, and a free ticket to instant factorization of $n$.


Why is Math.floor(Math.random()*9000) not secure in JavaScript? I heard that one can predict the output from Math.Random() of JavaScript, but another day I had an idea to combine Math.random() with Math.floor() to make it harder to predict, but a week ago I saw one user claimed that he can predict even if I used Math.floor() and that only takes 14 sample values to do that.

How is it possible mathematically?

The concrete construction in question is Math.floor(Math.random()*9000)+1000.

Various API specifications are here and there. Per this answer most browsers use Xorshift128+, possibly derived from this C source code.

In this comment the OP suggests that the question is about "Chrome's V8 implementation" and links to a Chromium commit.

According to this answer, math.random uses a Linear Congruential Generator (although it is not clear to me if that's on one specific browser, or on all JavaScript implementations).

In any case, a Linear Congruential Generator is known not to be secure, in the sense that, given partial output (which the Math.floor( 9000 * Math.random() ) operation allows), someone is able to reconstruct the initial seed, and from that, reconstruct the entire sequence.

In particular, if the browser uses the popular XORSHIFT128+ RNG, and you are able to deduce 128 lsbits from the underlying 32 bit outputs, you can reconstruct the initial state (by solving some binary linear equations).


Naming convention for NIST elliptic curves in OPENSSL NIST standardized 5 elliptic curves (P-192, P-224, P-256, P-384, P-521) for prime fields. When I looked into openssl, these curves are named as prime192v1, secp224r1, prime256v1, secp384r1, secp521r1. Is there any reason why the name convention was different for different curves?

The good thing about standards is that there are so many to choose from.

The P-192, P-224, P-256, P-384 and P-521 names come from the FIPS DSS (Latest version of which is FIPS 186-4):

https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

The secp224r1, secp384r1 and secp521r1 names come from SEC2:

https://www.secg.org/sec2-v2.pdf

The prime192v1 and prime256v1 names come from RFC3279:

https://www.ietf.org/rfc/rfc3279.txt

They're all the same curves though.


Question about the proof of the change of base formula for the discrete logarithm I was looking at the proof of a change of base formula for the discrete logarithm in this paper (page 6, 4th bullet indent).
In the intruduction, the paper states:
Let $F_q$ be a finite field of order $q$, where $q=p^n$ ($p$ prime), and let $F_q^* = F_q -\{0\}$. Given $g$, a primitive element of $F_q$, and an arbitrary $y\in F_q^*$, the discrete logarithm of $y$ base $g$ is defined as
$$ \log_g y = x \iff g^x=y \text{ in } F_q \text{ and } 0\leq x\leq q-2.$$
And then the author of the paper proves the change of base formula for the discrete logarithm:
Suppose $\Gamma$ is another primitive element of $F_q$ and we know $\log_g \Gamma = \gamma$.
$\Gamma$ and $g$ both primitive $\implies \gcd(\gamma , q-1)=1$
$\implies \exists \overline\gamma$ such that $\gamma \overline\gamma \equiv 1 \pmod{q-1} \implies g=\Gamma ^{\overline\gamma}$ in $F_q$.
Therefore $\log_g y = x \iff y = g^x = \Gamma ^{\overline\gamma x}$ in $F_q \iff \log_\Gamma y \equiv \overline\gamma x \pmod{q-1}$.
Multiplying the last congruence by $\gamma$ gives $\log_g y \equiv \log_g \Gamma \cdot \log_\Gamma y \pmod{q-1}$.
My question is, why does the following holds (from the beginning of the proof):
$$ g \text{ and } \Gamma  \text{ both primitive element of } F_q \text{ and } \log_g \Gamma =\gamma \implies \gcd(\gamma , q-1)=1  $$

Prove that:
$$g \text{ and } \Gamma  \text{ both primitive element of } F_q^* \text{ and } \log_g \Gamma =\gamma \implies \gcd(\gamma , q-1)=1$$
A primitive element in finite field means it is a generator, i.e. $\langle g\rangle = GF(q) =  F_q^* $.
Let  $g \text{ and } \Gamma$ be both primitive elements of $ GF(q)$. By using the contrapositive we will reach the opposite.
Assume that  $\gcd(\gamma , q-1) = d \neq 1$ where $\log_g \Gamma =\gamma$.
We can say that $\gamma = d \cdot k$ for some non-negative integer $k$ and $q-1 = d \cdot t$. $(q-1) \cdot t = \lambda \cdot k$. Therefore; $\lambda = \frac{(q-1)\cdot t}{k}$
$\log_g \Gamma =\gamma$ means $\Gamma = g^\gamma$ now,
\begin{align}
\Gamma &= g^\frac{(q-1)\cdot t}{k} && ;\text{replace } \lambda \text { with } \frac{(q-1)\cdot t}{k}\\
\Gamma^{k} &= g^{(q-1)\cdot t}  && ;\text{take } kth \text{ power}\\
\Gamma^{k} &= 1^t \\
\end{align}
Clearly, $k < q-1$ but we found a power $k$ of generator $\Gamma$ such that $\Gamma^{k} = 1$ this mean $\Gamma$ is not a primitive element. This proves the statement.


Multiple AES Key Derivation from a master key I need cryptography advice regarding this issue.

Kamus is a service that encrypts secrets for applications running on Kubernetes. When using AES (actually, Rijndael) symmetric encryption, Kamus uses a single key to encrypt the secrets for all apps.

Let's say I want to create from the generic key, a key that is unique per application - so that secrets that are encrypted for a specific application will not be able to decrypt with the key of another application (this is the case when using a KMS). I'm looking for an algorithm to "derive" a key from the application name (the service account name, to be accurate), something like:

f(key, name) = key

Is there an algorithm that I can use? What is the best approach here?

Multiple Key Generation from a Master key
HMAC-based Key Derivation Function (HKDF) rfc5869 is what you are looking for. HMAC security proof uses the fact that the compression function of the underlying hash is itself a PRF.

HKDF follows the "extract-then-expand" paradigm, where the KDF
logically consists of two modules.  The first stage takes the input
keying material and "extracts" from it a fixed-length pseudorandom
key K.  The second stage "expands" the key K into several additional
pseudorandom keys (the output of the KDF).

Extract:
$$\text{HKDF-Extract}(salt, IKM) \to PRK,$$where  $PRK$ is a pseudorandom key.
If the Input Key Material (IKM) is already a random key, as in your case, then the extract is not necessary, Expand is enough. HKDF can be used without the salt, however, using salt adds to the strengthening of HKDF and supporting source-independent extraction. Two different salts with the same $IKM$ result in fundamentally two different $PRK$s. And, in general, $x$ different salts with the same $IKM$ result in fundamentally $x$ different $PRK$s.
Expand:
$$\text{KDF-Expand}(PRK, info, L) \to OKM,$$where OKM is Output Keying Material. L is the desired key length.
The info can be used for the application-specific tag to derive different keys.
$$\text{KDF-Expand}(\text{Inittal Key}, \text{"application 1"}, 128) \to OKM_1$$
$$\text{KDF-Expand}(\text{Inittal Key}, \text{"application 2"}, 256) \to OKM_2$$

What is the probability of generating the same key, i.e. collision
It is hard to talk about directly on the HKDF, however, if we model it as a  uniform random function $f$, where $f(x)$ is uniform random HKDF value for each combined input ( $x = salt || IKM $) then we can turn back to birthday collisions.
Let $P(C; n, k)$ denotes the usual collision probability among $n$ people with $k$ possible birthdays. And, the usual way is to calculate from the complement $P(D; n, k) = 1 - P(C; n, k)$, that is all birthdays are distinct. Then we can approximate by
\begin{equation}
  P(C; n, k) = 1 - P(D; n, k) \leq \frac{n^2}{k}.
\end{equation} where $n \leq k/2$. The detail is everyhwere, and therefore skipped.
We have two cases;

The collision on the generating the $x$s. You may consider this as salt collision too if IKM is set fixed. For $n$ inputs $x_1,x_2,\ldots,x_n$ the collision probability is $P(C; n, k)$. When this occurs, that is the conditional probability than the outputs $f(x_1),f(x_2), \ldots, f(x_n)$ will have a collision with probaility 1.

If the inputs $x_i$s are distinct then this has $P(D; n, k) = 1 - P(C; n, k)$ probability. Now, conditionally on this we can have collision on the outputs $f(x_1),f(x_2), \ldots, f(x_n)$ with $P(C; n, k)$ probability.

Now sum up the above, then we have;
$$P(C; n, k) + (1 - P(C; n, k)) \cdot P(C; n, k) \\ = 2 P(C; n, k) - P(C; n, k)^2 \leq 2 \frac{n^2}{k}$$
So, this is just double of the usual collision attack. If you are not going to generate $2^{64}$ keys for a 128-bit key it then is not a problem for you. This case may be a problem with the multi-target attack. This is why you need to use AES-256.
You may notice that $2^{64}$ with 128 makes 2, this is due to the fact that the probability bound is not good for $n \approx \sqrt{k}$, there are tighter bound however when the input passes $\sqrt{k}$ it fastly approaches to 1.
It is important to note that 50% probability is too high in the sense of the adversary. One should stop way earlier than this. If you use AES-256, you should use it ( or ChaCha20 that has a 256-bit key), then the amount generating a collision is beyond us.

Note: There is also old KDF1 and KDF2
$$K_i = \operatorname{KDF}(K_{master}, i) = \operatorname{H}(K_{master} \mathbin\| c)$$ where $c$ is 4 byte encoded $i$, and it was commonly used wiht MD5,SHA-1, and SHA-256.

A sample code with python hkdf that contains the pop count on the output's x-or;
from hkdf import hkdf_extract,hkdf_expand
from binascii import unhexlify,b2a_hex
import sys

def bxor(b1, b2): # use xor for bytes
    parts = []
    for b1, b2 in zip(b1, b2):
        parts.append(bytes([b1 ^ b2]))
    return b''.join(parts)

prk = hkdf_extract(unhexlify(b"8e94ef805b93e683ff18"), b"asecretpassword")
key1 = hkdf_expand(prk, b"application 1", 16)
key2 = hkdf_expand(prk, b"application 2", 16)

print (b2a_hex(key1))
print (b2a_hex(key2))

#count the number of differnt bits by x-or and popup count.
print (bin(int.from_bytes(bxor(key1,key2), byteorder=sys.byteorder))[2:].count('1'))

outputs
 b'd6208cd3e14955c6ae0dc7f5ecd38a68'
 b'3b310a2e8cc9f4854237e966d289d9ba'
 64


Proving a function is a one way function I am trying to prove that a function is a one-way function.

The function I am working on in particular is $f'(x,y)=f(x)||f(x \oplus y)$.

For what I have understood looking at similar solved solutions (e.g. 1c), the strategy is the following:

Assume $f'$ is not one way, so exists an $A'$ that can invert $f'$ with non-negligible probability
Use $A'$ to construct $A$ that can invert $f$.
Show that $A$ inverts $A$ with non-negligible probability
Contradiction.

Based on this knowledge, I am trying to prove the given

$$f'(x,y)=f(x)||f(x \oplus y)$$

So, here is my attempt:

Assume $f'(x,y)$ is not one way function
So, exists a $A'$ that can invert $f'$ probability
Construct

$A(z)$:

pick a $w \in f(x)$ (for any $x$)
$x,y <- A'(f(z, y)) = A'(f(x) || f(x \oplus w))$
we have now inverted the first half
...
return $x,y$

However, although I understand the method I cannot find any valid way of making the construction:

How can you build such construction?
Is there something I am doing wrong? or am I in the right direction?

The easiest way to construct a probabilistic $A$ is simply, given $z$:

Select a random $w$
Compute $A'(z || f(w))$.
If $A'$ succeeds, then it'll evaluate to an $(x, y)$ pair with $z = f(x)$ and $f(w) = f(x \oplus y)$.
Discard $y$, and return $x$ as $A(z)$.

We select a random $f(w)$, rather than just inserting another copy of $z$, because it is possible that $A'$ would always fail on an input of the form $(z || z)$.  As I have written, if $A'$ succeeds on a nontrivial fraction of its inputs, then $A$ will succeed on the same nontrivial fraction of its inputs.


Boolean XOR function a valid way to verify the integrity of a message Does the Boolean XOR function represent a valid way to verify the integrity of a message ?

It really depends how you use it.

Per se the XOR operation is not a good way to perform any kind of integrity check because it is very easy to "cancel" a change by doing another change equal to the XOR with the value you want to obtain.

A lot of integrity checks are relying on the XOR operation under the hood to "combine" blocks together, but not without performing further operations on the said blocks.

For instance the CRC-32 algorithm, an error-detecting code is working as follows (pseudo code from Wikipedia):

Function CRC32
   Input:
      data:  Bytes
   Output:
      crc32: UInt32

crc32 ← 0xFFFFFFFF

for each byte in data do
   nLookupIndex ← (crc32 xor byte) and 0xFF;
   crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex] //CRCTable is an array of constants

crc32 ← crc32 xor 0xFFFFFFFF
return crc32

CRC-32 and the way it uses XOR is good to detect errors in a communication channel, but it is not good to provide an integrity check that would resist intentional, malicious alteration of data.

To resist such cases, you have to use cryptographic schemes, such as the ones discussed in that question. Also notice that hash function do not provide integrity, unlike MAC functions, hash-functions are only about collision resistance, pre-image resistance and second pre-image resistance.


Which is more secure PEPP-PT or DP-3T? Which of these population tracking protocols is better from a cryptography point of view?

Pan-European Privacy-Preserving Proximity Tracing (PEPP-PT)
Decentralized Privacy-Preserving Proximity Tracing (DP-3T)

I have read a paper discussing some of the security concerns, but it does not go into much detail about the cryptographic technology involved.

For example, what happens if Bluetooth keys are compromised? Is revocation possible in practice? How is key generation performed in the first place? Are keys generated locally by each device?

None of them is secure. Both include dramatic privacy risks:

PEPP-PT build a a central database with all social interactions
D3-PT allows for linking of infection reports to individuals:

Simply record all Rolling Proxymity Identifiers you see and there timestamps with a simple continuously scanning BLE device (e.g. Raspberry Pi)
Process this list against the infection warnings.
You now only need to match this timestamps with other transactions on entrances, point of sale, CCTV or logon

D3-PT also allows nation states to contact trace suspects by

injecting fake alerts in seized mobiles
suppressing alert display during risk analysis (like silent SMS work),
but using risk analysis to identify individuals

A similar technique can be used with active beacons to find out who was at a certain place at a certain time
Someone can relay (receive with an own device, transmit via internet anywhere, send out to somewhere else with  an BLE extender) all broadcasts received near a covid test station to self quarantine anyone.


tweakable block cipher and ideal block cipher Can the set of block ciphers obtained from a tweakable block cipher (using distinct tweaks) be considered as the set of ideal block ciphers ?

I'll write down the definitions for tweakable block ciphers and ideal block ciphers, and hopefully the distinction becomes more clear.

A tweakable block cipher is a function $E:\mathsf{K}\times\mathsf{T}\times\mathsf{X}\to\mathsf{X}$, where $\mathsf{K}$ is the set of keys, $\mathsf{T}$ the set of tweaks, and $\mathsf{X}$ the inputs. In particular, it should be the case that if you fix a key $K\in\mathsf{K}$ and tweak $T\in\mathsf{T}$, that $E(K,T,\cdot)$ is a permutation over $\mathsf{X}$. A regular block cipher is just a tweakable block cipher with only one tweak.

With a tweakable block cipher, you generate the key as you normally would with a block cipher, but now you're given access to a family of permutations via the tweak input, instead of just one permutation as with regular block ciphers. So $E(K,T_1,\cdot)$ and $E(K,T_2,\cdot)$ should give you access to different permutations. In fact, the security requirement of a tweakable block cipher says that each of those permutations $E(K,T_1,\cdot)$, $E(K,T_2,\cdot)$, $\ldots$, should 'look' independent of each other, and behave like ideal permutations (an ideal permutation is one which is generated uniformly at random from the set of all permutations over $\mathsf{X}$).

Now an ideal block cipher is a mathematical object. It has the same syntax as regular block ciphers, namely it takes a key and gives you an ideal permutation per key, but there is no tweak input. In some sense you could consider ideal block ciphers to be a tweakable analogue to ideal permutations, since now you're given a family of ideal permutations to access. And in fact, in the security definition for tweakable block ciphers, you will be comparing your tweakable block cipher to a family of permutations. Therefore, in some sense you could say that a tweakable block cipher gives you the same functionality as an ideal block cipher, but the biggest difference is that a tweakable block cipher needs a uniformly generated key in order for it to work properly, whereas an ideal block cipher does not: it is an ideal mathematical object.


EC ECKA-ElGamal Key Agereement availability in Bouncy Castle Java library I am trying to generate shared secret from remote EC public key(static) and client EC private key(ephemeral). In this process I am successfully able to generate shared secret using ECDH Key agreement available BC library.My work requirement is to use ElGamal key agreement but there is no specific supported Key agreement representing ECKA-ElGamal.

I was wondering if you can help confirm that ECKA-ElGamal is indeed a version of ECKA-ECDH where remote public key is static and client ephemeral key is dymanic.

Code snippet:

//I am using ECDH
KeyAgreement ka = KeyAgreement.getInstance("ECDH","BC");

// clientEphemeralPrivateKey is Client ephemeral Private key already generated
ka.init(clientEphemeralPrivateKey);

//serverECCPublicKey is remote server public key
ka.doPhase(serverECCPublicKey, true);

Yes, ElGamal indeed is DH with the sender using an ephemeral key and using the group operation for encryption.


What stops a physical attacker to use a dumped uninitialized SRAM with SRAM-PUF? Does SRAM-PUF require the microcontroller/system to be (1) on the same silicon piece and (2) to prevent access from dumping the SRAM in an uninitialized state in order to be tamper-proof?

  In SRAM PUF, there are two types of challenges that can be applied to the system. The challenge can be either the whole SRAM memory or specific addresses.

source: *Setyawan Sajim, A. (2018). Open-Source Software-Based SRAM-PUF for Secure Data and Key Storage Using Off-The-Shelf SRAM.

Does it mean that the response is only derived from the content of the SRAM in an uninitialized state? How can this be tamper-proof? As an attacker, I could just dump the content of the SRAM in an uninitialized state.

Does it mean that the response is only derived from the content of the SRAM in an uninitialized state?

For the raw RAM-PUF response, that's my understanding. How that is turned into a stable value (in practice identical across power-up cycles) is more complex, and requires long-term storage like conventional Flash for associated error-correction data (which at least in principle needs not be secret).

  How can this be tamper-proof?

My understanding is that the implicit attack model here includes: the adversary has no physical access to the RAM, and can't remotely read it in its power-up state. Perhaps the early stages of boot read the initial state of the RAM, use that, then zero that RAM.

Update: as noted in comment, if we assume that getting access to the content of the RAM-PUF at power-up is impossible without de-caping the IC, and such de-caping alters the RAM-PUF beyond the error-correction capability of the associated error-correction data, then the RAM-PUF can become a tamper-resistant vault for a secret key. I have no information about if the above assumptions hold in practice (and welcome input on that).

Another attack model commonly considered for RAM-PUF is that the attacker only attempts to make a silicon-level exact copy, or steal ICs on the fabrication line (perhaps rejects). That adversary is unable to write in Flash the associated error-correction data which, together with the unique content of the RAM-PUF, makes the device operative. In this model, reading the initial content of the RAM won't help the adversary bound to not redesign the IC.


SIDH: key agreement - why does it work? In SIDH both parties agree on the key in following way:

Alice calculates a kernel $R = mPB + nQB$
Thanks to Velu formulas (and further improvements), she can now compute isogeny $\phi_a$
She uses $\phi_a$ to start hers random walk and ends up with trio $(E_a, \phi_a(PB),\phi_a(PB))$
Now she sends this trio to Bob (I know, she actually sends 3 points)
Bob does the same, let say his secret isogeny is $\phi_b$. Upon receipt of corresponding trio from Bob $(E_b, \phi_b(PA), \phi_b(QA))$ Alice uses $m, n$ to compute new kernel $R' = m*\phi_b(PA) + n*\phi_b(QA)$ and new isogeny
Then she starts from $E_b$ and does the random walk again ending on $E_{ab}$
Bob proceeds mutatis mutandis and ends up on a probably different curve $E_{ba}$, but surely in same isomorphism class as Alice. Thanks to j-invariant then can agree on a shared secret $j(E_{ab}) == j(E_{ba})$

Now, I've to say point 6. and 7. are a bit black magic to me. I understand that we have this equality here:

$R' =m*\phi_b(PA) + n*\phi_b(QA) = \phi_b(m*PA + n*QA)$

But still, why exactly they will end up in the same isomorphism class? What is a mathematical base, for those two isogenies to converge to the same class. I'm wondering how would a proof look like for this.

I invented SIDH and can surely answer any technical questions about it. Proofs of $E_{ab} \cong E_{ba}$ are given in several places, though rarely in official Theorem / Proof form, because this result is just an application of well-established theory on elliptic curves rather than any sort of new mathematical result that merits formal statement as a theorem. See for example the original paper (Section 3.2, in particular the (unique) displayed equation in that section), or De Feo's survey article (page 34), or Martindale and Panny's cryptanalysis summary (page 4, paragraph "Key exchange").

If you have a more specific question, please ask away.


How does Diffie–Hellman differ from elliptic curve Diffie–Hellman? I didn't understand how ECDH actually works. Disclaimer: I know very little about elliptic curves.

Here is how DH works:

Alice and Bob agree on a prime number $P$ and a generator $G$. (They use one from RFC 3526)
Alice generates a long-enough (how long?) secret $S$ and
calculates $R = G^S \pmod{P}$ and sends the result $R$ to Bob
Bob does the same that Alice does in 2.
Alice and Bob exchange the values of $R$
They both calculate $R^S \pmod{P}$ with the value send by the other party, and find the same value $SS$.

$SS$ is the Shared Secret.

How do points 1..4 differ when using elliptic curves?

What are the "equivalent" values of RFC 3526 for EC?

You might want to checkout Wikipedia page of elliptic curves to get a basic overview.
The difference between DH and ECDH is mainly the group which is being chosen to compute the secret key(s). While DH uses a multiplicative group of integers modulo a prime $p$, ECDH uses a multiplicative group of points on an elliptic curve:

Alice and Bob agree on an elliptic curve $E$ over a Field $\mathbb{F}_q$ and a base point $G \in E/\mathbb{F}_q$.

Alice generates a (random) secret $k_A$ and computes $P_A = k_A P$.

Bob generates a (random) secret $k_B$ and computes $P_B = k_B P$.

Alice and Bob exchange $P_A$ and $P_B$.

Alice and Bob compute $P_{AB} = k_a P_B = k_b P_A$.
The secret $k_A$ and $k_B$ is a random value $\in \{1, ..., n-1\}$ where $n$ is the order of the group generated by $G$.

The equivalent RFC may be RFC 4753 (not sure, not into RFCs at all).
To agree on a common curve Alice and Bob may either generate a curve them selves or use predefined curves and base points. For this there are a couple of standards defined, see:

Brainpool
IEEE P1363
NIST
NSA Suite B
ANSI X9.63
...

Depending on application for ECDH you might want to choose different curves since some curves have benefits, for example amount of calculation steps for point multiplications.


Does encrypting twice using the same block cipher produce a security weakness? If I use the output of a cipher, for example a block cipher such as AES and encrypt it again with the same algorithm, I read that this introduces weaknesses into the overall security of the system.

Is this the case?

Well, I don't know where you read that.  However, depending on what they meant by that, that's either nonsense, or an appropriate cautionary tale.

What is known is that encrypting again cannot make the cipher weaker, as long as the keys you chose to encrypt a second time are independent of the keys you use the first time.  The logic behind this is straight-forward; the attacker is assumed to know everything about the cipher except the keys.  If he has some ciphertext that he wants to attack, there's nothing preventing him from picking his own "second time key", and then encrypting the ciphertext to form a doubly-encrypted ciphertext.  If double-encrypting was inherently weaker, then he could attack that (and hence single-encryption would be equally weak).

On the other hand, if the two keys you use during the first and the second use are the same, this logic does not apply.  And, in fact, there are ciphers where this encrypting twice with the same key is a Bad Idea.  For example, some ciphers will, if you run the ciphertext through a second time with the same key, will generate a 'doubly-encrypted ciphertext' that is exactly the same as the plaintext; this is obviously weaker than the 'singly-encrypted ciphertext'


What's a relatively fast way of checking if a string is decrypted English? I asked this on Stack Overflow but I was told to ask here.

I'm writing a program that decrypts text encrypted using a Vigenere cipher. It's been working very well so far, but my current issue is that I need an effective way of checking if a string is decrypted. So far, I've been checking how many times the string contains a set of the most common English words, but that doesn't work if the string has no spaces.

For example, the following "plaintext":

XPAWWALLTPJZYYZWBGSHGARECPVHDAAPLJLBGAPVTFVCWAS

contains "all", "are", "was", and "as", but it is clearly not decrypted.

What's a good way of checking if a string is decrypted?

Searching purley for substrings in a string would be a programming question but since Stackoverflow already sent you here I will give it a try:

Java:

public class MyClass
{
    public static void main(String[] args)
    {
        String myString = "XPAWWALLTPJZYYZWBGSHGARECPVHDAAPLJLBGAPVTFVCWAS";

        int intIndex = myString.indexOf("ARE");

        if(intIndex == - 1)
        {
            System.out.println("ARE was not found");
        }
        else
        {
            System.out.println("Found ARE at index "+ intIndex);
        }
    }
}

C#:

using System;

public class MyClass
{
   public static void Main()
   {
      string myString = "XPAWWALLTPJZYYZWBGSHGARECPVHDAAPLJLBGAPVTFVCWAS";

      if (myString.Contains("ARE") == true)
      {
         Console.WriteLine("Found ARE");
      }
      else
      {
         Console.WriteLine("Word ARE was not found!");
      }
   }
}

These should both work.

You can then create a loop that searches the string for common words.


How can the Schmidt–Samoa cryptosystem uniquely decrypt large messages? Suppose I choose $p=7$ and $q=11$.

This gives a public key of $p^2·q = 539$.

However, decryption occurs using a modulus of $p·q=77$.

If a person chooses to encrypt $500$ using my public key, how do I recover this value if the decryption modulus is so much smaller?

Is this a limitation of the Schmidt-Samoa scheme?

Is there a maximum message size for this scheme? How can this size be securely provided to the user without leaking information about the private key?

When you take a look at the paper you can see, that it is actually defined as a key-encapsulation mechanism, meaning that you will never encrypt data, but only keys for a symmetric encryption scheme. (That is, short messages.)

Further in $\mathsf{TKEM.Key}(pk)$ the "key carrier" that will be encrypted is explicitely chosen from $\{0, 1,\ldots, 2^{rLen} - 1\}$ where $rLen = 2k − 2$.
As $p$ and $q$ are both $k$-bit primes, $pq$ will always be greater then $2^{rLen} - 1$ and therefore the problem will not arise.

If you view the scheme as a public key encryption scheme, then the message space is simply $\{0, 1,\ldots, 2^{rLen} - 1\}$. You are not supposed to encrypt larger messages. (which is fine, because $k$ is a lot larger than in your example and you only want to encrypt short keys.)


What is the post-quantum cryptography alternative to Diffie-Hellman? Post-quantum cryptography concentrates on cryptographic algorithms that remain secure in the face of large scale quantum computers. In general, the main focus seems to be on public-key encryption algorithms and public-key signature algorithms - but there are dozens of other constructs like hashes, block ciphers, etc. - but with a quick peek, I didn't find any key agreement algorithms.

Most of todays interactive communication is focused on key agreement via Diffie-Hellman and authentication on top of that - the goal is to set up a "secure channel". Some schemes use signatures for non-repudiable authentication, but many use Diffie-Hellman for repudiable authentication. There are many protocols for key agreement, with varying security properties, that mostly just use Diffie-Hellman in complex ways and depend on the DDH or CDH assumptions on security. As an example of the protocols I mean, I present YAK and J-PAKE.

Now, my question is, what is the post-quantum cryptography answer to establishing a secure channel? Or, specifically - anonymous key agreement, authenticated key agreement and password-authenticated key agreement?

All of the different post-quantum cryptography systems seem to have some big drawback - large signatures, large public keys, large processing requirements etc. - so I am wondering which would offer the best tradeoff for key agreement?

In general, it would seem that any public key encryption algorithm could be used pretty easily for key agreement - but are there any concrete proposals on cryptographic protocols doing key agreement for some post-quantum cryptography algorithm? What properties do these provide, such as PFS, UKS, KCI, deniability, etc? Simply encrypting a random key to the recipients public key does not achieve forward secrecy, unless the recipient public key is ephemeral (random generated each time). If it is ephemeral, the question becomes how to tie some authentication in to the ephemeral key agreement, for which there's no obvious best method but a number of tradeoffs.

I understand that post-quantum cryptography isn't ready yet for general use - and the primitives are not secure enough or standardized enough to use these kinds of protocols in the real world yet - but it feels like there should be more preliminary work done on this problem as well. If you disagree, please let me know that, too!

Answering myself...

There is now a very analogous alternative to Diffie-Hellman in post-quantum cryptography: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies

The research paper is very new, but if the results turn out to be secure, this is a very competitive key agreement scheme for post-quantum cryptography.


Selective format-compliant JPEG encryption? I am working towards building a format-compliant encryption system for pictures. The aim of it is to be able to obscure specific areas of a picture (i.e. faces, car license numbers...) while keeping the rest unaltered. The aim would be, for instance, being able to publish a picture on any given social network, making the "sensitive" regions visible only to a limited number of people, probably a subset of your friends, whom have been granted permission.

I had some (arguable) ideas regarding pixel permutations and BMP, but I have stumbled face-first on the fact that most social networks use exclusively JPEG, and any other format is compressed, essentially ruining the scheme.

So now I am stuck trying to find a new encryption scheme. Ideally, it should have the following properties:

Format-compliant: the image should be still a valid JPEG, openable and viewable.
Unobtrusive: as much as possible, the encrypted image should not have a chunk of randomly colored pixels on the encrypted areas, but keep somewhat close to what it "should" look like - something like blurring or pixelation, but reversible. The rest of the image should be unaltered.
Secure: aside from the crypto perspective, from a perceptual point of view the image should be obscured enough so as to make, e.g. a face unrecognisable without decoding.

2 and 3 are somewhat opposite, so my aim is finding some acceptable middle ground between them.

I have been trying to work with Droogenbroeck and Benedett's "Techniques for a selective encryption of uncompressed and compressed images", which proposes, for every 8x8 square, keeping the DC (aka most significant) coefficient of the DCT, and encoding the rest. However, it works pretty badly for mid-large images: since encryption is done on small squares, and the DC coefficient -which holds most of the energy- is left unaltered, the larger the image is, the "smaller" those 8x8 become in proportion, eventually becoming useless for images over about 500x500.
Other than that, most papers I have found use JPEG2000 - which apparently would make everything much easier, but basically isn't supported by anything, so it doesn't seem a reasonable solution for now.

I know this is a bit on the open-ended-questions side, so specifically, my question is: Is there previous work, or any already discussed solution, for this problem or some other similar one? Do you have any ideas about how to approach this?

Thank you for your time, and please let me know if there is I can clarify - ideally I should link pictures of what I mean, but I don't think I'm allowed below a certain rep threshold :(

EDIT

As fgrieu noted, this has an added problem [please see below]. For example, Facebook apparently decompresses and recompresses the image on uploading, which means an additional, unavoidable quality loss. That means "fine-grained" tricks with coefficients – especially the least significant ones – would not work. (Also thanks to Ilmari Karonen for linking the paper!)

The problem pointed by fgrieu is avoidable in other social networks - for instance, Google+ does not recompress the image, so no problems there.

While I haven't heard of previous work on this exact problem,
splicing together some standard solutions to a few other problems almost solves this problem.

There is a loophole in the pigeonhole principle:
if the output file is bigger than the input image,
it is possible to store "extra" information.

Starting from the blurred image you want everyone to see,
you somehow want to add more information to it so that the appropriate people can extract an unblurred image.

picture frame

Perhaps you could keep every pixel of that blurred image unmodified, and add something like a picture frame above, below, or all the way around the image to store extra data,
like the way dotless QR codes store extra data without modifying the center parts of the image.
There's been a lot of work on designing barcodes in such a way that it's possible to recover all the original data, even when the barcode is distorted far worse than simply uncompressing a JPEG and then recompressing with worse quality settings.
If you have a very wide bezel picture frame, it may be possible to encode (an encrypted version of) the entire (unblurred) original image file in the frame in the form of a standard barcode.
If you create a "residual image", the difference between the (unblurred) original JPEG file vs the blurred JPEG image in the middle of the frame, that residual image should be all-zeros except for the regions that were blurred out, and so (a compressed and then encrypted version of) the residual image should require far fewer bits to encode than the entire original image, and therefore require a narrower frame around the blurred image.

borderless

If you want steganography and you think the frame is too much of a giveaway, there seems to be a bunch of research on digital watermarking designed to be robust enough to survive uncompressing a JPEG, making minor modifications to it, and recompressing.
Perhaps you can tweak such watermarking and steganography techniques enough to store (a compressed and then encrypted version of) the residual image.
"Hide data in files with easy steganography tools";
"How can you hide information inside a jpg or gif photo?";
etc.
If that doesn't give you enough storage space to store the entire residual image, perhaps you could scale up the image (each pixel of the blurred original image expands to 4 pixels of the expanded image),
giving more area to encode data.
Or perhaps you could scale up the blurred image, and then apply something like DataGlyph halftoning to create an image that from a distance looks like your blurred JPEG file, but the Dataglyph digital halftoning contains (a compressed and then encrypted version of) the residual file or the entire (unblurred) original file.


AIS31 Software and Documentation I have learned that there are two main test suitcase for randomness (reference):

AIS 31 - German Federal Office for Information Security (BSI)
SP 800-90B - U.S. National Institute for Standards and Technology (NIST)

I was able to run NIST tests on my data. I was wondering if there is any software (and documentation) available for AIS31. I was only able to find general information about it.

See the page below

https://www.bsi.bund.de/DE/Themen/Kryptografie_Kryptotechnologie/Kryptografie/Zufallszahlengeneratoren/zufallszahlengeneratoren_node.html

I looked at it with the Google translator.

There are quite a few useful links there. If you want full blown code for tests, you'd probably need to write your own.

Related question:

https://security.stackexchange.com/questions/89020/what-comprises-the-ais-31-standard-for-trngs