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.

Contents

Trapdoor Permutation

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
Returns:	the result TPElement from the computation
Throws:	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
Returns:	the result TPElement from the invert operation
Throws:	KeyException if there is no private key
Throws:	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 $f$ is a predicate $b$ (i.e., a function whose output is a single bit) which is easy to compute given $x$ but is hard to compute given $f(x)$ . In formal terms, there is no probabilistic polynomial time algorithm that computes $b(x)$ from $f(x)$ with probability significantly greater than one half over random choice of $x$ .

Parameters:	tpEl – the input to the hard core predicate
Returns:	(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 $f$ is a function $g$ which is easy to compute given $x$ but is hard to compute given $f(x)$ . In formal terms, there is no probabilistic polynomial time algorithm that computes $g(x)$ from $f(x)$ with probability significantly greater than one half over random choice of $x$ .

Parameters:	tpEl – the input to the hard core function
Returns:	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 $x$ . It checks that the $x$ value is valid for this trapdoor permutation.

Returns:	If the $x$ value is valid for this permutation return the created random element
Throws:	IllegalArgumentException if the given value $x$ is invalid for this permutation

public TPElement generateUncheckedTPElement(BigInteger x)¶

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

Returns:	Set the $x$ 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
Returns:	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
Returns:	(TPElValidity) enum number that indicate the validation of the element
Throws:	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
Throws:	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());
channel.send(maskedSecret.generateSendableData());

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