ISO/IEC 18033-6:2019

IT Security techniques — Encryption algorithms — Part 6: Homomorphic encryption

This document specifies the following mechanisms for homomorphic encryption. — Exponential ElGamal encryption; — Paillier encryption. For each mechanism, this document specifies the process for: — generating parameters and the keys of the involved entities; — encrypting data; — decrypting encrypted data; and — homomorphically operating on encrypted data. Annex A defines the object identifiers assigned to the mechanisms specified in this document. Annex B provides numerical examples.

Techniques de sécurité IT — Algorithmes de chiffrement — Partie 6: Chiffrement homomorphe

General Information

• Status: Published
• Publication Date: 01-May-2019
• ICS: 35.030 - IT Security
• Technical Committee: ISO/IEC JTC 1/SC 27 - Information security, cybersecurity and privacy protection
• Drafting Committee: ISO/IEC JTC 1/SC 27/WG 2 - Cryptography and security mechanisms
• Current Stage: 6060 - International Standard published
• Due Date: 20-Oct-2018
• Completion Date: 02-May-2019

Standards Content (Sample)

INTERNATIONAL ISO/IEC
STANDARD 18033-6
First edition
2019-05
IT Security techniques — Encryption
algorithms —
Part 6:
Homomorphic encryption
Techniques de sécurité IT — Algorithmes de chiffrement —
Partie 6: Chiffrement homomorphe
Reference number
ISO/IEC 18033-6:2019(E)
©
ISO/IEC 2019

---------------------- Page: 1 ----------------------
ISO/IEC 18033-6:2019(E)

COPYRIGHT PROTECTED DOCUMENT
© ISO/IEC 2019
All rights reserved. Unless otherwise specified, or required in the context of its implementation, no part of this publication may
be reproduced or utilized otherwise in any form or by any means, electronic or mechanical, including photocopying, or posting
on the internet or an intranet, without prior written permission. Permission can be requested from either ISO at the address
below or ISO’s member body in the country of the requester.
ISO copyright office
CP 401 • Ch. de Blandonnet 8
CH-1214 Vernier, Geneva
Phone: [phone]
Fax: [phone]
Email: [e-mail]
Website: www.iso.org
Published in Switzerland
ii © ISO/IEC 2019 – All rights reserved

---------------------- Page: 2 ----------------------
ISO/IEC 18033-6:2019(E)

Contents Page
Foreword .iv
Introduction .v
1 Scope . 1
2 Normative references . 1
3 Terms and definitions . 1
4 Symbols and abbreviations . 3
5 General model for homomorphic encryption . 4
5.1 Entities . 4
5.2 Key roles . 4
5.3 Algorithms . 4
5.4 Functional requirements . 4
6 Homomorphic encryption mechanisms . 5
6.1 General . 5
6.2 Exponential ElGamal encryption . 5
6.2.1 General. 5
6.2.2 Key generation algorithm . . 5
6.2.3 Encryption . 5
6.2.4 Decryption . 6
6.3 Paillier encryption . 6
6.3.1 General. 6
6.3.2 Key generation algorithm . . 7
6.3.3 Encryption . 7
6.3.4 Decryption . 7
Annex A (normative) Object identifiers . 9
Annex B (informative) Numerical examples .10
Bibliography .17
© ISO/IEC 2019 – All rights reserved iii

---------------------- Page: 3 ----------------------
ISO/IEC 18033-6:2019(E)

Foreword
ISO (the International Organization for Standardization) and IEC (the International Electrotechnical
Commission) form the specialized system for worldwide standardization. National bodies that
are members of ISO or IEC participate in the development of International Standards through
technical committees established by the respective organization to deal with particular fields of
technical activity. ISO and IEC technical committees collaborate in fields of mutual interest. Other
international organizations, governmental and non-governmental, in liaison with ISO and IEC, also
take part in the work.
The procedures used to develop this document and those intended for its further maintenance are
described in the ISO/IEC Directives, Part 1. In particular, the different approval criteria needed for
the different types of document should be noted. This document was drafted in accordance with the
editorial rules of the ISO/IEC Directives, Part 2 (see www .iso .org/directives).
Attention is drawn to the possibility that some of the elements of this document may be the subject
of patent rights. ISO and IEC shall not be held responsible for identifying any or all such patent
rights. Details of any patent rights identified during the development of the document will be in the
Introduction and/or on the ISO list of patent declarations received (see www .iso .org/patents) or the IEC
list of patent declarations received (see http: //patents .iec .ch).
Any trade name used in this document is information given for the convenience of users and does not
constitute an endorsement.
For an explanation of the voluntary nature of standards, the meaning of ISO specific terms and
expressions related to conformity assessment, as well as information about ISO's adherence to the
World Trade Organization (WTO) principles in the Technical Barriers to Trade (TBT) see www .iso
.org/iso/foreword .html.
This document was prepared by Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 27, IT Security techniques.
A list of all parts in the ISO/IEC 18033 series can be found on the ISO website.
Any feedback or questions on this document should be directed to the user’s national standards body. A
complete listing of these bodies can be found at www .iso .org/members .html.
iv © ISO/IEC 2019 – All rights reserved

---------------------- Page: 4 ----------------------
ISO/IEC 18033-6:2019(E)

Introduction
Homomorphic Encryption is a type of symmetric or asymmetric encryption that allows third parties
(i.e. parties that are neither the encryptor nor the decryptor) to perform operations on plaintext
data while keeping the data in encrypted form. The primary purpose of homomorphic encryption is
to allow third parties to perform such computations on data while simultaneously ensuring that the
confidentiality of the plaintext data is preserved. It is typically the case that homomorphic encryption
schemes require the plaintext to be represented in the form of elements of a group, rather than strings
of bits or bytes as is the case with most conventional methods of encryption.
Homomorphic encryption mechanisms can be categorized by the nature of the operation(s) on the
plaintext that they can support. This document considers homomorphic encryption mechanisms where
the plaintext operation is typically addition and/or multiplication in a prescribed group.
© ISO/IEC 2019 – All rights reserved v

---------------------- Page: 5 ----------------------
INTERNATIONAL STANDARD ISO/IEC 18033-6:2019(E)
IT Security techniques — Encryption algorithms —
Part 6:
Homomorphic encryption
1 Scope
This document specifies the following mechanisms for homomorphic encryption.
— Exponential ElGamal encryption;
— Paillier encryption.
For each mechanism, this document specifies the process for:
— generating parameters and the keys of the involved entities;
— encrypting data;
— decrypting encrypted data; and
— homomorphically operating on encrypted data.
Annex A defines the object identifiers assigned to the mechanisms specified in this document. Annex B
provides numerical examples.
2 Normative references
There are no normative references in this document.
3 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
ISO and IEC maintain terminological databases for use in standardization at the following addresses:
— ISO Online browsing platform: available at https: //www .iso .org/obp
— IEC Electropedia: available at http: //www .electropedia .org/
3.1
ciphertext
data which has been transformed to hide its information content
[SOURCE: ISO/IEC 18033-1:2015, 2.11]
3.2
decryption
reversal of a corresponding encryption (3.6)
[SOURCE: ISO/IEC 10116:2017, 3.5]
© ISO/IEC 2019 – All rights reserved 1

---------------------- Page: 6 ----------------------
ISO/IEC 18033-6:2019(E)

3.3
decryption algorithm
process which transforms ciphertext (3.1) into plaintext (3.14)
[SOURCE: ISO/IEC 18033-1:2015, 2.17]
3.4
decryptor
entity which decrypts ciphertexts (3.1)
[SOURCE: ISO/IEC 18033-5:2015, 3.1]
3.5
deterministic
characteristic of an algorithm that states that given the same input, the same output is
always produced
[SOURCE: ISO/IEC 18031:2011, 3.9, modified — "algorithm" has been removed from the term and added
as the domain.]
3.6
encryption
(reversible) transformation of data by a cryptographic algorithm to produce ciphertext (3.1), i.e. to hide
the information content of the data
[SOURCE: ISO/IEC 18033-1:2015, 2.21]
3.7
encryption algorithm
process which transforms plaintext (3.14) into ciphertext (3.1)
[SOURCE: ISO/IEC 18033-1:2015, 2.22]
3.8
encryptor
entity which encrypts plaintexts (3.14)
[SOURCE: ISO/IEC 18033-5:2015, 3.2]
3.9
group
set of elements S and an operation * defined on the set of elements such that (i) a*(b*c) = (a*b)*c for
every a, b and c in S, (ii) there exists an identity element e in S such that a*e = e*a = a for every a in S, and
−1 −1 −1
(iii) for every a in S there exists an inverse element a in S such that a*a = a *a = e
[SOURCE: ISO/IEC 15946-1:2016, 3.6]
3.10
homomorphic map
map from one group (3.9) to another that preserves their respective group operations
Note 1 to entry: A definition of homomorphic map is provided by Cohen et al. in [13].
3.11
key
sequence of symbols that controls the operation of a cryptographic transformation
Note 1 to entry: Examples are encryption (3.6), decryption (3.2), cryptographic check function computation,
signature generation, or signature verification.
[SOURCE: ISO/IEC 9798-1:2010, 3.16]
2 © ISO/IEC 2019 – All rights reserved

---------------------- Page: 7 ----------------------
ISO/IEC 18033-6:2019(E)

3.12
key generation
process of generating a key (3.11)
[SOURCE: ISO/IEC 11770-1:2010, 2.24]
3.13
key generation algorithm
method for generating asymmetric key (3.11) pairs
[SOURCE: ISO/IEC 18033-2:2006, 3.27]
3.14
plaintext
unencrypted information
[SOURCE: ISO/IEC 18033-1:2015, 2.30]
3.15
probabilistic
characteristic of an algorithm that states that given the same input, the output could take
different values
3.16
security parameter
variables that determine the security strength of a mechanism
[SOURCE: ISO/IEC 20008-2:2013, 3.5]
4 Symbols and abbreviations
a∈S Element a of the set S
sec.key Private key (secret key)
pub.key Public key
F Finite field with p elements for a prime p
p
g Element in F
p
k Security parameter
p Prime number
parameters Public parameters necessary for encryption, decryption or the group operation on
ciphertexts
q Prime order of g
* *
Z or Z Unit group of Z or Z , respectively
q n q n
Z or Z Residue ring modulo q or n, respectively
q n
(mod p) Modulo p
• Operation on the plaintext group
⨀ Operation on the ciphertext group
Group generated by g
© ISO/IEC 2019 – All rights reserved 3

---------------------- Page: 8 ----------------------
ISO/IEC 18033-6:2019(E)

5 General model for homomorphic encryption
5.1 Entities
There are three entities as follows.
— encryptor: an entity that performs homomorphic encryption using a public key;
— decryptor: an entity that performs homomorphic decryption using a private key;
— operator: an entity that performs homomorphic operations on ciphertexts.
5.2 Key roles
The private key sec.key shall be kept secret by the decryptor.
The public key pub.key shall be public to the encryptor or operator.
The parameters parameters are public.
5.3 Algorithms
A homomorphic encryption mechanism is composed of the following three algorithms.
— KeyGen(k). Given a security parameter k, produce a tuple (pub.key, sec.key, parameters) where pub.
key denotes the public key, sec.key denotes the private key and parameters denotes the parameters.
— Encrypt(m, pub.key, parameters). Given a public key pub.key, parameters parameters and a plaintext
m in the plaintext group, perform encryption and produce a ciphertext c.
— Decrypt(c, sec.key, parameters). Given a private key sec.key, parameters parameters and a ciphertext
c in the ciphertext group, perform decryption and produce a plaintext m.
5.4 Functional requirements
Given any tuple (pub.key, sec.key, parameters) produced by KeyGen(k), the following two properties are
required.
Correctness. For any plaintext m,
Decrypt(Encrypt(m, pub.key, parameters), sec.key, parameters) = m .
Homomorphic property. The encryption is a homomorphic map from the plaintext group to the
ciphertext group. More specifically, for any two plaintexts m and m in the plaintext group, and letting
1 2
c = Encrypt(m , pub.key, parameters)
1 1
c = Encrypt(m , pub.key, parameters),
2 2
it is required that
Decrypt(c ⨀c , sec.key, parameters) = m •m .
1 2 1 2
In all the mechanisms specified in this document, the key generation and encryption algorithms are
probabilistic, while the decryption is a deterministic algorithm.
4 © ISO/IEC 2019 – All rights reserved

---------------------- Page: 9 ----------------------
ISO/IEC 18033-6:2019(E)

6 Homomorphic encryption mechanisms
6.1 General
In Clause 6, two homomorphic encryption mechanisms are specified.
Annex A defines the object identifiers which shall be used to identify the mechanisms specified in this
document.
6.2 Exponential ElGamal encryption
6.2.1 General
The detailed algorithm is found in [14].
6.2.2 Key generation algorithm
Key generation: KeyGen(k) →(pub.key, sec.key, parameters)
Input: a security parameter k.
Output: a public key pub.key = y, a private key sec.key = x, and parameters parameters = (p, q, g).
Operations:
a) Parameters' key generation
1) Choose prime q with security parameter k uniformly at random and independently.
2) Choose prime p uniformly at random with security parameter k subject to the condition that q
divides p-1.
*
3) Choose g ∈ F with prime order q.
p
b) User key generation
1) Choose x ∈ {1,., q-1} uniformly at random.
x
2) Compute y = g (mod p).
3) Output (y, x, (p, q, g)).
NOTE 1 For the common security levels and corresponding sizes for p and q, see [11].
NOTE 2 For generating a random integer from the specified range, see ISO/IEC 18031.
NOTE 3 For prime number generation, see ISO/IEC 18032.
6.2.3 Encryption
Encryption: Encrypt(m, pub.key, parameters) → c
M
Input: a message m = g ∈ for M ∈ Z , a public key pub.key = y, and parameters parameters = (p, q, g).
q
Output: a ciphertext c = (u, v).
Operations:
*
a) Choose r uniformly at random from Z .
q
r
b) Compute u = g (mod p).
© ISO/IEC 2019 – All rights reserved 5

---------------------- Page: 10 ----------------------
ISO/IEC 18033-6:2019(E)

r M r
c) Compute v = my ( = g y )(mod p).
d) Output c as a ciphertext c = (u, v) of m.
NOTE When a message is used after a conversion function, see ISO/IEC 18033-2.
6.2.4 Decryption
M
Decryption: Decrypt(c, sec.key, parameters) → m = g
Input: a ciphertext c = (u, v), a private key sec.key = x, and parameters parameters = (p, q, g).
M
Output: exponential message m = g .
Operations:
x
a) Compute z = u (mod p).
−1 M
b) Decrypt the ciphertext as m = vz (mod p), where m = g ∈ .
The scheme has the homomorphic property with respect to the following two group operations:
— The operation • on plaintexts is defined by a multiplication on .
— The operation ⨀ on ciphertext is defined by coordinate-wise multiplication modulo p.
NOTE 1 A homomorphic property is satisf
...