Score:0

# How to extend operations from numbers to larger "objects" in cryptographic implementations?

I know I'm not supposed to roll my own crypto, but everyone starts somewhere! I'm implementing the PSI-CA protocol defined in Fast and Private Computation of Cardinality of Set Intersection and Union (Figure 1, Page 5), and I have it (more-or-less) working. My biggest issue is that I only have it working for int64_t types, and nothing else. Ultimately I'd like to compare strings or even arbitrary objects. So I figure I'll have to have an object expose functionality to serialize/hash itself, but then what? How do I extend this algorithm to multi-byte computations?

For example, if I want to use SHA-512 hashes instead of integers, during certain operations, say $$\forall i 1\leq i \leq v : a^{\prime}_i = (a_i)^{R^{\prime}_s}$$, how do I translate this from operating over integers (trivial) to bytefields? Do I simply perform this same operation for every byte in the field?

Is anything stopping you from interpreting and using the serialized / hashed version of an object as an integer? (Which of course requires that serialization / hashing preserves equality)
I think then it wouldn't be resistant to collisions, right? Like SHA-512 has a large range. The paper says I need two hash functions (modeled as ROM in the paper), so I'm not really sure what hash functions would satisfy these requirements to keep the information cryptographically secure.
Score:1

It is not clear to me (without seeing your code) what your current issue is. Glancing through the paper, I see (for example in fig. 1):

1. (arbitrary objects) $$c_1,\dots, c_v$$ and $$s_1,\dots, s_v$$

2. hashes of these objects, which are written $$hc_i = H(c_i)$$ and $$hs_i = H(s_i)$$ (up to a permutation applied to the $$s_i$$).

All of the remaining operations are in terms of the $$hc_i$$ and $$hs_i$$, which appear to be (from context) in $$\mathbb{Z}_p^*$$, i.e. the arithmetic is standard (although it is likely that you have to choose $$p$$ large enough such that the discrete logarithm problem is hard, so of $$\gg 1000$$ bits. In particular you likely should be using bigints rather than u64's. I haven't read closely enough that I know that they're assuming hardness of a DL-type assumption in $$\mathbb{Z}_p^*$$ though).

Scanning through the other figures, I see a similar story, namely that all arithmetic is done on hashed elements of $$\mathbb{Z}_p^*$$, rather than arbitrary bytestrings in $$\{0,1\}^*$$. I don't see your particular example:

$$1≤i≤v:a_i'=(a_i)^{R′_s}$$

as being an issue. For example, this seems to occur in figure 4, where prior to it I see $$a_i = (hs_i)^{R_s'}$$. In this figure I don't see the definition $$hs_i = H(s_i)$$, and I am only skimming, but it is plausible that this interpretation is being assumed, i.e. $$hs_i$$ is the hash of an arbitrary bytestring $$s_i$$, and is contained in $$\mathbb{Z}_p^*$$ (rather than $$\{0,1\}^*$$).

is going to be "no" (unless something specifically says to do this). Typically cryptographic protocols work on well-defined mathematical objects (say bit strings in $$\{0,1\}^*$$), and "chopping these up" to try to force things to work (when this is not specified as part of the protocol) can easily lead to security issues.