Description
Pseudorandom functions (PRFs) are one of the most fundamental primitives in cryptography. In this work, we provide a new algebraic framework which encompasses many of the existing algebraic PRFs, including the ones by Naor and Reingold (FOCS'97), by Lewko and Waters (CCS'09), and by Boneh, Montgomery, and Raghunathan (CCS'10), as well as the related-key-secure PRFs by Bellare and Cash (Crypto'10) and by Abdalla \etal (Crypto'14). To achieve this goal, we introduce two versions of our framework. The first, termed linearly independent polynomial security, states that the values $(g^{P_1(\vec{a})}, \ldots, g^{P_q(\vec{a})})$ are indistinguishable from a random tuple of the same size, when $P_1, \ldots, P_q$ are linearly independent multivariate polynomials of the secret key vector $\vec{a}$. The second, which is a natural generalization of the first framework, additionally deals with constructions based on the decision linear and matrix Diffie-Hellman assumptions. In addition to unifying and simplifying proofs for existing schemes, our new framework also yields several new results, such as related-key security with respect to arbitrary permutations of polynomials. All our constructions are in the standard model and do not require the existence of multilinear maps.
Prochains exposés
-
Verification of Rust Cryptographic Implementations with Aeneas
Orateur : Aymeric Fromherz - Inria
From secure communications to online banking, cryptography is the cornerstone of most modern secure applications. Unfortunately, cryptographic design and implementation is notoriously error-prone, with a long history of design flaws, implementation bugs, and high-profile attacks. To address this issue, several projects proposed the use of formal verification techniques to statically ensure the[…] -
On the average hardness of SIVP for module lattices of fixed rank
Orateur : Radu Toma - Sorbonne Université
In joint work with Koen de Boer, Aurel Page, and Benjamin Wesolowski, we study the hardness of the approximate Shortest Independent Vectors Problem (SIVP) for random module lattices. We use here a natural notion of randomness as defined originally by Siegel through Haar measures. By proving a reduction, we show it is essentially as hard as the problem for arbitrary instances. While this was[…] -
Endomorphisms via Splittings
Orateur : Min-Yi Shen - No Affiliation
One of the fundamental hardness assumptions underlying isogeny-based cryptography is the problem of finding a non-trivial endomorphism of a given supersingular elliptic curve. In this talk, we show that the problem is related to the problem of finding a splitting of a principally polarised superspecial abelian surface. In particular, we provide formal security reductions and a proof-of-concept[…]-
Cryptography
-