ISO/IEC 19592-2:2017

Error! Reference source not found.
ISO/IEC JTC 1/SC 27 N16825
Date: 2016-12-23
ISO/IEC 19592-2:2017(E)
ISO/IEC JTC 1/SC 27/WG 2
Secretariat: DIN
Information technology — Security techniques — Secret sharing — Part 2:
Fundamental mechanisms
Technologies de l'information ― Techniques de sécurité — Partage de secret — Partie 2: Mécanismes Fondamentaux

---------------------- Page: 1 ----------------------
Error! Reference source not found.
Copyright notice
This ISO document is a Draft International Standard and is copyright-protected by ISO. Except as
permitted under the applicable laws of the user's country, neither this ISO draft nor any extract
from it may be reproduced, stored in a retrieval system or transmitted in any form or by any
means, electronic, photocopying, recording or otherwise, without prior written permission being
secured.
Requests for permission to reproduce should be addressed to either ISO at the address below or
ISO's member body in the country of the requester.
ISO copyright office
Case postale 56 • CH-1211 Geneva 20
Tel. + 41 22 749 01 11
Fax + 41 22 749 09 47
E-mail copyright@iso.org
Web www.iso.org
Reproduction may be subject to royalty payments or a licensing agreement.
Violators may be prosecuted.
ii Error! Reference source not found.

---------------------- Page: 2 ----------------------
Error! Reference source not found.
Contents Page
Foreword iv
Introduction v
1 Scope .1
2 Normative references .1
3 Terms and definitions .1
4 Symbols and abbreviated terms .2
5 Secret sharing schemes .3
5.1 General .3
5.2 Shamir secret sharing scheme .4
5.2.1 General .4
5.2.2 Parameters .4
5.2.3 Message sharing algorithm .4
5.2.4 Message reconstruction algorithm.4
5.2.5 Properties .5
5.3 Ramp Shamir secret sharing scheme .5
5.3.1 General .5
5.3.2 Parameters .5
5.3.3 Message sharing algorithm .6
5.3.4 Message reconstruction algorithm.6
5.3.5 Properties .6
5.4 Additive secret sharing scheme for a general adversary structure .7
5.4.1 General .7
5.4.2 Parameters .7
5.4.3 Message sharing algorithm .7
5.4.4 Message reconstruction algorithm.7
5.4.5 Properties .8
5.5 Replicated additive secret sharing scheme .8
5.5.1 General .8
5.5.2 Parameters .8
5.5.3 Message sharing algorithm .9
5.5.4 Message reconstruction algorithm.9
5.5.5 Properties .9
5.6 Computational additive secret sharing scheme .9
5.6.1 General .9
5.6.2 Parameters .9
5.6.3 Message sharing algorithm . 10
5.6.4 Message reconstruction algorithm. 10
5.6.5 Properties . 10
5.6.6 Conversion Protocol . 11
Annex A (normative) Object identifiers . 13
Annex B (informative) Numerical examples . 15
B.1 Shamir secret sharing scheme . 15
B.2 Ramp Shamir secret sharing scheme . 15
Error! Reference source not found. iii

---------------------- Page: 3 ----------------------
Error! Reference source not found.
B.3 Additive secret sharing scheme for a general adversary structure . 16
B.4 Additive secret sharing scheme . 16
B.5 Computational additive secret sharing scheme . 16
Bibliography 22
iv Error! Reference source not found.

---------------------- Page: 4 ----------------------
Error! Reference source not found.
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. In the field of information technology, ISO and IEC have established a joint technical committee,
ISO/IEC JTC 1.
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).
Any trade name used in this document is information given for the convenience of users and does not
constitute an endorsement.
For an explanation on 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 the following
URL: 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 19592 series can be found on the ISO website.
Error! Reference source not found. v

---------------------- Page: 5 ----------------------
Error! Reference source not found.
Introduction
A secret sharing scheme is a cryptographic technique used to protect the confidentiality of a message by
dividing it into a number of pieces called shares. A secret sharing scheme has two main parts: a message
sharing algorithm for dividing the message into shares and a message reconstruction algorithm for
recovering the message from all or a subset of the shares.
The fundamental functions of a secret sharing scheme are sharing and reconstructing the message. A
secret sharing scheme can also have optional features such as reconstructing the message when some
shares provided for reconstruction are erroneous. This document specifies cryptographic secret sharing
schemes which possess the two fundamental functions of message confidentiality and message
recoverability.
Secret sharing can be used to store data (for example, confidential values or cryptographic keys)
securely in distributed systems. Moreover, secret sharing is a fundamental technology for secure multi-
party computation that can be used to protect the processing of data in a distributed system. To
facilitate the effective use of the technology and to maintain interoperability, ISO/IEC 19592 (all parts)
specifies secret sharing and related technology.
NOTE Annex A lists the object identifiers assigned to the secret sharing fundamental mechanisms specified in
this document. Annex B provides numerical examples.
vi Error! Reference source not found.

---------------------- Page: 6 ----------------------
Error! Reference source not found. Error! Reference source not found.

Information technology — Security techniques — Secret
sharing — Part 2: Fundamental mechanisms
1 Scope
This document specifies cryptographic secret sharing schemes.
2 Normative references
The following documents are referred to in the text in such a way that some or all of their content
constitutes requirements of this document. For dated references, only the edition cited applies. For
undated references, the latest edition of the referenced document (including any amendments) applies.
ISO/IEC 19592-1:2016, Information technology — Security techniques — Secret sharing — Part 1:
General
3 Terms and definitions
For the purposes of this document, the terms and definitions given in ISO/IEC 19592-1 and the
following apply.
ISO and IEC maintain terminological databases for use in standardization at the following addresses:
— IEC Electropedia: available at http://www.electropedia.org/
— ISO Online browsing platform: available at http://www.iso.org/obp
3.1
abelian group
group (3.8) (G, +) such that a + b = b + a for every a and b in G
[SOURCE: ISO/IEC 15946-1:2016, 3.1, modified]
3.2
complexity
number of unit operations required to execute a procedure
3.3
conversion protocol
protocol that converts the shares of a secret sharing scheme to the shares of another secret sharing
scheme
3.4
deterministic random bit generator
DRBG
Error! Reference source not found. 1

---------------------- Page: 7 ----------------------
Error! Reference source not found.
random bit generator that produces a random-appearing sequence of bits by applying a deterministic
algorithm to a suitably random initial value called a seed and, possibly, some secondary inputs upon
which the security of the random bit generator does not depend
Note 1 to entry: A DRBG takes a high-entropy, kept-secret random string as input and outputs a longer string of
bits which is computationally indistinguishable from random data to adversaries not knowing the input.
[SOURCE: ISO/IEC 18031:2011, 3.10, modified]
3.5
field
set of elements K and a pair of operations (+, *) defined on K such that: (i) a * (b + c) = a * b + a * c for
every a, b and c in K, (ii) K together with + forms an abelian group (3.1) (with identity element 0), and
(iii) K excluding 0 together with * forms an abelian group
[SOURCE: ISO/IEC 15946-1:2016, 3.4, modified]
3.6
finite cyclic group
abelian group (3.1) G such that there exist g in G, where every a in G is specified in g or a self-addition of
g
3.7
finite field
field (3.5) containing a finite number of elements
[SOURCE: ISO/IEC 15946-1:2016, 3.5, modified]
3.8
group
set of elements G 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 G, (ii) there exists an identity element e in G such that a + e = e + a = a for every a
−1 −1 −1
in G, and (iii) for every a in G there exists an inverse element a in G such that a + a = a + a = e
[SOURCE: ISO/IEC 15946-1:2016, 3.6, modified]
3.9
information dispersal algorithm
IDA
algorithm that includes two separated sub-algorithms: a splitting algorithm that splits a message into n
components and a recover algorithm that recovers the message from any k of the n components, where
k and n are integers and n ≥ k
Note 1 to entry: Unlike in a secret sharing scheme, there is no guarantee of security. That is, it can be possible to
reconstruct the secret or parts of the secret from less than k components.
4 Symbols and abbreviated terms
a ∈ A a is an element of A
A ⊂ B A is a subset of B
|A| number of elements of A
A × B direct product of A and B
2 Error! Reference source not found.

---------------------- Page: 8 ----------------------
Error! Reference source not found.
m
A set of m-tuples of elements of A
C binomial coefficient, namely i choose j
i j
[a] i-th share of secret a
i
n number of shares
k threshold of shares
G finite cyclic group
K finite field
K[x] set of all polynomials in x with coefficient in K
Split message splitting algorithm of an IDA scheme
Rec message reconstruction algorithm of an IDA scheme
Share message sharing algorithm of a secret sharing scheme
Reconst message reconstruction algorithm of a secret sharing scheme
HomShare message sharing algorithm of a homomorphic secret sharing scheme
HomReconst message reconstruction algorithm of a homomorphic secret sharing scheme
5 Secret sharing schemes
5.1 General
In this document, each of 5.2, 5.3, 5.4, 5.5 and 5.6 contains a specification of one or more secret sharing
schemes. For each secret sharing scheme, the following items are listed.
a) Parameters
1) Message space, i.e. the set of possible messages which can be input to the message sharing
algorithm.
2) Share space, i.e. the set of possible shares which can be output by the message sharing
algorithm.
3) Number of shares, i.e. the range of possible values of n supported by the scheme.
4) One of the following properties that represent which shares are required for the
reconstruction:
i) Threshold, i.e. a positive number k such that any k shares are sufficient for a successful
completion of the message reconstruction algorithm.
ii) Access structure, i.e. the minimal set of possible subsets of shares that are needed as input
in order for the message reconstruction algorithm to successfully output the message.
iii) Adversary structure, i.e. the set of subsets of shares that is not possible to reconstruct the
message.
5) Other parameters (if applicable).
b) Description of the message sharing algorithm, i.e. the method for dividing a message into shares.
Error! Reference source not found. 3

---------------------- Page: 9 ----------------------
Error! Reference source not found.
c) Description of the message reconstruction algorithm, i.e. the method for reconstructing the
message from a set of shares.
d) Properties of the secret sharing scheme (see ISO/IEC 19592-1:2016, Clause 4).
NOTE 1 None of the secret sharing schemes specified in this document possesses the verifiability property.
NOTE 2 In the mechanisms specified in this document, elements are chosen at random from some (finite) set.
All such choices are made uniformly (or near uniformly) at random from the set of possible values.
NOTE 3 If the message space is a group or field, arithmetic operations are performed in this group or field.
5.2 Shamir secret sharing scheme
5.2.1 General
5.2 describes the parameters, message sharing algorithm, message reconstruction algorithm and
[8]
properties of the Shamir secret sharing scheme .
5.2.2 Parameters
Message space: K.
Share space: same as the message space.
Number of shares: n, such that n ≥ 2, n < |K|.
Threshold: k, such that n ≥ k ≥ 2.
Fixed field elements: x ∈ K for 1 ≤ i ≤ n.
i
NOTE It is assumed that the fixed field elements are known to the receiver. These elements can be sent to the
receiver with the corresponding share or published as system parameters.
5.2.3 Message sharing algorithm
Input: message a ∈ K.
n
Output: share vector ([a] , ., [a] ) ∈ K .
1 n
a) Randomly select r , ., r ∈ K.
1 k−1
k−1
j
b) Compute []a =a+∈rx K for 1 ≤ i ≤ n.
ij∑
i
j=1
n
c) Output ([a] , ., [a] ) ∈ K .
1 n
5.2.4 Message reconstruction algorithm
k
Input: share vector a ,., aK∈ .
 
(  )
ii
1 k
Output: message a ∈ K.
k k
a) Compute a []a 0− x / xx−∈K .
( )
∑ i i ( ii )
∏
j u ju
j=1 u 1,uj≠
4 Error! Reference source not found.

=
=

---------------------- Page: 10 ----------------------
Error! Reference source not found.
b) Output a ∈ K.
k−1
j
NOTE The reconstruction algorithm is known as Lagrange interpolation. If f x a+ rx then the
( )
∑ j
j=1
secret is f(0) and each share [a] is f(x). Since f(x) is a polynomial of degree k, f(0) can be computed from k
i i
coordinates using Lagrange interpolation.
5.2.5 Properties
Confidentiality: The Shamir secret sharing scheme is perfectly information-theoretically confidential
when the receiver has access to less than k shares of the message.
Information rate: The Shamir secret sharing has an information rate of 1, as the size of a message and a
share are the same as the size of an element of the finite field K. Thus, the scheme is ideal.
Homomorphic operations: The Shamir secret sharing scheme is (+, +)-homomorphic where addition on
share vectors is performed by computing [a + a′] = [a] + [a′] .
i i i
Complexity: The message sharing algorithm requires (k−1)n multiplications and (k−1)n additions. The
2 2
message reconstruction algorithm requires k divisions, 2k − 3k multiplications and k − 1 additions. If
anything that does not involve a or r_jr for 1 ≤ j ≤ k−1 is preliminary prepared, both algorithms require
j
k multiplications and k−1 additions.
5.3 Ramp Shamir secret sharing scheme
5.3.1 General
5.3 describes the parameters, message sharing algorithm, message reconstruction algorithm and
[3]
properties of the ramp version of the Shamir secret sharing scheme . This mechanism is a
generalization of the scheme specified in 5.2. It reduces the size of each share in relation to the message
to be reconstructed by a factor of L. Although k shares are still required to reconstruct the message, any
number of shares greater than (k−L) reveals partial information about it. The parameters k and L can be
chosen flexibly following the restriction k ≥ L ≥ 1.
NOTE 1 The ramp Shamir secret sharing scheme with the parameter L = 1 is equivalent to the Shamir secret
sharing scheme specified in 5.2.
NOTE 2 In information-theoretically secure secret sharing schemes, each share of a secret is at least the size of
the secret. There are two approaches to mitigate this. One is to rely on computational hardness assumptions
instead of information theoretic security. The other is the use of ramp secret sharing schemes. In the ramp
scheme, shares can be shorter than the size of the secret, while there are sets of shares that are not meant to allow
access but which leak information about the secret.
5.3.2 Parameters
L
Message space: K .
Share space: finite field K.
Number of shares: n, satisfying n ≥ 2, n < |K|.
Threshold: k, satisfying n ≥ k ≥ 2.
Number of embedded messages: L, satisfying k ≥ L ≥ 1.
Fixed field elements: x ∈ K for 1 ≤ i ≤ n.
i
NOTE The fixed field elements can be sent to the receiver with the corresponding shares or published as
system parameters.
Error! Reference source not found. 5

=

---------------------- Page: 11 ----------------------
Error! Reference source not found.
5.3.3 Message sharing algorithm
L
Input: message (a , ., a ) ∈ K .
1 L
n
Output: share vector ([(a , ., a )] , ., [(a , ., a )] ) ∈ K .
1 L 1 1 L n
a) Randomly select r , …, r ∈ K.
L k−1
Lk−−11
jj
b) Compute  a ,.,a  a x+ rx∈K for 1 ≤ i ≤ n.
( )
1 Lj+1 j
∑∑ii
 
i
j 0 jL
n
c) Output ([(a , ., a )] , ., [(a , ., a )] ) ∈ K .
1 L 1 1 L n
5.3.4 Message reconstruction algorithm
 
k
   
Input: share vector aa,., ,., aa,., ∈K .
( ) ( )
 
1 L 1 L
   
i i
1 k
 
L
Output: messages (a , ., a ) ∈ K .
1 L
k k
a) Define polynomial   .
f( x) (a ,.,a ) x− x / x−∈x Kx 
( ) )
∑ 1 L ∏ i ( ii  
 
u ju
i
j
j=1 u 1,uj≠
k−1
i
b) Compute f x b x∈Kx and set a = b for 1 ≤ i ≤ L.
( )   i i
i+1
∑  
i=0
L
c) Output (a , ., a ) ∈ K .
1 L
5.3.5 Properties
Confidentiality: The ramp version of the Shamir secret sharing scheme is information-theoretically
confidential when the receiver has access to less than k – L + 1 shares. When the receiver has access to
more than k − L shares but less than k, partial information is revealed. This reduction in security is
quantified as follows: if an entity knows k – L + i shares for some i(1 ≤ i ≤ L − 1) then the entity knows
L−i
the secret message lies within a set of size |K| .
Information rate: The ramp version of the Shamir secret sharing scheme has an information rate of L as
the size of a message is equal to L times the size of a field element and the size of a share is the same as
the size of a field element.
Homomorphic operations: The ramp version of the Shamir secret sharing scheme is (+, +)-
homomorphic where addition on share vectors is performed by computing [(a + a′ , ., a + a′ )] = [(a ,
1 1 L L i 1
..., a )] + [(a′ , ..., a′ )] .
L i 1 L i
Complexity: The message sharing algorithm requires (k−1)n multiplications and (k−1)n additions. The
message reconstruction algorithm requires k(k−1)(k+1)/3 divisions, k(k−1)/2 multiplications and
k(k−1)(2k+5)/6 additions using the Gaussian elimination method. If anything that does not involve a or
r_jr for L ≤ j ≤ k−1 is preliminary prepared, the message sharing algorithm requires k multiplications
j
and k−1 additions.
6 Error! Reference source not found.

=
=
=
==
=

---------------------- Page: 12 ----------------------
Error! Reference source not found.
5.4 Additive secret sharing scheme for a general adversary structure
5.4.1 General
5.4 describes the parameters, message sharing algorithm, message reconstruction algorithm and
[5]
properties of the additive secret sharing scheme for a general adversary structure . Let A be the
adversary structure that contains m subsets of the numbers {1, 2, …, n} of variable size representing
groups of adversaries. The algorithms are arranged so that no set of adversaries in A can collaborate to
recover a. Let the elements of A be labelled Z , j = 1, 2, …, m. In the message sharing algorithm, values
j
rr,., are generated uniformly at random within the field and r = ar− + .+ r . Share
( )
ZZ Z ZZ
11m− mm1 −1
[a] then consists of all the r values whose indices do not contain the value i, where i = 1, 2, …, n.
i
NOTE 1 The adversary structure denotes the set of all maximal coalitions of participants who cannot recover
the secret.
NOTE 2 A complementary concept to the notion of the adversary structure of a secret sharing scheme is the
access structure of the scheme. The access structure contains all minimal coalitions of participants of the scheme
who can jointly recover the secret.
5.4.2 Parameters
Message space: G.
Share space: same as the message space.
Number of shares: n, such that n ≥ 2.
Adversary structure: A ⊂ {S| S ⊂{1, …, n}}.
Fixed subset: Z ∈ A.
0
NOTE The index Z ∈ A of r can be sent to the receiver with the corresponding share or be published as
Z
system parameter.
5.4.3 Message sharing algorithm
Input: message a ∈ G.
Output: share vector ([a] , …, [a] ).
1 n
a) Randomly select r ∈ G for all Z ∈ A−{Z } and compute r =a−∈rG .
Z 0
ZZ∑
0
ZZ∈−A {}
0
b) Compute [a] = {r | i ∉ Z ∈ A} for 1 ≤ i ≤ n.
i z
c) Output ([a] , …, [a] ).
1 n
5.4.4 Message reconstruction algorithm
Input: share vector {[a] | i ∈ K}, where K satisfies the requirement that for all Z ∈ A, there exists i ∈ K
i Z
such that i ∉ Z.
Z
Output: message a ∈ G.
a) Extract r ∈ G from share [a] for all Z ∈ A.
Z i
Z
b) Compute a rG∈ .
Z
∑
Z∈A
Error! Reference source not found. 7

=

---------------------- Page: 13 ----------------------
Error! Reference source not found.
c) Output a ∈ G.
5.4.5 Properties
Confidentiality: The additive secret sharing scheme for a general adversary structure is perfectly
information-theoretically confidential when the receiver only has access to shares {[a] | i ∈Z} for some
i
Z ∈ A.
Information rate: The information rate for the additive secret sharing scheme for a general adversary
structure is 1/ max {r |iZ∉ ∈ A} , as the size of a message is the same as the element size in G
1≤≤in Z
and the size of a share is at most max {r |iZ∉ ∈ A} times the element size. If |A| = 1, the scheme
1≤≤in Z
is ideal.
Homomorphic operations: The additive secret sharing scheme for a general adversary structure is (+,
+)-homomorphic where the addition on share vectors is performed by computing
[a] + [a′] = {r + r′ | i ∉ Z ∈ A}.
i i Z Z
Complexity: The message sharing algorithm requires |A|−1 additions. The message reconstruction
algorithm requires |A|−1 additions.
5.5 Replicated additive secret sharing scheme
5.5.1 General
5.5 describes the parameters, message sharing algorithm, message reconstruction algorithm and
[4]
properties of the replicated additive secret sharing scheme . In this scheme, each share is considerably
larger than the message being shared. However, reconstruction is computationally trivial, depending on
the group and the threshold number of shares used as parameters. This scheme is a special case of the
secret sharing scheme described in 5.4 with specific adversary structures A = {Z | Z ⊂{1, …, n},
|Z| = k−1}.
Each party has random numbers corresponding to those adversary sets that do not include the party.
Thus, parties that form a subset of a set of size k−1 cannot reconstruct the secret because they do not
have the random number corresponding to that set. On the other hand, parties that are not a subset of
any set of size k−1 can reconstruct the secret because for any set of size k−1 there exists a party that is
not included in that set and that party has the random number corresponding to that set of size k−1.
5.5.2 Parameters
Message space: G.
Share space: same as the message space.
Number of shares: n, such that n ≥ 2.
Threshold: k, such that n ≥ k ≥ 2.
Adversary structure: A = {Z | Z ⊂{1, …, n}, |Z| = k−1}.
Fixed subset:
...