Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
In the context of papers using the UC framework, I have seen the same cryptographic tools refereed as cryptographic primitives and functionalities. Are the two terms interchangeable?
An example is here:
Bulletin Boards and Smart Contracts are primitives which form the backbone of our result.
and
We also assume that there exists a Smart Contract functionality that incorporates this ideal Bulletin Board.
It is difficult to answer this question without looking at the same papers you are looking at. Still, I interpret these concepts as fairly different, for reasons I will sketch below.
A function is common in mathematics, and can be written as some mapping $f : X\to Y$ of inputs to outputs. Many algorithms implement the behavior of functions --- they take some batch of inputs, and return outputs. Consider prototypical examples as being "sorting algorithms" or "graph algorithms" or "essentially any algorithm you learn about in an algorithms course".
Functionalities do not necessarily collect all of their inputs before starting processing them. Later inputs can depend on prior inputs, potentially in non-trivial ways. This is in particular important for interactive protocols, where for a two-person protocol with participants $P_1$ and $P_2$, $P_2$'s later inputs can depend on $P_1$'s prior inputs (potentially in an adversarial way). This is somehow the "core" of the idea, where other similar concepts (say streaming algorithms) often are not called functionalities because of the lack of multiple participants. So functionalities can be seen as the mathematical abstraction which captures the notion of interactive algorithms.
A cryptographic primitive is some tuple of algorithms $(\mathcal{A}_1,\dots,\mathcal{A}_k)$ (which might each individually be a function or a functionality), along with certain conditions they must satisfy. There are many conditions you can impose, but common ones are things like:
For example, symmetric-key encryption is often described as a triple of algorithms $(\mathsf{KeyGen}, \mathsf{Enc}, \mathsf{Dec})$ such that:
There is a correctness condition:
$$\forall k\leftarrow\mathsf{KeyGen}(1^\lambda), \forall m\in\mathcal{M} : (\mathsf{Dec}_k\circ\mathsf{Enc}_k)(m) = m$$ Where $\mathcal{M}$ is the message space of the algorithm.
There is a secrecy condition, namely that for $k\leftarrow\mathsf{KeyGen}(1^\lambda)$, and $m_0\neq m_1$, $\{\mathsf{Enc}_k(m_0)\}$ is (some form of) indistinguishable from $\{\mathsf{Enc}_k(m_1)\}$, where these quantities are distributions over the choice of random coins of encryption.
So we can view each of the individual algorithms as being functionalities, but them combined together with conditions they must fulfil as being a cryptographic primitive that we call "symmetric key encryption".
Note that one could technically view something like a sorting algorithm as a "cryptographic primitive with solely a correctness condition", but this is rather non-standard. We generally assume all algorithms must be correct, so only start describing things as cryptographic primitives when the condition is something like "correct in an adversarial context", or conditions such as "secret" (or other "more than just correct" conditions).
While I believe this viewpoint is fairly common, I don't know if it is universally agreed upon by all authors at all times, so particular questions you have about particular papers would still be easier to answer with a pointer to those papers.
What Mark said in his answer is the crux of the matter, but here's how you interpret it in this particular situation:
When they talk about the smart contract primitive they're referring to an object with the security guarantees we expect from smart contracts, with input-output behavior agrees with our intuitive idea of smart contracts.
When they say "there exists a Smart Contract functionality that incorporates this ideal Bulletin Board" they mean there might exist some way to define the input-output behavior for smart contracts which uses the ideal bulletin board as a building block.
This is a really good question because these two things definitely seem interchangeable at first and the difference is subtle. You can also get pretty close to understanding what the authors mean by assuming that they are interchangeable. I hope my answer's helpful!
