Is there a public-key, "deal-less", all-or-nothing, "secret-length message" cryptosystem or some easy way to derive it?

donaastor

9/25/23, 6:40 PM

I want to make an ecryption algorithm that is secure in, well, really many ways, which is hard I see, so I came up with some ideas of how to implement it using some primitives that I know and I actually discovered some online that resemble it, but I thought it's time to consult the forum about it.

Firstly I should define my goal. All participants have their private and public keys. Communication has to be possible without any pre-made deal (no secret, symmetric keys). This is not negligible because of another property... Basically, I want participants who find messages directed to them, randomly, unexpectedly, to still be able to decrypt them while preserving all security levels.

Let's say we have S, the sender, and R, the receiver. When I say someone "can't", I mean that they still may ask questions and guess in way and in amount as described for IND-CCA2. I am differentiating information about the ends of plain- or cipher-text, from any other information about them (that being contents, and which I will refer to as info about plaintext). Knowing contents is stronger in sense that I would allow anyone to deduce at least something about the ends, if they know at least something about the content. I would like these properties:

Only R can distinguish the ciphertext from random noise.
Only S can generate a correct ciphertext.
Only R can decrypt.
Only S can encrypt.
Only R and S can distinguish the ciphertext from random noise, given the plaintext.
Given a ciphertext with corrupt bits in the middle of some stream of random data, nobody can learn any info about the ends of the ciphertext, or any info about the plaintext.
Given a ciphertext with corrupt bits at the beginning or the ending of some stream of random data, nobody can learn any info about the other end of the ciphertext, or any info about the plaintext.
Given a ciphertext with corrupt bits, knowing both of its ends, nobody can learn any info about the plaintext.
Given a correct ciphertext at the beginning of some stream of random data, only R can (and that efficiently, in linear time) find the end of the ciphertext, and no one else can do it.
The difference between lengths of ciphertext and plaintext is constant.

It is ok if you can tell me about some cryptosystem that provides some and maybe not all of these properties. Maybe I can figure out how to finish it. And it is ok to add your own interpretation of the difference of infos about the ends and plaintext.

I would need some time to translate to English my files with my current ideas of algorithms, but there is barely anything. I noticed OAEP++ and saw some similarities to my ideas, but that's all. I am constantly failing to hold so many details in my head...

Here is my attempt.

0 + 0

public-key

oaep

indistinguishability

aont

SAI Peregrinus

9/25/23, 11:25 PM

Requirements 2, 4, and the indistinguishability from random make this rather complex. I'd probably end up with something using Elligator for key hiding, Ristretto for key exchange & signature groups, and a sign-then-encrypt system where the plaintext is signed, then encrypted with an Authenticated Hedged Encryption with Associated Data scheme with the signing public key and a hash of the ephemeral secret key in the associated data. Pad with PADMÉ. That'd allow R to reject messages from anyone other than S, provide a random-looking message, etc. Very hard to get right though.

kodlu

9/26/23, 11:05 AM

What is the difference between 2 and 4? Aren't they equivalent?

poncho

9/26/23, 11:46 AM

If requirement 9 means 'linear time in the length of the plaintext' (which can be considerably shorter than the ciphertext), then there is a contradiction between that and 8. For 9 to be true, the decryptor cannot examine the entire ciphertext to determine the plaintext length; 8 asserts that modifying some ciphertext bits prevents anyone from learning anything about the plaintext (including the length); what if the bits that are modified aren't those examined when determining the plaintext length?

donaastor

9/26/23, 12:17 PM

@SAIPeregrinus Thank you a lot! That's a lot of insight that I will gladly take time to look at and come back to my task and this post readier.

donaastor

9/26/23, 12:18 PM

@kodlu Not really. In theory, one could be able to produce a ciphertext starting from something that is not plaintext and still be convinced that what he created is a proper ciphertext, but on the other hand be unable to produce ciphertext, starting from plaintext. So, 4 implies 2, but I am very unsure that 2 implies 4.

donaastor

9/26/23, 12:21 PM

@poncho You are right, my bad. I had a hard time writing last 3 properties, because I couldn't clearly see how to split info about the length apart from all other infos (like contents of the message). You noticed a contradiction in my first attempt, I will try to fix it now.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is there a public-key, "deal-less", all-or-nothing, "secret-length message" cryptosystem or some easy way to derive it?

TH: มีระบบการเข้ารหัสลับแบบ "deal-less", all-or-nothing, "secret-long message" หรือวิธีง่ายๆ ในการได้มาหรือไม่?

RO: Există un criptosistem cu cheie publică, „fără acord”, totul sau nimic, „mesaj de lungime secretă” sau vreo modalitate ușoară de a-l deriva?

RU: Существует ли криптосистема с открытым ключом, «без сделки», «все или ничего», «секретная длина сообщения» или какой-то простой способ ее получить?

VI: Có hệ thống mật mã khóa công khai, "không thỏa thuận", tất cả hoặc không có gì, "tin nhắn có độ dài bí mật" hoặc một số cách dễ dàng để lấy được nó không?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.