2
$\begingroup$

I want a cryptosystem with the following four functions:

declare function encrypt(text: string, key: CryptoKey): ArrayBuffer;
declare function decrypt(ciphertext: ArrayBuffer, key: CryptoKey): string;
declare function concat(ciphertext1: ArrayBuffer, ciphertext2: ArrayBuffer): ArrayBuffer;
declare function slice(ciphertext: ArrayBuffer, start: number, end?: number): ArrayBuffer;

These functions work such that for any two strings (text1 and text2) and key the following expression is true:

decrypt(concat(encrypt(text1, key), encrypt(text2, key)), key) === text1 || text2;

And for any string (text), index into the string (i), and key, the following is true:

const ciphertext = encrypt(text, key);
decrypt(concat(slice(ciphertext, 0, i), slice(ciphertext, i)), key) === text; 

Essentially, I want to arbitrarily slice and concatenate the strings represented by ciphertexts without decrypting anything. Is this kind of cryptosystem possible? Can I use homomorphic encryption to accomplish this? Are there any systems out in the wild which do something like this? I assume the length of the original text must be inferable without the key to accomplish this.

EDIT: To avoid certain trivial solutions brought up in this answer, which simply concatenate/slice ciphertexts trivially using delimiters/tokens, I would like the following to be true as well:

const ciphertext1 = encrypt(text1, key);
const ciphertext2 = encrypt(text2, key);
concat(ciphertext1, ciphertext2) === encrypt(text1 || text2, key);

const ciphertext = encrypt(text, key);
slice(ciphertext, i, j) === encrypt(text.slice(i, j), key));

// I’m using typescript as pseudocode but assuming equivalent ArrayBuffers are tripe-equals equivalent here, even though they aren’t
$\endgroup$
  • 1
    $\begingroup$ I think the complexity of achieving this would depend on your encryption algorithm. I.e. if you would use the simple caesar-cipher it wouldn't be a problem at all, since it's a monoalphabetic substitution cipher. A problem I could think of is a polyalphabetic substitution cipher (for example the Vigenère cipher), because you couldn't just slice messages up at any point and concatenate them again, that's because of the length of the key. $\endgroup$ – AleksanderRas Oct 10 '19 at 18:21
  • 1
    $\begingroup$ You can do it with FHE. I think, however, you don't need it if you know the position to slice. What is your actual problem? $\endgroup$ – kelalaka Oct 10 '19 at 18:24
  • $\begingroup$ @kelalaka I have a closed-source OT/CRDT library where documents (simple DOMstrings) can be edited collaboratively by passing around/ingesting patches. I’m brainstorming ways to implement an end-to-end encryption scheme to protect both the contents of documents and patches. My problem is that encrypting both the document and patches individually means that each client must have a recent document and work its way forward. If I had the above cryptosystem, I could continually update the document on the server and send down the latest snapshot to any client without knowing its contents. $\endgroup$ – brainkim Oct 10 '19 at 18:34
  • $\begingroup$ Solutions which either concatenate cyphertexts with a delimiter or add indices to the ciphertext are suboptimal; in that case, I’d rather just stick to my current encryption scheme because eventually the size of the ciphertext would far exceed the size of the underlying text. $\endgroup$ – brainkim Oct 10 '19 at 18:37
  • 1
    $\begingroup$ I don't think readers will be confused with the current notation, but if you think it would be better to use concat(a, b) to indicate concatenation then go right ahead - it's your question and it should be formatted the way you want it to be, all other things being equal. $\endgroup$ – Ella Rose Oct 10 '19 at 21:20
2
$\begingroup$

Unless you add further restrictions, it is possible to achieve what you are asking for, using a totally trivial construction. For example, the encrypt algorithm can output ciphertexts of the form "normal ciphertext: $c$". The concat algorithm can output ciphertexts of the form "concatenation of $c_1$ and $c_2$". To be clear, I am proposing that ciphertexts in this scheme literally start with the strings "normal ciphertext", and "concatenation of", etc. The decrypt algorithm can just parse and do the right thing for ciphertext of these different forms.

I'm sure this is not what you want. So if you don't want to trivialize the question, then you will need to add some other kind of requirement. For example:

  • The output of $\textsf{concat}(\textsf{Enc}_k(m_1), \textsf{Enc}_k(m_2))$ is indistinguishable from the output of $\textsf{Enc}_k(m_1 \| m_2)$.

  • Even with knowledge of $k$, the output of $\textsf{slice}(\textsf{Enc}_k(m), i, j)$ doesn't leak any information about $m$[$:i$] or $m$[$j:$].

There could be several reasonable ways to define away the trivial solution.

I'll also point out that this property is clearly incompatible with CCA security. The best you can hope for is CPA security.

CTR-mode encryption supports slicing, at least at the block level. If $(iv, c_1, c_2, \ldots, c_n)$ is a CTR-mode encryption of $m_1, \ldots, m_n$, then $(iv+i-1, c_i, \ldots, c_j)$ is a CTR-mode encryption of $m_i, \ldots, m_j$.

Most (all?) block cipher modes support truncation at the end, but not necessarily arbitrary slicing.

The best approach for allowing concatenation that I can think of is to just independently encrypt each block. I can't think of any approach that preserves the the additive ciphertext expansion of a typical block cipher mode.

$\endgroup$
  • $\begingroup$ Given that were talking CPA here, wouldn't simply individually encrypting bit by bit (or character by character of "strings" refers to non-binary strings) allow slicing/concatenation, while actually achieving indistinguishability from fresh ciphertexts and perfectly hiding the slice? $\endgroup$ – Maeher Oct 10 '19 at 19:45
  • $\begingroup$ Yes, that is what I mention in the last paragraph. $\endgroup$ – Mikero Oct 10 '19 at 19:52
  • $\begingroup$ Indeed. I somehow missed that part. $\endgroup$ – Maeher Oct 11 '19 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.