I've read in a pdf written by Ayantika Chatterjee and Khin Mi Mi Aung whose title is "Fully Homomorphic Encryption in Real World Applications" that it is possible to implement a bubble sort algorithm using certain Fully homomorphic libraries to be able to compare and sort messages while they are encrypted, here is a snippet of the pdf:  The FHS circuit depends on two main operations: subtraction operation and decision making based on the subtraction result. Fully Homomorphic subtraction, which is implemented by performing homomorphic addition of one ciphertext with 2’s complement of another ciphertext. For two plaintext numbers a and b, subtraction can be computed as: a − b = a + 2’s complement of b   Now a homomorphic subtraction of a' and b' which are the encryptions of a and b respectively is computed using the homomorphic addition as follows: a' − b' = a' + Encrypt(2’s complement of b) The 2’s complement of b in the encrypted domain is obtained as follows: Encrypt((2's complement of b), pk) = b' ⊕ Encrypt(11 . . . 1, pk) ⊕ Encrypt(1, pk)   They also say that:  The MSB (most significant bit) of the substraction output is further fed to the decision making module as a selection line. The following equations represent how the swap operation takes place between two elements A[i] and A[i + 1] depending on MSB (represented here as bt): temp = bt ∗ A[i] + (1 − bt) ∗ A[i + 1] A[i + 1] = (1 − bt) ∗ A[i] + bt ∗ A[i + 1] A[i] = temp   So they make very clear that its the MSB of the substraction that determines which encrypted message is the biggest/smallest.  So my question is how were they able to determine that is only the MSB which determines the answer because i know that if we have the number 2 which is smaller than the number 3 after encryption we don't have a guarantee that Enc(2) is smaller than Enc(3)
88195
I am actually trying to study homomorphic encryption (on lattices) but I'm facing a problem. Every paper that I have read so far talk about writing the function to evaluate on ciphertexts as a circuit, either boolean or arithmetic according to our scheme if I understood this part well. My problem is that I couldn't find explicit documentation on how to turn a function to a circuit.   Especially, in circuits, we can't have loops or conditions and I would have liked to apply my FHE scheme to the weights of a neural network, but I'm kinda stuck on how to represent the activation function (I think I would use the sigmoid, that can be represented with its Taylor expansion) and simple gradient descent.  Does anyone have a clue or a good paper to help me understand how to write such functions to circuits?
81249
Ok, so PHP isn't the best language to be dealing with arbitrarily large integers in, considering that it only natively supports 32-bit signed integers. What I'm trying to do though is create a class that could represent an arbitrarily large binary number and be able to perform simple arithmetic operations on two of them (add/subtract/multiply/divide).  My target is dealing with 128-bit integers.  There's a couple of approaches I'm looking at, and problems I see with them. Any input or commentary on what you would choose and how you might go about it would be greatly appreciated.  Approach #1: Create a 128-bit integer class that stores its integer internally as four 32-bit integers. The only problem with this approach is that I'm not sure how to go about handling overflow/underflow issues when manipulating individual chunks of the two operands.  Approach #2: Use the bcmath extension, as this looks like something it was designed to tackle. My only worry in taking this approach is the scale setting of the bcmath extension, because there can't be any rounding errors in my 128-bit integers; they must be precise. I'm also worried about being able to eventually convert the result of the bcmath functions into a binary string (which I'll later need to shove into some mcrypt encryption functions).  Approach #3: Store the numbers as binary strings (probably LSB first). Theoretically I should be able to store integers of any arbitrary size this way. All I would have to do is write the four basic arithmetic functions to perform add/sub/mult/div on two binary strings and produce a binary string result. This is exactly the format I need to hand over to mcrypt as well, so that's an added plus. This is the approach I think has the most promise at the moment, but the one sticking point I've got is that PHP doesn't offer me any way to manipulate the individual bits (that I know of). I believe I'd have to break it up into byte-sized chunks (no pun intended), at which point my questions about handling overflow/underflow from Approach #1 apply.
68164
Let $H:\{0,1\}^*\to\{0,1\}^n$ be a cryptographic hash function as a black-box, and suppose we have unlimited space.  As I understand, finding $x$ such that $H(x)=0$ (if such exists) would require a preimage attack, and avg. time $O(2^n)$ (linear in the size of the output). On the other hand, finding $x\neq y$ such that $H(x)\oplus H(y)=0$ could use the birthday attack, and therefore avg. time $O(2^{n/2})$.  My question is, if something better can be said for finding 3 (or more) distinct values $x,y,z$ such that $H(x)\oplus H(y)\oplus H(z)=0$. It seems clear that this could be done using less samples of $H$, but it's not clear to me if the time complexity could be improved.
1319
I am creating a program in C language with DES (Data Encryption Standard) functionality, but don't know how to apply the initial permutation.   Is it achieved by swapping the values? If "yes", then how is the index of the original message created?
28259
In this article , specifically in the section 4.1 of the initialization phase,the following cryptographic hash functions have been chosen: \begin{align} h_1&amp;:   \mathbb G\to\mathbb Z_q^*\\ h_2&amp;:  \{0,1\}^*\times\{0,1\}^*\times\mathbb G\to\mathbb Z_q^*\\ h_3&amp;:  \{0,1\}^*\to\mathbb Z_q^* \end{align} where G is an additive group with order q. Can anyone explain to me what's the meaning of their notations and how to use them for example in SHA algortihm? Or maybe give me a simple example with real inputs?
13511
I was reading upon Biham and Shamir's paper and a fact has been presented over there: if $ P_1 = \bar P_2$ and I choose a key $K_1 = \bar K_2$ then in that case  $$T_1 = DES(P_1, K_1)$$ $$T_2 = DES(P_2, K_2)$$  then $T_1 = \bar T_2$ . Does this hold for only that particular combination of S-box or it will be same for any S-box combination. I mean if I change S-boxes randomly then will it still be same?  Also there is one more thing mentioned on the paper, but I am not able to get it. PFB the image.   Here output $T$ will be $\bar T_2$ only if I $P_2$ was inserted with $\bar K$. And clearly I am entering $P_1$ (which is $\bar P_2$) hence the output can never be $T_2$. Please correct.
67138
I know simple formulas like  $$E(x) = (ax+b)\pmod n$$  where $E(x)$ stands for encryption,  $$D(y)= z(y-b)\pmod n$$  where $D(y)$ stands for decryption,  and   $$ax==1\pmod n$$  Assuming someone gives us an encrypted string, is there a way to find $a$ and $b$ from that string? If not, what informations we should have to find $a$ and $b$ keywords from the encrypted string? Is there a way to find a and b keywords in an affine cipher when only ciphertext but no plaintext is known?    Note that this is not a duplicate of . In that other question, the user knows beginning of both encrypted and decrypted message.
89837
There is a lot of confusion between hash- and encryption algorithms; I would like to understand:   When do we use a hash algorithm and when do we use an encryption algorithm (a cipher)? How difficult it is to reverse hash- and encryption algorithms? From the theoretical/mathematical perspective, what differentiates a hash- and encryption algorithm?
75316
I am considering attacks on Two-Key Triple-DES Encryption assuming $2^{32}$ known plaintext/ciphertext pairs (that's a mere 32 of ciphertext) by the method devised by Paul C. van Oorschot and Michael J. Wiener:  (in ), or another published method not requiring significantly more DES computations. As a synthetic information for decision makers, I am looking for an independent estimate of how much time this is expected to require, assuming all the RAM ever built by mankind to that day (of April 2012) was put to full use. Note: I'm purposely not asking when the attack could become feasible using all the RAM ever built by mankind, because estimates on the amount of RAM mankind will build, and when, are less falsifiable. Update: I am not considering cost; neither of RAM, power, logic including DES engines (as long as the number of DES operations remains within $2^{90}$). I am willing to assume that the amount of RAM used, and its effective speed, are the only factors to account for in determining the expected duration of the attack. This is similar to the hypothesis made by the authors of the linked paper, that their attack is limited by the amount (or cost) of RAM used, with all other factors of secondary importance. Update: sadly, nobody dared answer the question and the bounty period is over. Thus  is a first order answer to criticize.
31547
I was given a cryptography question during an interview the other day.   Imagine you are given an efficient algorithm which for a given RSA public key (n,e) is able to decrypt 1% of the messages encrypted with that key.   1% means that the algorithm will deterministically decrypt 1% of all possible ciphertexts on the first call, and will never decrypt the other 99% of all possible ciphertexts with any number of invocations.   Figure out an algorithm that uses this one and can decrypt any message. Any ideas?
45047
I understand what's going on in higher level. But i don't understand what's really going on in page 3 and 4 of  slide.   Specifically,   How S0 and S1 is used? What goes in what goes out? How exactly  key bits determine which s-box is to be used at each position? Position refers to what? is the function "f" in page 4 exactly the same SP network in page 3?  why split plain text into left L and right R? why XOR L with R after applying "f"?  why rotate after  applying last "f"? why XOR is used? why not some other bitwise operation?    slides for reference
41201
There seems to be sources like , this , and some  that discuss elliptic curves in general and how they're used.  But what I'd like to know is why these particular curves are so important in cryptography as opposed to, let's say, any other polynomial degree $\gt$ 2 which you can then mod over some group.  It seems like once a modulus is applied then other function types should be acceptable as well.  It seems even less intuitive when just looking at the bubble vs curve as here:    Since there are other curves (let's say anything from a sin wave to the $x^3 + x$ or even just some unusually shaped contour) that could do the job.  It seems like they would provide much more surface area to get a larger space in $\mathbb{Z}_p$ or really just more possible combinations of connecting lines from some arbitrary $P$ and $Q$ to get $R$ as opposed to something as restrictive (on the graph) as beginning from some bubble (which would seem to unnecessarily reduce the possible combinations) and then use a modulus to implement the discrete logarithm problem.  Sorry if this seems a little naive of a question, I'm trying to write an implementation right now and just to understand it fully even if that means asking something that is taken for granted.  Perhaps just walking through a simple example (most of the ones I've searched are anything but), just a few sentences, would be rather helpful, from "A wants to talk to B" all the way up to "now E can't listen in between A and B".  EDIT:  So it seems like this is the version of elliptic curves over a finite field:    Yes that looks pretty random.  But I'm still not really seeing why they are the only equations that have cryptographic significance.  It's difficult to imagine that if you simply took some other higher degree equation and applied modulus (to place within a group), then it seems like it would make sense that you'd get something that's also comparatively random.
84512
If I have the plain text, the ciphertext and the key for an AES-128 CBC operation, can I determine the IV, even if I don't know the padding (assuming the padding follows one of the more common formats)?  I believe it should be possible since my understanding is that the IV is only used as an initial XOR of the plain text in encryption, and should, therefore, be able to be available like this:  AESDecrypt(key, ciphertext) =&gt; (PlainText XOR IV); IV = ((Plaintext XOR IV) XOR (Plaintext))   Is this correct?
44823
I'm going to provide “proof” why a hash function can be reversed, and I hope you can tell my why I'm wrong  So, a hash function can be implemented as a series of logic gates. All logic gates can be implemented using only NOT and OR gates. (I'm fairly sure about both of these, but please correct me if I'm wrong.)  Therefore, a hash function can be implemented as a series of NOT and OR gates.  A NOT gate can be easily reversed by going through another NOT gate.  An OR gate cannot be reversed, since it fundamentally losses information. However, a possible input can be derived from any given output.  Therefore, I should be able to construct a possible input given an output from a set of logic gates, including from a hash function.  What have I gotten wrong here?
45067
I'm trying to understand the working of RSA algorithm. I am getting confused in the decryption part. I'm assuming   $$n = pq$$ $$m = \phi(n) = (p - 1)(q - 1)$$  E is the encryption key $\gcd(\phi(n), E) = 1$  D is the decryption key, and  $DE = 1 \mod \phi(n)$  $x$ is the plain text  Encryption works as ($y = x^E \mod n$) and decryption works as ($x = y^D \mod n$)  The explanation for why the decryption works is that since $DE = 1 + k\phi(n)$,  $$y^D = x^{ED} = x^{1 + k \phi(n)} = x(x^{\phi(n)})^k = x \mod n$$  The reason why last expression works is $x^{\phi(n)} =  1 \mod n$ ? According to Eulers theorem this is true only if $x \text{ and }\phi(n)$ are coprimes. But $x$ is only restricted to be  $0 &lt; x &lt; n$  and $\phi(n) &lt; n$. So $x$ should be chosen to be coprime with $\phi(n)$?  Help me clear out the confusion!
70480
Edit  Does the state register (the LFSR) always have to remain with 16 bits (I'm assuming yes).  If so, are we shifting the register right by one (lfsr&gt;&gt;1) and inserting the output bit onto the left-most bit (lfsr&gt;&gt;1 | bit&lt;&lt;15) which allows us to wraparound within the same 16-bit address space.  So with this in mind, how does one generate the continuous keystream given:  seed: 1100101001110101  taps: 3, 12, 14, 15    Assuming you are given the following information:  Seed: 1100101001110101  Key Fragment: 000100011110101100001101101111101  And the following ciphertext/encrypted stream: 10101011000000010010110011001100101000010101010101010111101111110111010000010011  I am seemingly unable to decrypt the entire text into some ASCII values (UTF-8 decoded). I initially wrote a Berlekamp-Massey implementation and an  to grab the tap positions of the above key fragment, which returned the following polynomial:  $$x^{15} + x^{14}+x^{12}+x^{3}+1$$  Fibonacci LFSR implemented in Rust:  fn next(&amp;mut self) -&gt; Option&lt;(u16, u16)&gt; {     self.bit = ((self.lfsr &gt;&gt; self.taps[0]) ^ (self.lfsr &gt;&gt; self.taps[1]) ^                 (self.lfsr &gt;&gt; self.taps[2]) ^ (self.lfsr &gt;&gt; self.taps[3])) &amp; 1;      self.lfsr = (self.lfsr &gt;&gt; 1) | (self.bit &lt;&lt; 15);      if self.lfsr != self.seed {         Some((self.bit, self.lfsr))     } else {         None     } }    The key fragment never appears in the generated key stream, indicating something probably went wrong. The decrypted cipher doesn't map to ASCII values, just cryptic UTF-8 symbols.   The Berlekamp-Massey implementation is based off of the following whitepaper -   And the full code can be found here -
2620
I have two encryption schemes $\Pi_0, \Pi_1$, at least one of them is IND-CPA secure but I don't know which one. The task is to construct a scheme $\Pi$ that is guaranteed to be CPA secure and to provide a proof for this.  Despite reading ,  I still don't understand the best way to construct the scheme and how to fully prove its security.  Any ideas or hints into the right direction are appreciated!