Trapdoor Permutation¶

A trapdoor permutation is a bijection (1-1 and onto function) that is easy to compute for everyone, yet is hard to invert unless given special additional information, called the “trapdoor”. The public key is essentially the function description and the private key is the trapdoor.

The TPElement Interface¶

The TPElement interface represents a trapdoor permutation element.

public BigInteger getElement()

Returns the trapdoor element value as BigInteger.

Returns: the value of the element
public TPElementSendableData generateSendableData()

This function extracts the actual value of the TPElement and wraps it in a TPElementSendableData that as it name indicates can be send using the serialization mechanism.

Returns: A Serializable representation of the TPElement

The TrapdoorPermutation Interface¶

This interface is the general interface of trapdoor permutation.

Core Functionality¶

public TPElement compute(TPElement tpEl)

Computes the operation of this trapdoor permutation on the given TPElement.

Parameters: tpEl – the input for the computation the result TPElement from the computation IllegalArgumentException if the given element is invalid for this permutation
public TPElement invert(TPElement tpEl)

Inverts the operation of this trapdoor permutation on the given TPElement.

Parameters: tpEl – the input to invert the result TPElement from the invert operation KeyException if there is no private key IllegalArgumentException if the given element is invalid for this permutation
public byte hardCorePredicate(TPElement tpEl)

Computes the hard core predicate of the given tpElement.

A hard-core predicate of a one-way function is a predicate (i.e., a function whose output is a single bit) which is easy to compute given but is hard to compute given . In formal terms, there is no probabilistic polynomial time algorithm that computes from with probability significantly greater than one half over random choice of .

Parameters: tpEl – the input to the hard core predicate (byte) the hard core predicate.
public byte[] hardCoreFunction(TPElement tpEl)

Computes the hard core function of the given tpElement.

A hard-core function of a one-way function is a function which is easy to compute given but is hard to compute given . In formal terms, there is no probabilistic polynomial time algorithm that computes from with probability significantly greater than one half over random choice of .

Parameters: tpEl – the input to the hard core function byte[] the result of the hard core function

Generating TPElements¶

public TPElement generateRandomTPElement()

creates a random TPElement that is valid for this trapdoor permutation

Returns: the created random element
public TPElement generateTPElement(BigInteger x)

Creates a TPElement from a specific value . It checks that the value is valid for this trapdoor permutation.

Returns: If the value is valid for this permutation return the created random element IllegalArgumentException if the given value is invalid for this permutation
public TPElement generateUncheckedTPElement(BigInteger x)

Creates a TPElement from a specific value . This function does not guarantee that the the returned TPElement object is valid. It is the caller’s responsibility to pass a legal value.

Returns: Set the value and return the created random element
public TPElement reconstructTPElement(TPElementSendableData data)

Creates a TPElement from data that was probably obtained via the serialization mechanism.

Parameters: data – serialized data necessary to reconstruct a given TPElement the reconstructed TPElement

Checking Element Validity¶

public TPElValidity isElement(TPElement tpEl)

Checks if the given element is valid for this trapdoor permutation

Parameters: tpEl – the element to check (TPElValidity) enum number that indicate the validation of the element IllegalArgumentException if the given element is invalid for this permutation
public enum TPElValidity

Enum that represent the possible validity values of trapdoor element. There are three possible validity values:

Parameters: VALID – it is an element NOT_VALID – it is not an element DONT_KNOW – there is not enough information to check if it is an element or not

Encryption Keys Functionality¶

public void setKey(PublicKey publicKey, PrivateKey privateKey)

Sets this trapdoor permutation with public key and private key.

Parameters: publicKey – the public key privateKey – the private key that without it the permutation cannot be inverted efficiently
public void setKey(PublicKey publicKey)

Sets this trapdoor permutation with a public key. After this initialization, this object can do compute() but not invert(). This initialization is for user that wants to encrypt messages using the public key but cannot decrypt messages.

Parameters: publicKey – the public key InvalidKeyException if the key is not a valid key of this permutation
public boolean isKeySet()

Checks if this trapdoor permutation object has been previously initialized. To initialize the object the setKey() function has to be called with corresponding parameters after construction.

return: true if the object was initialized, false otherwise.
public PublicKey getPubKey()
Returns: returns the public key

BasicUsage¶

We demonstrate a basic usage scenario with a sender party that wish to hide a secret using the trapdoor permutation, and a receiver who is not able to invert the permutation on the secret.

Here is the code of the sender:

//Create public key, private key and secret
...

//instantiate the trapdoor permutation:
TrapdoorPermutation trapdoorPermutation = TrapdoorPermutationFactory.getInstance().getObject("RSA", "SCAPI");
//set the keys for this trapdoor permutation
trapdoorPermutation.setKey(publicKey, privateKey);

// represent the secret (originally was of BigInteger type) using TPElement
TPElement secretElement = trapdoorPermutation.generateTPElement(secret);
//hide the secret using the trapdoor permutation
TPElement maskedSecret = trapdoorPermutation.compute(secretElement);

// this line will succeed, because the private key is known to the sender
TPElement invertedElement = trapdoorPermutation.invert(maskedSecret);

// send the public key and the secret to the other side
channel.send(publicKey.getEncoded());

Here is the code of the receiver:

Serializable pkey = channel.receive();
TPElementSendableData secretMsg = (TPElementSendableData) channel.receive();

// reconstruct publicKey from pkey
...

//instantiate the trapdoor permutation:
TrapdoorPermutation trapdoorPermutation = TrapdoorPermutationFactory.getInstance().getObject("RSA", "SCAPI");
//set the keys for this trapdoor permutation
trapdoorPermutation.setKey(publicKey);

// reconstruct a TPElement from a TPElementSendableData
TPElement maskedSecret = trapdoorPermutation.reconstructTPElement(secretMsg);

// this line will fail, and throw KeyException, because the private key is not known to the receiver
TPElement secretElement = trapdoorPermutation.invert(maskedSecret);

Supported Trapdoor Permutations¶

In this section we present possible keys to the TrapdoorPermutationFactory.

Scapi’s own implementation of RSA trapdoor permutation:

Key Class
ScapiRSA edu.biu.scapi.primitives.trapdoorPermutation.ScRSAPermutation

Crypto++ implementation of RSA trapdoor permutation and Rabin trapdoor permutation:

Key Class
CryptoPPRSA edu.biu.scapi.primitives.trapdoorPermutation.cryptopp.CryptoPpRSAPermutation
CryptoPPRabin edu.biu.scapi.primitives.trapdoorPermutation.cryptopp.CryptoPpRabinPermutation

OpenSSL implementation of RSA trapdoor permutation:

Key Class
OpenSSLRSA edu.biu.scapi.primitives.trapdoorPermutation.openSSL.OpenSSLRSAPermutation