Weird crypto concepts

At Teserakt, we solve real security engineering problems by leveraging cryptography, aiming for the best choices in terms of security, performance, and ease of integration. Being part of the community for many years, we actively follow the theoretical and applied research in cryptography and security, in order to build innovative yet robust solutions to modern IoT systems.

If you know a bit about cryptography, you sure know basic concepts such as encryption, hashing, as well as notions such as preimage resistance, forward secrecy, semantic security, zero-knowledge proof, and others that we routinely encounter in modern applications. However, cryptography is a rich field with a broad unexplored territory, with many notions that haven’t yet made it to popular applications. In this post we’d like to give an overview of some of these notions, and provide leaks to further readings, would you be interested in learning more about them.

AES-GCM-SIV and SIV-AES

AES-GCM-SIV is variant of AES-GCM where the nonce used for encryption is determined from the tag computed by authenticating the plaintext (and any associated data). AES-GCM-SIV’s MAC, called POLYVAL, is slightly different from GCM’s GMAC. The benefit of AES-GCM-SIV compared to AES-GCM is that it remains secure if a same nonce is reused—a.k.a. misuse resistance.

SIV-AES is a different thing from AES-GCM-SIV.

For some reason, AES in SIV mode is not called AES-SIV, but goes by the official name of Synthetic Initialization Vector (SIV) Authenticated Encryption Using the Advanced Encryption Standard (AES), abbreviated to SIV-AES—having AES-CCM, AES-GCM, AES-GCM-SIV, and AES-SIV wasn’t confusing enough.

Like AES-GCM-SIV, the main reason for using AES-SIV is to avoid the hazard of repeated nonces. Unlike AES-GCM-SIV, SIV-AES does not use a MAC based on binary polynomial multiplication, but instead the AES-based CMAC, a variant of CBC-MAC. This makes SIV-AES simpler than AES-GCM-SIV, but also slightly less fast.

More:
https://tools.ietf.org/html/rfc5297
https://tools.ietf.org/html/rfc8452

Catalytic space computation

A form of computation where the memory required does not need to be completely empty, but may contain information that is restored after the computation is completed. This has been leveraged in proofs of catalytic space, for example proposed as a proof-of-resource for blockchain protocols.

More:
https://iuuk.mff.cuni.cz/~koucky/papers/catalytic.pdf
https://eprint.iacr.org/2018/194

Dolev–Yao model

Cryptographers sometimes pedantically refer to the “Dolev–Yao model”‘ when they just mean the active attacker adversarial model, wherein the attacker can eavesdrop, intercept, and modify data transmitted. But the Dolev–Yao model is much more than this. It is the first formal model for cryptographic protocols, and a symbolic framework to describe an analyze their security.

More:
https://www.cse.huji.ac.il/~dolev/pubs/dolev-yao-ieee-01056650.pdf
https://cseweb.ucsd.edu/classes/sp05/cse208/lec-dolevyao.html

Indelibility

The property of a timed transaction record (such as a blockchain transaction) that cannot be back-dated. In the context of IoT transactions, this can be an important property in situations with extreme network latencies and unreliable clocks.

More:
https://eprint.iacr.org/2018/664.pdf

INT-CTXT

Integrity of ciphertexts, a security notion applicable to authenticated encryption schemes that formalizes the practical impossibility for an attacker to create a valid ciphertext even if they know many valid ciphertexts for messages of their choice. If an authenticated cipher is both IND-CPA and INT-CTXT, then it is also IND-CCA.

More:
https://www.cosic.esat.kuleuven.be/school-iot/slides/AuthenticatedEncryptionII.pdf
https://eprint.iacr.org/2018/135.pdf

Invisible and anonymous signatures

Invisibility is the property of a public-key signature that cannot be identified as valid or invalid unless the signer has agreed to reveal that information. This may sound like it makes the signature anonymous (that is, the signature does not reveal the signer identify, or public key), but it does not necessarily (counterexample: sign in addition the signature with a non-invisible signature scheme). However, any anonymous signature is invisible.

More:
https://en.wikipedia.org/wiki/Undeniable_signature
https://www.researchgate.net/publication/338794416_A_Note_on_the_Invisibility_and_Anonymity_of_Undeniable_Signature_Schemes

Non-outsourceability

The property of a proof-of-work system whose “work” cannot be outsourced to third parties without also sharing the outsourcer’s private key, and therefore access to mining reward. This was proposed to prevent pools and hosted mining. More generally, non-outsourceability can be the property of computations that cannot be delegated without compromising some sensitive data.

More
http://soc1024.ece.illinois.edu/nonoutsourceable_full.pdf
https://eprint.iacr.org/2020/044.pdf

Indistinguishability obfuscation (iO)

Obfuscation is about taking as input a program and producing a second program that in some sense hides how the first program works—its internal variables, secret arguments, and so on. Cryptography sees a program as one of the possible abstract representations, typically a Boolean circuit with AND, OR, and NOT gates. iO can be seen as a raw encoding of the input–output relation that hides the “implementation details”, such as sub-procedures or intermediates variables.

The notion of indistinguishability is just a way to formalize the intuitive security notion of secure obfuscation, by saying that obfuscations of two distinct, yet equivalent programs, should not tell which of the two programs has been obfuscated. iO is very powerful and sounds like the solution to many problems, but in practice it’s not because of the high complexity and ineffiency. For example, iO gives you a straightforward way to created functional encryption and proxy re-encryption schemes, by obfuscating the decrypt-and-reencrypt process (interestingly, you can also get iO from functional encryption).

More:
https://eprint.iacr.org/2013/454.pdf
https://eprint.iacr.org/2015/163.pdf