Search results for PublicKey Cryptography

Akira Takahashi, Greg ZaveruchaPublished 20240409 Show abstract PDF
Verifiable encryption (VE) is a protocol where one can provide assurance that an encrypted plaintext satisfies certain properties, or relations. It is an important building block in cryptography with many useful applications, such as key escrow, group signatures, optimistic fair exchange, and others. However, the majority of previous VE schemes are restricted to instantiation with specific publickey encryption schemes or relations. In this work, we propose a novel framework that realizes VE protocols using zeroknowledge proof systems based on the MPCinthehead paradigm (Ishai et al. STOC 2007). Our generic compiler can turn a large class of zeroknowledge proofs into secure VE protocols for any secure publickey encryption scheme with the undeniability property, a notion that essentially guarantees binding of encryption when used as a commitment scheme. Our framework is versatile: because the circuit proven by the MPCinthehead prover is decoupled from a complex encryption function, the work of the prover is focused on proving the encrypted data satisfies the relation, not the proof of plaintext knowledge. Hence, our approach allows for instantiation with various combinations of properties about the encrypted data and encryption functions. We then consider concrete applications, to demonstrate the efficiency of our framework, by first giving a new approach and implementation to verifiably encrypt discrete logarithms in any prime order group more efficiently than was previously known. Then we give the first practical verifiable encryption scheme for AES keys with postquantum security, along with an implementation and benchmarks.

Gabrielle De Micheli, Nadia HeningerPublished 20240409 Show abstract PDF
Sidechannel attacks targeting cryptography may leak only partial or indirect information about the secret keys. There are a variety of techniques in the literature for recovering secret keys from partial information. In this work, we survey several of the main families of partial key recovery algorithms for RSA, (EC)DSA, and (elliptic curve) DiffieHellman, the classical publickey cryptosystems in common use today. We categorize the known techniques by the structure of the information that is learned by the attacker, and give simplified examples for each technique to illustrate the underlying ideas.

Loïs HugueninDumittan, Serge VaudenayPublished 20240409 Show abstract PDF
Proving whether it is possible to build INDCCA publickey encryption (PKE) from INDCPA PKE in a blackbox manner is a major open problem in theoretical cryptography. In a significant breakthrough, Gertner, Malkin and Myers showed in 2007 that shielding blackbox reductions from INDCCA to INDCPA do not exist in the standard model. Shielding means that the decryption algorithm of the INDCCA scheme does not call the encryption algorithm of the underlying INDCPA scheme. In other words, it implies that every tentative construction of INDCCA from INDCPA must have a reencryption step when decrypting.
This result was only proven with respect to classical algorithms. In this work we show that it stands in a postquantum setting. That is, we prove that there is no postquantum shielding blackbox construction of INDCCA PKE from INDCPA PKE. In the type of reductions we consider, i.e. postquantum ones, the constructions are still classical in the sense that the schemes must be computable on classical computers, but the adversaries and the reduction algorithm can be quantum. This suggests that considering quantum notions, which are stronger than their classical counterparts, and allowing for quantum reductions does not make building INDCCA publickey encryption easier.

Manuel Barbosa, Deirdre Connolly, João Diogo Duarte, Aaron Kaiser, Peter Schwabe, Karolin Varner, Bas WesterbaanPublished 20240409 Show abstract PDF
XWing is a hybrid keyencapsulation mechanism based on X25519 and MLKEM768. It is designed to be the sensible choice for most applications. The concrete choice of X25519 and MLKEM768 allows XWing to achieve improved efficiency compared to using a generic KEM combiner. In this paper, we introduce the XWing hybrid KEM construction and provide a proof of security. We show (1) that XWing is a classically INDCCA secure KEM if the strong DiffieHellman assumption holds in the X25519 nominal group, and (2) that XWing is a postquantum INDCCA secure KEM if MLKEM768 is itself an INDCCA secure KEM and SHA3256 is secure when used as a pseudorandom function. The first result is proved in the ROM, whereas the second one holds in the standard model. Loosely speaking, this means XWing is secure if either X25519 or MLKEM768 is secure. We stress that these security guarantees and optimizations are only possible due to the concrete choices that were made, and it may not apply in the general case.

Aurélien Dupin, Simon AbelardPublished 20240409 Show abstract PDF
The problem of Broadcast Encryption (BE) consists in broadcasting an encrypted message to a large number of users or receiving devices in such a way that the emitter of the message can control which of the users can or cannot decrypt it.
Since the early 1990s, the design of BE schemes has received significant interest and many different concepts were proposed. A major breakthrough was achieved by Naor, Naor and Lotspiech (CRYPTO 2001) by partitioning cleverly the set of authorized users and associating a symmetric key to each subset. Since then, while there have been many advances in publickey based BE schemes, mostly based on bilinear maps, little was made on symmetric cryptography.
In this paper, we design a new symmetricbased BE scheme, named $\Sigma\Pi$BE, that relies on logic optimization and consensual security assumptions. It is competitive with the work of Naor et al. and provides a different tradeoff: the bandwidth requirement is significantly lowered at the cost of an increase in the key storage.