How can Alice enable Bob to look-up values in a private map
Many (most?) leading PSI protocols can be easily adapted to provide this functionality. It is sometimes called &quot;PSI with associated data&quot; or &quot;PSI with data transfer&quot;. For example, you can see this variant of PSI described explicitly in:

Emiliano De Cristofaro and Gene Tsudik. Practical private set intersection protocols with linear complexity. Financial Cryptography 2010.

Even many protocols which don't mention &quot;associated data&quot; explicitly can be easily modified to provide it. I know for sure that the following papers (which are the fastest 2-party semi-honest PSI) will support it:

Benny Pinkas, Thomas Schneider, Gil Segev, Michael Zohner: Phasing: Private Set Intersection using Permutation-based Hashing. Usenix 2015.
Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, Ni Trieu: Efficient Batched Oblivious PRF with Applications to Private Set Intersection.
CCS 2016.

These protocols use an &quot;oblivious PRF&quot; paradigm for PSI, which works roughly like this:

Parties perform an Oblivious PRF where Alice learns (description of) a random function $F$ and Bob learns $F(y)$ for every $y$ in his set.

Alice can compute and send $F(x)$ for every $x$ in his set. Now Bob can compare against his set of $F$-values and identify the intersection. For values $x$ that Alice has but Bob doesn't have, the corresponding $F(x)$ value looks random to Bob, so leaks no information about that $x$.


There is a fair amount of other algorithmic/combinatorial stuff in these protocols, but eventually at some level the protocol is doing what I described above.
To add associated data to this protocol outline, you can just use the $F(x)$ values as keys to encrypt the associated data. Something like this:

For every $y$, Bob has $F(y)$ and (if it's not long enough) expands it with a PRG to get two values $tag_y$ and $k_y$.

For every $x$, Alice similarly expands $F(x)$ into $tag_x$ and $k_x$. She sends $(tag_x, \mathsf{Enc}(k_x, data[x]))$, where $data[x]$ is the record/data associated with key $x$.

Bob can look for tuples of the form $(\tau, c)$ where $\tau$ is a tag that he recognizes as $tag_y$. He can then decrypt $c$ with the corresponding key $k_y$ to obtain the data associated with $y$.