wondering what the largest integer is which they were able to factor with a small quantum computer

Stunts
Before the present answer, the largest claim for quantum-related factoring seems to have been 4088459=2017×2027, by Avinash Dash, Deepankar Sarmah, Bikash K. Behera, and Prasanta K. Panigrahi, in [DSBP2018] Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer  (arXiv:1805.10478, 2018) using 2 qubits (per their measure) of IBM quantum processors with 5-qubit and 16-qubit.
That's a pure stunt without application to cryptography, brought to a higher degree than in earlier work of Nikesh S. Dattani and Nathaniel Bryans, Quantum factorization of 56153 with only 4 qubits (arXiv:1411.6758, 2014) "factoring" e.g. 56153=233×241. The method applies only to a very narrow class of integers (those product of integers differing only by 2 bits, perhaps with some other constraints). 4088459 and 56153 are determined to fit the method.
The above "factorizations" extend, without requiring any experimental improvement, the earlier record of 143=11×13 by Nanyang Xu, Jing Zhu, Dawei Lu, Xianyi Zhou, Xinhua Peng, and Jiangfeng Du in Quantum Factorization of 143 on a Dipolar-Coupling Nuclear Magnetic Resonance System (Physical Review Letters, 2012). Their technique factors an integer product of two odd exactly-4-bit integers (thus with two unknown bits per factor). The scarcity of primes in range [8,15] makes 143 the only product of two distinct primes that the technique can factor. Their experimental setup iteratively minimizes a function with a 2-bit input.
An experimental improvement to 3-bit input, with application to 551=19×29, is claimed by Soham Pal, Saranyo Moitra, V. S. Anjusha, Anil Kumar, and T. S. Mahesh's Hybrid scheme for factorization: Factoring 551 using a 3-qubit NMR quantum adiabatic processor (arXiv:1611.00998, 2016). The authors acknowledge that the technique probably can't factor some larger 10-bit integers. The number factored depends on the molecule (dibromofluoromethane) used.
Zhaokai Li, Nikesh S. Dattani, Xi Chen, Xiaomei Liu, Hengyan Wang, Richard Tanburn, Hongwei Chen, Xinhua Peng, Jiangfeng Du's High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spinsystem:  Application to the experimental factorization of 291311(arXiv:1706.08061, 2017) tackle 291311=523×557 using a different molecule ($^3C$-labeled diethyl-fluoromalonate).
Breaking news: I hereby claim a new stunt record. I change the last line of equation (2) in [DSBP2018] from $p_i=q_i=1;\ i\in\{5,6,7,8,9\}$ to $p_i=q_i=1;\ i\in\{5,6,\dots,87\}$, and the very same quantum experiment yields the "factorization" of the 178-bit biprime 383123885216472214589586724601136274484797633168671371=618970019642690137449562081×618970019642690137449562091, or otherwise said that $2^{178}-(13\times2^{91})+651=(2^{89}-21)\times(2^{89}-31)$.

Adiabatic quantum computing records
For something non-stunt, defined as aiming to factor a wide fraction of arbitrary composites up to some limit, the record¹ may be Raouf Dridi and Hedayat Alghassi's Prime factorization using quantum annealing and computational algebraic geometry (in Nature scientific reports, 2017) factoring up to 223357=401×557 using the D-Wave 2000Q (an adiabatic quantum computer). A year later, the debate was still raging about the size of the true quantum computer that it could emulate.

CAUTION - All the above is practically pointless!
None of the above techniques implement Shor's algorithm. They express factorization as a combinatorial minimization problem, solved using a variant of Grover's algorithm or adiabatic quantum computing. There is no argument for hope that these approaches could scale to factorization of integers of cryptographic interest.

Shor's algorithm on quantum computers
We must separately consider the title's question:

Largest integer factored by Shor's algorithm?

I'm not aware of anything above 21=3×7 claimed by Enrique Martin-Lopez, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou, and Jeremy L. O'Brien in Experimental realisation of Shor's quantum factoring algorithm using qubit recycling (Nature Photonics, 2012).
This beats 15=3×5 first obtained by Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood and Isaac L. Chuang in Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance (Nature, 2001), then several others.
However it is debatable if these are really factoring, or rather confirming a known factorization. John A. Smolin, Graeme Smith and Alexander Vargo in Oversimplifying quantum factoring (Nature, 2013, formerly arXiv:1301.7007 with a different title) go as far as:

(there is) danger in ‘compiled’ demonstrations of Shor's algorithm. To varying degrees, all previous factorization experiments have benefited from this artifice.

Update (Sept 2020)
More stunts factorizations have appeared (see my critic), but the one in this answer remains the true (if under-reported) champion in this dubious category.
The progress on experimental non-stunt implementations seems to have stopped, both for combinatorial approaches using quantum adiabatic computers² and Schoor's algorithm. We do better understand the limitations of current hardware: Mirko Amico, Zain H. Salee, and Muir Kumph's Experimental study of Shor’s factoring algorithm using the IBM Q Experience (in physical review A, July 2019) conclude their work "fails to factor N=35". Experimental quantum computing currently prefers to focus not on beating classical computers at existing problems, but rather on finding problems where that happens beyond simulation of quantum computers.
An interesting new line of work makes mental experiments in factorization on hypothetical quantum computers: see Craig Gidney, Martin Ekerå's How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (arXiv:1905.09749, Dec 2019).

¹ Shuxian Jiang, Keith A. Britt, Travis S. Humble, and Sabre Kais in Quantum Annealing for Prime Factorization (arXiv:1804.02733, 2018) "present how to factorize" 376289=571×659, but I was pointed that it is not an experimental result, sorry for having been careless.
² A close call was Baonan Wang, Feng Hu, Haonan Yao and Chao Wang's Prime factorization algorithm based on parameter optimization of Ising model (Scientic letter, April 2020) which claims a new combinatorial method factoring all integers to 10000, and in the stunt category 1028171=1009×1019, but got eliminated from both lists because that's on a simulation of a D-Wave quantum computer.


human readable unpredictable & no collision uid based on time

The problem can be reduced to generating a random permutation of the numbers 0 to 99,999,999. One way to do it is to use something like the Fisher-Yates shuffle but this will require you to store 12,500,000 bytes (one bit for every possible number in your sequence). Adapted for your use, what you would do is every time you want a number for your sequence, the Fisher-Yates shuffle would have you:

Pick a random number k from 1 to the number of unstruck numbers remaining.
In your your 100 million bit array, set to 1 the kth remaining 0 bit. Use the position of that bit as the hashed number.

I can't think of a way to assure no collisions without using that much storage.

A cheap solution if you don't mind getting only a small subset of the 100 million factorial possible sequences would be to choose some number relatively prime to 100 million and repeatedly modulo add it to generate your sequence. If you choose a big enough number it will look unpredictable to a human. In abstract algebra terms, we choose a generator of the cyclic group of order 100 million and use it to generate all the elements of the group.


Can Pseudorandom values be used as secure keys?

Yes and yes, as mentioned in the comments.

It is worth noting that Bitcoin wallets use a scheme similar to this in BIP32, a method of creating n various EC keypairs from a single seed deterministically:

https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

EDIT: This answer only holds true if  is a CSPRNG.  (This application is sort of why the definition for CSPRNG exists.)


Is it a "simple" multiplication (such as 5*5 = 10) or the same way we multiply k by G to generate a public key?

It's multiplication modulo the curve order.  For example, if dA = 9, R = 7 and p = 13, then dA * R = 9 * 7 mod 13 = 63 mod 13 = 11.


What is purpose of a simulator and extractor in zero knowledge proof protocols?

The rigorous way to argue that the verifier learns nothing more than the validity of a statement in by designing a simulator. The simulator is an efficient machine that has oracle access to the verifier and given input the statement it simulates the view of the (adversarial) verifier. Since the simulation is possible using only the statement, it can be argued that the verifier learns nothing more (about the witness).

The extractor concerns zero-knowledge proofs of knowledge which are zero-knowledge proofs which additionally guarantee that the prover indeed holds the witness. In particular, the extractor given access to the prover (which it can potentially rewind) can extract this witness for example by rewinding it.


how to use these hash functions in python?

The $q$ is defined as the order of the ECC is used. Therefore we need to use a hash function that has at least 256-bit output since the secure curves use at least around that. Let choose SHA256.

$h_1 : \mathbb G\to\mathbb Z_q^*$
Given $g \in \mathbb G$ represent it in binary and hash with SHA256. Note that the $Z_q^*$ means $Z_q - \{0\}$ so you need to discard if the hash value is zero. Wait, if you luckily hit zero, publish a short paper.

$h_2:  \{0,1\}^*\times\{0,1\}^*\times\mathbb G\to\mathbb Z_q^*$
The $\times$ is used as the function takes input from 3 spaces. You can concatenate the inputs from them, however, two distinct delimiters are required since the first two spaces are not bound (Kleine star). This unboundedness can cause simple collisions, like $aab||ba$ and $aa||bba$ are two distinct inputs from two different input spaces, however, both have the same hash, and this is a collision since the inputs are from different spaces.
You may need to use 3 inputs like $$String1||\text{delimeter1} || String2 || \text{delimeter1} || g$$ where $String1$ from the first space, $String2$ from the second space and $g \in \mathbb G$.

$h_3:  \{0,1\}^*\to\mathbb Z_q^*$
Nothing special from the above cases.

They say you need 3 distinct hash functions. It is not clear that you may benefit from domain separation like below.
\begin{align}
h_1(x)&:  \operatorname{SHA256}(\texttt{"Hash-one"}||x)\\
h_2(x)&:  \operatorname{SHA256}(\texttt{"Hash-two"}||x)\\
h_3(x)&:  \operatorname{SHA256}(\texttt{"Hash-threee"}||x)
\end{align}
If it is not this case you may need 3 different hash functions.
Also note that, if the $q > 256$ you cannot use SHA256 directly then use SHA512, Blake2, etc. and trim the result whenever needed.


A (current or soon-to-be) NIST-recommended alternative to ECC?

To my knowledge, NIST has not really decided or announced anything about successors to ECC. However, they do run workshops and such on post-quantum cryptography, so when the time is right something will probably move towards standardization.

NSA, on the other hand, recently announced that they will soon push for a post-quantum system, going so far as to say that moving from RSA to ECC may be unnecessary in the mean time.

The reason here is not performance or efficiency, however. By many measures the possible candidates for the successor are less efficient. Instead, they want something that remains secure even if quantum computers become practical (known as post-quantum security). Neither ECC nor RSA has that property.

But no, no specific alternative has yet been chosen. Because of this and the above mentioned recommendation to skip ECC, some have even wondered whether post-quantum security is the actual reason for the announcement.


Precisely how does CBC mode use the initialization vector?

The schemas from the relevant Wikipedia page really explain it all:

As you see in the decryption schema, the IV is used for a single XOR that yields the first plaintext block; it is obvious that the IV impacts only that block. When encrypting, though, modifying the IV alters the first ciphertext block, then the second ciphertext block, and so on.

The role of CBC is to hide redundancy in plaintext blocks. A block cipher is deterministic: encrypt twice the same input block with the same key, and you get the same output. Real-world plaintext data has redundant blocks; this leads to detectable leaks if nothing is done about that, as in ECB mode (the famous penguin picture is a clear illustration of the problem). CBC solves this by "randomizing" input blocks before encryption, and this is done by XORing each block with the ciphertext from the previous block: the output of a block cipher is assumed to be randomish enough to be efficient at avoiding as most as is feasible input block repetition.

Since the first block has no "previous block", the IV is needed to get the mode started. It is a synthetic "zero-th block".

If you take CBC-encrypted data and simply flip the k-th bit in the n-th block, then, upon decryption, this will result in replacing the n-th plaintext block with garbled junk, and flipping exactly the k-th bit in the n+1-th plaintext block; nothing else is changed. (This also highlights by having a MAC is very important to deter malicious alterations; even without knowing the key, attackers can have rather precise control on what they can do to the resulting plaintext by modifying the ciphertext.)

There is a common myth about CBC being a way to make every ciphertext bit depend on all plaintext bits. This is a myth; CBC does not do that and never aimed at doing that.


8th SharifCTF — What is the advisable way to recover the key of single round DES here?

Can we use a known plaintext attack

Considering that you have 1,000 plaintext-ciphertext pairs, you should be able to.

Known plaintext attack(s)

Try applying linear cryptanalysis, DES is relatively weak against it.

Alternatively, you could try differential cryptanalysis; DES is usually considered to be relatively strong against it, but with only a single round you might still make some headway.

  or would another attack be more advisable? If, which one?

Chosen plaintext attack

Do you have access to an encryption oracle? If not, then you can't perform a chosen-plaintext attack.

Chosen ciphertext attack

Do you have access to a decryption oracle? If not, then you can't perform a chosen-ciphertext attack.

Slide attack

Since the cipher is a reduced round variant that uses only a single round, you cannot use a slide attack.

Brute force

You could probably rent a supercomputing cluster and simply crack the key with brute force. This is probably the slowest, most expensive, and least enlightening technique, but it will work against regular (not triple) DES.


What are the specifics behind MD5 being weak against collisions?

We know techniques for cheaply computing collisions in MD2, MD4, SHA-0, and, of course, MD5.

The first cheaper-than-generic technique for computing MD5 collisions was published by Hans Dobbertin in 1996; then a collision in MD5, computed in a few hours on an IBM p690, was published by Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu in 2004, and the technique explained in a followup paper in 2005 (some details on the history); an independently developed technique was used in an international incident of industrial sabotage by the United States and Israel against Iran; and the techniques for computing MD5 collisions have since improved nearly to the point of being a parlor trick.

We also know a technique for computing collisions in SHA-1 much more cheaply than a generic collision search on a 160-bit hash function.  It is nowhere near as cheap as MD5—it cost about $2^{64}$ evaluations of SHA-1, whereas a generic collision search costs $2^{80}$ evaluations of the hash function, and the current best known MD5 collision search by Tao Xie, Fanbao Liu, and Dengguo Feng costs only $2^{18}$ MD5 evaluations.  But it has been executed to find SHA-1 collisions, and for Merkle–Dåmgard hash functions like MD5 and SHA-1, one collision of equal-length messages can be trivially extended into many, so knowing one SHA-1 collision is enough to get you in trouble!

We don't know any techniques for finding collisions with reasonable cost in SHA-2, SHA-3, any of the SHA-3 finalists, BLAKE2, or various hash functions of lesser import.

Many crypanalysts have tried, and failed, to figure out techniques for finding collisions in these.  Any hash function widely used by many applications, especially financial or political applications, will be subjected to scrutiny because of its high value.  It's possible that a spook or crook who found an attack might choose not to publish it, of course!  The SHA-3 competition subjected a number of candidates to years of scrutiny by the world's top public academic cryptanalysts, compiled at the SHA-3 zoo, so that we have some confidence in them to resist collisions.

We also don't consider any hash functions with small outputs, e.g. less than (say) 192-bit, to be collision-resistant because the cost of generic collision searches, counted in number of evaluations of the hash function, is small enough to be within the realm of feasibility for humanity to execute.

To put the number in perspective, the Bitcoin network today performs about $30 \times 10^{18}$ SHA-256 computations every second, about $2^{64}$ per second or $2^{90}$ per year.  A generic collision search on a 192-bit hash function would cost an expected $2^{96}$ evaluations.  That's not cheap, but it's imaginable.


can a weak cipher in a cascade weaken the result?

I'm tailoring my question specifically to VeraCrypt where needed.

  So if We have AES(Twofish)) with the key : Test-password123 The
  "Test-pass" Part would be used for AES and the "word123" part gor
  twofish right ?

No.
VeraCrypt (and any other somewhat decent encryption program for that matter) uses a so-called "password-based key derivation function" (more precisly PKCS#5 PBKDF2), which takes the full password and iterates a moderately fast function (a so-called hash function) very often. This is done so an attacker can't easily verify a guess for your password. Now the result (a sequence of bytes) is taken and split into different sub-keys (2-6 keys in the case of VeraCrypt)1.

  So if you would use something like rc4(AES)) cascade , The rc4 would
  weaken the AES cipher right ?

It depends, but in general no.
AES, Twofish and Serpent are so-called block ciphers, that means they take a block of (16) bytes and transform them into a different block of (16) bytes using the key, such that the transformation is reversible given the key and not if not given the key.
These block ciphers need to be run in a so-called mode of operation (XTS in this case). There is no known attack that performs (significantly 2) better than brute-force key search for this cascade, so you are required to perform at least $2^{256}$ operations which is infeasible.
In your concrete example, it depends on the mode of operation for AES. If this mode is a so-called stream cipher then there's a result that states that the encryption is at least as strong as the stronger algorithm.

1: Actually it runs this chain mulitple times to generate a set of key-bytes each time and then splits.
2: Actually double-encryption is only slightly better than single encryption due to the meat-in-the-middle attack.


What is the purpose of using different hash functions for the leaves and internals of a hash tree?

If the same standard hash function was used for both leaves and branch nodes, it would be easy to generate collisions and even second preimages.

For example, let $M$ be a message which is longer than the segment size of the hash tree, but (for simplicity) no more than two segments long. Then the hash value of $M$ is calculated as $$H(M) = H_I(H_L(M_0) \,\|\, H_L(M_1)),$$ where $H_I$ is the internal hash function, $H_L$ is the leaf hash function, and $M_0$ and $M_1$ are the first and second segments of $M$.  We'll also assume that the segment size of the hash tree is at least twice as long as the length of the output of $H_L$.

Now let $M' = H_L(M_0) \,\|\, H_L(M_1)$.  Since $M'$ is, by assumption, at most one segment long, its hash will be calculated as $$H(M') = H_L(M') = H_L(H_L(M_0) \,\|\, H_L(M_1)).$$  If $H_L = H_I$, then $H(M') = H(M)$, and we've just found a second preimage for $H(M)$.


ECDSA signature verifiable 1-way transformations

Use a zero-knowledge proof of knowledge (ZKPoK) of a value $(r,s)$ that is a valid signature.  For instance, you might be able to adapt existing ZKPoKs for proof of knowledge of a discrete logarithm to this problem.  Because it is zero-knowledge, you will know that it reveals nothing about $(r,s)$ and is not transferable.


Performing a cryptographically secure HMAC using multiple input parameters

Yes, you can simply concatenate unless the encoding is not canonical, e.g. when the order isn't set or when the dynamic size of the fields make it possible that there is room for overlap between the fields.

It does seem that you've chosen string representations while it would be easier to use encoding to bytes directly. E.g. an IP 4 address usually consists of just 4 bytes. The seconds since the Linux epoch could be a number encoded into 32 bits. That way the chance of overlap is also zero because the field boundaries would be well defined.

Another issue is that you need to make the character encoding explicit., e.g. aways use US-ASCII or UTF-8.


You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 \lt x, y \lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.

The rightmost digit of $n$ in base $B$ is $(x y) \bmod B$. Since $\{x,y\} \le B-1$, $(x^2 + y^2) B + x y \le 2 (B-1)^2 B + (B-1)^2 \lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) \lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 \le z \lt 2$, i.e. $z \in \{0, 1\}$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y \in \{W_0, W_1\}$.

Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.


Preimage resistance is usually defined not for all the inputs, but for all the outputs, since what you are trying to model is the inability to, given any output $y$, obtain an input $x$ such that $H(x) = y$.

I'm not going to solve the problem for you since you may be able to do it by yourself. Just try to think of the patterns in the output and if this can be related to some input.


Group Encryption or Multi-Party Encryption

This kind of thing would typically be done via role based accessed control (RBAC), not encryption.  To do something like this strictly with encryption if you could assign identities upfront then you could use hybrid encryption to achieve this (though it seems a bit clumsy).  A public/private key pair is assigned to each role.  Data is encrypted with a randomly generated symmetric key and that key is then encrypted with the private key of the role(s) that access the data.  Each user has a role and therefore a set of public keys associated with that role.  If the user has a public key that can decrypt the symmetric key they can then decrypt the data and view it.

RBAC is a better solution.


Since @fgrieu was interested in question 2, I'm going to break with site policy and give a full answer for that part, even though this is almost certainly homework.
Theorem.
Let $F : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ be a PRF. Then, $F_2 : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$, defined as
$$F_2(k,x) := F(F(k,0^n),x)$$
is also a PRF.
Before we give a formal proof, let's build some intuition why this should be the case. Note that the inner invocation of $F$ is not on some part of the input, but instead on a constant (i.e., $0^n$). This means that once we fix the key $k$, the key used by the outer invocation of $F$ for all evaluations of $F_2$ is a fixed key $k' := F(k,0^n)$. Since $k$ is not used elsewhere in the construction, $k'$ should, by the security of the underlying PRF, be indistinguishable from a uniformly random key $k''$, as long as $k$ is chosen uniformly at random. This would mean than an oracle evaluating $F_2(k,\cdot)$ and an oracle evaluating $F(k,\cdot)$ should in fact be indistinguishable. Since $F(k,\cdot)$ is already known to be indistinguishable from a uniformly chosen random function $f(\cdot)$ and indistinguishablity (in the asymptotic sense) is transitive, it would follow that $F_2$ must also be a PRF.
So let's formalize this intuition.
Proof. Let $A$ be an arbitrary PPT algorithm with
$$\Bigl|\Pr_k[A^{F_2(k,\cdot)}(1^n)=1] - \Pr_f[A^{f(\cdot)}(1^n)=1]\Bigr|=\epsilon(n).$$
We are looking to give a negligible upper bound for $\epsilon$. To do this we will prove a series of claims.
Claim 1. $\Bigl|\Pr\limits_k[A^{F(F(k,0^n),\cdot)}(1^n)=1] - \Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1]\Bigr| \leq \mathsf{negl}(n)$
Consider the following adversary $B$ against the PRF security of $F$.
Upon input $1^n$ and given access to an oracle, $B$ queries $0^n$ to the oracle an receives back a value $k'$. It then invokes $A$ on input $1^n$. Whenever $A$ sends a query $x$ to its oracle, $B$ responds by computing $y:=F(k',x)$. Eventually, $A$ will output a bit $b$ which $B$ also outputs.
It is easy to see that $$\Pr_k[B^{F(k,\cdot)}(1^n)=1] = \Pr_k[A^{F(F(k,0^n),\cdot)}(1^n)=1]$$ and $$\Pr_f[B^{f(\cdot)}(1^n)=1] = \Pr_f[A^{F(f(0^n),\cdot)}(1^n)=1].$$
Further, since $F$ is a secure PRF, it must hold that
$$\Bigl|\Pr_k[B^{F(k,\cdot)}(1^n)=1]-\Pr_f[B^{f(\cdot)}(1^n)=1]\Bigr|\leq \mathsf{negl}(n)$$
and the claim follows.
Claim 2. $\Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1] = \Pr\limits_{k}[A^{F(k,\cdot)}(1^n)=1]$
To see that this is the case, it is easiest to think of $f$ as being lazily sampled when queried. Since $f$ is only ever invoked on $0^n$, sampling $f$ is equivalent to simply sampling $f(0^n)$ once as a uniformly random value $k\in \{0,1\}$, which is identical to the right hand side.
Claim 3. $\Bigl|\Pr_{k}[A^{F(k,\cdot)}(1^n)=1] - \Pr_{f}[A^{f(\cdot)}(1^n)=1]\Bigr| \leq \mathsf{negl}(n)$
This claim is in fact just a restatement of the assumption that $F$ is a PRF and thus follows trivially.
Using the triangle inequality, we can conclude
\begin{align}
  \epsilon(n) =&\quad \Bigl|\Pr_k[A^{F_2(k,\cdot)}(1^n)=1] - \Pr_f[A^{f(\cdot)}(1^n)=1]\Bigr|\\
  \leq&\quad\Bigl|\Pr\limits_k[A^{F(F(k,0^n),\cdot)}(1^n)=1] - \Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1]\Bigr|\\
&+ \Bigl|\Pr\limits_{f}[A^{F(f(0^n),\cdot)}(1^n)=1] - \Pr\limits_{k}[A^{F(k,\cdot)}(1^n)=1]\Bigr|\\
&+ \Bigl|\Pr_{k}[A^{F(k,\cdot)}(1^n)=1] - \Pr_{f}[A^{f(\cdot)}(1^n)=1]\Bigr|\\
&\leq 2\cdot\mathsf{negl}(n)
\end{align}
and the theorem statement immediately follows.$\tag*{$\square$}$


Unit testing a library RNG and its seeding for practical security

You're not going to like this answer, but strictly speaking, you can't.

In a number of specific cases you can do what you want. For example, in the specific case of the Debian PRNG debacle, you could detect that (and as a matter of fact, bad keys generated by this PRNG failure were tracked down). But that's because the RNG was not seeded much at all and ended up with some small number of possible states. (I'm saying RNG not CSPRNG because I'm not considering any cryptographically insecure pseudo-random number generators.)

But if the output stage of your PRNG comes from a suitable pseudo-random function, it will pass all your tests. AES in counter mode, an iterated hash function, and so on will all be just fine -- these outputs are themselves pseudo-random functions and therefore pass all your pseudo-random tests. It will be cryptographically secure from a mathematical reference point. If it is insecure, it will be insecure because of an operational failure, like the Debian problem, which was operational, not mathematical.

You are only going to find practical failures of a PRNG by white-box testing. You will have to have a reasonably smart crypto person to code-review it. You will have to look inside it to see if it is constructed correctly.

Consider this as a badly-built PRNG: imagine a chip with a PRNG that is seeded with a completely random 64-bit number to which is added the chip's serial number, and then a high-quality output stage (Yarrow, SP 800-90 DRBG, etc.) generates random bits from that seed from then on.

In other words, for the entire family of chips, there's a single 64-bit chunk of entropy E, and each chip has put into it E+1, E+2, ... E+N for the N chips we manufacture. Call this number E_n.

We'll presume that all re-seeding is broken and has no effect. You very likely won't be able to tell this from testing the output only.

You might in some cases -- for example, let's suppose that the output is a naïve iterated hash. You might be able to detect that the substring R[i..i+31] is equal to SHA256(R[i-32..i-1]). But be lucky to detect that, because you'd have to explicitly check for it.

Similarly, testing its output can tell you if the output function isn't a PRF, but not a lot more than that, and these days the errors aren't going to be because of the output function. Even dummies are going to get that right; look at the Debian debacle again. The problem was seeding, not pseudo-randomness.

You wouldn't find it if the bogus chip hashed in E_n along with each iterated hash, or if there was an HMAC. You wouldn't find it if there was a simple counter hashed in, either. You almost certainly wouldn't detect anything amiss if the PRNG used a cipher in counter mode with E_n as the key, either. (There are plenty of edge cases where you would -- for example, if you used DES in counter mode and happened to pick a weak key, you might detect that. Bear with me for the general case here.)

This completely bogus random number chip has only 64 bits of good randomness in the entire chip production, and yet no black box testing is going to detect that. You're only going to find the problem by auditing its design and implementation, not by testing its output.

I told you you weren't going to like my answer, but there it is. Black box testing will only detect a small class of stupid errors, and none of the evil ones.

Jon


Generating random non-repeating numbers from a small group

If you are going to generate ALL the numbers in the output domain, an attacker's job of guessing the next number becomes easier the more numbers you use, once you pass the halfway point. I would suggest with whatever method you choose, to never exceed $N/2$ values used, where $N$ is the total number of elements that can be generated using that method, $N=2^{16}$ in your example.

I actually see no problem with using a finite field, but you would need to make it difficult for the attacker to guess the values used to generate it, even if the method was known.

My solution would be to use the same finite field inversion method as was used to generate the AES S-box, but in $GF(2^{16})$ with the APA method. It is a highly nonlinear sequence, and there are simply too many combinations of generator values and reduction polynomials to brute force every option like there are in $GF(2^{8})$.

Essentially, you perform an affine transformation on the input, then find the inverse in the field, and then perform the affine transformation again, with an irreducible polynomial chosen at random from the list of possible polynomials. There are specific combinations of affine generators and vectors within each finite field that generate high quality results useful for S-boxes, but you would not be constrained by the same conditions, giving you more flexibility. The mathematical description of the algorithm would be very simple.

The format preserving option easily allows you to build a Feistel cipher of whatever block size you want since your domain size is an even power of 2, in your case 16-bit, by using another block cipher or PRF as the F-function. You can drop in AES, use the 8-bit block half plus a round counter as an input, and truncate the output to 8-bits. This would be very easy to code and very quick to generate numbers, at the expense of a complex description of the final algorithm. You can also generate 128-bit subkeys in CTR mode, then use these as independent AES keys for each round, at the expense of additional computation.


Any real world implementation using message recovery?

A signature scheme with message recovery is standardized as ISO/IEC 9796-2 (link to preview). Scheme 1 in this standard is commonly used in the Smart Card industry, despite its known weaknesses in a chosen-message setup.

Example real-life uses include the EMV banking application (the free documents linked there include a description of an industry-standard subset of ISO/IEC 9796-2 Scheme 1; there is support for this subset in JavaCard 2.2.2 and up); and the certificates in the European Digital Tachograph system (head to Annex 1B, appendix 11).

Update: As kindly pointed by Maarten Bodewes, that is also used in ICAO e-passport specifications, appendix 4.


Are there any cryptographic algorithms, which lets the user apply some modifications on the encoded data, without decoding it?

Can I modify encrypted data without accessing it? if there is an example appreciate it

If access means altering the data without decryption as an attacker then the answer is yes for messages without integrity.

Take OTP, execute bit flipping attack, done.

Take CTR mode, execute bit flipping attack, done.

Take CBC, execute bit flipping attack, done.

Similarly, take any stream cipher, modify one bit,
Let $c_i = m_i \oplus x_i$ where $x_i$ is the $i$th bit form the stream cipher then
$$c_i \oplus 1 = m_i \oplus x_i \oplus 1 = \bar m_i \oplus  x_i$$ where the $\bar m_i$ is the bit complement of the bit $m_i$.

Take CFB, execute bit flipping attack, done

and so on...

These also called the ciphertext malleable.
Note that the reason for this kind of attack is that they are at most CPA secure ( well OTP can have perfect secrecy with fixed-length messages ) and that doesn't mean that the modifications are detectable. To mitigate this attack one needs at least integrity. The integrity may not be enough, since the attack in some cases reuses some part of the encryption and send it. Therefore, at least we need a Message Authentication Code (MAC), like HMAC, GMAC, CMAC, etc. With MACs, the attacker need also forge the message to execute such attacks on the encryption.
Note that the bit flipping is the minimum attack. The attacker can modify more than one bit whenever it fits their aim.

If access means you want to operate on the encrypted data that the answer is yes for a very long time;

Textbook RSA is multiplicative so that you can multiply the ciphertext. Let $(n,e)$ be the public modulus with $d$ is the private exponent. Let the ciphertext $c = m^e \bmod n$ and $c' = 2^e \bmod n$ then
$$c \cdot c' =  m^e \cdot 2^e = (2m)^e \bmod n.$$
One should keep track of the overflow that is when the modifications exceed the modulus the value will be rounded.

ElGamal can be both additive and multiplicative

Paillier encryption is additive where the multiplication of the ciphertext is the addition of the plaintext.

Goldwasser–Micali where the multiplication of the ciphertext is the x-or of the plaintext.

2DNF enables 1 multiplication and many additions.

The above was before Gentry's Seminal work; Fully Homomorphic encryption that enables operation of arbitrary operations on the encrypted data. This was envisioned by On data banks and privacy homomorphisms. by Shamir et. al, immediately after RSA.
The FHE simply having two homomorphic operations on the data so that arbitrary circuits can be computed;
$$E(a) \boxplus E(b) =E(a \oplus b)$$
$$E(a) \boxtimes E(b) =E(a \times b)$$
Note that for the plaintext and ciphertext operations different notation is used since the FHE schemes are not restricted to those. Some notable FHE libraries are;

HeLib, THFE, GSW, BGV, LTV, FHEW,....

There is a post about how these operations handled; Representing a function as FHE circuit


How is CipherCloud doing homomorphic encryption?

I could not find any evidence pointing towards homomorphic encryption. What I could find were different combinations of deterministic and format-preserving encryption. There is probably also a variant that preserves order, but I couldn't find any material depicting it.

This post is based on material published on the CipherCloud website at CipherCloud Cloud Security Learning Center - Featured Content. CipherCloud notes that the actual product has additional encryption features that offer stronger security and don't suffer from the listed weaknesses (see CipherCloud response section).

Material 1: A screenshot from their whitepaper Best Practices in Securing Your
Customer Data in Salesforce,
Force.com, and Chatter on page 10:

[image removed due to DMCA request]

Description: This screenshot depicts contact details (name, address, phone, etc.) in three columns.

The first column shows the policy which determines how different fields should be encrypted. For most fields this is "AES Crypto Encryption", for some fields such as phone numbers it's a specialized form of encryption, such as "Telephone Number Encryption".
The second column shows the plaintext ("As seen by authorized users")
The third column the ciphertext ("As seen by Unauthorized Users")

Analysis: When a field consists of several parts(say firstname and lastname) they split it into those parts and encrypt them individually.

Some important fields, such as "annual revenue" aren't encrypted at all, probably because they need to do use it in calculations.

The encryption for names and addresses preserved the length of the individual words and the position of spaces. There are special tags between words that seem to mark encrypted parts and separate tokens.

Preserving length strongly hints at deterministic encryption, as does support for search. In theory, it'd be possible to use difference nonces for different records, but I consider that unlikely since it'd be hard to keep a search index in such a case.

Material 2: Feature list from the same whitepaper (page 11):

  Encryption Options: AES-256, Function Preserving Encryption,
  Length Restricting Encryption, etc. Ability
  to select on a field-by-field basis

Analysis: Same length encryption was already observed in Material 1. Presumably preserved functions search and ordering. Probably it's possible to choose which functions to preserve on a per-field basis. Material 3 will demonstrate a form of encryption that allows search, but does not appear to preserve ordering.

Material 3: CipherCloud Connect AnyApp Demo Video around 2:30 and 3:00:

[screenshot omitted due to DMCA request]

Description: This shows a typical message board that is part of the yammer web-application. There are two open windows showing the same thread. One shows the encrypted messages (as the yammer.com server sees it), the other the plaintext form as it is seen when accessed through CipherCloud. The message bodies are encrypted, the usernames and post times are not. The encrypted messages are a mix of Asian and ASCII characters.

Analysis:

There is a clear correspondence between plaintext words and ciphertext token. Each token starts with zqx1, ends with 0j1xqz and corresponds to one word. Punctuation marks are not encrypted at all.

Words that occur multiple times in the plaintext (for example meet, to, want) appear as identical tokens in the ciphertext.

The words new and will are even more interesting. They occur both in lowercase and uppercase form. The encrypted form of New might look like zqx1賓翡祀徠鈞祁記勤机琦芸稶70j1xqz1 and the encrypted form of new like zqx1賓翡祀徠鈞祁記勤机[linebreak]20j1xqz2.

So I assume the first part of the token encodes the word in a case insensitive form and the second part supplies the casing information. Sid made the same observation in his post. This form of encryption allows the case insensitive search they demoed in the video, where a search for apac turned up a message containing APAC since the beginning of the word is the same, regardless of case. This certainly looks like a 1:1 mapping between lower case words and the first part of the token.

The first part of the token seems to have a constant size of 9 Asian Characters. Given a large number of such characters, that would be enough to encode 128 bits or one AES block. So one possible implementation would use AES in ECB or CBC mode with constant IV encrypting a single block. But this paragraph is pure speculation that can't be proven from the limited observations we made.

An inherent weakness in such a scheme is that it doesn't offer semantic security.  If the same word gets encrypted in different places, an attacker can see that the same word was used in both places. If he can figure out one of them, he automatically knew the other too.

The attacker could also employ some kind of word-level frequency analysis on tokens. Once part of the ciphertext has been recovered, the known words serve as a context for further guesses. Once a certain knowledge threshold has been exceeded this should allow recovery of most words. So it's essentially to prevent an attacker from learning any (ciphertext, plaintext) pairs, even for harmless messages. Quoting public material or storing drafts which later will be published is also quite dangerous.

A similar non-deterministic scheme

The above scheme is essentially a word-level substitution cipher. Classical substitution ciphers usually use a single letter (or a small fixed amount of letters) as a substitution unit. Modern block ciphers such as AES trivially allow using whole words as a substitution unit which was a bit difficult to do without a computer.

Those early substitution ciphers had similar weaknesses to the above scheme (1:1 mapping between letters, deterministic encryption, and frequency analysis). Of course with short/letter units these weaknesses where much more pronounced than with long/word units.

One technique used to reduce the impact of these weaknesses is having multiple possible substitutions for each plaintext unit and randomly choosing one during encryption. This technique is called Homophonic substitution. This technique can obviously be applied to word-level substitution ciphers as well.

When a word has n possible ciphertexts, one could still do searches by triggering n separate searches over the encrypted data and merging the results. This would turn above 1:1 mapping into a 1:n mapping, make the encryption non-deterministic and, depending on the chosen probability distribution, frequency analysis might be less effective as well. Of course, such a combined search would leak some information to the server about which ciphertext units might correspond to the same plaintext unit.

There is no evidence that CipherCloud uses a homophonic word substitution cipher. I only mentioned this scheme because it's the simplest change to the above scheme that doesn't contradict the claims in their DMCA notice. Ciphercloud claims not to suffer from the above weaknesses, thanks to "patent pending mechanisms". I certainly hope that their mechanisms are better than simply switching to a homophonic word substitution cipher.

CipherCloud's claims in their DMCA notice:

As a counterpoint to this analysis here are some claims made in their DMCA notice:

  Such false, misleading and defaming statements include the following sample:

  (2) "If the same string gets encrypted in different places, an attacker can see that the same string was used in both places." [statement from an old version of this post]
      * Again, CipherCloud's product is NOT deterministic.

  (4) "As CodesInChaos suggested in an earlier answer, this makes the solution extremely vulnerable to frequency-analysis attacks." [from AdrenaLion's post]
      * The referenced scheme does NOT represent CipherCloud functionality. In fact, CipherCloud has patent-pending mechanisms to defeat frequency-analysis attacks.

  (7) "Basically they end up with a 1:1 mapping of lower case words." [Sid's post, referring to the message board discussed in this post]
      * The statement is patently false. Sid implies that what was perceived from a public demo is CiperCloud's product offering. [emphasis mine] CipherCloud does not incorporate 1:1 mapping.

(10 sample statements were included in the DMCA notice, I picked those most relevant to this post. I inserted notes linking quoted statements to their original posts)

Conclusion

The observed encryption has significant weaknesses, most of them inherent to a scheme that wants to encrypt data while enabling the original application to perform operations such as search and sorting on the encrypted data without changing that application. There might be some advanced techniques (homomorphic encryption and the likes) that avoid these weaknesses, but at least the software demoed in the video does not use them.

The only way I see to reconcile the statements in their DMCA notice with the observed encryption properties is that the actual CipherCloud product is significantly different (and better) than what is shown in their promotional material.

If they don't want to be judged based on the information they published about their product, perhaps they should update their material to match their actual product more closely.

CipherCloud response

CipherCloud post a response on their blog: Responding to the Myths about CipherCloud’s Encryption Technology

Pretty little concrete information, but here some relevant parts:

  I wanted to provide some clarity to the question of whether CipherCloud uses homomorphic encryption.  The answer is NO.  Homomorphic encryption is far from ready for practical usage due to performance and lack of capabilities.

  The cited CipherCloud product demo in the board threads was focused on highlighting our reverse-proxy concept for cloud information protection to organizations using cloud applications. Some of the fundamental security features made available  (e.g. full-field encryption, randomization through IVs, etc.) were disabled because we were not comfortable sharing such IP on the internet while our patents are still pending.

1 The actual Asian characters were different from the one in my post, but the general form was the same.
2 The linebreak is an artifact of the browser displaying the text. It might have hidden some characters.


How to use Homomorphic encryption for secure computing Arctan() function?

While this may be of interest as an academic exercise, they can't securely compute it without revealing their coordinates (or at the very least leaking a lot of information about their coordinates).

Consider that partyB gives a secure service to partyA whereby partyA can calculate the arctan without exposing its coordinate. Let's say this result is $v$. Then clearly $y_2 = y_1 + (x_2 - x_1)\tan v$, which is already leaking a very large amount of information about $(x_2,y_2)$. Indeed, if partyA can make an additional query to that service, passing in some other coordinate, then partyA has sufficient data to calculate the coordinate precisely.


Message encrypted with a LFSR based stream cipher

I will try to not directly answer your question, but this exercise is so simple that it gets hard to help you without doing that.

You are going to use a symmetric cipher (One-Time Pad - OTP), thus your initial step is to compute your key. This is given by the execution of the LFSR as you described, until a key-stream of the length of the message is obtained. Then, simply apply the OTP decryption step (*) into your pair (key, ciphertext).

(*) I hope you know what the OTP decryption step looks like! ;-)


TL;DR: it depends on the API implementation of the AES encryption function you are using.

AES is a block cipher with specific key sizes, 128, 192, 256 bits. To use it as an actual encryption mechanism it is required to use it in a specific mode of operation. Otherwise it is only useful to permute a single 128 bit block. These mode of operations (usually) do not affect the key size.
You can broadly distinguish the following possibilities:

If you use a programming API with a badly sized key then it usually will generate an error (special return value or exception);
Some API's actually implement the full Rijndael instead of AES; AES is a subset of Rijndael. Rijndael accepts all key sizes between 128 and 256 bits with a step of 32 bits (AES is based on 32 bit operations) but it will not accept just any key size such as a key size smaller than 128 bits as in your example;
Yet other API's do not perform input validation at all, for instance the horribly crappy C/PHP mcrypt library simply right-pads with zero bytes and may even use a partial key if it is too big (nowadays it additionally outputs a message to the warning log);
If you're using a lower level programming language and API (your code kind of hints at C) then it may be that you first need to select AES-128, -192 or -256 and then provide a key. As the key size is now known this could be simply a pointer in memory. In that case the short key will be used together with any byte value that comes after the key. If you would not be able to re-generate (guess, brute force or simply get lucky because the program always behaves similarly) then the message you've just encrypted may get lost forever (!). If the key is too large then part of the key may be simply ignored (just like it would for possibility #3).
Sometimes API's are also programmed on a higher level where instead of a key a password is accepted. This should be apparent from the API, if the API was designed well. In that case a Password Based Key Derivation Function (PBKDF) should be used to convert a password to a 128, 192 or 256 bit key. This function should be documented as well. The result is called Password Based Encryption or PBE. One standard for this is PKCS#5: Password-Based Cryptography Specification (Version 2.1) in RFC 8018.

Note that the bits in an AES key should be indistinguishable from random. A string such as a password doesn't have this property, even if it is encoded to bytes. ASCII for instance only uses 95 printable characters per byte. Even though other encodings (Windows-1252 or UTF-8) may contain more possible values per byte, they won't match the requirement of having 256 random values per byte.
PBKDF's (see reason #5) such as PBKDF2, bcrypt, scrypt or Argon2 strengthen the password and output the requested number of bytes, all of which depend on the password. The output of the PBKDF can then be used as key (and other pseudo random data such as the IV).


Basically all hash functions have this "problem". Pretty much all are finite in length.

The real problem happens when collisions can be generated in less work than brute force. Due to the birthday problem with an $n$-bit hash function we would expect to see a collision after computing $n/2$ digests. If $n$ is large enough (say $n=160$) we would not expect any realistic adversary to be able to generate collisions.

A hash function is broken when someone can demonstrate collisions in fewer than $n/2$ operations.


What's wrong with this curve (generation algorithm)?

As a lone curve, yours is not bad. But Barreto's proposal offers an extra property, which is that the quadratic twist also has prime order.

In general, in a given finite field $K$, if you have a non-quadratic residue $d$ (i.e. a field element which is not a square), then, for the curve $E$:
$$ E: Y^2 = X^3 + aX + b $$
then you can define another curve called its "quadratic twist":
$$ E^d:Y^2 = X^3 + ad^2X + bd^3 $$
It can be seen that if $X$ is a valid first coordinate for one curve, then it is not for the other, and vice versa. It implies that that if field $K$ has cardinal $q$ (in your case, $q = 2^{255}-19$), curve $E$ has order $n_1$, and $E^d$ has order $n_2$, then $n_1 + n_2 = 2(q + 1)$. It also implies that the exact choice of $d$ does not matter much, in that all twisted curves you may get all have the same order, hence they are all "the same curve" in some sense (they are isomorphic to each other). This is why we talk of the quadratic twist.

(When $p = 3 \pmod 4$, it is convenient to use $d = -1$, but in your case, $-1$ is a quadratic residue because $2^{255}-19 = 1 \pmod 4$.)

Note that the quadratic twist of the quadratic twist is the original curve (or something isomorphic to it).

Quadratic twists may matter because in some cases they allow to avoid point validation. If you consider normal ECDH with point compression, both parties will send the $X$ coordinates of their public points to each other. Normally, each receiving party would then rebuild $Y$ from the received $X$, and check that indeed they got a point on the curve. That process would go thus: receive $X$, compute $X^3+aX+b = Y^2$, then apply a square root algorithm to get $Y$. If the received $X$ does not correspond to a point on the curve, then the recomputed $Y^2$ is not a square: this is where point validation happens.

Historically, a number of implementations have got validation wrong and blindly kept on computing with whatever point they had. In practice, if you get an $X$ that does not map to a point on the curve, then you are really computing on the quadratic twist. Therefore, it seems to be a good idea if the curve and its quadratic twist both have a prime order.

In Barreto's proposed curve, both the curve and its twist have prime order. In your curve, the twist's order is not prime. That's what is "wrong" with your curve.

In my opinion, the issue about validation is overrated. Point validation is not hard; it uses up negligible CPU compared to the actual computations you are about to do, and the code size overhead is small. Implementations that do not point validation are basically sloppy, and sloppiness, like love, knows no limit. However, if you can have some extra protection against sloppiness at low cost, then why not?


Why use variable p, q, g for Diffie-Hellman?

The following are the reasons I came up with for not using static/standard DH parameters.

You might not trust the person who generated the group. They could have generated a group with a trapdoor (e.g., group order is smooth) which would allow them to break the resulting system.

The longer you use the same group, the more time an attacker has to attack the group.
E.g., if millions of people are using the same group, millions of times a day and the attacker has a database of terabytes of pairs $(g^x,x)$, they may be able to break a key establishment.

In DH, remember we must choose a random exponent. We have seen a number of recent cases were random number generators weren't as random as originally thought (e.g., Debian OpenSSL RNG). Not reusing the same group could potentially thwart bad RNGs (though if the new group is generated using the same RNG...).

You should remember though that there are also issues with generating new groups all the time, so you have to weigh the tradeoffs. I wouldn't think that there is a clear, definitive winner for how to do it that applys to all circumstances, though when done correctly either way is secure. If the group parameters were chosen by someone I trusted (e.g., NIST), then I'd personally just use the parameters they suggest.
Why would I still recommend using a standard group
Even given the potential problems I listed above, I personally would still use a standardized group generated by someone I trust because:

If they have generated it properly, you will know the order of the (sub-)group and know that it isn't smooth.
The probably of #2 is still very, very small
If your RNG is bad, there are probably so many other issues that even changing the group won't save you.
The possibility of you not checking things exactly right when generating your own group is pretty high.
Generating a new group will add significant computation time with little added security.


How we can create a protocol using Schnorr as identification scheme and a hash function as a puzzle?

Related question here:
Proving knowledge of a preimage of a hash without disclosing it?
Over at theoretical computer science SE:
Zero knowledge proof for value of a hash function

From the general properties of hash functions, we can not derive such a proof of knowledge. The reason for this is, hash functions are intended to destroy all meaningful structure. In most zero knowledge proofs structures with oneway-trapdoor functions and homomorphic properties are used, because then those proofs are short and elegant. Practical hash functions don't have that. On the contrary, a homomorphic property could be used to find collisions, which shouldn't be possible for hash functions.

For specfic ones, like sha 256, there are ways to get a proof of knowledge, and it is explicitly an example of Zero-Knowledge Using Garbled Circuits
or How To Prove Non-Algebraic Statements Efficiently, by Jawurek, Kerschbaum and Orandi (2013). There is an experimental evaluation as well. The experiment had a result of over 5s for sha 256.

That should cover your first question, but I am not sure what you mean with the second question. In a proof of work you usually have the following steps: 1. The client requests something, 2. the server gives the client a task, e.g. a partial preimage to a hash, 3. the client sends the solution, 4. the server grants the request.

Now, you can replace the 3. step of sending the solution with a proof of knowledge. But that doesn't really make any sense, because the task should be possible to complete within reasonable time (partial preimage, or preimage in a reduced input space), and the server has to know that it is actually solvable. So if the server actually wants to get the solution, he can just calculate it himself. A proof of knowledge only makes sense if the input has to be kept secret from the server, but if he can't find the solution within reasonable time, then this challenge is useless in a proof of work - the challenge has to be solvable within reasonable time.

edit: I have no idea what you mean with your references to the Schnorr identifiation scheme and commited verifier zero knowledge. Those elegant kind of proofs like the Schnorr signature scheme are unusable for hash functions.


Is email an example of public-key cryptography?

This is a very abstract and wrong analogy and I assume you are talking about encryption. Often for introducing public key encryption one encounters the "box with lock" example: You publish a box and a lock (your public key) and everyone can put something in the box and close the lock and send it to you. You (the only guy that has the key to the lock  - the private key) can unlock the lock and get the stuff that has been put in there, but no one else ( because you are the only guy with the key to the lock) can do so.

But your email example lacks the main desired feature of this analogy (which is called confidentiality), i.e., anyone who runs your email server or listens in the wire can read all the mails intended to you without the need to know your password. Public key encryption relates the public and private key in a mathematical way (by means of some hard to compute function) such that decryption without knowledge of the private key is computationally infeasible, which is obviously not the case in your example.

Interestingly, identity based encryption does something that comes near to what you describe although cryptographically secure. There your email address (or any arbitrary string) can be your public key. But your private key is not an arbitrary independently chosen password, but some secret that is derived from some trusted party based on your email address. Then, anyone can use your email address to encrypt messages for you and only you knowing the corresponding private key can decrypt.


I'll answer your "detailed questions", I'm sure the "main security issues" will become obvious afterwards.

How does asymmetric encryption work in bitmessage?
The bitmessage wiki explains how the encryption takes place. I'll quickly explain the basics.
For each message, generate a secure 128-bit IV. Generate a new message key by generating a new ECDH key pair and "agree" on a shared key with the recipient's (=Bob) public key. Hash the shared secret (using SHA-512) and use the first 256-bit as key for HMAC-SHA-256 and the second 256-bit as the key for AES-CBC with PKCS#7 padding. Encrypt the message using this symmetric encryption scheme and form the HMAC on the ciphertext. The message will be composed of the IV, the public ECDH value, the ciphertext and the MAC.
Decryption is pretty straightforward. Derive the shared key using the provided public ECDH value and your private key, derive the authentication key, check the MAC is correct and decipher the message. If the MAC's invalid discard the message as "not for you".

Why there are collisions with addresses?
The way the public addresses are generated is quite complicated and is documented here. I'm not aware of any collisions, however the collision resistance isn't also at 80 bits. Basically you'll obtain a collision if the RIPEMD160 of the SHA-512 of the two public keys (encrypting, verifying) yields a collision. Now the odds of finding a collision are even a bit lower than the birthday bound of RIPEMD160 (80 bits) as the hash has to start with a zero (or more zeroes). Furthermore the addresses have to live in the same stream (at the moment there's only one) and they have to share the address version.

How is the private key stored (or not)?
The protocol doesn't describe how the private key is to be stored. However the reference implementation does the following:
The private key is stored keys.dat, without encryption, easily accessible by anyone having access to this file. In case of deterministic addresses it can be reproduced with a passphrase, in case of random addresses it can't be.

As you see, the main security issues with the points you mentioned are, that the keys are stored unprotected and that the uniqueness of addresses relies on the collision resistance of RIPEMD160.


Is it secure using LWE-based cryptosystem under RLWE-based parameters?

Am I right?

Possibly, but it's not guaranteed, even if we assume that LWE is secure.

RLWE is a special instance of LWE; however that doesn't mean that RLWE is secure if LWE is.  The LWE assumption holds if we have a random instance; that is, one chosen from a specific probability distribution.  The RLWE problem has a different probability distribution; one in which the vast majority of LWE instances have probability 0.  The probability that the LWE will choose an instance which has a nonzero probability for being a RLWE instance is negligible.  It may be that the RLWE instances happen to be weak; that would not practically impact the security of LWE.

Now, it's not known that any such weakness applies specifically to RLWE; however it's also not proven that there isn't, either.


Elgamal with secret key equal to zero possible?

It's worse than that: if $x = 1283767$, then the ciphertext will be $(g^r, m \cdot g^{r \cdot 1283767})$, which an adversary can immediately detect by checking whether $h = g^{1283767}$ and subsequently exploit to decrypt messages!  The same trick works for $x = -1$, $x = 42$, and $x = 123456789$.

We pick $q$ and $g$ so that the space of values for $x$ is so large that if we choose $x$ uniformly at random, the adversary's probability of success at guessing it is negligible, below $2^{-128}$—so small that you should be more worried about cosmic rays flipping bits in your RAM than you are about this event.

There are much better attacks recovering $x$ from $h = g^x$, requiring you to choose $q$ to have thousands of bits.  You should be much more worried about how you're using Elgamal encryption and how you shoehorn arbitrary messages in your application into integers mod $q$, and even more worried about articulating higher-level application security goals.


How secure is AES-256, but with an effective key length of 56-bits?

It would appear that this is as a consequence of the Wassenaar Arrangement (more detailed explanation). Basically, because cryptography falls under certain laws regarding munitions and arms trafficking there are restrictions on the strength of the cryptography you are allowed to sell (if the product is not a mass market product). It would appear that the limit on key size for symmetric algorithms is 56 bits. The exact verbage on the restriction is is:

  A "symmetric algorithm" employing a key length in excess of 56 bit

Source: Section 5. A. 2. a. 1. a (Page 87) of this document.

What I assume they do is something similar to zero pad a 56 bit key of random bits to a length of 256 bits so that the key is the correct size but the export restrictions are still met.

Edit: As otus points out, I neglected to mention that 56 bits is not a whole lot in regard to security. It's so small that EFF cracked a 56 bit DES key via brute force in 1998 with roughly $250,000 of custom hardware.


What is the maths behind Bitcoin's BIP32?

It seems to me (and I'm probably mistaken) that the HMAC-SHA512 and concatenation is not important, and that there is a simpler way of making child keys from just the appropriate type of parent key.

Yes you are mistaken - the trick definitely lies in the HMAC (or similar) one way function that protects the parent keys. This is also where the "chain code" comes at play, since it protects the parent keys with the HMAC (or similar).

Or are there functions which just depend on a child-number, i, and the parent key of the appropriate type, to generate child keys?

There are but they are not considered safe - imagine putting sha256(parentPivateKey || i) to the public where i is known and the length of your parentPivateKey is known, that could be attacked in a lot of ways.
PS: Instead of "child-number" you meant probably a child identifier


Is Curve25519 vulnerable to private key exposure in the case of a bad RNG?

Any key generation algorithm for any cryptosystem is going to be weak if the attacker can predict what seed was used to generate the key. They can just generate the same key. However, assuming the the random number generator is not that bad, different algorithms start to look different.

If you are just using the output of the random number generator as a private key, Curve25519 (the encryption algorithm) will use that as the secret curve point. That means any structure in the output of the RNG might be visible. So whether it's theoretically exploitable depends on how broken the RNG is.

In contrast, in Ed25519 (the signature algorithm you linked to), the actual elliptic curve point is derived from the private key using a hash function. That means as long as there's enough entropy in the key that the attacker cannot guess it, there should be no visible structure to take advantage of, unless the hash function – SHA-512 – is also broken.

With Ed25519 it's about as good as it can get. The RNG is only used in key generation, signatures require no entropy and so aren't vulnerable. Even if the RNG was slightly biased, it should be hidden by the hash.


How can AES be considered secure when encrypting large files?

Encrypting big amounts of data is no problem for block cipher - if you remember a few important things.

You can't encrypt plaintext which is bigger than the block size. You need to do some addition work. Most cipher operation modes first divide the plaintext into blocks of the size of the cipher. Now you can do different things: How about just encrypting each individual block, plain and simple? That's called ECB mode.

What happens if you encrypt the same block twice at different positions in a file? You get the same cipher text. If an attacker sees this, he can tell: "At this two positions there's the same plaintext." - The attacker could also swap two blocks without it being detectable (at least if the decrypted plaintext still makes sense).

Then there's the CBC mode. You first xor an Initialization vector (IV) with the first plaintext block. The IV should be randomly generated and has to be as big as the block size. Now you encrypt the resulting block. This is your first ciphertext block. As next step, you xor this first block with the next plaintext block. Block cipher algorithms create mostly random looking blocks after encryption and as a result, the xor of this and a plaintext block creates a new block to encrypt. This removes the two mentioned problems of the ECB mode: Swapping two blocks results in at least one garbage plaintext block. Also the same plaintext block will (in nearly every case) encrypt into different ciphertexts.

There are many more encryptions modes like the Counter mode (CTR). Also you should normally use some kind of Authenticated encryption. The use of a good cipher mode is not enough to avert most attacks. Things like a Message authentication code (MAC) are also important. A commonly used, but pretty complex way of combining both ways is the Galois/Counter Mode.


Using C_Sign to create a PKCS7 signature

The PKCS#7 standard is a messaging standard which includes messaging formats for signed data, enveloped data or signed and enveloped data. The PKCS#11 api will produce a "raw" signature, which you will have to wrap in the PKCS#7 signed data formats. If you are using Java or .Net I would recommend looking at the Bouncycastle apis, which include full PKCS#7 wrapper classes. If you are using C / C++ you may have to look for an appropriate ASN.1 library.


The private key can be anything within the group order, if you take the key more than 32 bytes, then your key will work, but due to the cyclic nature of the group, your public key will be equal to the remainder of the key from the group order (modulo the group order).

As for the public key, it will not necessarily be 64 bytes (two numbers are the x and y coordinates, modulo the final field p), because, for example, the x or y coordinate can be less than 32 bytes, which ultimately will give public key less than 64 bytes.

The private key is generated using complex random cryptographic functions. You can also flip a coin 256 times and write 0 or 1 when an eagle or tails falls out, so you get a 256 bit (32 byte) random number, or you can use the random number generation functions that many cryptography protocols have.

Here my answer for private key more 32 byte for secp256k1, but the meaning is the same


Supersingular isogenies are a rather recent attempt at post quantum security. You will have a hard time finding an efficient and secure implementation, and even if you write one yourself, the algorithms have not yet seen that much cryptanalysis. (Although that's a subjective judgement call.)

If post quantum security wasn't a concern, you could choose from any number of non-NSA elliptic curves. However, quantum computers, if practical, can break elliptic curves (using Shor's algorithm).

NTRU is, like the other answer notes, a more practical and established alternative for post quantum cryptography. It still isn't necessarily as efficient or well studied as elliptic curves, though. As a practical matter the main implementation is under GPLv2.

For key exchange there is also the "new hope" lattice algorithm which is being field-tested by Google as a possible successor of ECC in TLS. (Personally I find this to be one of the likelier algorithms to see use, but I would not use it – alone – for anything important yet.)

For file encryption, or anything that works with a secret key, you can use existing symmetric algorithms. You may want to choose a key size of at least 256-bits, though, to account for the quantum Grover's attack. SNOW 3G in particular isn't post quantum secure for that reason – it has a 128-bit key. Other standardized general purpose ciphers like AES-256 or something on the eSTREAM portfolio (Salsa20 at least has a 256-bit key) would work fine.


Where shall we use an authenticated encryption mode?

OCB, CCM, EAX, and GCM, being modes of operation, only work with block ciphers. Some of them, like GCM, are only defined for block ciphers with a particular block size. Note that these authenticated block modes do use MACs (GCM for example is essentially CTR mode with GMAC). Other MACs like HMAC and Poly1305 work with any symmetric cipher, including stream ciphers. So for example if you wanted to use ChaCha20 or were stuck with AES in CBC mode, you could use HMAC-SHA-256 or Poly1305.

These modes all work differently, and in fact are not always even based on the same concept. The only similarity they have is that they can all be used to turn an unauthenticated symmetric cryptosystem into an authenticated one. Internally, each construct is different. GCM for example is an authenticated cipher mode of operation, HMAC is a keyed pseudorandom function, and Poly1305 is a universal hashing one-time MAC. They are quite different, but they all happen to be useful for authenticated encryption.

Although the specific modes you provided all provide effective authentication, they're not always suitable for use everywhere. They are each based on completely different concepts, and they can each be used for only specific purposes. Their only similarity is that they can all be used to authenticate a symmetric cipher. Here is a quick summary of the various modes and where you might use them:

OCB, an authenticated mode of operation for cryptographic block ciphers, is fast and lightweight, but is patented so might not be legally viable for everyone.
CCM, an authenticated mode of operation for cryptographic block ciphers, was written as a non-patented alternative to OCB for use in 802.11, but is very slow.
EAX, an authenticated mode of operation for cryptographic block ciphers, was written to address several criticisms of CCM mode, but is just as slow as it is.
GCM, an authenticated mode of operation for cryptographic block ciphers, is fast and widely supported in hardware, but can be vulnerable to side-channel attacks.
HMAC, a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret key, in ETM (Encrypt-Then-MAC) mode is easy to plug in to any cipher, but is not fast.
Poly1305, a universal hashing one-time MAC, is extremely fast and almost always a good choice. It's only recently gotten popular.

In general, you should not need to think about the specific authentication mode you use. You should be using a simple and friendly library that does all this for you, like NaCl (which I believe uses Poly1305).


It's at the authors discretion. See the footnote in the book (below). Also Wikipedia makes it clear.

:


What does ''latency'' really mean when a block cipher is partially unrolled?

When talking about a circuit (FPGA, ASIC...) implementing some encryption algorithm, the relevant measures are:

Bandwidth: how many input bytes can be processed per second.
Latency: how much time occurs between the moment an input byte (or block) is injected, and the corresponding output byte (or block) is obtained.
Circuit area, energy consumption...

AES (with 128-bit keys) is defined as using 10 successive rounds; the important point being that each round works over the output of the previous round. Thus, the ten rounds MUST be computed sequentially. However you implement it, the data block will have to go ten times through a circuit computing one round. Ten times through the same circuit, or five times through two copies of the circuit, or through ten distinct copies of the circuit: this does not matter here. The latency for an AES invocation is related to the number of rounds.

If you do a loop, with a single circuit for one round and some gates to reuse that circuit ten times, then you will have minimal total circuit area, but also lowest bandwidth, because you will have to wait for completion of the ten rounds before starting a new AES invocation. For instance, if processing one round takes one clock cycle, then you will have a latency of 10 cycles (it takes 10 cycles to get an encrypted block from the plaintext block), and a bandwidth of one block per 10 cycles. If you "unroll" the implementation with 10 copies of the "round" circuit, then latency will still be 10 cycles: when you inject one block, the corresponding output block will be available 10 cycles later. However, you can then inject one block per cycle: ten times the circuit area, but also ten times the bandwidth.

To sum up, loop unrolling and pipelining in a circuit does not change the latency, but the bandwidth.

All of the above is about doing "AES invocations", i.e. applying the AES algorithm on 16-byte blocks which are independent of each other. When encrypting a message (as a potentially very long sequence of bytes), you are using the AES through a block cipher mode of operation which can add its own constraints. For instance, if using CBC, then, by construction, you need the result of the encryption of one block before beginning the encryption of the next block (because you first XOR each block with the previous encrypted block). Therefore, even if you have a fully unrolled AES circuit with a latency of 10 cycles and a bandwidth of one block per cycle, you will not be able to encrypt more than one block every 10 cycles. Conversely, CTR mode allows for the full bandwidth of one block per cycle, because all the elementary encryptions in CTR can be done in parallel.

Here, I am not talking about the latency of the block cipher itself (AES), but the latency induced by its mode of operation.

If we go one step further and think about overall message processing: consider SSL/TLS. In SSL, data is encrypted as records where each record contains up to 16 kB of data, and has its own MAC. Upon receiving a record, an SSL implementation must first verify the MAC over the complete (decrypted) record before beginning to use the data (until the MAC is verified, the SSL implementation cannot assume that the data has not been altered). This means a much higher latency: between the time the first encrypted record byte is received and the time the corresponding plaintext byte is really available, the decryption and MAC processing of the whole record must occur.

This example shows that the notion of "latency" is flexible and occurs at many levels, so it is important to be clear about what we are talking. In the case of a block cipher like AES, the "latency" is about the minimum processing time for one block independently of other blocks. This translates to the latency for a "message" only insofar as the encryption mode and other protocol characteristics like a MAC do not add their own constraints.


How to design a deliberately weak PRNG for experimentation?

I'd suggest starting with the dieharder suite of generators, as that list covers a lot of popular generators with known weaknesses, and the application can emit bitstreams from each generator.

The most famous bad RNG (other than the xkcd comic one) is RANDU.  That's very low-hanging fruit as a warm-up exercise.

Typically these generators produce something like a 32-bit or 64-bit word, and to treat this as a bitstream from a black box you just append all the words.  This implies that the bitstream is likely to show patterns with respect to every 32nd or 64th bit; and a naive test might be confounded by simply emitting 31 bits instead of 32 (this can be perfectly sensible in hardware, but rare in software).

What I don't see in that list (or may simply fail to recognise in their abbreviated names) are LFSR and xorshift generators.  These have an upper limit on the number of zeroes they can emit in a row (commonly 32 or 64) and their output is always a fairly simple bitwise transform of bits seen recently, but at least xorshift can still pass a lot of statistical tests.

Linear congruential generators have high-frequency periodicity in their low-order bits (the least significant bit can only oscillate between 0 and 1, the next bit cycles through four states before repeating, etc.); some generators discard the low order bits so that the least-significant bit might repeat on a period of 65536.  There's a bunch of heavier mathematics I've never bothered to think about which might be interesting to you.

Any of the dieharder tests that fail dieharder's own testing obviously do have a pattern, and that'd be a good place to look.  In that sense I suppose dieharder documents your options better than I ever will.

Of those that pass all statistical tests, most are still considered insecure when you have insight into how the generator might work.  dieharder is not a cryptographic tool.


Performance consideration in XEdDSA and VXEdDSA Signature Schemes

Note the following three lines in XEdDSA:
$\newcommand{\opn}{\operatorname}$

  $r=\opn{hash}(a\parallel M\parallel Z)\bmod q$
  $R=rB$
  $h=\opn{hash}(R\parallel A\parallel M)\bmod q$

As you can see, the hash input of the third instruction depends on the hash output of the first instruction. And even worse you can't "just append" said output, it ahs to come first.

Now assume that you have a large message (like one gigabyte in size). While you could stream-process the first hash easily, you would have to buffer the full message so that you can feed it into the second hash invocation, requiring you to either a) have a stupid large statically-allocated buffer or b) significantly limit message size or c) use dynamic allocation (which is really slow).

So how can we fix this? Pre-Hashing. Assume that the "$M$" for the signing algorithm isn't actually the 1GB M, but rather the fixed-size $\opn{hash}(M)$. Now we can use a small, constant-sized buffer to store the "$M$" and we can just stream-compute $\opn{hash}(M)$, meaning we don't need unnecessarily large buffers there either. However the obvious downside of doing pre-hashing is that a collision on the hash easily translates into a forgery attack on the signature scheme (as $\opn{hash}(M)$ and $\opn{hash}(M')$ have the same hash, they are essentially the same message for the signature algorithm even though $M\neq M'$).

I said "stream-process" here multiple times, so I'll give you a quick understanding what it means. In actual implementations of hash functions you usually find the following three functions:

hash_init(context*)
hash_update(context*,byte* data)
hash_final(context*,byte* digest)

So you normally initialize some context for the hash, then you update the context with data a few times and finally extract the hash value (the digest) out of the context. Most hash functions are designed to support this style of implementation and allow context to be a compile-time-sized structure so that if you get a stream of data, you can continually call hash_update and then discard the message part's buffer (if you have no further use for it, that is). So in this case, you end up with a small context structure, a small message-part buffer as opposed to one giant full-message-buffer.


Automated testing of cipher security for import/export compliance

No.  There is no known automated method to determine whether some cipher is secure or not.  So, given some new cipher you've never heard of there's no automated way to test whether it meets your particular security requirements.

Instead, normally you would rely upon a cryptographer expert (e.g., a consultant or in-house expert) or upon standards or best practices to select a cipher that is widely believed to meet your security requirements -- then you implement the cipher, and use test vectors and other methods to test whether you have correctly implemented that cipher.  For instance, you might use one of the export-strength ciphersuites in SSL.

This answer is not intended to advise you on the export regulations of any country.  If you need to know what they are, consult a lawyer.


What is the order and cofactor of a base point?

Put simply, the order of the basepoint is the number of points the basepoint generates under repeated addition. If you have point $G$ and you repeatedly add $G$ to itself, you will eventually get the identity element $O$ (where $O + G = G$). The order of $G$ is the smallest $n$ where $nG = O$.

The cofactor is the order of the entire group (number of points on the curve) divided by the order of the subgroup generated by your basepoint. Because of Lagrange's theorm, we know that the number of elements of every subgroup divides the order of the group.

  Is it possible to deduct the order and cofactor, given just the basepoint. What about the other way around from order and cofactor to basepoint?

Not easily unless you know the order of the group.

There are algorithms for efficiently computing the order of an elliptic curve. After you know the order of the curve, you can factor it to find the size of its subgroups. Using the factors, you can test each one and find the order of any point.


Where can I find a sample of data with a known entropy to see how well NIST SP 800-90B does on it?

The question really asks for a sample of data from a source with a known entropy rate.

I suggest starting with the simplest: sources with zero entropy rate. Examples from which the first megabytes can be readily obtained:

a source producing only bytes at zero.
a source cycling over the 256 bytes incrementally.
a source consisting of the SHA-256 hashes of bytestrings of increasing length, in lexicographic order.
/dev/random or /dev/urandom modified to replace the input of their built-in PRNG with zeroes.
a source producing the bytes of $\pi$ (e.g. using Bellard's method).

NIST SP 800-90B tests won't help distinguish the last three from a source with some entropy. That illustrates these (or similar) tests can't reliably detect even a total lack of entropy, unless some hypothesis is made on the nature of the source.

We can use a lightly conditioned source. It's easy to make one from a microphone in front of something emitting noise (a fan will do), sampled by an ADC (sound input of a PC will do), and the bytes from some number of samples fed thru some light conditioning (like: group $n$ 16-bit samples and output the sum modulo 256 of the $2n$ bytes). That's a better fit for what NIST SP 800-90 is designed to work on. It'll be interesting to see how the gain of the microphone preamplifier, the position of the microphone, and parameter $n$, all influence the results. This source doesn't have a known entropy rate, though.

We can manufacture a source with biased but (presumably) independent bytes and a known biased distribution leading to (at most) a certainly known entropy. One way is to take /dev/urandom (or any source which output can't be discerned from that of a perfect true random source), group bytes by two to form an integer in $[0\ldots2^{16})$, and output the high-order byte of that unless the integer is less than $k$, for some parameter $k\in[0\ldots2^8]$. This leads to a source with byte zero having probability $(2^8-k)/(2^{16}-k)$, and the others $2^8/(2^{16}-k)$. Entropy in bit/byte is easy to compute as a function of $k$, and goes (for $k$ up to $100$):


Tactics available to help prove security of a new system?

Prove resistance to differential cryptanalysis.

For example, this presentation: Provable security against Impossible Differential Cryptanalysis. Or this paper:  ProvableSecurity Against a Differential Attack (1995)
Prove resistance to linear cryptanalysis.

For example: On Measuring Resistance to Linear Cryptanalysis
Run a bunch of statical tests against the cipher.

For example: Cryptographic Randomness Testing of Block Ciphers and Hash Functions


In a lattice, how can one define a good basis and a bad basis?

A good basis are the set of "almost" orthogonal set of vectors which have small norms. They allow us to solve certain variants of closest vector problem $\mathsf{CVP}$ very efficiently (for example, use LLL). Usually, the private keys are "good" basis.

A bad basis are those basis which are in certain sense hardest instance to solve: if you solve any problem in the worst basis setting, you can solve the problem in almost all basis defining the same lattice. For very obvious reasons, bad basis are used as the public key.

If you want more concrete understanding, I refer you to read Miccianio's work Improving lattice based cryptosystems using the hermite normal form which first proposed HNF variant of basis to be used as the public key.


Is the Discrete logarithm problem suitable for this pairing scheme?

First of all, let us simplify the equation by replacing things that the attacker can compute with known constants.  We come up with:

$$a \cdot b^x = y$$

where the attacker knows $a$ (which is $e(g,h)^k$) and $b$ (which is $e(g, h)$, which he can compute, as he knows $g, h$), and the attacker solves for $x, y$.

If it is sufficient for an attacker to find a solution, he can do that easily; he can select a random $x$, and solve it for $y$; there's a solution.

If he needs to find "the correct" solution (that is, the one possible $x, y$ pair that satisfies additional criteria), he doesn't have enough information to pick out which one it is.  He might be able to if he knows what that additional criteria is; it would depend on what that looks like.


Somewhat Homomorphic Encryption versus Fully Homomorphic Encryption?

PHE (partially homomorphic encryption) schemes are in general more efficient than SHE and FHE, mainly because they are homomorphic w.r.t to only one type of operation: addition or multiplication.

SHE is more general than PHE in the sense that it supports homomorphic operations with additions and multiplications. The drawback is that you can perform only a limited number hom. operations.

To answer your first question, a SHE scheme is also a PHE. This implies that PHE's are at least as efficient as SHE's.

FHE allows you to do an unbounded number of hom. operations by bootstrapping. This step can only be done (currently) by evaluating the decryption circuit inside a SHE scheme.

AFAIK, all plaintext / ciphertext operations are done within a known modulus. The only unknown thing should be the secret key. See a construction example here: DGHV Scheme.


Would it matter if my miner was hashing random vs incremental values?

For a good hash function, like Skein, diversity of inputs has no impact on diversity of outputs. So, if you have no information about the space of possible pre-images (e.g., it is not a human generated password, it is a completely random input from your prospective), then the expected number of attempts before retrieving the pre-image is the same in either case. Should also be the same number of attempts to find an input with a specific hamming-weight from the input.

As you note, however, there are benefits to using the counter. You can easily save state. You know you will never see the same input. If you are generating random 64-bit values, the odds of seeing a colliding input is actually not as small as you would think. You would expect to see a collision after $2^{32}$ inputs.


Is this really the correct way to do an IND-CPA test?

That sounds like an overly succinct description of the 'Find then Guess' (FTG) notion of security, described in the paper "A Concrete Security Treatment of Symmetric Enryption".

And you are correct, there is something the test is missing: the two 'challenge' plaintexts must be the same length ($|m_0| = |m_1|$).  Also, the description is so succinct I can't tell whether they meant to give this impression, but it sounds like a 'non-adaptive' approach to FTG-CPA, in that the Adversary only has access to the encryption oracle prior to getting the challenge.  In the 'adaptive' FTG-CPA (the version described in the linked paper), the Adversary continues to be able to query the encryption oracle after receiving the challenge (and prior to making its guess).

By the way, the FTG notion is only one variant of IND-CPA.  There is also the Left Or Right (LOR) notion, and the Real OR Random (ROR) notions.  LOR and ROR are somewhat stronger than FTG, in that there is a tight reduction from a LOR or ROR advantage-bound to a FTG advantage-bound, but the reduction is not as tight going the other way around.  So if you prove in the FTG game that any opponent has at most an advantage of $\epsilon$, you can only say that any opponent in the LOR game has an advantage of at most $q_e\epsilon$, where $q_e$ is the number of queries made to the encryption oracle (so opponents might have much larger advantage in the LOR game if there were a lot of queries).


What is the quantum-resistant signature scheme with the smallest signature + pubkey?

Choose some 128-bit hash function, such as RIPEMD-128, and a way of randomizing it, such as this.

The private key is either 60 uniformly random 128-bit strings s00,s01,...,s58,s59

and a uniformly random short salt or a seed to regenerate those. $\:$ For each i in

{00,01,...,58,59}, vi is the result of hashing si 19 times. $\:$ The public key is the

result of randomized-hashing v00 || v01 || ... || v58 || v59 with that salt.

To sign a message, the signer chooses a longer salt uniformly at random, computes the base-20 representation of the randomized hash of the message with the longer salt, and outputs

[[the two salts] and [for each j in {00,01,...,28,29}, the result of hashing s[2*j]

[19 minus the j-th digit of the base-20 representation] times and the result of

hashing s[(2*j)+1] [the j-th digit of the base-20 representation] times].

To verify a signature, the verifier computes the base-20 representation of the randomized-hash

of the message with the longer salt, [for each j in {00,01,...,28,29}, lets v[2*j] and

v[(2*j)+1] be the result of hashing the corresponding 128-bit parts of the signature [the j-th

digit of the base-20 representation] and [19 minus the j-th digit of the base-20 representation]

times respectively], and checks that the result of randomized-hashing

v00 || v01 || ... || v58 || v59 with the shorter salt is the public key.

If the length of the salts are fixed or can be efficiently computed from the sum of their lengths, then

the length of $\; signature \hspace{.04 in} || \hspace{.04 in} public\text{_}key \;$ will be $\;\;$ 7808 bits + the sum of the lengths of the salts.


Fair exchange protocols aren't new by any means, but there is a lack of layman-friendly material out there, unfortunately. I think the high prevalence of theoretical cryptography in fair exchange protocols may be partially responsible for that.

At any rate, here is the basic idea behind a fair exchange protocol. Suppose you have two parties, Alice and Bob, who wish to trade (cryptographic) "items" somehow. However, you run into a problem: suppose Alice sends her item to Bob, but Bob then refuses to send his item to Alice. In that case, it is not a fair exchange: Bob got Alice's item, but Alice got nothing in return, the poor thing.

Fair exchange protocols seek to ensure that scenario never happens---either they both get each other's "item" or they both get nothing. If the "item" being exchanged fits certain criteria, then fair exchange protocols can be improved upon to have other nice properties, like no longer requiring a trusted third party or being able to detect a dishonest third party.

There are other questions on this site which go into more details about specific fair exchange situations, like

Is there a way to do fair exchange between two parties who don't trust each other?
Alice trusts Bob only when Bob trusts Alice

which both link to useful papers. Further, there are some really nice results in the Google results for fair exchange cryptography. Some of them are indeed quite technical in nature, but usually you can read the abstract and maybe the introduction without getting too involved in the mathematical specifics of the protocol in question. One link in particular stands out as being a layman-friendly explanation. The other links should give you some idea of what "items" are traded, often digital signatures. Fair Exchange in E-commerce gives a really nice overview of the field, especially in the first few pages, and also has friendly terminology definitions on page "11" (page 3 of the pdf), defining terms such as "optimistic" fair exchange schemes (which only require a trusted third party to intervene in the event of a cheating player).


I'm not an expert yet, but this is how I remember it.

DPA or differential power analysis is a side-channel attack on hardware implementations of cryptographic algorithm.

All electronic circuits consume different amount of power depending on the activity of individual transistors. For example, more transistors may switch when adding the hexadecimal bytes A7 to B9 than when adding 01 to 00.

When attacker connects something like AES protected memory card to a machine that allows him to gather very precise information about it's power usage he can, after having enough measurements, statistically guess some things that he was not supposed to know and brake chosen-plaintext attack security. That way (given enough time) attacker will guess the key faster then using exhaustive search (brute force algorithm)