Search results for PostQuantum Cryptography

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.

Décio Luiz Gazzoni Filho, Guilherme Brandão, Julio LópezPublished 20240409 Show abstract PDF
Efficient polynomial multiplication routines are critical to the performance of latticebased postquantum cryptography (PQC). As PQC standards only recently started to emerge, CPUs still lack specialized instructions to accelerate such routines. Meanwhile, deep learning has grown immeasurably in importance. Its workloads call for teraflopslevel of processing power for linear algebra operations, mainly matrix multiplication. Computer architects have responded by introducing ISA extensions, coprocessors and specialpurpose cores to accelerate such operations. In particular, Apple ships an undocumented matrixmultiplication coprocessor, AMX, in hundreds of millions of mobile phones, tablets and personal computers. Our work repurposes AMX to implement polynomial multiplication and applies it to the NTRU cryptosystem, setting new speed records on the Apple M1 and M3 systemsonchip (SoCs): polynomial multiplication, key generation, encapsulation and decapsulation are sped up by $1.54$–$3.07\times$, $1.08$–$1.33\times$, $1.11$–$1.50\times$ and $1.20$–$1.98\times$, respectively, over the previous stateoftheart.

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.