# Homomorphism and Zero Knowledge in FIPS 140-2 compliant systems

I am analyzing a system that needs to be at least level 3 FIPS 140-2 compliant. The system may leverage from homomorphic and Zero Knowledge constructs, but, as far as I can see, the algorithms approved for FIPS are the most standard ones: RSA, AES, SHA-*, etc.

Is there a similar standard (or an extension to FIPS 140-2) that enables the use of (say) Lifted ElGamal or Paillier? If not, how could one evaluate commercial solutions that support said algorithms?

-

I'm no FIPS expert but I strongly suspect the answer is no. FIPS is incredibly restrictive and laughably behind the times.

To evaluate those algorithms that don't appear in FIPS, first make sure their component parts are secure (maybe even built with FIPS algorithms as subroutines). Then, if there are known answer tests anywhere, maybe from the authors of the algorithm, you can test the implementation against those. Do a thorough code audit, making especially sure that the malleability of a partially-homomorphic scheme does not lead to a side channel somehow.

If you get to this point, the schemes will be better-audited than 99% of crypto code, and you can probably sleep soundly knowing that you did the best you could with a non-standard algorithm.

As an aside, exactly what "homomorphic" and "zero-knowledge" techniques does it use? The term "zero-knowledge" especially is thrown around a lot in industry, so there's really no telling what they're doing without more info.

-
I would say that the requirements are rather standard among these categories: given a set of individually encrypted messages, calculate the encryption of the sum, given a ZK-proof that each encrypted message is the encryption of a value within a preset range. It would also be important to generate a proof that the sum generated is the sum of all the values only the values encrypted. The specific techniques are yet to be defined. I know that Lifted ElGamal is an option to support both requirements, but I'd prefer to be exhaustive in my search. – Sergio Andrés Figueroa Santos Feb 16 at 19:02
Wow, ok. I seriously doubt there will ever be a FIPS standard for such complicated functionality - the relevant standards bodies can barely even decide what to standardize for something as simple as public-key encryption. I shudder to think what a standards document for a ZKP would even look like.... – pg1989 Feb 16 at 20:47

The question mentions FIPS 140-2 Level 3 compliant. I answer this as if the question had said the intent is to validate the product as FIPS 140-2 Level 3. This may sound like hairsplitting, but there are many modules claiming to be FIPS 140-2 compliant, which factually could not be validated without large changes to functionality.

FIPS 140-2 really intends to use wellknown and proven algorithms like AES, Triple-DES, RSA, DSA, etc. in addition, the key lengths have been restricted so that the algorithm strength should be equivalent to 112-bit symmetric encryption algorithm or better.

The detailed set of algorithms accepted are given in FIPS 140-2 Annexes A, B, C, D, and in Implementation Guidance. Annexes generally list acceptable FIPS/NIST standards and Implementation Guidance allows use of certain standards and schemes beyond.

There does not appear to be any ZKA or homomorphic schemes in any of these resources.

The ways to have new cryptographic schemes allowed or accepted in FIPS 140-2 module include:

• If the scheme is based on established cryptography algorithms, and the
non-approved algorithm can be considered as some form of data formatting or data transformation.

• Maybe this algorithm is used for a specific area allowing some other algorithms in FIPS 140-2 module. One problem where other algorithms are reasonable is Split knowledge procedure for manually entering keys.

• Implementation Guidance is based on questions asked from NIST and their answers, so new allowed schemes can occasionally get approved. So you could ask them. The process is very slow.

• Wait for NIST to write NIST SP 800 or FIPS document on standard you're
interested in and add it to one of Annexes.

None of these options currently clearly allow the algorithms you're interested in, but in the most cases these are the valid options.

-

See if you product really needs to be FIPS 140-2 compliant.

No, seriously. Unless it will be used by the U.S. Federal Government, or if mandated by a contract, it does not.

-